编译原理王生原(第二章).ppt

,第二讲,Decaf / Mind 编译实验项目,项目框架的总体结构,实验环境,实验内容,Decaf / Mind 编译实验项目,实验安排,项目回顾,考核方案,项目回顾,Decaf 语言 一种强类型的、单继承的简单面向对象语言 许多大学用作教学语言 Stanford University Massachusetts Institute of Technology University of Tennessee Brown University Texas A&M University Southern Adventist University ,项目回顾,清华 Decaf / Mind 项目 始于计算机系98级本科生编译原理课 基于 Stanford University 课程 CS143 /class/cs143/ 根据实际需要进行了一定的修改和简化 如：适应 Windows 平台 增加目标代码在 X86 上的执行 02 级的 TOOL 项目 03 级之后经历了3 次较大改动,项目回顾,清华 Decaf / Mind 项目 03-04 级 Decaf 项目 实验框架中开发语言由 C+ 改为 Java 计 50 班 Mind 项目 实验框架由原来的单遍组织改为多遍组织 开发语言为 C+，Decaf 语言有所精简（Mind语言） 05 级至今 Decaf / Mind 项目 以 Mind 项目为基础，开发语言由 C+ 改为 Java,项目回顾,清华 Decaf / Mind 项目 参与项目开发的部分同学 杨俊峰（Stanford 助教） 张迎辉（计99-计00助教） 毛雁华（计00-计01助教，X86后端） 刘天淼（计01助教，Windows环境） 唐 硕（计02助教，TOOL） 梁英毅（计03-计05助教，Java 版，Mind，RA） 张 铎（计05-计07助教，改 Mind 至 Java 版） 蒋 波（参与 Decaf 语言规范的翻译 ） （还有许多同学没有一一列举）,项目框架的总体结构,当前项目中编译器的逻辑结构,当前项目中编译器的逻辑结构,项目框架的总体结构,实验内容,四个阶段,实验内容,四个阶段 Phase 1 词法和语法分析 借助 Lex 和 Yacc 实现词法和语法分析 一遍扫描后产生一种高级中间表示 （实验指定的抽象语法树 AST） Phase 2 语义分析 遍历抽象语法树构造符号表、实现静态语 义分析，产生带标注的抽象语法树 Phase 3 生成三地址码 TAC Phase 4 基于 TAC 实现一些简单的数据流分析,实验内容,Phase 1 借助 Lex 和 Yacc 实现词法和语法分析,生成一种高级中间表示（抽象语法树 AST）,实验内容,生成一种高级中间表示（抽象语法树 AST）,Phase 1 借助 Lex 和 Yacc 实现词法和语法分析,实验内容,Phase 1 借助 Lex 和 Yacc 实现词法和语法分析,定义 Decaf 语法的一个可能的上下文无关文法GProgram （片断）,实验内容,Phase 1 借助 Lex 和 Yacc 实现词法和语法分析,比较:语法分析结果（具体语法树 CST）,生成一种高级中间表示（抽象语法树 AST）,实验内容,Phase 2 遍历 AST 构造符号表、实现静态语义分析,实验内容,Phase 2 遍历 AST 构造符号表、实现静态语义分析,实验内容,Phase 2 遍历 AST 构造符号表、实现静态语义分析,实验内容,Phase 3 由带标注的 AST 生成三地址码 TAC,实验内容,Phase 3 由带标注的 AST 生成三地址码 TAC,每个 class 对应一个 vtable,实验内容,Phase 3 由带标注的 AST 生成三地址码 TAC,实验内容,Phase 3 由带标注的 AST 生成三地址码 TAC,实验内容,Phase 3 由带标注的 AST 生成三地址码 TAC,实验内容,Phase 4 基于 TAC 实现简单的数据流分析,划分基本块以及活跃变量数据流分析,实验内容,Phase 5 （不在课程计划内） 由 TAC 生成 MIPS 汇编代码,可选的工作如指令选择和寄存器分配算法的改进以及其它类优化,实验内容,关于自行扩展实验 完成 Phase 1-4 之后 2 周内提交 需要同时提交详细的设计和测试文档 在已有实验框架基础上有意义的改进工作 函数式风格语句的实现 例外处理支持 垃圾回收机制 新的代码生成机制(必要时增加新的低级表示) 实现有意义的优化算法(必要时增加新的中间表示) ,实验环境,编程环境和相关工具 Lex & YACC 简介,编程环境和相关工具,编程语言 Java (版本和操作系统信息参见实验说明),Lex & YACC 工具 Jflex http:/jflex.de/ BYACC/J /,其他辅助工具 MIPS SPIM (Wisconsin大学 ) /larus/spim.html Eclipse /,Lex 与 YACC 工具,Lex & YACC 简介,Lex 源程序式样 % 定义节 /* 可选，包含头文件、宏定义或全局 C 代码*/ % 辅助定义节 /*可选，在此可以为正规式定义宏名字*/ % 规则节 /* 源程序的主体，不可或缺，由模式 （Lex 正规表达式）和动作（ C 语句或 一段 C 程序）组成 */ % C 语言用户子程序节 /* 可选，包含规则节用到的 局部 C 函数*/,Lex & YACC 简介,% #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 */ $ ./count count.l $,count.l build run,Lex & 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 联用时的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 源程序式样 % 声明节 /* 将被原样拷贝,可选*/ % 辅助定义节 /* 定义文法相关的名称和属性,可选*/ % 语法规则节 /* 定义语法规则及语义动作. Yacc中的产生式 格式为 非终结符: 右端 C语句表示的语义动作 */ % 支撑函数节 /* 规则节用到的局部 C 函数定义, 可选*/,YACC (Yet Another Compiler-Compiler),Lex & YACC 简介,YACC 源程序举例 exp.y,/* 用YACC实现的一个简单的计算器 */ % #include % /* 终结符 */ %token INTEGER /* 优先级和结合性 */ %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 () yyparse (); 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 （其中包含 yyparse()）及 y.tab.h gcc y.tab.c lex.yy.c -ly -ll -o exp 运行结果 $ ./exp 4+3*5 19,Lex 与YACC 的联用举例,Lex & YACC 简介,实验安排,时间安排 第 4 周开始 共 8 周 自行扩展部分随后两周内完成提交,提交方式 通过课程 ftp 服务器 具体要求参见实验说明,考核方案,