编译原理实验报告3-LL文法构造

《编译原理实验报告3-LL文法构造》由会员分享，可在线阅读，更多相关《编译原理实验报告3-LL文法构造（18页珍藏版）》请在装配图网上搜索。

1、实验3 LL（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； j Pi| ，其中不以Pi开头，则修改产生式为：Pi PiPi Pi|3）化简上述所得文法。3、 提取左因子的算法： A 1|2|n|1|2|m

2、(其中,每个不以开头)那么,可以把这些产生式改写成 A A|1| 2|m A1|2|n4、 利用上述算法，实现构造一个LL（1）文法：1） 从文本文件g.txt中读入文法，利用实验1的结果，存入实验1设计的数据结构；2） 设计函数remove_left_recursion（）和remove_left_gene（）实现消除左递归和提取左因子算法，分别对文法进行操作，消除文法中的左递归和提出左因子；3） 整理得到的新文法；4） 在一个新的文本文件newg.txt输出文法，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。四、实验环境PC

3、微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境五、实验步骤 1、学习LL（1）文法的分析条件； 2、学习构造LL（1）文法的算法；3、结合实验1给出的数据结构，编程实现构造LL（1）文法的算法；4、结合实验1编程和调试实现对一个具体文法运用上述算法，构造它的LL（1）文法形式；5、 把实验结果写入一个新建立的文本文件。六、测试数据 输入数据：编辑一个文本文文件g.txt，在文件中输入如下内容：S-Qc|c|cab;Q-Rb|b;R-Sa|a;正确结果： 本实验的输出结果是不唯一的，根据消除左递归是选择非终结符号的顺序不同，或选择新

4、的非终结符号的不同，可能会得到不同的结果，下面只是可能的一个结果：S-Qc|cT;T-|ab; /由于无法输出，用代替Q-Rb|b;R-bcaU|caU|cabaU|aU;U-bcaU|;七、实验报告要求实验报告应包括以下几个部分：1、 满足LL（1）文法的分析条件；转换前要求文法中不含回路（经过推导有形如P-P之类的），也不含以为右部的产生式。一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。首先需要定义一些规则：1. 在程序运行前文法就必须输入进文本文件中，输入的文法只包含其中的所有产生式，并且默认其为可转换的非LL（1）文法，即通过消除左递归和反复提取

5、公共左因子，就转换成了LL（1）文法。2. 输入的产生式为原实验1的结果，即一个非终结符只有一条产生式，候选之间用“|”隔开。3. 产生式与产生式之间只能以换行符或分号隔开。4. 开始符号对应的产生式必须第一个输入，即默认输入的第一个产生式的左部的大写字母是开始符号。5. 输入与输出都会保存在文本文件中文件名分别是g.txt和newg.txt，本实验测试数据时，将两个文本放在了桌面。6. 用代替，输入与输出都使用。7. 新产生的非终结符统一使用没有在非终结符集合中出现的大写字母。8. 规定产生式最多只有20个。2、 构造LL（1）文法的算法；算法：1) 从文本文件g.txt中读入文法，存入结构

6、体中。将第一个读到的大写字母记为开始符号S，将读到的包括开始符号在内的所有大写字母判定为非终结符，并将第一次出现的存入文法的非终结符集合中，终结符小写字母也一样。将以换行符或分号隔开的字符串判断为一条产生式存入文法中。实现函数是scanP()。2) 对文法中的产生式消除左递归。实现函数是remove_left_recursion()。3) 对文法中的产生式反复提取公共左因子。实现函数是remove_left_gene ()。4) 向newg.txt中输出文法的所有产生式。3、 消除左递归文法和提取左因子算法实现方法；消除左递归文法（包括其中用到其它的子函数）：/*字符串分割函数，将产生式右部的

7、候选返回,识别|，从pos位开始分割*/string strsplit(string strTok,int pos ) string str;size_t position;position = strTok.find(|,pos);if (position != string:npos) /找到了|str = strTok.substr(pos,position - pos);else /没找到str = strTok.substr(pos, strTok.size() - pos);return str;/*获得一个文法中尚未定义的非终结符，即特定的大写字母*/char GetWord(c

8、har *p) char ch,word = A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q,R, S, T, U, V, W, X, Y, Z ;int w,x;for (w = 0; w 26; w+) ch = wordw;for (x = 0; x m; x+) if (ch = px) break;if (x = m) break;return ch;/*判断非终结符是否已存在*/bool checkWord(char ch, string Vn) int i;bool flag = true;for (i = 0; i Vn0);

9、/初始化设置开始符号bool flag20;flag0 = false;/标记哪个产生式需要删除char ch;int i,j,k,l,o;for (i = 0; i str.size(); i+) for (j = 3; j PsVni.size(); j+) for (k = 0; k PsVnij PsVnij Z) break;/不是非终结符无需判断if (gp-PsVnij = gp-Vnk) /判断从开始符号可以到达的非终结符在Vn的哪个位置flagk = false;if (checkWord(gp-Vnk, str) /将在str中没有的有用非终结符插入strint e = s

10、tr.size();sVne = k;str.insert(str.size(), 1, gp-Vnk);break;for (l = 0; l Vnl = ;for (o = l + 1; o Vno - 1;gp-Vno - 1 = gp-Vno;gp-Vno = ch;gp-Po - 1.clear();gp-Po - 1.swap(gp-Po);m-;void remove_left_recursion(struct grammar *gp) /子函数，消除文法左递归int i, j,num_i,num_j,ipos,jpos;char ch_i, ch_j;for (i = 1; i

11、 Vni - 1;/获取当前要被处理的非终结符，即Pi/分割产生式，得到右部的所有候选while (ipos != gp-Pi - 1.size() + 1) str_inum_i = strsplit(gp-Pi - 1, ipos);restr_inum_i = str_inum_i;ipos = ipos + str_inum_i.size() + 1;num_i+;for (j = 1; j Vni - 1;/重新获取当前要被处理的非终结符，即Pi/分割产生式，得到右部的所有候选while (ipos != gp-Pi - 1.size() + 1) str_inum_i = strs

12、plit(gp-Pi - 1, ipos);restr_inum_i = str_inum_i;ipos = ipos + str_inum_i.size() + 1;num_i+;repeat = true;string str_j20;int l;jpos = 3; num_j = 0;ch_j = gp-Vnj - 1;/获取当前要替换的非终结符，即Pj/分割产生式，得到右部的所有候选while (jpos != gp-Pj - 1.size() + 1) str_jnum_j = strsplit(gp-Pj - 1, jpos);jpos = jpos + str_jnum_j.si

13、ze() + 1;num_j+;for (l = 0; l ; stri.insert(0,1,ch_i);int index = 0;while (1) /将替换后的Pi的所有候选进行重组并存进文法中if (index = num_i)break;if (index = num_i - 1)stri = stri + str_iindex;elsestri = stri + str_iindex + |;index+;gp-Pi - 1 = stri;/消除直接左递归string splitstr30, resplitstr30;int s = 0,ps = 3,h = 0;while (1

14、) /分割替换后的产生式splitstrs = strsplit(gp-Pi - 1, ps);resplitstrs = splitstrs;ps = ps + splitstrs.size() + 1;if (ps = gp-Pi - 1.size() + 1)break;s+;string Pi = -,Pichange = -;Pi = ch_i + Pi;int link = 0,flag = -1;bool flagpos30; char newWord;for (; link Vn);/获取一个新的非终结符gp-Vnm = newWord;Pichange = newWord +

15、 Pichange;m+;splitstrlink = splitstrlink.substr(1) + newWord;flagposlink = false;gp-Pm - 1 = Pichange + splitstrlink + |;if (flag 0) splitstrlink = splitstrlink.substr(1) + newWord;flagposlink = false;gp-Pm - 1 = gp-Pm - 1 + splitstrlink + |;/对消除了直接左递归的候选进行重组成为产生式并存入文法if (flag -1) gp-Pi - 1 = -;gp-P

16、i - 1.insert(0, 1, ch_i);for (; h Pi - 1 = gp-Pi - 1 + splitstrh + |;gp-Pm - 1 += ;gp-Pi - 1.erase(gp-Pi - 1.size() - 1, 1);simplify(gp);/化简无用的产生式提取左因子（包括辅助函数）：/对字符串数组排序void str_sort(string *str, int num) int i, j;for (i = 0; i num; i+) for (j = i + 1; j strj)stri.swap(strj);/*子函数，提取左因子*/void remove

17、_left_gene(struct grammar *gp) int rule_a, i, j, k, l, matchnum,oldmatchnum, resize,size;char ch, newWord;for (rule_a = 0; rule_a Prule_a.size() + 1) /分割替换后的产生式strnum = strsplit(gp-Prule_a, ps);restrnum = strnum;ps = ps + strnum.size() + 1;num+;str_sort(str, num);/对所有候选按ASCII码进行排序，以便于简化对公共左因子的判断，只需先

18、对前面候选判断str_sort(restr, num);int ca_i;string Pa = -;Pa.insert(0, 1, gp-Vnrule_a);for (ca_i = 0; ca_i Prule_a = Pa;int ipo = 0;/辅助免除对已判断过有左因子的候选的遍历for (i = 0; i num; i+,i += ipo) /遍历候选ipo = 0;size = 0;resize = 0;oldmatchnum = 0;int i_s = stri.size();for (j = 0; j i_s; j+) /对候选的逐个字符遍历matchnum = 0;/标记除了

19、本身，有几个候选有公共左因子ch = strij;int kf = num;for (k = i + 1; k num & k Vn);/得到新的非终结符gp-Vnm = newWord;/将新非终结符存入文法m+;newP = -;newP.insert(0, 1, newWord);repstr = match + newWord;/得到要被替换的有公共左因子的所有候选int renum = num;if (bre 0) /若对同一产生式还存在另一个公共左因子（之前提取过一次左因子），需进行特别处理size = resize = 0;renum = 0;ps = 3;while (ps !

20、= gp-Prule_a.size() + 1) /分割变化后的产生式restrrenum = strsplit(gp-Prule_a, ps);ps = ps + restrrenum.size() + 1;renum+;/*将已经提取过左因子的以候选为单位的字符串重新组合成产生式（包括新产生式）*/for (l = 0; l = i - oldpo) size += restrl.size();can = restrl.substr(j);if (can = )can = ;if (l = i - oldpo + oldmatchnum) newP += can;elsenewP = ne

21、wP + can + |;gp-Pm - 1 = newP;else resize += restrl.size();resize+;gp-Prule_a.replace(resize + 3, size + oldmatchnum, repstr); /原产生式以替换的方式进行改变if (i + 1 + oldmatchnum num) break; elseoldpo = ipo = oldmatchnum;4、 主程序代码；#include#includeusing namespace std;struct grammar /使用结构体定义文法char Vn20;/非终结符char Vt

22、20;/终结符char S;/开始符号string P20;/产生式;int m = 0, n = 0;/全局变量，分别表示最近存入结构体的非终结符与终结符是字符数组的第几个位置char GetBC(FILE* fpi) /子函数，用于读取一个非空格字符char ch;do ch = fgetc(fpi); while (ch = );return ch;/*整型函数，读入一行产生式分析出文法成员，参数分别是输入文本的文件指针、文法结构体的指针第几行的产生式*/void scanP(FILE* fpi,struct grammar *gp) char ch;string str;/存入一条产生

23、式if (feof(fpi)return;/到达文件尾则返回ch = GetBC(fpi);if (ch = A & ch Vnm = ch;/将非终结符存入结构体m+;ch = GetBC(fpi);if (ch = -) str += ch;ch = GetBC(fpi);if (ch = ) str += ch;while (1) ch = GetBC(fpi);if (ch = n | ch = ;)break;/读入换行符或分号，退出循环str += ch;if (ch = a & ch = z) /读入终结符int num;for (num = 0; num Vtnum = ch)

24、break;if (num = n) /存入结构体中未出现的终结符gp-Vtn = ch;n+;gp-Pm - 1 += str;/将产生式存入结构体int main() FILE* fpi;/定义输入文本指针FILE* fpo;/定义输出文本指针errno_t err;if (err = fopen_s(&fpi,C:UsersAdministratorDesktopg.txt, r) != 0) /只读方式打开文件printf(file can not open!n);/打开文件出错提示exit(0);/安全退出程序struct grammar g, *gp;gp = &g;/定义结构体及

25、其指针/读取第一个大写字母作为开始符号char ch;do ch = GetBC(fpi); while (ch = Z);gp-S = ch;fseek(fpi, -1L, 1);/搜索指示器回调一个字符while (!feof(fpi) /从文本文件中读入产生式得到文法四个部分，并存入结构体中scanP(fpi,gp);fclose(fpi);/关闭fpi指向的文件fpi = NULL;/避免指向非法内存remove_left_recursion(gp);remove_left_gene(gp);err = fopen_s(&fpo,C:UsersAdministratorDesktopn

26、ewg.txt, w); /只写方式打开文件，不存在则自动建立if (err != 0) printf(file can not open!n);/打开文件出错提示exit(0);/安全退出程序int i;for (i = 0; i Pi.data(), fpo);fputs(n, fpo);fclose(fpo);/关闭fpi指向的文件fpo = NULL;/避免指向非法内存5、 整个测试程序的流程；向g.txt中输入文法启动程序main()反复调用scanP()到达文件尾完成文法输入调用remove_left_recursion()调用remove_left_gene()将文法输出到new

27、g.txt程序结束查看结果文法6、 程序的测试结果和问题；实验源文法：其它文法：书上的文法，不过调换了顺序，且改变开始符号为R，结果会删除关于Q的无用产生式：实验中遇到的问题：1. 开始设计程序的时候，并没有很好的运用数据结构来简化问题，只是使用了实验一的数据结构，构造了一个结构体。实验大部分的处理过程需要用到文法的产生式，但是结构体中产生式只是用字符串数组存储，其中夹杂着”-”和”|”，分析时要将这些符号去除（迭代时前面有过变化，还要重新分割得到候选），得到候选，给处理过程增加了复杂度，如果能对产生式另外设计一个结构体，只将左部的非终结符和右部的所有候选及候选的个数进行封装，将极大地简化代码

28、，又或者将其直接定义为类，这样还可以使用其中的成员函数，过程将更加清晰有条理。2. 代码的重用性问题，由于缺乏对C+编程的经验，几乎没有使用类、对象这些更优越的技术来实现。另外有些地方的，诸如重新对候选进行分割，另外设置存储位置作为缓冲等等，没有设置子函数去处理，使得主过程变得冗余。3. 对C的字符数组运用的不熟练，用其来存储字符串时，不能灵活的使用相应的库函数来处理问题，不得已使用了C+的string类，其实关于字符数组的许多库函数非常有用，高效。4. 编程时使用的VS2015，由于之前一直使用DevC+，所以编程时对一些软件功能不熟悉，浪费了时间在查看说明，认识快捷键上。今后还是需要多在V

29、S下编写C。5. 编程经验不足导致的查阅或者大量修改，降低了效率。6. 调试程序时变量太多，查错费了不少时间，这也是没有多多使用子函数带来的弊端。7、 实验总结。 实验本身是比较麻烦的，好在关键的remove_left_recursion（）和remove_left_gene（）两个子函数提供了算法再加上本身理论课提供的大量额外知识，很容易有思路。主要就在于实现这两个子函数的具体过程。而这两个函数的实现过程将与文法的数据结构关系密切，如果能首先在设计数据结构上下工夫，能够设计得到一个好的数据结构，绝对能事半功倍！所以以后对于相对复杂的问题，要首先设计好数据结构，其次慢慢完成算法。完成算法及其代

30、码的编写后，就是调试了。要高效完成这项工作，需要了解IDE关于调试的各种功能，这样借助软件的这些功能，调试会更加容易，当然其中免不了会发现错误，需要修改程序的时候，我觉得特别要注意修改，这就像是一个状态转换的过程，你在修改前程序在一个过程，修改后是另一个过程，但到达的过程究竟是是否是你要的，就在于你的修改，修改时要特别将需要修改的部分用软件本身的自动将相同变量调亮的功能进行标记，免得漏改，一旦漏改，很容易进入思维误区，觉得刚才的修改方法出错，但其实不过是漏改了，这点错误在变量达到十几二十个时很容易犯，所以调试时要重点关注修改！八、思考题1、 是不是所有的文法都可以通过上述程序构造LL（1）文法

31、？答：不是；文法本身要能够被转换，在经过转换前要不含回路，不含以空字为右部的产生式，转换时，在提取公共左因子时还存在某些文法不能在有限步骤内提取完左公因子。例如：S-Ap|BqA-aAp|dB-aBq|e那么在转换后还要在经过判断才能最终确认是否是LL（1）文法。2、 LL（1）文法在整个语法分析中的作用？答：语法分析包括两类：一类是自上而下分析法，一类是自下而上分析法自上而下的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下的为输入串建立一棵语法树。或者说，为输入串寻找一个最左推倒，这种分析过程的本质是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程我主要是自上

32、而下的过程。而在自上而下的分析法中，主要是研究LL(1)分析法。3、 实验1中设计的文法数据结构对本实验的影响？答：使用数据结构本身是能够简化问题，可以使具体算法的思路有倾向性，也可以使得程序处理过程更加有条理，另外实验1的数据结构，完整的将开始符号，终结符，非终结符及所有产生式存储，对于消除左递归和提取左因子，可以对非终结符和产生式有进行更加有效的处理，较之没有使用数据结构或没有存储非终结符而言可以在迭代时单个处理，而不需要再所有步骤完成后才进行统一处理。4、 如何更好地组合实验1和实验3，使之具有更高的效率？答：使用结构体来定义文法，包括文法的四个部分，终结符和非终结符用string类，以

33、便于可以调用string类的成员函数处理问题，产生式用C+类来定义，在存储文法时得到其左部的非终结符和右部的所有候选，并将候选按ASCII码排好序再存储，其数据有非终结符，所有候选，以及候选的个数，成员函数要能够查看，增加，修改，删除所有的成员，如果可以候选最好能使用链表，这样增加，替换，删除将更加简单，高效。在实验1中还要将有回路的和右部有空字的产生式进行判断，提示输入的文法不合理，另外再将由实验3定义的一些规定转接到实验1，这样文法的结构定义，文法的完整输入以及对可转换的非LL（1）文法的判断，以及其它输入的提示及出错检测全部集中在原来实验1要完成的部分，原来实验3的部分只关注将文法进行转换和输出，即消除左递归、提取左因子和输出到文本文件中。