编译原理实验指导

1编译原理实验指导2目录实验1：文法的读入和输出.........................................................................................3实验2：词法分析程序的设计.....................................................................................5实验3：LL（1）文法构造..........................................................................................7实验4：语法分析程序的设计（1）.........................................................................10实验5：语法分析程序的设计（2）.........................................................................12实验6：逆波兰式的翻译和计算...............................................................................15实验7：语法制导的三地址代码生成.......................................................................172,3,5,6/73实验1文法的读入和输出一、实验目的熟悉文法的结构，了解文法在计算机内的表示方法。二、实验内容1、设计一个表示文法的数据结构；2、从文本文件中读入文法，利用定义的数据结构存放文法，并输出；3、本实验结果还将用于实验3。三、实验要求1、了解文法定义的4个部分：G（Vn,Vt,S,P）Vn文法的非终结符号集合，在实验中用大写的英文字母表示；Vt文法的终结符号集合，在实验中用小写的英文字母表示；S开始符号，在实验中是Vn集合中的一个元素；P产生式，分左部和右部，左部为非终结符号中的一个，右部为终结符号或非终结符号组成的字符串，如S-ab|c2、根据文法各个部分的性质，设计一个合理的数据结构用来表示文法，1）若使用C语言编写，则文法可以设计成结构体形式，结构体中应包含上述的4部分，2）若使用C++语言编写，则文法可以设计成文法类形式，类中至少含有4个数据成员，分别表示上述4个部分文法数据结构的具体设计由学生根据自己想法完成，并使用C或C++语言实现设计的数据结构。3、利用完成的数据结构完成以下功能：1）从文本文件中读入文法（文法事先应写入文本文件）；2）根据文法产生式的结构，分析出文法的4个部分，分别写入定义好的文法数据结构的相应部分；3）整理文法的结构；4）在计算机屏幕或者文本框中输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。四、实验环境PC微机DOS操作系统或Windows操作系统4TurboC程序集成环境或VisualC++程序集成环境五、实验步骤1、根据文法定义，设计出文法数据结构2、用学生选择的语言，实现文法的数据结构3、编写调试文法读入和输出程序，4、测试程序运行效果：从文本文件中读入一个文法，在屏幕上输出，检查输出结果。六、测试数据输入数据：编辑一个文本文文件g.txt，在文件中输入如下内容：S-Qc;S-c;Q-Rb;Q-b;R-Sa;R-a;正确结果：上述文法整理后的输出形式：S-Qc|c;Q-Rb|b;R-Sa|a;七、实验报告要求实验报告应包括以下几个部分：1、文法数据结构的设计和实现；2、文法的读入算法3、文法的输出方法4、程序的测试结果和问题5、实验总结八、思考题1、如何让设计的文法结构满足各种文法的要求？2、如何设计文法才能跟简单地表示文法，同时又降低程序编写难度？5实验2词法分析程序的设计一、实验目的掌握计算机语言的词法分析程序的开发方法。二、实验内容编制一个能够分析三种整数、标识符、主要运算符和主要关键字的词法分析程序。三、实验要求1、根据以下的正规式，编制正规文法，画出状态图；标识符字母(字母|数字字符)*十进制整数0|(（1|2|3|4|5|6|7|8|9）（0|1|2|3|4|5|6|7|8|9）*)八进制整数0（1|2|3|4|5|6|7）（0|1|2|3|4|5|6|7）*十六进制整数0x（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）（0|1|2|3|4|5|6|7|8|9|a|b|c|d|e|f）*运算符和界符+-*/=()；关键字ifthenelsewhiledo2、根据状态图，设计词法分析函数intscan()，完成以下功能：1）从文本文件中读入测试源代码，根据状态转换图，分析出一个单词，2）以二元式形式输出单词单词种类，单词属性其中单词种类用整数表示：0：标识符1：十进制整数2：八进制整数3：十六进制整数运算符和界符，关键字采用一字一符，不编码其中单词属性表示如下：标识符，整数由于采用一类一符，属性用单词表示运算符和界符，关键字采用一字一符，属性为空3、编写测试程序，反复调用函数scan()，输出单词种别和属性。四、实验环境PC微机DOS操作系统或Windows操作系统TurboC程序集成环境或VisualC++程序集成环境五、实验步骤1、根据正规式，画出状态转换图；2、根据状态图，设计词法分析算法；63、采用C或C++语言，设计函数scan()，实现该算法；4、编制测试程序（主函数main）；5、调试程序：读入文本文件，检查输出结果。六、测试数据输入数据：编辑一个文本文件program.txt，在文件中输入如下内容：正确结果：七、实验报告要求实验报告应包括以下几个部分：1、词法的正规式描述；2、变换后的状态图；3、词法分析程序的数据结构与算法。八、思考题1、词法分析能否采用空格来区分单词？ifdata+920x3fthendata=data+01;elsedata=data-01;if,-0,data+,-1,92,-3,3fthen,-0,data=,0,data+,-2,1;,-else,-0,data=,-0,data-,-2,-;,-72、程序设计中哪些环节影响词法分析的效率？如何提高效率？实验3LL（1）文法构造一、实验目的熟悉LL（1）文法的分析条件，了解LL（1）文法的构造方法。二、实验内容1、编制一个能够将一个非LL（1）文法转换为LL（1）文法；2、消除左递归；3、消除回溯。三、实验要求1、将一个可转换非LL（1）文法转换为LL（1）文法，要经过两个阶段，1）消除文法左递归，2）提取左因子，消除回溯。2、提取文法左因子算法：1）对文法G的所有非终结符进行排序2）按上述顺序对每一个非终结符Pi依次执行:for(j=1；ji-1；j++)将Pj代入Pi的产生式（若可代入的话）；消除关于Pi的直接左递归：Pi-Piα|β，其中β不以Pi开头，则修改产生式为：Pi—＞βPi′Pi′—＞αPi′|ε3）化简上述所得文法。3、提取左因子的算法：A—＞δβ1|δβ2|…|δβn|γ1|γ2|…|γm(其中,每个γ不以δ开头)那么,可以把这些产生式改写成A—＞δA′|γ1|γ2…|γmA′—＞β1|β2|…|βn4、利用上述算法，实现构造一个LL（1）文法：1）从文本文件g.txt中读入文法，利用实验1的结果，存入实验1设计的数据结构；2）设计函数remove_left_recursion（）和remove_left_gene（）实现消除左递归和提取左因子算法，分别对文法进行操作，消除文法中的左递归和提出左因子；3）整理得到的新文法；4）在一个新的文本文件newg.txt输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。8四、实验环境PC微机DOS操作系统或Windows操作系统TurboC程序集成环境或VisualC++程序集成环境五、实验步骤1、学习LL（1）文法的分析条件；2、学习构造LL（1）文法的算法；3、结合实验1给出的数据结构，编程实现构造LL（1）文法的算法；4、结合实验1编程和调试实现对一个具体文法运用上述算法，构造它的LL（1）文法形式；5、把实验结果写入一个新建立的文本文件。六、测试数据输入数据：编辑一个文本文文件g.txt，在文件中输入如下内容：正确结果：本实验的输出结果是不唯一的，根据消除左递归是选择非终结符号的顺序不同，或选择新的非终结符号的不同，可能会得到不同的结果，下面只是可能的一个结果：七、实验报告要求实验报告应包括以下几个部分：1、满足LL（1）文法的分析条件；2、构造LL（1）文法的算法；3、消除左递归文法和提取左因子算法实现方法；4、整个测试程序的流程；5、程序的测试结果和问题；6、实验总结。八、思考题1、是不是所有的文法都可以通过上述程序构造LL（1）文法？S-Qc|c|cab;Q-Rb|b;R-Sa|a;S-Qc|cT;T-@|ab;//由于无法输出ε，用@代替Q-Rb|b;R-bcaU|caU|cabaU|aU;U-bcaU|@;92、LL（1）文法在整个语法分析中的作用？3、实验1中设计的文法数据结构对本实验的影响？4、如何更好地组合实验1和实验3，使之具有更高的效率？10实验4语法分析程序的设计（1）一、实验目的通过设计、编制、调试一个典型的语法分析程序，实现对词法分析程序所提供的单词序列进行语法检查和结构分析，进一步掌握常用的语法分析中递归下降分析方法。二、实验内容设计一个文法的递归下降分析程序，判断特定表达式的正确性。三、实验要求1、给出文法如下：G[E]E-T|E+T;T-F|T*F;F-i(E);利用实验3的方法将上述文法转化为LL（1）文法；2、根据递归下降分析方法为转化后的文法设计递归下降分析程序，利用C语言或C++语言实现；3、利用递归下降分析程序完成下列功能：1）手工将测试的表达式写入文本文件，每个表达式写一行，用“；”表示结束；2）读入文本文件中的表达式；3）调用实验2中的词法分析程序搜索单词；4）把单词送入递归下降分析程序，判断表达式是否正确（是否是给出文法的语言），若错误，应给出错误信息；5）完成上述功能，有余力的同学可以对正确的表达式计算出结果。四、实验环境PC微机DOS操作系统或Windows操作系统TurboC程序集成环境或VisualC++程序集成环境五、实验步骤1、分析文法，将给出的文法转化为LL(1)文法；2、学习递归下降分析程序的结构，设计合理的递归下降分析程序；3、编写测试程序，包括表达式的读入和结果的输出；4、测试程序运行效果，测试数据可以参考下列给出的数据。六、测试数据输入数据：编辑一个文本文文件expression.txt，在文件中输入如下内容：11正确结果：（1）10;输出：正确（2）1+2;输出：正确（3）(1+2)*3+(5+6*7);输出：正确（4）((1+2)*3+4输出：错误（5）1+2+3+(*4+5)输出：错误（6）(a+b)*(c+d)输出：正确（7）((ab3+de4)**5)+1输出：错误七、实验报告要求实验报告应包括以下几个部分：1、给定文法的LL（1）形式；2、递归下降分析程序的算法和结构；3、程序运行流程；4、程序的测试结果和问题；5、实验总结。八、思考题1、为什么文法必须先转化为LL（1）文法再来做递归下降分析？2、如果用预测分析法来改写本程序，如何来实现？10;1+2;(1+2)*3+(5+6*7);((1+2)*3+4;1+2+3+(*4+5);(a+b)*(c+d);