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