《编译原理》实验指导书(吴元斌)

《《编译原理》实验指导书(吴元斌)》由会员分享，可在线阅读，更多相关《《编译原理》实验指导书(吴元斌)（19页珍藏版）》请在金锄头文库上搜索。

1、编译原理实验指导书“编译原理”课程是计算机本科专业的必选课程，上机实验是该课程的重要环节，实验学时数为 8 学时。一个编译程序把源程序翻译成等价的目标程序，一般应做词法分析、语法分析、语义分析、代码生成和代码优化等五个方面的工作，为了使学生对其有较深的理解，必须根据这五个方面设计实验。本指导书正是根据课程的内容，将实验分为前期准备阶段、基本操作阶段和技术提高阶段三个阶段进行：前期准备阶段的实验主要是为后续实验做好准备，应围绕编译原理课程进行设计，如：学生可根据教科书的内容，设计一个源程序的输入和扫描程序，并完成相应的设计报告；基本操作阶段的实验是围绕着编译原理的五个方面的工作来进行，其内容主要

2、是词法分析、语法分析、语义分析、代码生成和代码优化等，如：简单的词法分析程序、LL(1) 分析法算法、语义分析程序、中间代码和目标代码生成算法的实验，这些实验基本上包括了以上知识要点，学生可结合书本上有关的知识来完成；技术提高阶段的实验是综合性课程设计实验，根据编译原理编制应用程序，不仅要求把书本上的内容掌握好，同时还需要自学一些相关的知识。 1 实验一、词法分析（2 学时）一、 实验目的熟悉正规文法、正规式和有穷自动机，了解词法分析的主要任务，掌握词法分析是如何根据正规文法规则逐一分析词法得到属性字的，即掌握了词法分析过程。二、 实验内容编制一个读单词过程，从输入的源程序中，识别出各个具有独

3、立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 （遇到错误时可显示“Error” ，然后跳过错误部分继续显示） 。三、 实验原理词法分析是编译过程的第一步，要想做好该实验，必须熟悉正规文法、正规式和有穷自动机的概念和原理，实验前须先定义语言的正规文法或正规式，构造确定的有穷自动机，然后根椐有穷自动机设计程序模块，源程序的输入。 2 四、 实验步骤（一） 准备：1.阅读课本有关章节，花二天时间明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。2.初步编制好程序。3.准备好多组测试数据。（二） 上课上机：将源代码拷

4、贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三） 程序思路（仅供参考）：0. 定义部分：定义常量、变量、数据结构。1. 初始化：从文件将源程序全部输入到字符缓冲区中。2. 取单词前：去掉多余空白。3. 取单词后：去掉多余空白（可选，看着办） 。4. 取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。 （关键是如何判断取单词结束？取到的单词是什么类型的单词？）5. 显示结果。五、 实验报告要求（1）功能描述：该程序具有什么功能？（2）程序结构描述：函数调用格式、参数含义、返回值描述、函数功能； 3 函数之间的调用关系图、程序总体执行流程图（参考课本第二章） 。（3）

5、实验过程记录：出错次数、出错严重程度、解决办法摘要。（4）实验总结：你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？六、 注意事项1为了能设计好程序，应做好以下工作：模块设计：将程序分成合理的多个模块（函数） ，每个模块做具体的同一事情；写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等；编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2. 该实验课约课余准备 4 小时；上机 2 小时；完成实验报告 2 小时；3需提交：程序源代码；已经测试通过的测试数据 3 组（

6、以“第一组输入/ 输出/第二组输入/输出/第三组输入/输出”的顺序存放） 。七、 思考题1. 如何根据正规式构造有穷自动机？2该实验的难点和重点在哪里？ 4 实验二、 LL（1 ）分析算法（2 学时）一、 实验目的熟悉前面所学的语法分析过程，了解语法分析是如何根据语法规则逐一分析词法分析时所得到的属性字，以及检查语法错误的，即掌握了语法分析过程；具体来说，要求学生掌握LL(1)分析法的基本原理、掌握 LL(1)分析表的构造方法、掌握 LL(1)驱动程序的构造方法。二、 实验内容根据课本所提供的 LL（1）分析算法，编写一个语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，

7、训练学生对常用语法进行分析的能力。本实验可以算术表达式为例完成语法分析，其的文法可以是（你可以根据需要适当改变）：EE+T|T, TT*F|F, F（E）|i根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确。三、 实验原理LL(1)是自顶向下的语法分析方法之一，它是编译过程的第二步，要想做好该实验，必须熟悉 LL(1) 分析方法的基本原理，掌握表达式文法的预测分析表的构造方法；且实验前须先定义好表达式的文法规则，构造预测分析表，然后设计程序模块，并进行调试和运行。四、 实验步骤（一）准备：1.阅读课本有关章节，花二天时间确定算术表达式的文法，设计出表达式文法的预测分析表；2.考

8、虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。（二）上课上机：上机调试，发现错误，分析错误，再修改完善。教师根据学生的设计方案与学生进行探讨，以修改方案和代码。（三）程序要求：程序输入/输出示例：如参考 C 语言的运算符。输入如下表达式（以 #为结束）和输出结果：（1）10#输出：正确（2）1+2#输出：正确 5 （3）(1+2)*3#输出：正确（4）(1-2)/3+4#输出：错误（5）1+2-3+(*4/5)#输出：错误注意：1.为降低难度，表达式中不含变量（只含无符号整数） ；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好） ；3.测试用的表达式事先放在文本文

9、件中，一行存放一个表达式，同时以#号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；4.对学有余力的同学，可增加功能：当判断一个表达式正确时，输出计算结果，计算过程用浮点表示，但要注意不要被 0 除。程序思路（仅供参考）：1.借用实验二的结果，可将其中的取字符函数几乎原封不动地移植过来，其中的分割和分析单词的方法可借用过来分割现在这个实验的运算符、常量和变量。2.模块结构：（1）初始化：设立表达式文法的预测分析表、初始化变量空间（包括堆栈、结构体、数组等） ；（2）控制部分：将一个表达式从文件中读出；（3）词法分析：将表达式分割成单词序列；（4）利用表达式文法进行表达式处理

10、：根据预测分析表对表达式单词序列进行堆栈操作，如果遇到错误则显示错误信息。（四）练习该实验的目的和思路：程序比较复杂，需要利用到大量的编译原理，也用到了大量编程技巧和数据结构，通过这个练习可极大提高编程能力。程序规模大概为 250 行。本实验的结果可作为课程设计的基础。通过练习，掌握对表达式进行处理的一种方法。五、 实验报告要求（1）功能描述：该程序具有什么功能？（2）程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图、程序总体执行流程图（参考课本第三章） 。（3）实验过程记录：出错次数、出错严重程度、解决办法摘要。（4）实验总结：你在编程过程中花时多少？多少时间

11、在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？ 6 六、 注意事项1为了能设计好程序，应做好以下工作：模块设计：将程序分成合理的多个模块（函数） ，每个模块做具体的同一事情。写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。编程时注意编程风格：空行的使用、注释的使用、缩进的使用、变量合理命名等。2该实验课约须课余准备 4 小时；上机一次 2 小时；完成实验报告 2 小时；3需提交：程序源代码；已经测试通过的测试数据 10 组（以“第一组输入/输出/第二组输入/输出/第三组输入/ 输出”的格式存放） 。

12、七、 思考题1比较前面所学的几种语法分析方法的特点，思考为什么选用 LL（1）分析法处理判断算术表达式的正确性？2改用算符优先分析法或 LR（1）能否实现以上功能？实验三、语义分析程序（2 学时）一、实验目的复习前面课文中所学的语义分析的相关知识，使学生了解语义检查目的和意义，掌握语义检查的一般内容，掌握语义检查的方法。二、实验内容在语法分析的基础上，利用 SNL 等编译器或自己编写一个语义分析程序对语法分析内容进行语义错误检查，对运行结果进行分析，并纠正运行过程中出现的各种错误，训练学生对常用语义进行分析的能力，和增强对本章节的理解。三、实验仪器、设备及材料1、一人一台计算机，独立完成实验。

13、 7 2、计算机硬件的最低配置为：Pentium CPU、128M RAM、CDROM、硬盘、软驱、彩显。3、计算机软件的基本要求：SNL 语言编译器或软件开发工具，如 Eclipse + MinGW、Microsoft Visual C+等。四、实验原理语义分析（Semantic Analysis）是任何编译程序必不可少的一个阶段，也是编译程序最实质性的工作。在整个编译过程中，词法分析和语法分析是对源程序形式上的识别和处理，而语义分析程序是对源程序的语义做相应的处理工作。在 SNL 编译器中，语义错误检查涉及标识符的重复声明错误，有使用无声明错误和类型一致性检查。前面提到了标识符的重复声明错

14、误的检查，对于标识符有使用无声明错误，也是以先根次序遍历语法分析树节点，遍历时只对含有变量标识符，类型标识符和过程标识符使用的语法树节点进行处理。即：赋值语句类型节点，读语句类型节点，表达式类型节点和过程调用语句节点。处理的时候，先查符号表，如果标识符不在符号表中，则为标识符的有使用无声明错误，输出语义错误信息。否则，读取标识符的相关信息。在类型一致性检查过程中，按照后根次序遍历语法分析树，即在遍历处理语法分析树的子节点之后，再处理该节点，进行类型检查。在对语法树节点处理过程中，只针对运算类型表达式节点，常量表达式类型节点，标识符表达式类型节点，条件语句类型节点，赋值语句类型节点，写语句类型节

15、点，循环语句类型节点，过程调用语句类型节点。五、实验步骤（一）准备：阅读课本有关章节，准备被分析的源程序等测试数据。（二）上课上机：上机调试，发现错误，分析错误，给出错误原因，并写出该源程序的语义分析结果。（三）具体步骤：（1）熟悉 SNL 语言的语义，了解语义分析阶段需要进行哪些语义检查同时要掌握符号的作用域原则；（2）准备以上实验数据；（3）检查标识符的有使用无声明错误：先根遍历语法树，遍历时只对含有变量标识符，类型标识符和过程标识符使用的语法树节点进行处理。（4）类型一致性检查：后根遍历语法树，遍历时只针对运算类型表达式节点，常量表达式类型节点，标识符表达式类型节点，条件语句类型节点，赋

16、值语句类型节点，写语句类型节点，循环语句类型节点，过程调用语句类型节点。（四）练习该实验的目的和思路：本实验需要利用到大量的编译原理的相关知识，通过这个练习可大大提高学生对语义 8 分析的理解。本实验的结果可作为课程设计的基础。六、实验报告要求（1）功能描述：该子模块具有什么功能？（2）程序结构描述：程序总体执行流程图。（3）实验过程记录：出错次数、出错严重程度、解决办法摘要。（4）实验总结：你在实验准备过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的实验效果评价如何？你的收获有哪些？七、注意事项1本实验的要求为掌握语义检查的一般内容；学会在语法分析的同时进行语义检查；学会将语义分析作为一遍独立的扫描。2如果自己设计程序，应做好以下工作：模块设计：将程序分成合理的多个模块（