编译原理实验指导书.doc

计算机科学与技术系 编译原理实验指导书编译原理实验指导书计算机科学与技术系2007年6月目 录实验目的和任务1实验一：词法分析器1实验二：语法分析器15实验三：语法分析器29实验四：语义分析和中间代码生成器1112实验目的和任务编译原理是一门实践性很强的课程，只有通过实践，才能真正理解其理论的深层内涵，切实掌握编译器的生成技术。实际的编译程序是十分复杂的，有时多达十几万条指令组成，实现起来难度很大。在编译原理的实验中，简化了真实程序设计语言要面临的许多问题，选用了具有一定表现能力的实用语言的子集。实验主要涉及最关键的个环节词法分析、语法分析和中间代码生成，每个环节既独立又相互关联，前后衔接，可合为一体，能较清楚地展现编译器前端的工作状况。编程语言要求：C、C+或JAVA。实验一：词法分析器一、 实验目的通过编写词法分析程序，了解词法分析的过程。二、 实验内容编写能识别给定的程序设计语言的词法规则，输出单词流的识别程序。三、 实验设备及工具1硬件：PC机Pentium100以上。2软件：Win2000或WinXP、BC+、VC+或JAVA开发环境。四、 实验说明 以下所给文法是进行词法分析和语法分析的依据，并将该文法中涉及到的单词信息提取到了单词符号与种别对照表中。本次实验要求编写符合该文法构词规则的词法分析器。1. 文法G（）BEGIN END.|;=IF THEN ELSE WHILE DO BEGIN END|+|-|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z0|1|2|3|4|5|6|7|8|9注意阴影部分，其中和被看作最小词法单位。2. 单词符号与种别对照表1-1，存放了上述文法的所有单词及种别。单词符号与种别对照表1-1种别单词符号种别单词符号种别单词符号1BEGIN2END3IF4THEN5ELSE6WHILE7DO8=9+10-1114.15;16整数17标识符五、 实验步骤为了实现编译程序的实用，源程序可采用自由书写格式，即一行内可以书写多个语句，一个语句也可以占领多行书写；标识符的前20个字符有效；整数用2个字节表示。这样词法分析程序的主要工作为：1 从源程序文件中读入字符。2 统计行数和列数用于错误单词的定位。3 删除空格类字符，包括回车、制表符空格。4 按拼写单词，并用（种别，单词）二元式表示。5 根据需要是否填写标识符表供以后各阶段使用。6 这里采用的编译程序的实现方法是一遍扫描，即从左到右只扫描一次源程序，也就是词法分析作为语法分析的一个子程序。故在编写词法分析程序时，用重复调用词法分析子程序取一单词的方法得到整个源程序的二元式流。7 源程序存放到文件*.pas。8 词法分析器从*.pas中读取字符流，输出为单词二元式流，并将输出结果存放到*.dc文件中。9 分别用正确的和错误的源程序测试词法分析器；正确的源程序示例test.pas：BEGIN I=10; J=I+5; WHILE I= =10 DO BEGIN R=J+I; I=I-1 ENDEND.输出结果为：（1 ，“BEGIN”）（17，“I”）（8 ，“=”）（16，“10”）（15，“；”） 10 实验完成后，将词法分析器程序代码、测试程序代码(正确的及错误的至少各一例)、输出的单词二元式流和相应的注释都存放到一个文件中提交打印并书写实验报告。六、 实验类型验证性实验。七、 实验学时3学时。八、 考核方式本实验总分为5分，具体评分标准如下：5分：实验准备充分，上机准时，能独立编写和调试程序，结果正确，实验报告内容齐全，格式规范。4分：实验准备良好，上机准时，能在教师指导下顺利编写和调试程序，结果较正确，实验报告内容比较齐全，格式比较规范。3分：实验准备较好，上机准时，基本完成实验任务，实验报告内容基本齐备，结果基本正确。2分：程序功能模块基本完整，但没有完成程序调试，无实验结果，提交了实验报告且有重大缺陷。1分：程序功能模块不完整，有重大问题，没有完成程序调试，无实验结果，提交的实验报告有重大缺陷。0分：没有参加实验，没有提交实验报告。九、 思考题1除了你使用的关键字检查方法，还有哪些可行性方案?比较其优劣。2词法分析过程中查出错误后怎样保证分析尽可能继续进行？3如何将词法分析器改造成函数，以供语法分析器调用? 实验二：语法分析器1 一、 实验目的掌握自上而下的语法分析方法，构造预测分析程序。二、 实验内容1 构造实验一所给文法（应考虑改造）的FIRST集合和FOLLOW集合；2 构造LL(1)分析表；3 构造预测分析的总控程序；4 利用分析表、分析栈和总控程序对源程序进行自上而下的语法分析测试； 5 输出整个语法分析过程中栈的变化过程及分析结果，如符合语法规则输出“正确”，否则输出“错误”。三、 实验设备及工具1硬件：PC机Pentium100以上。2软件：Win2000或WinXP、BC+、VC+或JAVA开发环境。四、 实验提示本次实验是设计性实验，可参考以下处理方法进行预测分析器的设计与实现。1由于预测分析是自上向下的分析方法，需将实验一中的文法改写成无左递归和无左共因子的文法（注意有阴影部分的规则）：BEGIN END.;|=IF THEN ELSE WHILE DO BEGIN END+|- |整数标识符2非终结符的内码表为了将非终结符和终结符一起存入栈参，将非终结符的内码从128开始标记。其对照表见表2-1。表2-1 非终结符和内码对照表内码非终结符内码非终结符内码非终结符1281291301311321331341351361371381391401413程序设计思想为了压缩存储，采用一个二维数组存放规则的右部，每个规则对应一个子数组，用0表示每条规则的结束。在预测分析表中用规则的序号代表相应的规则，分析表中的出错用-1表示。由于规则的右部存在相同的符号串，故相同的符号串只要保存一个即可，如规则。（这种方法对语法识别没有影响，但在语义分析和代码生成时，需区分是何种规则的右部）。规则右部符号串编号及内码表示：规则右部符号串编号内码（1）BEGIN END. （2）（3）;（4）（5）（6）（7）（8）（9）=（10）IF THEN ELSE （11）WHILE DO （12）BEGIN END（13）（14）+（15）- （16）（17）整数（18）（19）（22）标识符1 129 2 14 0130 131 015 129 00132 0133 0134 0135 0136 8 137 03 138 4 130 5 130 06 138 7 130 01 129 2 0139 140 09 139 140 010 139 140 0136 016 0137 141 137 011 012 013 017 04分析表和程序在预测分析法中所有预测分析法的总控分析程序都是一样的，主要是分析表不同。在预测分析表中的元素如用规则来表示，则分析表需三维数组，若用该方法表示分析表所需的存储空间较大，为此用规则号表示预测分析表中的元素。另外，一个算法语言的预测分析表中的元素大多是出错元素，可用-1表示。要在程序中直接用内码表示预测分析表，则该分析表还是很大的，可用(非终结符,终结符,规则号)三元式表示；非终结符和终结符匹配时，用规则号的规则推导。为减少查询分析表的时间，在分析程序初始化时，将三元式（非终结符，终结符，规则号）转换成分析表。最后，由总控程序根据分析表来分析源程序是否是文法上定义的“程序”。五、 实验要求1. 设计要求可以选择手工构造FIRST集合和FOLLOW集合以及LL(1)分析表；也可以编写FIRST集合和FOLLOW集合以及LL(1)分析表的生成程序,通过输入规则自动生成语法分析所需集合与分析表。后者难度和工作量较大，学生可以根据情况自行选择。对构造的预测分析程序总控程序，要能够显示语法分析过程中分析栈的动态变化及分析结果。2. 关于设计性报告的书写：（1） 请在实验报告中写明实验内容和要求，详细阐述解决问题的思路和方法；（2） 分析有哪些可选方案，采用目前方案的原因和理由；（3） 讲明选择了哪种语言进行设计，其优势在哪里；（4） 若对算法有所改进或思考，也请加以阐述；（5） 解释在程序设计中采用的哪种数据结构，其优点是什么？（6） 较详细地画出流程图，对程序代码加以注释；（7） 对实验结果进行分析，对存在问题提出改进思路。六、 实验类型设计性实验。七、 实验学时3学时。八、 考核方式本实验总分为5分，具体评分标准如下：5分：实验准备充分，上机准时，能独立编写和调试程序，结果正确，实验报告内容齐全，格式规范。4分：实验准备良好，上机准时，能在教师指导下顺利编写和调试程序，结果较正确，实验报告内容比较齐全，格式比较规范。3分：实验准备较好，上机准时，基本完成实验任务，实验报告内容基本齐备，结果基本正确。2分：程序功能模块基本完整，但没有完成程序调试，无实验结果，提交了实验报告且有重大缺陷。1分：程序功能模块不完整，有重大问题，没有完成程序调试，无实验结果，提交的实验报告有重大缺陷。0分：没有参加实验，没有提交实验报告。实验三：语法分析器2一、 实验目的掌握自下而上的语法分析方法，构造算符优先分析程序。二、 实验内容1 按所给文法构造FIRSTVT集合和LASTVT集合；2 构造优先矩阵；3 构造算符优先分析的总控程序；4 利用优先矩阵、分析栈和总控程序对源程序进行自下而上的语法分析测试； 5 输出整个语法分析过程中栈的变化过程及分析结果，如符合语法规则输出“正确”，否则输出“错误”。三、 实验设备及工具1硬件：PC机Pentium100以上。2软件：Win2000或WinXP、BC+、VC+或JAVA开发环境。四、 实验说明本次实验要求编制能够识别下面给定文法的算符优先分析器，其中所需的集合与分析表的构造可以手工实现，也可以编写自动生成程序。算符优文法G():=|+|-|*|/|整数|（）标识符五、 实验步骤1 构造FIRSTVT和LASTVT集合；2. 构造算符优先矩阵；3. 编写算符优先分析程序；4. 测试语句：(1) price=perimeter*2+height*5/7(2) result:=3*radius*( radius +2*height)(3) 其他错误的语句5. 写出各句的分析过程中栈和输入串的变化。六、 实验类型验证性实验。七、 实验学时3学时。八、 考核方式本实验总分为5分，具体评分标准如下：5分：实验准备充分，上机准时，能独立编写和调试程序，结果正确，实验报告内容齐全，格式规范。4分：实验准备良好，上机准时，能在教师指导下顺利编写和调试程序，结果较正确，实验报告内容比较齐全，格式比较规范。3分：实验准备较好，上机准时，基本完成实验任务，实验报告内容基本齐备，结果基本正确。2分：程序功能模块基本完整，但没有完成程序调试，无实验结果，提交了实验报告且有重大缺陷。1分：程序功能模块不完整，有重大问题，没有完成程序调试，无实验结果，提交的实验报告有重大缺陷。0分：没有参加实验，没有提交实验报告。九、 思考题1当发现错误时采取哪些措施可以保证分析继续进行?2构造FIRSTVT、LASTVT集合与构造FIRST、FOLLOW集合有何异同？3能否将自上而下和自下而上的分析方法结合使用？实验四：语义分析和中间代码生成器一、 实验目的掌握语法制导翻译方法，理解表达式的中间代码生成的过程。二、 实验内容在实验三所给文法中加上语义动作，使其在语法分析的同时，产生相应的四元式序列。三、 实验设备及工具1硬件：PC机Pentium100以上。2软件：Win2000或WinXP、BC+、VC+或JAVA开发环境。四、 实验说明语法制导翻译是在语法分析的基础上增加语义操作来实现翻译。原则上每个产生式对应一个语义子程序。在语法分析的过程中，当一个产生式获得匹配或进行归约时，相应的语义子程序便开始工作，生成中间代码，查填有关表格，检查并报告源程序中的错误，修改编译程序某些变量的值。五、 实验步骤1 在实验三所给文法中加上语义动作；2 编写语义分析和中间代码生成程序；3 测试语句：（1） price=perimeter*2+height*5/7（2） result=3*radius*( radius +2*height)（3） 其他语句4 写出分析各句后产生的四元式序列。六、 实验类型验证性实验。七、 实验学时3学时。八、 考核方式本实验总分为5分，具体评分标准如下：5分：实验准备充分，上机准时，能独立编写和调试程序，结果正确，实验报告内容齐全，格式规范。4分：实验准备良好，上机