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

编译原理实验指导书“编译原理”课程是计算机本科专业的必选课程，上机实验是该课程的重要环节，实验学时数为8学时。一个编译程序把源程序翻译成等价的目标程序，一般应做词法分析、语法分析、语义分析、代码生成和代码优化等五个方面的工作，为了使学生对其有较深的理解，必须根据这五个方面设计实验。本指导书正是根据课程的内容，将实验分为前期准备阶段、基本操作阶段和技术提高阶段三个阶段进行：前期准备阶段的实验主要是为后续实验做好准备，应围绕编译原理课程进行设计，如：学生可根据教科书的内容，设计一个源程序的输入和扫描程序，并完成相应的设计报告；基本操作阶段的实验是围绕着编译原理的五个方面的工作来进行，其内容主要是词法分析、语法分析、语义分析、代码生成和代码优化等，如：简单的词法分析程序、LL(1) 分析法算法、语义分析程序、中间代码和目标代码生成算法的实验，这些实验基本上包括了以上知识要点，学生可结合书本上有关的知识来完成；技术提高阶段的实验是综合性课程设计实验，根据编译原理编制应用程序，不仅要求把书本上的内容掌握好，同时还需要自学一些相关的知识。实验一、词法分析（2学时）一、 实验目的熟悉正规文法、正规式和有穷自动机，了解词法分析的主要任务，掌握词法分析是如何根据正规文法规则逐一分析词法得到属性字的，即掌握了词法分析过程。二、 实验内容编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本保留字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。（遇到错误时可显示“Error”，然后跳过错误部分继续显示）。三、 实验原理词法分析是编译过程的第一步，要想做好该实验，必须熟悉正规文法、正规式和有穷自动机的概念和原理，实验前须先定义语言的正规文法或正规式，构造确定的有穷自动机，然后根椐有穷自动机设计程序模块，源程序的输入。四、 实验步骤（一） 准备：1.阅读课本有关章节，花二天时间明确语言的语法，写出基本保留字、标识符、常数、运算符、分隔符和程序例。2.初步编制好程序。3.准备好多组测试数据。（二） 上课上机：将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。（三） 程序思路（仅供参考）：0. 定义部分：定义常量、变量、数据结构。1. 初始化：从文件将源程序全部输入到字符缓冲区中。2. 取单词前：去掉多余空白。3. 取单词后：去掉多余空白（可选，看着办）。4. 取单词：利用实验一的成果读出单词的每一个字符，组成单词，分析类型。（关键是如何判断取单词结束？取到的单词是什么类型的单词？）5. 显示结果。五、 实验报告要求（1）功能描述：该程序具有什么功能？（2）程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图、程序总体执行流程图（参考课本第二章）。（3）实验过程记录：出错次数、出错严重程度、解决办法摘要。（4）实验总结：你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？六、 注意事项1为了能设计好程序，应做好以下工作：模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情；写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等；编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。2. 该实验课约课余准备4小时；上机2小时；完成实验报告2小时；3需提交：程序源代码；已经测试通过的测试数据3组（以“第一组输入/输出/第二组输入/输出/第三组输入/输出”的顺序存放）。七、 思考题1. 如何根据正规式构造有穷自动机？2该实验的难点和重点在哪里？实验二、LL（1）分析算法（2学时）一、 实验目的熟悉前面所学的语法分析过程，了解语法分析是如何根据语法规则逐一分析词法分析时所得到的属性字，以及检查语法错误的，即掌握了语法分析过程；具体来说，要求学生掌握LL(1)分析法的基本原理、掌握LL(1)分析表的构造方法、掌握LL(1)驱动程序的构造方法。二、 实验内容根据课本所提供的LL（1）分析算法，编写一个语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，训练学生对常用语法进行分析的能力。本实验可以算术表达式为例完成语法分析，其的文法可以是（你可以根据需要适当改变）： EE+T|T, TT*F|F, F（E）|i根据算符优先分析法，将表达式进行语法分析，判断一个表达式是否正确。三、 实验原理 LL(1)是自顶向下的语法分析方法之一，它是编译过程的第二步，要想做好该实验，必须熟悉LL(1) 分析方法的基本原理，掌握表达式文法的预测分析表的构造方法；且实验前须先定义好表达式的文法规则，构造预测分析表，然后设计程序模块，并进行调试和运行。四、 实验步骤（一）准备：1.阅读课本有关章节，花二天时间确定算术表达式的文法，设计出表达式文法的预测分析表；2.考虑好设计方案；3.设计出模块结构、测试数据，初步编制好程序。（二）上课上机：上机调试，发现错误，分析错误，再修改完善。教师根据学生的设计方案与学生进行探讨，以修改方案和代码。（三）程序要求：程序输入/输出示例：如参考C语言的运算符。输入如下表达式（以#为结束）和输出结果：（1）10#输出：正确（2）1+2#输出：正确（3）(1+2)*3#输出：正确（4）(1-2)/3+4#输出：错误（5）1+2-3+(*4/5)#输出：错误注意：1.为降低难度，表达式中不含变量（只含无符号整数）；2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）；3.测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以#号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照；4.对学有余力的同学，可增加功能：当判断一个表达式正确时，输出计算结果，计算过程用浮点表示，但要注意不要被0除。程序思路（仅供参考）：1.借用实验二的结果，可将其中的取字符函数几乎原封不动地移植过来，其中的分割和分析单词的方法可借用过来分割现在这个实验的运算符、常量和变量。2.模块结构：（1）初始化：设立表达式文法的预测分析表、初始化变量空间（包括堆栈、结构体、数组等）；（2）控制部分：将一个表达式从文件中读出；（3）词法分析：将表达式分割成单词序列；（4）利用表达式文法进行表达式处理：根据预测分析表对表达式单词序列进行堆栈操作，如果遇到错误则显示错误信息。（四）练习该实验的目的和思路：程序比较复杂，需要利用到大量的编译原理，也用到了大量编程技巧和数据结构，通过这个练习可极大提高编程能力。程序规模大概为250行。本实验的结果可作为课程设计的基础。通过练习，掌握对表达式进行处理的一种方法。五、 实验报告要求（1）功能描述：该程序具有什么功能？（2）程序结构描述：函数调用格式、参数含义、返回值描述、函数功能；函数之间的调用关系图、程序总体执行流程图（参考课本第三章）。（3）实验过程记录：出错次数、出错严重程度、解决办法摘要。（4）实验总结：你在编程过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的程序的评价？你的收获有哪些？六、 注意事项1为了能设计好程序，应做好以下工作：模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。编程时注意编程风格：空行的使用、注释的使用、缩进的使用、变量合理命名等。2该实验课约须课余准备4小时；上机一次2小时；完成实验报告2小时；3需提交：程序源代码；已经测试通过的测试数据10组（以“第一组输入/输出/第二组输入/输出/第三组输入/输出”的格式存放）。七、 思考题1比较前面所学的几种语法分析方法的特点，思考为什么选用LL（1）分析法处理判断算术表达式的正确性？ 2改用算符优先分析法或LR（1）能否实现以上功能？实验三、语义分析程序（2学时）一、实验目的复习前面课文中所学的语义分析的相关知识，使学生了解语义检查目的和意义，掌握语义检查的一般内容，掌握语义检查的方法。二、实验内容在语法分析的基础上，利用SNL等编译器或自己编写一个语义分析程序对语法分析内容进行语义错误检查，对运行结果进行分析，并纠正运行过程中出现的各种错误，训练学生对常用语义进行分析的能力，和增强对本章节的理解。三、实验仪器、设备及材料1、一人一台计算机，独立完成实验。2、计算机硬件的最低配置为：Pentium CPU、128M RAM、CDROM、硬盘、软驱、彩显。3、计算机软件的基本要求：SNL语言编译器或软件开发工具，如Eclipse + MinGW、Microsoft Visual C+等。四、实验原理语义分析（Semantic Analysis）是任何编译程序必不可少的一个阶段，也是编译程序最实质性的工作。在整个编译过程中，词法分析和语法分析是对源程序形式上的识别和处理，而语义分析程序是对源程序的语义做相应的处理工作。在SNL编译器中，语义错误检查涉及标识符的重复声明错误，有使用无声明错误和类型一致性检查。前面提到了标识符的重复声明错误的检查，对于标识符有使用无声明错误，也是以先根次序遍历语法分析树节点，遍历时只对含有变量标识符，类型标识符和过程标识符使用的语法树节点进行处理。即：赋值语句类型节点，读语句类型节点，表达式类型节点和过程调用语句节点。处理的时候，先查符号表，如果标识符不在符号表中，则为标识符的有使用无声明错误，输出语义错误信息。否则，读取标识符的相关信息。在类型一致性检查过程中，按照后根次序遍历语法分析树，即在遍历处理语法分析树的子节点之后，再处理该节点，进行类型检查。在对语法树节点处理过程中，只针对运算类型表达式节点，常量表达式类型节点，标识符表达式类型节点，条件语句类型节点，赋值语句类型节点，写语句类型节点，循环语句类型节点，过程调用语句类型节点。五、实验步骤（一）准备：阅读课本有关章节，准备被分析的源程序等测试数据。（二）上课上机：上机调试，发现错误，分析错误，给出错误原因，并写出该源程序的语义分析结果。（三）具体步骤：（1）熟悉SNL语言的语义，了解语义分析阶段需要进行哪些语义检查同时要掌握符号的作用域原则；（2）准备以上实验数据；（3）检查标识符的有使用无声明错误：先根遍历语法树，遍历时只对含有变量标识符，类型标识符和过程标识符使用的语法树节点进行处理。（4）类型一致性检查：后根遍历语法树，遍历时只针对运算类型表达式节点，常量表达式类型节点，标识符表达式类型节点，条件语句类型节点，赋值语句类型节点，写语句类型节点，循环语句类型节点，过程调用语句类型节点。（四）练习该实验的目的和思路：本实验需要利用到大量的编译原理的相关知识，通过这个练习可大大提高学生对语义分析的理解。本实验的结果可作为课程设计的基础。六、实验报告要求（1）功能描述：该子模块具有什么功能？（2）程序结构描述：程序总体执行流程图。（3）实验过程记录：出错次数、出错严重程度、解决办法摘要。（4）实验总结：你在实验准备过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的实验效果评价如何？你的收获有哪些？七、注意事项1本实验的要求为掌握语义检查的一般内容；学会在语法分析的同时进行语义检查；学会将语义分析作为一遍独立的扫描。2如果自己设计程序，应做好以下工作：模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。编程时注意编程风格：空行的使用、注释的使用、缩进的使用、变量合理命名等。3 该实验课约须课余准备4小时；上机一次2小时；完成实验报告2小时。4需提交：程序源代码；已经测试通过的测试数据10组（以“第一组输入/输出/第二组输入/输出/第三组输入/输出”的格式存放）。八、思考题1该试验的主要难点是什么？如何克服？2这一章的重点和难点是什么？实验四、中间代码生成（2学时）一、实验目的复习前面课文中所学的中间代码生成的相关知识，使学生掌握几种常见的中间代码表示形式，了解几种常见的中间代码生成方法，掌握由语法树到四元式中间代码的生成方法。二、实验内容在语义分析的基础上，利用SNL等编译器或自己编写一个程序将语法和语义分析的结果变为四元式等中间代码，以增强学生对本章节中的四元式等中间代码理解。三、实验仪器、设备及材料1、一人一台计算机，独立完成实验。2、计算机硬件的最低配置为：Pentium CPU、128M RAM、CDROM、硬盘、软驱、彩显。3、计算机软件的基本要求：SNL语言编译器或软件开发工具，如Eclipse + MinGW、Microsoft Visual C+等。四、实验原理中间代码生成阶段不是编译器的必须阶段，生成中间代码的目的是为了便于优化和移植。在SNL语言的编译器中，经过语法分析或语义分析得到的语法树实际上已经是一种中间代码表示形式，可以在它的基础上进行优化和目标代码生成操作。但是，为了更好地了解中间代码表示形式、中间代码生成和优化技术，SNL语言编译器将中间代码生成作为独立的一遍扫描。变量的中间代码、表达式的中间代码、语句的中间代码的结构见教材。从语法树到四元式的生成方法，下面以赋值语句节点为例给出解释。赋值语句节点结构如下：（StmtK，AssignK，child0，child1，Null），其四元式的生成过程如下：1. 以赋值语句节点的第一个儿子节点child0为参数,调用变量的处理函数GenVar,生成赋值左部变量的中间代码,并返回变量的ARG结构指针Larg；2. 以赋值语句节点的第二个儿子节点child1为参数,调用表达式的处理函数GenExpr,生成赋值右部表达式的中间代码,并返回表达式的ARG结构指针Rarg；3. 生成中间代码(ASSIG，Rarg，Larg，NULL)五、实验步骤（一）准备：阅读课本有关章节，准备测试数据。（二）上课上机：上机调试，发现错误，分析错误，给出错误原因，并写出该源程序的语义分析结果。（三）具体步骤：（1）熟悉SNL语言的定义，明确SNL语言的程序结构；（2）熟悉语法树的结构，准备上机实验数据；（3）熟悉要使用的四元式代码，扫描语法树生成中间代码。（四）练习该实验的目的和思路：本实验需要利用到大量的编译原理的相关知识，通过这个练习可大大提高学生对中间代码生成的理解。本实验的结果可作为课程设计的基础。六、实验报告要求（1）功能描述：该子模块具有什么功能？（2）程序结构描述：程序总体执行流程图。（3）实验过程记录：出错次数、出错严重程度、解决办法摘要。（4）实验总结：你在实验准备过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的实验效果评价如何？你的收获有哪些？七、注意事项1本实验的要求为：了解中间代码生成是为优化和移植而进行的；了解几种常见中间代码表示形式掌握符号表应包含的符号的属性信息；会用简单的程序实现中缀式到后缀式的转换；会用栈实现复杂表达式的求值；掌握常见程序结构的中间代码结构；掌握由语法树到四元式中间代码的转换方法。2如果自己设计程序，应做好以下工作：模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。编程时注意编程风格：空行的使用、注释的使用、缩进的使用、变量合理命名等。3该实验课约须课余准备4小时；上机一次2小时；完成实验报告2小时。4需提交：程序源代码；已经测试通过的测试数据10组（以“第一组输入/输出/第二组输入/输出/第三组输入/输出”的格式存放）。八、思考题1该试验的主要难点是什么？如何克服？2这一章的重点和难点是什么？实验五、目标代码生成（2学时）一、实验目的复习前面课文中所学的中间代码生成的相关知识，使学生了解目标代码生成阶段在编译处理过程中的功能和作用；了解常用的三种目标代码形式及其优缺点；了解虚拟机及其指令系统；深入理解并掌握有中间代码向目标代码转换的过程和原理。二、实验内容利用SNL等编译器或自己编写一个程序将语法分析树或四元式等中间代码变为目标代码，使学生了解常用的三种目标代码形式及其优缺点，并深入理解并掌握有中间代码向目标代码转换的过程和原理。三、实验仪器、设备及材料1、一人一台计算机，独立完成实验。2、计算机硬件的最低配置为：Pentium CPU、128M RAM、CDROM、硬盘、软驱、彩显。3、计算机软件的基本要求：SNL语言编译器或软件开发工具，如Eclipse + MinGW、Microsoft Visual C+等。四、实验原理在SNL语言的编译器中，经过语法分析或语义分析得到的语法树实际上已经是一种中间代码表示形式，可以在它的基础上进行优化和目标代码生成操作。通常的目标代码，即在实际机器上的指令序列，有绝对地址机器代码、可重定位的机器代码、汇编代码三种。在本系统中采用虚拟目标代码，即在虚拟机上运行的目标程序，在本地机器上具备虚拟机的解释器。通过本实验可以使学生了解常用的代码生成程序的开发方法、全局寄存器分配法和代码生成程序的自动化构造方法。五、实验步骤（一）准备：阅读课本有关章节，准备测试数据。（二）上课上机：上机调试，发现错误，分析错误，给出错误原因，并写出该源程序的语义分析结果。（三）具体步骤：（1）四元式到目标代码的转换分析1）取ARG结构值对应的目标代码四元式中间代码的操作分量和目标量以ARG结构给出，在生成目标代码的过程中，首先要根据ARG结构取得对应的值或者地址，存入累加寄存器ac中，再生成运算的目标代码。从ARG结构取值的过程如下表所示： ARG结构种类 取值对应的目标代码常量c LDC，ac，c，0 标号lab LDC，ac，lab，0 源变量或临时变量v直接变量取v的绝对地址到ac； (表-2)LD，ac，0，ac间接变量取v的绝对地址到ac； (表-2)LD，ac1，0，ac LD，ac，0，ac12）取变量的绝对地址对应的目标代码如下表所示：变量种类 取绝对地址对应的目标代码源变量v LDA，ac，level，displayoff ADD，ac，ac，sp LDC，ac1，off，0 ADD，ac，ac ，ac1注：level为变量v所在的层数，off为变量v的偏移。 临时变量t LDC，ac1，off，0 ADD，ac，sp，ac1注：off为临时变量t的偏移量（2）关键问题的处理 1） 标号和跳转的处理：处理标号和跳转，需要用到标号地址表；表的结构为： 中间代码标号 目标代码地址 下一项 Labeldestnumnexta 遇到标号定位时：设标号为L，应转向的目标代码为p1，分为两种情况： 在标号地址表中没有L项，则填写表项(L，p1,NULL)，并链入表尾； 在标号地址表中有L项(L，addr，Next)，则根据当前pc，回填addr对应的目标代码。b 遇到跳转代码时：设要跳到的标号为L，这条语句对应的目标地址为p2，分为两种情况： 在标号地址表中没有L项，则构造一个表项(L，p2，NULL)，链入表尾； 在标号地址表中有L项(L，p1，next)，则从中取出L的代码地址p1，直接生成目标代码。2)形实参结合的处理：a 形参为值参： 实参是常数值：将常数值送入相应存储单元； 实参是直接变量：找到变量的存储地址，取值，送相应存储单元； 实参是间接变量：此时变量的存储单元存放的是地址。找到变量的存储地址，取内容作为地址，再取内容，得到实参值，送相应存储单元；b 形参为变参：这时实参必须是变量，长度为1。 实参是直接变量：应将实参变量的地址送入形参单元；找到变量的存储地址，送相应存储单元； 实参是间接变量：要送实参变量单元的内容；找到变量的存储地址，取内容，送相应存储单元。3) 过程调用的工作分配：由于过程调用中的有些工作是相同的，如果都放在调用语句处处理，当一个过程被多个过程调用时，就要重复很多目标代码。从语法树生成目标代码时，所有过程调用的处理工作都必须放在调用语句处进行处理。而从中间代码生成目标代码时，由于有过程入口和过程出口中间代码的存在，我们就可以把有些工作安排在子程序的入口和出口处完成。这样，过程调用中的整个工作(除过程体的执行部分)可分配到过程调用处，过程入口处和过程出口处。这样就可以节省一些目标代码。具体分配如下： 过程调用代码完成：保存旧的display表的偏移量；设置新的display表的偏移；保存返回地址；转向过程入口。 过程入口处完成： 保存sp值； 保存层数； 保存累加寄存器的内容，ac，ac1，ac2 构造NewAR的Display表；修改sp和top值：sp:=top ；top:= top+NewAR.Size 过程出口处完成： 恢复寄存器的内容；恢复sp和top的值：top:=sp；sp:=CurrentAR.sp；取出返回地址，返回。（四）练习该实验的目的和思路：本实验需要利用到大量的编译原理的相关知识，通过这个练习可大大提高学生对目标代码生成的理解。本实验的结果可作为课程设计的基础。六、实验报告要求（1）功能描述：该子模块具有什么功能？（2）程序结构描述：程序总体执行流程图。（3）实验过程记录：出错次数、出错严重程度、解决办法摘要。（4）实验总结：你在实验准备过程中花时多少？多少时间在纸上设计？多少时间上机输入和调试？多少时间在思考问题？遇到了哪些难题？你是怎么克服的？你对你的实验效果评价如何？你的收获有哪些？七、注意事项1本实验的要求为：熟练掌握虚拟机的指令系统；理解并掌握指令选择的方法；理解多寄存器分配的原则和方法；熟练掌握基本语句从四元式中间代码形式到目标代码的翻译原理和方法；如有可能，独立完成目标代码生成程序。2如果自己设计程序，应做好以下工作：模块设计：将程序分成合理的多个模块（函数），每个模块做具体的同一事情。写出（画出）设计方案：模块关系简图、流程图、全局变量、函数接口等。编程时注意编程风格：空行的使用、注释的使用、缩进的使用、变量合理命名等。3该实验课约须课余准备4小时；上机二次4小时；完成实验报告4小时。4需提交：程序源代码；已经测试通过的测试数据10组（以“第一组输入/输出/第二组输入/输出/第三组输入/输出”的格式存放）。八、思考题1该试验的主要难点是什么？如何克服？2这一章的重点和难点是什么？实验报告示例：有限自动机的运行（下面以实验报告的形式向大家展示如何设计程序，以及如何书写实验步骤）一、实验题目：有限自动机的运行（或“利用状态图判断无符号定点实数”等）二、实验目的：1理解有限自动机的作用；2利用状态图和状态表表示有限自动机；3以程序实现有限自动机的运行过程。三、实验内容：利用状态表和有限自动机的运行原理编制程序，使得程序能够识别一个输入串是否为一个有效的无符号定点实数。四、实验仪器、设备及材料1、一人一台计算机，独立完成实验。2、计算机硬件的最低配置为：Pentium CPU、128M RAM、CDROM、硬盘、软驱、彩显。3、计算机软件的基本要求：PL/0编译程序和