编译原理 王生原(第二章).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 根据实际需要进行了一定的修改和简化 如：适应 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大学)http:/pages.cs.wisc.edu/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-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-ll$./toupper count.l,Lex 源程序举例 toupper.l,Lex&YACC 简介,和 YACC 联用时的Lex 源程序 例 exp.l%#include“”%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/*产生，其中包含 yylex()*/yacc-d exp.y/*产生（其中包含 yyparse()）及 gcc-ly-ll-o exp运行结果$./exp 4+3*5 19,Lex 与YACC 的联用举例,Lex&YACC 简介,实验安排,时间安排 第 4 周开始 共 8 周 自行扩展部分随后两周内完成提交,提交方式 通过课程 ftp 服务器 具体要求参见实验说明,考核方案,评分 Phase 1-3 各 9 分 Phase 4 8 分 自行扩展部分 5 分（直接加入总评成绩）,迟交和扣分说明 共有 2 天的晚交额度（可在任何阶段使用）每超过额度一天在实验总成绩中扣两分 发现抄袭者取消阶段成绩 进一步的信息参见实验说明,课后作业,1.进一步阅读有关 Lex&Yacc 的技术文档,2.掌握 Jflex&BYACC/J 的使用,Thank You,Thats all for today.,