编译原理王生原第二章

1、编译原理第二讲第二讲 Decaf / Mind 编译实验项目编译实验项目编译原理 项目框架的总体结构项目框架的总体结构 实验环境实验环境 实验内容实验内容Decaf / Mind 编译实验项目编译实验项目 实验安排实验安排 项目回顾项目回顾 考核方案考核方案编译原理项目回顾项目回顾 Decaf 语言语言- 一种强类型的、单继承的一种强类型的、单继承的简单面向对象语言简单面向对象语言- 许多大学用作许多大学用作教学语言教学语言 Stanford University Massachusetts Institute of Technology University of Tennessee Bro

2、wn University Texas A&M University Southern Adventist University 编译原理项目回顾项目回顾 清华清华 Decaf / Mind 项目项目- 始于计算机系始于计算机系98级本科生级本科生编译原理编译原理课课- 基于基于 Stanford University 课程课程 CS143 /class/cs143/- 根据实际需要进行了一定的根据实际需要进行了一定的修改和简化修改和简化 如：适应如：适应 Windows 平台平台 增加目标代码在增加目标代码在 X86 上的执行上的执行 02

3、 级的级的 TOOL 项目项目- 03 级之后经历了级之后经历了3 3 次较大改动次较大改动编译原理项目回顾项目回顾 清华清华 Decaf / Mind 项目项目- 03-04 级级 Decaf 项目项目 实验框架中开发语言由实验框架中开发语言由 C+ 改为改为 Java- 计计 50 班班 Mind 项目项目 实验框架由原来的单遍组织改为实验框架由原来的单遍组织改为多遍组织多遍组织 开发语言为开发语言为 C+C+，Decaf 语言有所精简（语言有所精简（Mind语言）语言） - 05 级至今级至今 Decaf / Mind 项目项目 以以 Mind 项目为基础，开发语言由项目为基础，开发语言

4、由 C+ 改为改为 Java编译原理项目回顾项目回顾 清华清华 Decaf / Mind 项目项目- 参与项目开发的部分同学参与项目开发的部分同学 杨俊峰（杨俊峰（Stanford 助教）助教） 张迎辉（计张迎辉（计99-99-计计0000助教）助教） 毛雁华（计毛雁华（计00-00-计计0101助教，助教，X86后端）后端） 刘天淼（计刘天淼（计0101助教，助教，Windows环境）环境） 唐唐 硕（计硕（计0202助教，助教，TOOL） 梁英毅（计梁英毅（计03-03-计计0505助教，助教，Java 版，版，Mind，RA） 张张 铎（计铎（计05-05-计计0707助教，改助教，改

5、Mind 至至 Java 版）版） 蒋蒋 波（参与波（参与 Decaf 语言规范的翻译语言规范的翻译 ） （还有许多同学没有一一列举）（还有许多同学没有一一列举）编译原理项目框架的总体结构项目框架的总体结构 当前项目中编译器的逻辑结构当前项目中编译器的逻辑结构编译原理 当前项目中编译器的逻辑结构当前项目中编译器的逻辑结构项目框架的总体结构项目框架的总体结构编译原理实验内容实验内容 四个阶段四个阶段编译原理实验内容实验内容 四个阶段四个阶段- Phase 1Phase 1 词法和语法分析词法和语法分析 借助借助 Lex 和和 Yacc 实现词法和语法分析实现词法和语法分析 一遍扫描后产生一种高级

6、中间表示一遍扫描后产生一种高级中间表示 （实验指定的抽象语法树（实验指定的抽象语法树 AST）- Phase 2 Phase 2 语义分析语义分析 遍历抽象语法树构造符号表、实现静态语遍历抽象语法树构造符号表、实现静态语 义分析，产生带标注的抽象语法树义分析，产生带标注的抽象语法树 - Phase 3 Phase 3 生成生成三地址码三地址码 TAC- Phase 4 Phase 4 基于基于 TAC 实现一些简单的数据流分析实现一些简单的数据流分析编译原理实验内容实验内容 Phase 1Phase 1- 借助借助 Lex 和和 Yacc 实现词法和语法分析实现词法和语法分析生成一种高级中间表

7、示（抽象语法树生成一种高级中间表示（抽象语法树 ASTAST）编译原理实验内容实验内容生成一种高级中间表示（抽象语法树生成一种高级中间表示（抽象语法树 ASTAST） Phase 1Phase 1- 借助借助 Lex 和和 Yacc 实现词法和语法分析实现词法和语法分析编译原理实验内容实验内容 Phase 1Phase 1- 借助借助 Lex 和和 Yacc 实现词法和语法分析实现词法和语法分析定义定义 Decaf Decaf 语法的一个语法的一个可能的上下可能的上下文无关文法文无关文法GProgram GProgram （片断）（片断） 编译原理实验内容实验内容 Phase 1Phase 1

8、- 借助借助 Lex 和和 Yacc 实现词法和语法分析实现词法和语法分析比较比较: :语法分析结果语法分析结果（具体语法树（具体语法树 CSTCST）生成一种高级中间表示生成一种高级中间表示（抽象语法树（抽象语法树 ASTAST）编译原理实验内容实验内容 Phase 2Phase 2- 遍历遍历 AST 构造符号表、实现静态语义分析构造符号表、实现静态语义分析编译原理实验内容实验内容 Phase 2Phase 2- 遍历遍历 AST 构造符号表、实现静态语义分析构造符号表、实现静态语义分析编译原理实验内容实验内容 Phase 2Phase 2- 遍历遍历 AST 构造符号表、实现静态语义分析

9、构造符号表、实现静态语义分析编译原理实验内容实验内容 Phase 3Phase 3 - 由由带标注的带标注的 AST 生成生成三地址码三地址码 TAC 编译原理实验内容实验内容 Phase 3Phase 3 - 由由带标注的带标注的 AST 生成生成三地址码三地址码 TAC 每个每个 class 对对应一个应一个 vtable编译原理实验内容实验内容 Phase 3Phase 3 - 由由带标注的带标注的 AST 生成生成三地址码三地址码 TAC 编译原理实验内容实验内容 Phase 3Phase 3 - 由由带标注的带标注的 AST 生成生成三地址码三地址码 TAC 编译原理实验内容实验内容

10、 Phase 3Phase 3 - 由由带标注的带标注的 AST 生成生成三地址码三地址码 TAC 编译原理实验内容实验内容 Phase 4Phase 4- 基于基于 TAC 实现简单的数据流分析实现简单的数据流分析划分基本块以及活跃变量数据流分析划分基本块以及活跃变量数据流分析编译原理实验内容实验内容 Phase 5 Phase 5 （不在课程计划内）（不在课程计划内）- 由由 TAC 生成生成 MIPS 汇编代码汇编代码可选的工作如指可选的工作如指令选择和寄存器令选择和寄存器分配算法的改进分配算法的改进以及其它类优化以及其它类优化编译原理实验内容实验内容 关于自行扩展实验关于自行扩展实验-

11、 完成完成 Phase 1-4 Phase 1-4 之后之后 2 周内提交周内提交 需要同时提交详细的设计和测试文档需要同时提交详细的设计和测试文档- 在已有实验框架基础上有意义的改进工作在已有实验框架基础上有意义的改进工作 函数式风格语句的实现函数式风格语句的实现 例外处理支持例外处理支持 垃圾回收机制垃圾回收机制 新的代码生成机制新的代码生成机制( (必要时增加新的低级表示必要时增加新的低级表示) ) 实现有意义的优化算法实现有意义的优化算法( (必要时增加新的中间表示必要时增加新的中间表示) ) 编译原理实验环境实验环境 编程环境和相关工具编程环境和相关工具 Lex & YACC

12、 简介简介编译原理编程环境和相关工具编程环境和相关工具 编程语言编程语言- Java ( (版本和操作系统信息参见实验说明版本和操作系统信息参见实验说明) ) Lex & YACC 工具工具- Jflex http:/jflex.de/- BYACC/J http:/ 其他辅助工具其他辅助工具- MIPS SPIM ( (Wisconsin大学大学 ) ) /larus/spim.html- Eclipse / 编译原理 Lex 与与 YACC 工具工具Lex & YACC 简介简介编译原理

13、 Lex 源程序式样源程序式样 % 定义节定义节 /* 可选，包含头文件、宏定义或全局可选，包含头文件、宏定义或全局 C 代码代码*/ % 辅助定义节辅助定义节 / /* *可选，在此可以为正规式定义宏名字可选，在此可以为正规式定义宏名字* */ / % 规则节规则节 /* 源程序的主体，不可或缺，由模式源程序的主体，不可或缺，由模式 （Lex 正规表达式）和动作（正规表达式）和动作（ C 语句或语句或 一段一段 C 程序）组成程序）组成 */ % C 语言用户子程序节语言用户子程序节 /* 可选，包含规则节用到的可选，包含规则节用到的 局部局部 C 函数函数*/Lex & YACC

14、简介简介编译原理%#include int num_lines = 0, num_chars = 0;%n +num_lines; +num_chars;. +num_chars;%Int main() yylex(); printf( “num of lines = %d, num of chars = %dn, num_lines, num_chars ); return 0; Lex 源程序举例源程序举例 count.l Lex & YACC 简介简介编译原理$ lex count.l$ gcc -o count lex.yy.c -ll /*对于 flex 用-lfl */$

15、./count count.l $ count.l build runLex & YACC 简介简介编译原理Lex 可单独作为文本处理工具来使用，例如可单独作为文本处理工具来使用，例如 toupper.l 源程序源程序 % #include % % a-z Printf(%c,yytext0+A-a) %Build & Run $ lex toupper.l $ gcc -o toupper lex.yy.c -ll $ ./toupper count.l Lex 源程序举例源程序举例 toupper.l Lex & YACC 简介简介编译原理和和 YACC 联用时的联

16、用时的Lex 源程序源程序 例例 exp.l % #include “y.tab.h” % % 0| 1-90-9 * yylval = atoi(yytext); return INTEGER; +*()n return yytext0; . /*do nothing*/ % Lex 源程序举例源程序举例Lex & YACC 简介简介编译原理- YACC 源程序式样源程序式样 % 声明节声明节 / /* * 将被原样拷贝将被原样拷贝, ,可选可选* */ / % 辅助定义节辅助定义节 /* 定义文法相关的名称和属性定义文法相关的名称和属性,可选可选*/ % 语法规则节语法规则节 /*

17、 定义语法规则及语义动作定义语法规则及语义动作. Yacc中的产生式中的产生式 格式为格式为 非终结符非终结符: 右端右端 C语句表示的语义动作语句表示的语义动作 */ % 支撑函数节支撑函数节 /* 规则节用到的局部规则节用到的局部 C 函数定义函数定义, 可选可选*/ YACC (Yet Another Compiler-Compiler)Lex & YACC 简介简介编译原理 YACC 源程序举例源程序举例 exp.y/* 用用YACC实现的一个简单的计算器实现的一个简单的计算器 */% #include % /* 终结符终结符 */%token INTEGER/* 优先级和结合

18、性优先级和结合性 */%left +%left *Lex & YACC 简介简介编译原理 YACC 源程序举例源程序举例 （续）（续）% input: /* empty string */ | input line ;line: n | exp n printf (t%dn, $1); | error n ;exp: INTEGER $ = $1; | exp + exp $ = $1 + $3; | exp * exp $ = $1 * $3; | ( exp ) $ = $2; ;%Lex & YACC 简介简介编译原理/* 用户子程序用户子程序 */main () yyp

19、arse (); int yylex() /* 自行编写或从自行编写或从 Lex 得到得到, 随后介绍随后介绍 Lex和和YACC 的联用，需删去这里的的联用，需删去这里的 yylex()定义定义 */yyerror (char *s) printf (%sn, s); YACC 源程序举例源程序举例 （续）（续）Lex & YACC 简介简介编译原理- 设设 exp.l 和和exp.y 分别为前述的分别为前述的Lex 和和YACC 源程序文件源程序文件 可如下实现可如下实现Lex 和和YACC的联编：的联编： lex exp.l /* 产生产生lex.yy.c，其中包含，其中包含 yylex() */ yacc -d exp.y /* 产生产生y.tab.c （其中