COMPILER-实验指导书.doc

计算机图形学实验指导书课程名称:编译原理英文名称:Compiler Principle课程性质:必修 / 限选编写人:孔繁茹 卢云宏2010年9月1日计算机学院阅读说明l 未加标注的为必做实验l 标有的为选做实验实验要求l 每个小组不超过4人，需要完成以下任务n 必做实验: 全部完成(70%) 实验1.1(20%) 实验1.2(10%) 实验1.3(20%) 实验1.4(10%)n 选做实验: 至少完成3个(30%)n 实验报告(10%)l 实验成绩上限 (120%)第1部分 单元实验实验1.1 根据状态转换图手工构造词法分析程序一、实验目的1. 理解词法分析器的基本功能2. 理解词法规则的描述方法3. 理解状态转换图及其实现4. 能够编写简单的词法分析器二、实验平台C/C+三、实验内容手工构造一个简单的词法分析程序, 能够识别标识符、整数、关键字、算符、界符。1. 画出识别所有单词的状态转换图。(若状态转换图过于复杂,可以只画出主要部分)2. 根据状态转换图手工构造词法分析程序。从以下方法中选一： 词法分析器可以作为独立的一遍 也可以作为一个子程序被语法分析器调用3. 实现状态转换图。从以下方法中选一： 直接转向法 表驱动法四、设计文档1. 画出状态转换图 若通过正规式或正规文法手工转换得到，需写明转换步骤 若通过正规式或正规文法编程转换得到，需附源程序清单2. 分析直接转向法和表驱动法的优缺点五、参考资料1. 程序设计语言编译原理国防 陈火旺 3.2 词法分析器的设计实验1.2 用LEX自动构造词法分析程序一、实验目的1. 掌握词法分析程序的自动构造方法2. 掌握词法分析程序自动构造工具Lex的工作原理和使用方法3. 熟悉LEX源程序语法4. 学习使用自动构造软件SLex 二、实验平台Windows + Slex三、实验内容1实现以下步骤, 掌握SLex的工作过程a) 构造LEX源程序, 例如命名为Test.Lex b) 编译lex源程序，生成C语言词法分析程序lexyy.c在DOS 命令提示符下执行编译 Slex Test.Lex得到目标文件 lexyy.c c) 改写生成的C语言代码lexyy.c ，增加主函数(如果没有)main ( ) yylex(); d) 编译lexyy.c，产生可执行程序lexyy.exee) 运行生成的可执行文件 lexyy Test2.pl0 f) 察看运行结果，并对结果进行分析2. 编写LEX源程序, 使其自动生成的C程序能够实现以下功能 (至少完成2个) 复制一个文件，将文件中每个非空的空白符号序列替换为单个空格 将输入文件中的所有小写字母转换成大写字母，将转换后的文件存入另一个文件，同时在屏幕上输出转换后的文件内容。 输入一个C源程序文件, 将其中的所有关键字(即保留字)均转换为大写字母, 将转换后的文件存入另一个文件，同时在屏幕上输出转换的关键字个数。 将输入文件中的标识符输出到屏幕上。 将输入文件中所有能被9整除的整数输出到屏幕上。 为输入文件的每一行打印行行号。 统计输入文件中的字符个数、字母个数、各类单词个数、行数。(字符包括空格、制表符，不包括换行符) 把一个文件改变为 “Pig Latin”文. 假设该文件是一个用空白符分隔开的单词(字母串)序列, 每当你遇到一个单词时:(1) 如果第一个字母是辅音字母, 则将它移到单词的结尾, 并加上 ay(2) 如果第一个字母是元音字母, 则只在单词的结尾加上 ay所有非字母的字符不加处理直接复制到输出 3. 用Lex自动生成词法分析程序 词法分析的输出存入文件中, 输出的单词序列格式可以自己定义 4. 修正Slex的bugSlex本身存在Bug，每次运行后不能正常退出。注意：因此前已有学生完成了bug修正，所以只有提出不同的修正方案，或者更好的修正方案，才可以得分。四、设计文档1. 分析Test.lex的功能2. 分析词法分析程序的自动生成原理3. 分析自动生成的词法分析程序的结构4. 若对Slex的bug进行了修正, 详细写出修正方案。五、参考资料1. lex源程序: Test.lex 2. 参考函数: atoi() 将字符串转换成整数。例如，调用atoi(“123”)，得到整数123实验1.3 递归下降分析一、实验目的1. 加深对递归下降分析的理解。二、实验平台Windows + VC三、实验内容1. 选择一个文法或自己设计一个文法(应与范例中的文法不同)，写出文法接受的语言。2. 对该文法进行LL(1)判别，若不是LL(1)文法，则进行等价变换。3. 针对文法手工构造递归下降分析程序，实现以下功能： 输入一符号串, 输出语法分析的结果 (接受/出错)。从文件中读入若干个符号串, 依次输出语法分析的结果用可视化工具输出语法树四、设计文档1. 文法、文法描述的语言、预测分析表五、参考资料1. 递归下降分析程序: “ 2-递归下降.c ”此程序对应的文法如下：G:(1) ETG(2) G+TG|-TG(3) G(4) TFS(5) S*FS|/FS(6) S(7) F(E)(8) Fi实验1.4 在Windows平台下使用Flex和Bison一、实验目的1. 学习使用词法分析程序自动构造工具Flex和语法分析程序自动构造工具Bison二、实验平台Windows + Flex + Bison三、实验内容1. 实现以下步骤, 掌握Flex和Bison的工作过程a) 在DOS 命令提示符下依次执行以下两行命令flex -olexyy.c calc.lexbison -ocalc.c calc.yb) 编译运行 calc.cc) 分析运行结果2. 用Flex和Bison实现以下功能(1) 扩充范例程序, 实现以下功能之一 乘方、开方运算 按位运算 与、或、非. 三角函数运算 sin、cos. 其他功能(2) 编写Yacc程序，使其自动生成的C程序能够实现以下功能: 输入中缀表达式,输出后缀表达式参考属性文法:G:E ET print +E T T T*F print *T FF (E) F i print i(3) 扩充范例程序, 实现实数运算(4) 编写Yacc程序, 使其自动生成的C程序能够实现以下功能:输入二进制数,输出十进制数参考属性文法G:N S1.S N.v=S1.v+S.v*2-S.L S S1B S.v=S1.v*2+B.v, S.L=S1.L+1 S B S.v=B.v, S.L=1 B 0 B.v=0 B 1 B.v=1 (5) 对给定文法G编写Yacc程序，使其自动生成的C程序能够实现以下功能:读入输入符号串，若输入符号串合法，则输出括号()的对数G:S ( L ) | aL L , S | S参考语义规则：S Sprint (S. num)S ( L )S. num := L.num + 1S aS. num := 0L L1 , SL. num := L1. num + S. numL SL. num := S.num 四、设计文档1. 详细说明参考源程序calc.lex和calc.y实现的功能。2. 介绍自己添加的新功能。附程序源码、测试用例。3. 完成附加题目的同学，附语义规则、程序源码、测试用例五、参考资料1. 源程序: calc.lexcalc.y 实验1.5 用YACC自动构造语法分析程序一、实验目的1. 掌握语法法分析程序的自动构造方法2. 掌握语法分析程序自动构造工具Yacc的工作原理和使用方法3. 熟悉Yacc源程序语法4. 学习使用自动构造软件Yacc 二、实验平台Windows + Slex + Yacc三、实验内容用LEX和YACC自动构造一个PL/0程序的命令行解释程序，要求具有变量和常量定义语句Var和Const，具有基本输入输出语句Read 和Write,包含基本的算术运算 + 、-、*、/ 和( ) 运算，语句以分号（；）结束,整个程序以END结束。1. 学习YACC语法的使用2. 使用LEX构造词法分析程序 yylex.c3. 使用YACC构造语法分析程序实现以下步骤, 掌握Yacc的工作过程a) 构造YACC源程序, 例如命名为PL0.YACb) 编译Yacc源程序，生成C语言语法分析程序pl0.C在DOS 命令提示符下执行编译 YACC pl0.yac产生C语言代码 pl0.C c) 编译pl0.C，产生可执行程序pl0.exed) 在DOS 命令提示符下执行生成的 pl0.exe 输入程序示例如下: Const a =3 ; Var b,c ; Read(b); c := a + b ; Write(c) ; END. e) 察看运行结果，并对结果进行分析四、设计文档1. 解答: YACC所依据的文法是什么？2. 分析语法分析程序的自动生成原理。2. 分析生成的语法分析程序是如何工作的。 五、参考资料1. Yacc源程序: pl0.yac 实验1.6 用JFlex构造词法分析程序一、实验目的1. 学习使用Jflex二、实验平台Java三、实验内容1. 设计一个简单的语言，用正规式描述其词法规则。2. 下载词法分析程序自动生成工具JFlexJFlex本身采用Java语言编写，并且生成Java语言的词法分析源程序。下载Flex，根据你自己的安装配置，修改JFlex安装目录下脚本文件binjflex.bat中的两个环境变量JFLEX_HOME 和 JAVA_HOME的设置。然后运行JFlex附带的输入源文件例子，以验证你是否正确安装并配置了JFlex。3. 生成词法分析程序参考JFlex使用手册，构造词法分析程序。四、设计文档1. 语言、词法规则描述、附JFlex源文件。五、参考资料1. 相关链接：http:/www.jflex.de/download.html/projects/jflex//appel/modern/java/JLex/ 实验1.7 用JavaCUP构造语法分析程序一、实验目的1. 学习使用JavaCUP二、实验平台Java三、实验内容1. 从附录中选择一个语言。2. 下载语法分析程序自动生成工具JavaCUPJavaCUP本身采用Java语言编写，并且生成Java语言的语法分析源程序。下载JavaCUP，运行附带的输入源文件例子(一个基于命令行的简单计算器应用)，以保证你正确安装并配置了JavaCUP。3. 生成语法分析程序参考JavaCUP使用手册，构造语法分析程序。四、设计文档1. 语言、语法规则描述、附JavaCUP源文件。五、参考资料1. 相关链接：/projects/cup/第2部分 综合实验 实验2.1 理解Ansi C的 文法规则一、实验目的1. 进一步理解Lex和Yacc的工作原理2. 理解Ansi C的文法规则二、实验平台Lex + Yacc三、实验内容1. 阅读Ansi C 的Lex和Yacc源程序，理解词法和语法规则2. 对Ansi C 的文法进行改进：(1) 添加 + + 和 操作符提示: 在词法分析程序段添加正规式，同时在Yacc程序的前缀表达式和后缀表达式中添加相应的文法规则，也可以只在Yacc程序段中添加文法规则。(2) 限定标识符长度为32个字符，超过32个字符部分无效，并给出警告信息。提示: 在词法分析程序段中添加计算标识符长度的函数，并根据计算结果做出相应处理。、五、参考资料1. 参考源码:ANSI C grammar (Lex).htmANSI C grammar (Yacc).htm 实验2.2 扩充PL/0编译程序一、实验目的1. 掌握自上而下的语法分析方法 2. 掌握递归子程序的书写方法3. 了解编译器前端的实现过程二、实验平台C 或 Pascal三、实验内容从以下任务中选一：1. 扩充条件语句为 := IF THEN ELSE 2. 增加重复语句为 := REPEAT ; UNTIL3. 增加一维整型数组为VAR ( : )4. 增加FOR语句5. 增加CASE语句6. 增加多维数组四、设计文档补充要求:1. 写出对PL/0语言扩充语句的的一般步骤。 2. 给出PL/0扩充部分的语法描述图和巴科斯-瑙尔范式的文法表示。3. 对程序的修改部分给出注释。五、参考资料1. 参考源码: PL0编译程序（Pascal版本/C版本） 实验2.3 对选定的语言实现编译器前端一、实验目的1. 掌握编译器前端的实现过程二、实验平台任选三、实验内容1. 选定附录中的一个文法，分析其描述的语言，确定语言中的终结符和非终结符。若选了标注的语言，则自起评点额外获得相应数。2. 分析文法的二义性3. 编写源程序 编写两个以上语法正确的源程序，要求用到该语言的所有语法结构。如果有可能，你编写的源程序最好有实际意义，比如求平均值、阶乘、斐波那契序列等 编写两个以上有语法错误的源程序，既包含词法错误，也包含语法错误 以上源程序可作为测试用例4. 构造词法分析程序 若文法中包含词法定义，将词法定义分离出来；否则自己补全词法定义。将词法定义写成正规式的形式。 可以采用手工构造方式，也可以选择自动生成方式 5. 构造语法分析程序 可以采用手工构造方式，也可以选择自动生成方式 注意：若采用递归下降分析法，当文法不满足LL(1)条件时，需等价变换为LL(1)文法 对一个存在词法错误或语法错误的源程序，需至少指出一处语法错误的原因及其位置(错误产生的位置定位允许有偏差) 可尝试在错误中恢复并继续进行语法分析6. 为其添加相应的语义动作，生成中间代码。 中间代码可以采用三地址代码或抽象语法树五、参考资料1. 参考源码: 附录A. straight-line语言Straight-line语言的简洁EBNF文法Stm Stm; StmStm id := ExpStm print (ExpList)Exp id Exp num Exp Exp Binop Exp Exp (Stm, Exp)ExpList Exp, ExpList ExpList Exp Binop +Binop Binop Binop /B. SimpleBlock语言SimpleBlock语言的简洁EBNF文法simpleblock:=LBRACE assignment RBRACEassignment:=assignment_expression SEMICOLONassignment_expression:=IDENTIFIER EQ expressionexpression:=expression binary_operator expression |LPAREN expression RPAREN |IDENTIFIER |INTEGER_LITERALbinary_operator:=PLUS | MINUS | MULT | DIV | MOD一个SimpleBlock程序有一个内含0条或多条赋值语句的语句块组成，每条赋值语句由一个赋值表达式后跟分号(;)组成。C. QTiny语言 QTiny语言的文法表示Program(BEGIN StatementList ENDStatementList(StatementList Statement | StatementStatement(Ident = Expr;| READ(IdList);|WRITE(ExprList);IdListIdList,Ident |IdentExprListExprList, Expr |ExprExprExpr Op Factor |FactorFactor(Expr) |Ident |INTOp+ |-IdentIDQtiny语言范例程序BEGINREAD(X,AB);Z = (AB+(X+1);WRITE(X,AB,Z,X-AB,X+AB,X+1);ENDD. Tiny语言 Tiny语言的文法表示Programstmt-sequencestmt-sequencestmt-sequence ; statement | statementstatementif-stmt | repeat-stmt | assign-stmt | read-stmt | write-stmtIf-stmtif expr then stmt-sequence end |if expr then stmt-sequence else stmt-sequence endrepeat-stmtrepeat stmt-sequence until exprassign-stmtidentifier := exprread-stmtread identifierwrite-stmtwrite exprexprsimple-expr comparison-op simple-expr| simple-exprcomparision-op | =simple-exprsimple-expr add-op term | termadd-op+ | -termterm multiple-op factor | factormultiple-op* | /factor(expr) | identifier| numberidentifierletter | letter numbernumber digit | number digitlettera | b | | z | A | B | | Zdigit(0 | 1 | | 9E. C0语言 C0语言的文法表示:= +|-:= * |:= |!=|=:= _|a|.|z|A|.|Z:= |:= |.|:= /字符串中可以出现所有合法的可打印字符集中的字符:= :=const,;:=:=+|- |:=|:=int:=，；:=(|void ):=:=():=int，int | :=void main():=| :=:=|()|:= | | | ;|; | ; | ; | ; | ;:=:=if()else:=|:=while():=():=，|:=:=scanf():=printf(,|):=return ()F. MiniJava语言 MiniJava语言文法表示Program MainClass ClassDecl*MainCla