编译原理E 实验指导书.doc

编译原理(E)实验指导书计算机软件与工程系 何春梅2011-12-28 目 录实验1 词法程序设计(1) 1实验2 词法程序设计(2) 3实验3 语法程序设计(1) 4实验4 语法程序设计(2) 5实验5 语法程序设计(3) 6实验6 中间代码生成 8 实验1 词法程序设计 DFA（确定的有穷自动机）的化简一、 实验目的与要求通过设计、编写和调试将确定的有穷自动机的状态数变为最少的C程序，使得学生掌握化简为有穷自动机的过程中的相关概念和方法。DFA的表现形式可以为表格或图形。二、 问题描述每一个正规集都可以由一个状态数最少的DFA所识别，这个DFA是唯一的（不考虑同构的情况）。任意给定的一个DFA，根据以下算法设计一个C程序，将该DFA 化简为与之等价的最简DFA。三、 算法（1）构造具有两个组的状态集合的初始划分I：接受状态组 F 和非接受状态组 Non-F。（2）对I采用下面所述的过程来构造新的划分I-new. For I 中每个组G do Begin 当且仅当对任意输入符号a,状态s和读入a后转换到I的同一组中； /*最坏情况下，一个状态就可能成为一个组*/ 用所有新形成的小组集代替I-new中的G; end（3）如果I-new=I，令I-final=I,再执行第（4）步，否则令I=I=new,重复步骤（2）。（4）在划分I-final的每个状态组中选一个状态作为该组的代表。这些代表构成了化简后的DFAM状态。令s是一个代表状态，而且假设：在DFA M中，输入为a时有从s到t转换。令t所在组的代表是r,那么在M中有一个从s到r的转换，标记为a。令包含s0的状态组的代表是M的开始状态，并令M的接受状态是那些属于F的状态所在组的代表。注意,I-final的每个组或者仅含F中的状态，或者不含F中的状态。（5）如果M含有死状态（即一个对所有输入符号都有刀自身的转换的非接受状态d）,则从M中去掉它；删除从开始状态不可到达的状态；取消从任何其他状态到死状态的转换。四、基本要求1、输入一个DFA M,输出一个与之等价的最小化的DFA M，上机编程实现。2、实验报告格式要求书写要点：概要设计（总体设计思想）；详细设计：程序主流程、DFA的存储格式（即数据结构）、关键函数的流程图；结果分析（输入与输出结果、存在问题及有待改进善的地方、实验心得）五、测试数据输入下图的DFA M,得到其最简的DFA M。 DFA M六、 实现提示：（1） 可将输入的DFA存放在外部文本文件中，也可以直接从NFA转换得到。对DFA的最小化分两部分进行化简，即分别对状态（结点）和路径（弧）进行最小化，最后输出最小化的DFA。（2） 实现的数据结构：用链表实现DFA的构造：由结点链表和转换弧链表组成： struct node /结点的定义int pos;/结点在哪个组中 int num；/结点的序号 int accept; /结点是否为接受状态 struct node *next; NODE; struct arc/弧的定义 int start; /开始的顶点位置 char input; /弧上所接受的输入字符 int end; /结束的顶点位置 struct arc *next;ARC; Struct groups /分组后各结点所在组 int n; /属于哪个组 int i;/在组中的位置GROUPs;（3） 实现方法：根据accept的值为0还是1进行初次划分I，将accept为0的所有结点构建成一个链表，将accept为1的所有结点构建一个链表。然后执行最小化函数，对每一个输入字符遍历以上个链表，对每个结点.num=弧.start的情况，查看该弧.end的组号是否相等，相等则不划分；若不相等，则需进一步划分，构建新的链表等。划分完成后选头结点为代表，删除结点链表上其他结点，并将弧线链表上需被删的弧.start或弧.end该为头结点。实验2 词法程序设计DFA模拟程序一、实验目的 通过实验教学，加深学生对所学的关于编译的理论知识的理解，增强学生对所学知识的综合应用能力，并通过实践达到对所学的知识进行验证。通过对DFA模拟程序实验，使学生掌握词法分析的实现技术，及具体实现方法。通过本实验加深对词法分析程序的功能及实现方法的理解 。二、实验环境 供Windows系统的PC机，可用C+/C#/Java等编程工具编写三、实验内容 1、定义一个右线性正规文法，示例如(仅供参考) GS：SaU|bV UbV|aQ VaU|bQ QaQ|bQ|e实验前要考虑清楚用哪种数据结构存储上述文法。2、构造其有穷确定自动机，如3、利用有穷确定自动机M=(K,f, S,Z）行为模拟程序算法，来对于任意给定的串，若属于该语言时，该过程经有限次计算后就会停止并回答“是”，若不属于，要么能停止并回答“不是”。K:=S；c:=getchar;while ceof do K:=f(K,c); c:=getchar; ;if K is in Z then return (yes)else return (no)四、 实验方式与要求1、每位同学定义的语言或文法不同，上机编程实现2、实验报告格式要求书写要点：概要设计（总体设计思想）；详细设计（程序主流程、自动机的存储格式、关键函数的流程图）；结果分析（输入与输出结果、存在问题及有待改进善的地方、实验心得）实验3 语法程序设计判断文法是否是LL(1)文法？一、实验目的 首先能让用户输入一个文法，然后让计算机自动判断是否是一个LL(1)文法，通过实验教学，加深学生对所学的关于编译的理论知识的理解，增强学生对所学知识的综合应用能力，并通过实践达到对所学的知识进行验证。二、实验环境 供Windows系统的PC机，可用C+/C#/Java等编程工具编写三、实验步骤 1、让计算机接受一个文法，示例如(仅供参考)：GS 为:SAB SbCA AbB BaDCAD CbDaS Dc1. 2、编程实现对上述文法是否是LL(1)文法的判断，是则给出肯定回答，否则给出否定回答。2. 判别是否是LL(1)文法以链表或数组等数据结构保存文法.求出能推出的非终结符.计算FIRST集,FOLLOW集和SELECT集SELECT(A)SELECT(A)=?输出肯定回答是输出否定回答否实验流程图如下：实验4-5 语法程序设计基于LL(1)文法的预测分析表法DFA模拟程序一、实验目的 通过对基于LL(1)文法的预测分析表法DFA模拟程序实验，使学生掌握确定的自上而下的语法分析的实现技术，及具体实现方法。通过本实验加深对语词法分析程序的功能及实现方法的理解。二、实验环境 供Windows系统的PC机，可用C+/C#/Java等编程工具编写三、实验步骤 1、定义一个LL(1)文法，示例如(仅供参考) GE：E TE E+TE|T FT T *FT| F i|(E)2、构造其预测分析表，如3、LL(1)文法的预测分析表的模型示意图4、预测分析控制程序的算法流程 5、运行结果，示例如下四、实验方式与要求1、每位同学定义的文法不同，上机编程实现;2、实验报告格式要求书写要点：概要设计（总体设计思想）；详细设计（程序主流程、自动机的存储格式、关键函数的流程图）；结果分析（输入与输出结果、存在问题及有待改进善的地方、实验心得）.实验6 逆波兰式的产生及计算一、实验目的： 将非后缀式用来表示的算术表达式转换为用逆波兰式来表示的算术表达式，并计算用逆波兰式来表示的算术表达式的值。 二、实验内容: 1.定义部分：定义常量、变量、数据结构。 2.初始化：设立算符优先分析表、初始化变量空间（包括堆栈、结构体、数组、临时变量等）； 3.控制部分：从键盘输入一个表达式符号串； 4.利用算符优先分析算法进行表达式处理：根据算符优先分析表对表达式符号串进行堆栈（或其他）操作，输出分析结果，如果遇到错误则显示错误信息。 5.对生成的逆波兰式进行计算。 三、实验预习提示: 1、逆波兰式定义 将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表达式也称做后缀式。逆波兰式的特点在于运算对象顺序不变，运算符号位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，其优点在于易于计算机处理表达式。 2、产生逆波兰式的前提 中缀算术表达式 3、逆波兰式生成的实验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 四、逆波兰式计算的实验设计思想及算法 (1)构造一个栈，存放运算对象。 (2)读入一个用逆波兰式表示的简单算术表达式。 (3)自左至右扫描该简单算术表达式并判断该字符，如果该字符是运算对象，则将该字符入栈。若是运算符，如果此运算符是二目运算符，则将对栈顶部的两个运算对象进行该运算，将运算结果入栈，并且将执行该运算的两个运算对象从栈顶弹出。如果该字符是一目运算符，则对栈顶部的元素实施该运算，将该栈顶部的元素弹出，将运算结果入栈。 (4)重复上述操作直至扫描完整个简单算术表达式的逆波兰式，确定所有字符都得到正确处理，我们便可以求出该简单算术表达式的值。 五、实验步骤： （一）准备： 1.阅读课本有关章节， 2.考虑好设计方案； 3.设计出模块结构、测试数据，初步编制好程序。 （二）上课上机： 将源代码拷贝到机上调试，发现错误，再修改完善。第二次上机调试通过。 （三）程序要求： 程序输入/输出示例： 输出的格式如下： (1)逆波兰式的生成及计算程序，编制人：姓名，学号，班级 (2)输入一以#结束的中缀表达式(包括+*/（）数字#)：在此位置输入符号串如(28+68)*2# (3)逆波兰式为：28&68+2* (4)逆波兰式28&68+2*计算结果为192 备注：(1)在生成的逆波兰式中如果两个数相连则用&分隔，如28和68，中间用&分隔； (2)在此位置输入符号串为用户自行输入的符号串。 注意：1.表达式中允许使用运算符（+-*/）、分割符（括号）、数字，结束符#； 2.如果遇到错误的表达式，应输出错误提示信息（该信息越详细越好）； 3.对学有余力的同学，测试用的表达式事先放在文本文件中，一行存放一个表达式，同时以分号分割。同时将预期的输出结果写在另一个文本文件中，以便和输出进行对照。11