实验3：LL()文法构造.docxVIP

实 验 报 告 实验课程： 编译原理 学生姓名： 学 号： 专业班级： 计科 实验3 LL（1）文法构造 一、实验目的 熟悉LL（1）文法的分析条件，了解LL（1）文法的构造方法。? 二、实验内容 1、编制一个能够将一个非LL（1）文法转换为LL（1）文法； 2、消除左递归； 3、消除回溯。? 三、实验要求 将一个可转换非LL（1）文法转换为LL（1）文法，要经过两个阶段，1）消除文法左递归，2）提取左因子，消除回溯。 提取文法左因子算法： 1）对文法G的所有非终结符进行排序 2）按上述顺序对每一个非终结符Pi依次执行: for( j=1； j i-1；j++) 将Pj代入Pi的产生式（若可代入的话）； 消除关于Pi的直接左递归： Pi - Piα|β ，其中β不以Pi开头，则修改产生式为： Pi —＞ βPi′ Pi′—＞ αPi′|ε 3）化简上述所得文法。 提取左因子的算法： A —＞ δβ1|δβ2|…|δβn|γ1|γ2|…|γm (其中,每个γ不以δ开头) 那么,可以把这些产生式改写成 A —＞ δA′|γ1| γ2…|γm A′—＞β1|β2|…|βn 利用上述算法，实现构造一个LL（1）文法： 从文本文件g.txt中读入文法，利用实验1的结果，存入实验1设计的数据结构； 设计函数remove_left_recursion（）和remove_left_gene（）实现消除左递归和提取左因子算法，分别对文法进行操作，消除文法中的左递归和提出左因子； 整理得到的新文法； 在一个新的文本文件newg.txt输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。 ?四、实验环境 PC微机 DOS操作系统或 Windows 操作系统 Turbo C 程序集成环境或 Visual C++ 程序集成环境 ?五、实验步骤 1、学习LL（1）文法的分析条件； 2、学习构造LL（1）文法的算法； 3、结合实验1给出的数据结构，编程实现构造LL（1）文法的算法； 4、结合实验1编程和调试实现对一个具体文法运用上述算法，构造它的LL（1）文法形式； 把实验结果写入一个新建立的文本文件。 ?六、测试数据 输入数据： 编辑一个文本文文件g.txt，在文件中输入如下内容： S-Qc|c|cab;Q-Rb|b; S-Qc|c|cab; Q-Rb|b; R-Sa|a;? 正确结果： 本实验的输出结果是不唯一的，根据消除左递归是选择非终结符号的顺序不同，或选择新的非终结符号的不同，可能会得到不同的结果，下面只是可能的一个结果： S-Qc|cT; S-Qc|cT; T-@|ab; //由于无法输出ε，用@代替 Q-Rb|b; R-bcaU|caU|cabaU|aU; U-bcaU|@;? 七、实验报告要求 实验报告应包括以下几个部分： 满足LL（1）文法的分析条件； 构造LL（1）文法的算法； 消除左递归文法和提取左因子算法实现方法； 整个测试程序的流程； 程序的测试结果和问题； 实验总结。 代码 #includeiostream #includestring using namespace std; typedef struct Chomsky //定义一个产生式结构体 { string left; //定义产生式的左部 string right; //定义产生式的右部 }Chomsky; int n;//产生式总数 string strings;//存储产生式 char q[20]; void apart(Chomsky *p,int i) //分开产生式左右部i代表产生式的编号 { int j; for(j=0;jstrings.length();j++) if(strings[j]==-) { p[i].left=strings.substr(0,j);//从0开始的j长度的子串即0~j-1 p[i].right=strings.substr(j+1,strings.length()-j);//从j+1开始的后面子串 } } int zero(Ch