编译原理实验指导.doc

编 译 原 理 实 验指 导 目 录 实验1：文法的读入和输出 3 实验2：词法分析程序的设计 5 实验3：LL（1）文法构造 7 实验4：语法分析程序的设计（1） 10 实验5：语法分析程序的设计（2） 12 实验6：逆波兰式的翻译和计算 15 实验7：语法制导的三地址代码生成 17 2,3,5,6/7 实验1 文法的读入和输出 一、实验目的 熟悉文法的结构，了解文法在计算机内的表示方法。? 二、实验内容 设计一个表示文法的数据结构； 从文本文件中读入文法，利用定义的数据结构存放文法，并输出； 本实验结果还将用于实验3。? 三、实验要求 了解文法定义的4个部分： G（Vn, Vt, S, P） Vn 文法的非终结符号集合，在实验中用大写的英文字母表示； Vt 文法的终结符号集合，在实验中用小写的英文字母表示； S 开始符号，在实验中是Vn集合中的一个元素； P 产生式，分左部和右部，左部为非终结符号中的一个，右部为终结符号或非终结符号组成的字符串，如S-ab|c 根据文法各个部分的性质，设计一个合理的数据结构用来表示文法， 若使用C语言编写，则文法可以设计成结构体形式，结构体中应包含上述的4部分， 若使用C++语言编写，则文法可以设计成文法类形式，类中至少含有4个数据成员，分别表示上述4个部分 文法数据结构的具体设计由学生根据自己想法完成，并使用C或C++语言实现设计的数据结构。 利用完成的数据结构完成以下功能： 从文本文件中读入文法（文法事先应写入文本文件）； 根据文法产生式的结构，分析出文法的4个部分，分别写入定义好的文法数据结构的相应部分； 整理文法的结构； 在计算机屏幕或者文本框中输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。 ?四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 ?五、实验步骤 1、根据文法定义，设计出文法数据结构 2、用学生选择的语言，实现文法的数据结构 3、编写调试文法读入和输出程序， 测试程序运行效果：从文本文件中读入一个文法，在屏幕上输出，检查输出结果。 ?六、测试数据 输入数据： 编辑一个文本文文件g.txt，在文件中输入如下内容： S-Qc; S-c; Q-Rb; Q-b; R-Sa; R-a; 正确结果： 上述文法整理后的输出形式： S-Qc|c; Q-Rb|b; R-Sa|a;? 七、实验报告要求 实验报告应包括以下几个部分： 文法数据结构的设计和实现； 文法的读入算法 文法的输出方法 程序的测试结果和问题 实验总结? 八、思考题 如何让设计的文法结构满足各种文法的要求？ 如何设计文法才能跟简单地表示文法，同时又降低程序编写难度？ 实验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）* 运算符和界符 + - * / = ( ) ； 关键字 if then else while do 2、根据状态图，设计词法分析函数int scan( )，完成以下功能： 从文本文件中读入测试源代码，根据状态转换图，分析出一个单词， 以二元式形式输出单词单词种类，单词属性 其中单词种类用整数表示： 0：标识符 1：十进制整数 2：八进制整数 3：十六进制整数 运算符和界符，关键字采用一字一符，不编码 其中单词属性表示如下： 标识符，整数由于采用一类一符，属性用单词表示 运算符和界符，关键字采用一字一符，属性为空 3、编写测试程序，反复调用函数scan( )，输出单词种别和属性。 ?四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环