编译原理实验指导.docx
- 文档编号:5881101
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:22
- 大小:24.09KB
编译原理实验指导.docx
《编译原理实验指导.docx》由会员分享,可在线阅读,更多相关《编译原理实验指导.docx(22页珍藏版)》请在冰点文库上搜索。
编译原理实验指导
计算机图形学
实验指导书
课程名称:
编译原理
英文名称:
CompilerPrinciple
课程性质:
必修/限选
编写人:
孔繁茹卢云宏
2010年9月1日
计算机学院
阅读说明
●未加标注的为必做实验
●标有★的为选做实验
实验要求
●每个小组不超过4人,需要完成以下任务
⏹必做实验:
全部完成(70%)
✧实验1.1(20%)
✧实验1.2(10%)
✧实验1.3(20%)
✧实验1.4(10%)
⏹选做实验:
至少完成3个★(30%)
⏹实验报告(10%)
●实验成绩上限(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命令提示符下执行编译SlexTest.Lex得到目标文件lexyy.c
c)改写生成的C语言代码lexyy.c,增加主函数(如果没有)
main()
{yylex();}
d)编译lexyy.c,产生可执行程序lexyy.exe
e)运行生成的可执行文件lexyy f)察看运行结果,并对结果进行分析 2.编写LEX源程序,使其自动生成的C程序能够实现以下功能(至少完成2个) ✧复制一个文件,将文件中每个非空的空白符号序列替换为单个空格 ✧将输入文件中的所有小写字母转换成大写字母,将转换后的文件存入另一个文件,同时在屏幕上输出转换后的文件内容。 ✧输入一个C源程序文件,将其中的所有关键字(即保留字)均转换为大写字母,将转换后的文件存入另一个文件,同时在屏幕上输出转换的关键字个数。 ✧将输入文件中的标识符输出到屏幕上。 ✧将输入文件中所有能被9整除的整数输出到屏幕上。 ✧为输入文件的每一行打印行行号。 ✧统计输入文件中的字符个数、字母个数、各类单词个数、行数。 (字符包括空格、制表符,不包括换行符) ✧把一个文件改变为“PigLatin”文. 假设该文件是一个用空白符分隔开的单词(字母串)序列,每当你遇到一个单词时: (1)如果第一个字母是辅音字母,则将它移到单词的结尾,并加上ay (2)如果第一个字母是元音字母,则只在单词的结尾加上ay 所有非字母的字符不加处理直接复制到输出 ★3.用Lex自动生成词法分析程序 ✧词法分析的输出存入文件中,输出的单词序列格式可以自己定义 ★4.修正Slex的bug Slex本身存在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)E→TG (2)G→+TG|-TG (3)G→ε (4)T→FS (5)S→*FS|/FS (6)S→ε (7)F→(E) (8)F→i 实验1.4在Windows平台下使用Flex和Bison 一、实验目的 1.学习使用词法分析程序自动构造工具Flex和语法分析程序自动构造工具Bison 二、实验平台 Windows+Flex+Bison 三、实验内容 1.实现以下步骤,掌握Flex和Bison的工作过程 a)在DOS命令提示符下依次执行以下两行命令 flex-olexyy.ccalc.lex bison-ocalc.ccalc.y b)编译运行calc.c c)分析运行结果 2.用Flex和Bison实现以下功能 (1)扩充范例程序,实现以下功能之一 ✧乘方、开方运算 ✧按位运算–与、或、非... ✧三角函数运算–sin、cos... ✧其他功能 (2)编写Yacc程序,使其自动生成的C程序能够实现以下功能: 输入中缀表达式,输出后缀表达式 参考属性文法: G: EE+T{print‘+’} ET TT*F{print‘*’} TF F(E) Fi{print‘i’} ★(3)扩充范例程序,实现实数运算 ★(4)编写Yacc程序,使其自动生成的C程序能够实现以下功能: 输入二进制数,输出十进制数 参考属性文法 G: NS1.S{N.v=S1.v+S.v*2-S.L} SS1B{S.v=S1.v*2+B.v,S.L=S1.L+1} SB{S.v=B.v,S.L=1} B0{B.v=0} B1{B.v=1} ★(5)对给定文法G编写Yacc程序,使其自动生成的C程序能够实现以下功能: 读入输入符号串,若输入符号串合法,则输出括号()的对数 G: S(L)|a LL,S|S 参考语义规则: SSprint(S.num) S(L)S.num: =L.num+1 SaS.num: =0 LL1,SL.num: =L1.num+S.num LSL.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.c 3.使用YACC构造语法分析程序 实现以下步骤,掌握Yacc的工作过程 a)构造YACC源程序,例如命名为PL0.YAC b)编译Yacc源程序,生成C语言语法分析程序pl0.C 在DOS命令提示符下执行编译YACCpl0.yac 产生C语言代码pl0.C c)编译pl0.C,产生可执行程序pl0.exe d)在DOS命令提示符下执行生成的pl0.exe 输入程序示例如下: Consta=3; Varb,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.下载词法分析程序自动生成工具JFlex JFlex本身采用Java语言编写,并且生成Java语言的词法分析源程序。 下载Flex,根据你自己的安装配置,修改JFlex安装目录下脚本文件bin\jflex.bat中的两个环境变量JFLEX_HOME和JAVA_HOME的设置。 然后运行JFlex附带的输入源文件例子,以验证你是否正确安装并配置了JFlex。 3.生成词法分析程序 参考JFlex使用手册,构造词法分析程序。 四、设计文档 1.语言、词法规则描述、附JFlex源文件。 五、参考资料 1.相关链接: http: //www.jflex.de/download.html http: //www.cs.princeton.edu/~appel/modern/java/JLex/ ★实验1.7用JavaCUP构造语法分析程序 一、实验目的 1.学习使用JavaCUP 二、实验平台 Java 三、实验内容 1.从附录中选择一个语言。 2.下载语法分析程序自动生成工具JavaCUP JavaCUP本身采用Java语言编写,并且生成Java语言的语法分析源程序。 下载JavaCUP,运行附带的输入源文件例子(一个基于命令行的简单计算器应用),以保证你正确安装并配置了JavaCUP。 3.生成语法分析程序 参考JavaCUP使用手册,构造语法分析程序。 四、设计文档 1.语言、语法规则描述、附JavaCUP源文件。 五、参考资料 1.相关链接: http: //www2.cs.tum.edu/projects/cup/ 第2部分综合实验 ★★实验2.1理解AnsiC的文法规则 一、实验目的 1.进一步理解Lex和Yacc的工作原理 2.理解AnsiC的文法规则 二、实验平台 Lex+Yacc 三、实验内容 1.阅读AnsiC的Lex和Yacc源程序,理解词法和语法规则 2.对AnsiC的文法进行改进: (1)添加'++'和'––'操作符 提示: 在词法分析程序段添加正规式,同时在Yacc程序的前缀表达式和后缀表达式中添加相应的文法规则,也可以只在Yacc程序段中添加文法规则。 (2)限定标识符长度为32个字符,超过32个字符部分无效,并给出警告信息。 提示: 在词法分析程序段中添加计算标识符长度的函数,并根据计算结果做出相应处理。 、 五、参考资料 1.参考源码: ANSICgrammar(Lex).htm ANSICgrammar(Yacc).htm ★★★实验2.2扩充PL/0编译程序 一、实验目的 1.掌握自上而下的语法分析方法 2.掌握递归子程序的书写方法 3.了解编译器前端的实现过程 二、实验平台 C或Pascal 三、实验内容 从以下任务中选一: 1.扩充条件语句为 <条件语句>: : =IF<条件>THEN<语句>[ELSE<语句>] 2.增加重复语句为 <重复语句>: : =REPEAT<语句>{;<语句>}UNTIL<语句> 3.增加一维整型数组为 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;Stm Stm→id: =Exp Stm→print(ExpList) Exp→id Exp→num Exp→ExpBinopExp Exp→(Stm,Exp) ExpList→Exp,ExpList ExpList→Exp Binop→+ Binop→− Binop→× Binop→/ B.SimpleBlock语言 SimpleBlock语言的简洁EBNF文法 simpleblock: : =LBRACE{assignment}RBRACE assignment: : =assignment_expressionSEMICOLON assignment_expression: : =IDENTIFIEREQexpression expression: : =expressionbinary_operatorexpression |LPARENexpressionRPAREN |IDENTIFIER |INTEGER_LITERAL binary_operator: : =PLUS|MINUS|MULT|DIV|MOD 一个SimpleBlock程序有一个内含0条或多条赋值语句的语句块组成,每条赋值语句由一个赋值表达式后跟分号(;)组成。 C.QTiny语言★ QTiny语言的文法表示 Program(BEGINStatementListEND StatementList(StatementListStatement |Statement Statement(Ident=Expr; |READ(IdList); |WRITE(ExprList); IdListIdList,Ident |Ident ExprListExprList,Expr |Expr ExprExprOpFactor |Factor Factor(Expr) |Ident |INT Op+ |- IdentID Qtiny语言范例程序 BEGIN READ(X,AB); Z=(AB+(X+1)); WRITE(X,AB,Z,X-AB,X+AB,X+1); END D.Tiny语言★★ Tiny语言的文法表示 Programstmt-sequence stmt-sequencestmt-sequence;statement|statement statementif-stmt |repeat-stmt |assign-stmt |read-stmt |write-stmt If-stmtifexprthenstmt-sequenceend |ifexprthenstmt-sequenceelsestmt-sequenceend repeat-stmtrepeatstmt-sequenceuntilexpr assign-stmtidentifier: =expr read-stmtreadidentifier write-stmtwriteexpr exprsimple-exprcomparison-opsimple-expr |simple-expr comparision-op<|= simple-exprsimple-expradd-opterm|term add-op+|- termtermmultiple-opfactor|factor multiple-op*|/ factor(expr)|identifier|number identifierletter|letternumber numberdigit|numberdigit lettera|b|…|z|A|B|…|Z digit(0|1|…|9 E.C0语言★★★ C0语言的文法表示 <加法运算符>: : =+|- <乘法运算符>: : =*|/ <关系运算符>: : =<|<=|>|>=|! =|== <字符>: : =_|a|...|z|A|...|Z <数字>: : =0|<非零数字> <非零数字>: : =1|...|9 <字符串>: : ="{<合法字符>}" //字符串中可以出现所有合法的可打印字符集中的字符 <程序>: : =[<常量说明部分>][<变量说明部分>]{<子函数定义部分>}<主函数> <常量说明部分>: : =const<常量定义>{,<常量定义>}; <常量定义>: : =<标识符>=<整数> <整数>: : =[+|-]<非零数字>{<数字>}|0 <标识符>: : =<字符>{<字符>|<数字>} <声明头部>: : =int <标识符> <变量说明部分>: : =<声明头部>{,<标识符>}; <子函数定义部分>: : =(<声明头部>|void<标识符>)<参数><复合语句> <复合语句>: : =‘{’[<常量说明部分>][<变量说明部分>]<语句序列>‘}’ <参数>: : =‘(‘<参数表>‘)’ <参数表>: : =int<标识符>{,int<标识符>}|<空> <主函数>: : =voidmain’(‘‘)’<复合语句> <表达式>: : =[+|-]<项>{<加法运算符><项>} <项>: : =<因子>{<乘法运算符><因子>} <因子>: : =<标识符>|’(‘<表达式>‘)’|<整数>|<子函数调用语句> <语句>: : =<条件语句>|<循环语句> |’{‘<语句序列>‘}’ |<子函数调用语句>;|<赋值语句>; |<返回语句>;|<读语句>;|<写语句>; |; <赋值语句>: : =<标识符>=<表达式> <条件语句>: : =if’(‘<条件>‘)’<语句>[else<语句>] <条件>: : =<表达式><关系运算符><表达式>|<表达式> <循环语句>: : =while’(‘<条件>‘)’<语句> <子函数调用语句>: : =<标识符>‘(‘<值参数表>‘)’ <值参数表>: : =<表达式>{,<表达式>}|<空> <语句序列>: : =<语句>{<语句>} <读语句>: : =scanf’(‘<标识符>‘)’ <写语句>: : =printf’(‘<字符串>,<表达式>|<字符串>|<表达式>‘)’ <返回语句>: : =return[‘(‘<表达式>‘)’] F.MiniJava语言★★★ MiniJava语言文法表示 Program→MainClassClassDecl* Mai
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 实验 指导