编译原理实验3-LL(1)文法构造

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< i-1；j+)将Pj代入Pi的产生式（若可代入的话）；消除关于Pi的直接左递归：Pi -> Pi| ，其

2、中不以Pi开头，则修改产生式为：Pi PiPi Pi|3）化简上述所得文法。3、 提取左因子的算法： A 1|2|n|1|2|m (其中,每个不以开头)那么,可以把这些产生式改写成 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输出文法

3、，文法输出按照一个非终结符号一行，开始符号引出的产生式写在第一行，同一个非终结符号的候选式用“|”分隔的方式输出。 四、实验环境PC微机DOS操作系统或 Windows 操作系统Turbo C 程序集成环境或 Visual C+ 程序集成环境 五、实验步骤 1、学习LL（1）文法的分析条件； 2、学习构造LL（1）文法的算法；3、结合实验1给出的数据结构，编程实现构造LL（1）文法的算法；4、结合实验1编程和调试实现对一个具体文法运用上述算法，构造它的LL（1）文法形式；5、 把实验结果写入一个新建立的文本文件。 六、测试数据 输入数据：编辑一个文本文文件g.tx

4、t，在文件中输入如下内容：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|; 七、实验报告要求实验报告应包括以下几个部分：1、 满足LL（1）文法的分析条件；转换前要求文法中不含回路（经过推导有形如P->P之类的），也不含以为右部

5、的产生式。一个文法要能进行LL（1）分析，那么这个文法应该满足：无二义性，无左递归，无左公因子。首先需要定义一些规则：1. 在程序运行前文法就必须输入进文本文件中，输入的文法只包含其中的所有产生式，并且默认其为可转换的非LL（1）文法，即通过消除左递归和反复提取公共左因子，就转换成了LL（1）文法。2. 输入的产生式为原实验1的结果，即一个非终结符只有一条产生式，候选之间用“|”隔开。3. 产生式与产生式之间只能以换行符或分号隔开。4. 开始符号对应的产生式必须第一个输入，即默认输入的第一个产生式的左部的大写字母是开始符号。5. 输入与输出都会保存在文本文件中文件名分别是g.txt和newg.

6、txt，本实验测试数据时，将两个文本放在了桌面。6. 用代替，输入与输出都使用。7. 新产生的非终结符统一使用没有在非终结符集合中出现的大写字母。8. 规定产生式最多只有20个。2、 构造LL（1）文法的算法；算法：1) 从文本文件g.txt中读入文法，存入结构体中。将第一个读到的大写字母记为开始符号S，将读到的包括开始符号在内的所有大写字母判定为非终结符，并将第一次出现的存入文法的非终结符集合中，终结符小写字母也一样。将以换行符或分号隔开的字符串判断为一条产生式存入文法中。实现函数是scanP()。2) 对文法中的产生式消除左递归。实现函数是remove_left_recursion()。3

7、) 对文法中的产生式反复提取公共左因子。实现函数是remove_left_gene ()。4) 向newg.txt中输出文法的所有产生式。3、 消除左递归文法和提取左因子算法实现方法；消除左递归文法（包括其中用到其它的子函数）：/*字符串分割函数，将产生式右部的候选返回,识别|，从pos位开始分割*/string strsplit(string strTok,int pos ) string str;size_t position;position = strTok.find("|",pos);if (position != string:npos) /找到了|str =

8、strTok.substr(pos,position - pos);else /没找到str = strTok.substr(pos, strTok.size() - pos);return str;/*获得一个文法中尚未定义的非终结符，即特定的大写字母*/char GetWord(char *p) char ch,word = 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', '

9、;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

10、= m) break;return ch;/*判断非终结符是否已存在*/bool checkWord(char ch, string Vn) int i;bool flag = true;for (i = 0; i < Vn.size(); i+) if (ch = Vni)flag = false;return flag;/*化简无用产生式*/void simplify(struct grammar *gp) string str;/存储从开始符号可以到达的非终结符的序列int sVn20;/标记在哪个产生式sVn0 = 0;str.insert(0, 1, gp->Vn0);/

11、初始化设置开始符号bool flag20;flag0 = false;/标记哪个产生式需要删除char ch;int i,j,k,l,o;for (i = 0; i < str.size(); i+) for (j = 3; j < gp->PsVni.size(); j+) for (k = 0; k < m;k+) if (gp->PsVnij < 'A' | gp->PsVnij > 'Z') break;/不是非终结符无需判断if (gp->PsVnij = gp->Vnk) /判断从开始符号可

12、以到达的非终结符在Vn的哪个位置flagk = false;if (checkWord(gp->Vnk, str) /将在str中没有的有用非终结符插入strint e = str.size();sVne = k;str.insert(str.size(), 1, gp->Vnk);break;for (l = 0; l < m; l+) /删除无用的产生式和相应的非终结符char ch;if (flagl) gp->Vnl = ' 'for (o = l + 1; o < m; o+) ch = gp->Vno - 1;gp->Vno

13、 - 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 < m + 1;i+) bool repeat = true;/标记相对于本轮循环上轮过程产生式是否有过变化，有则需要重新分割得到候选num_i = 0,ipos = 3;st

14、ring str_i20,restr_i20, ex = "a"ch_i = gp->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 <= i - 1; j+) if (!repeat) num_i

15、 = 0, ipos = 3;ch_i = gp->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+;repeat = true;string str_j20;int l;jpos = 3; num_j = 0;ch_j = gp->Vnj -

16、 1;/获取当前要替换的非终结符，即Pj/分割产生式，得到右部的所有候选while (jpos != gp->Pj - 1.size() + 1) str_jnum_j = strsplit(gp->Pj - 1, jpos);jpos = jpos + str_jnum_j.size() + 1;num_j+;for (l = 0; l < num_i; l+) /逐个判断Pi的候选中是否含有Pj,有则进行替换string change;ex0 = ch_j;size_t pos = restr_il.find(ex);if (pos = string:npos) cont

17、inue; /无需替换else if (pos = 0)/Pj在该候选的第一个字符repeat = false;/string s = str_il.substr(1, str_il.size() - 1);/得到候选中除Pj外的剩余部分str_il.swap(change);/清空字符串int link = 0;while (1) /将Pj的所有候选与Pi中匹配的候选的剩余部分连接，中间还添加“|”if (link = num_j)break;str_jlink += s;if (link = num_j - 1)str_il += str_jlink;elsestr_il = str_il

18、 + str_jlink + "|"link+;else if (pos = str_il.size() - 1) /Pj在该候选的最后一个字符repeat = false;/string s = str_il.substr(0, str_il.size() - 1);str_il.swap(change);int link = 0;while (1) if (link = num_j)break;str_jlink = s + str_jlink;if (link = num_j - 1)str_il += str_jlink;elsestr_il = str_il +

19、str_jlink + "|"link+;else /Pj在该候选的中间repeat = false;/string s1 = str_il.substr(0,pos - 1);/得到该候选中Pj前的字符串string s2 = str_il.substr(pos + 1, str_il.size() - pos - 1);/得到该候选中Pj后的字符串str_il.swap(change);int link = 0;while (1) if (link = num_j)break;str_jlink = s1 + str_jlink + s2;if (link = num_

20、j - 1)str_il += str_jlink;elsestr_il = str_il + str_jlink + "|"link+;string stri = "->" 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

21、+;gp->Pi - 1 = stri;/消除直接左递归string splitstr30, resplitstr30;int s = 0,ps = 3,h = 0;while (1) /分割替换后的产生式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 = "->&quo

22、t;Pi = ch_i + Pi;int link = 0,flag = -1;bool flagpos30; char newWord;for (; link <= s; link+) /遍历所有候选，校验其中是否有左递归size_t posi;posi = resplitstrlink.find(ch_i);if (posi = 0) /存在直接左递归flag+;/对候选标记左递归if (flag = 0) /处理出现左递归的第一个候选newWord = GetWord(gp->Vn);/获取一个新的非终结符gp->Vnm = newWord;Pichange = new

23、Word + 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 + "|"/对消除了直接左递归的候选

24、进行重组成为产生式并存入文法if (flag > -1) gp->Pi - 1 = "->"gp->Pi - 1.insert(0, 1, ch_i);for (; h <= s; h+) if (flagposh) splitstrh += newWord;gp->Pi - 1 = gp->Pi - 1 + splitstrh + "|"gp->Pm - 1 += ""gp->Pi - 1.erase(gp->Pi - 1.size() - 1, 1);simplify(g

25、p);/化简无用的产生式提取左因子（包括辅助函数）：/对字符串数组排序void str_sort(string *str, int num) int i, j;for (i = 0; i < num; i+) for (j = i + 1; j < num; j+) if (stri > strj)stri.swap(strj);/*子函数，提取左因子*/void remove_left_gene(struct grammar *gp) int rule_a, i, j, k, l, matchnum,oldmatchnum, resize,size;char ch, new

26、Word;for (rule_a = 0; rule_a < m; rule_a+) /遍历所有产生式int bre = -1;/标记已对产生式进行过左因子的提取int oldpo = 0;int num = 0, ps = 3;string str30,restr30;/前者用于判断，需要保持原样，后者用于对有公共左因子的候选进行提取，可变while (ps != gp->Prule_a.size() + 1) /分割替换后的产生式strnum = strsplit(gp->Prule_a, ps);restrnum = strnum;ps = ps + strnum.si

27、ze() + 1;num+;str_sort(str, num);/对所有候选按ASCII码进行排序，以便于简化对公共左因子的判断，只需先对前面候选判断str_sort(restr, num);int ca_i;string Pa = "->"Pa.insert(0, 1, gp->Vnrule_a);for (ca_i = 0; ca_i < num; ca_i+) /对排序后的候选进行重组并存入文法if (ca_i = num - 1)Pa += strca_i;elsePa += strca_i + "|"gp->Prule

28、_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;/标记除了本身，有几个候选有公共左因子ch = strij;int kf = num;for (k = i + 1; k < num && k < kf; k+) /对i之

29、后的候选进行判断，是否有与i对应的公共左因子if (strkj = ch) /有公共左因子matchnum+;else break;if (j = 0) /判断是否有公共左因子是i的第一个字符的情况，有则特别处理if (matchnum = 0)break;else oldmatchnum = matchnum; kf = i + 1 + oldmatchnum; else if (oldmatchnum != matchnum)break;/*有公共左因子的处理过程*/if (matchnum != oldmatchnum | j = i_s) bre +;string match, rep

30、str, can, newP;match = stri.substr(0, j);/获取公共左因子newWord = GetWord(gp->Vn);/得到新的非终结符gp->Vnm = newWord;/将新非终结符存入文法m+;newP = "->"newP.insert(0, 1, newWord);repstr = match + newWord;/得到要被替换的有公共左因子的所有候选int renum = num;if (bre > 0) /若对同一产生式还存在另一个公共左因子（之前提取过一次左因子），需进行特别处理size = resiz

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

32、.substr(j);if (can = "")can = ""if (l = i - oldpo + oldmatchnum) newP += can;elsenewP = newP + can + "|"gp->Pm - 1 = newP;else resize += restrl.size();resize+;gp->Prule_a.replace(resize + 3, size + oldmatchnum, repstr); /原产生式以替换的方式进行改变if (i + 1 + oldmatchnum >

33、num) break; elseoldpo = ipo = oldmatchnum;4、 主程序代码；#include<iostream>#include<string>using namespace std;struct grammar /使用结构体定义文法char Vn20;/非终结符char Vt20;/终结符char S;/开始符号string P20;/产生式;int m = 0, n = 0;/全局变量，分别表示最近存入结构体的非终结符与终结符是字符数组的第几个位置char GetBC(FILE* fpi) /子函数，用于读取一个非空格字符char ch;d

34、o ch = fgetc(fpi); while (ch = ' ');return ch;/*整型函数，读入一行产生式分析出文法成员，参数分别是输入文本的文件指针、文法结构体的指针第几行的产生式*/void scanP(FILE* fpi,struct grammar *gp) char ch;string str;/存入一条产生式if (feof(fpi)return;/到达文件尾则返回ch = GetBC(fpi);if (ch >= 'A' && ch <= 'Z') /读入产生式左部的非终结符str += c

35、h;gp->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;fo

36、r (num = 0; num < n; num+) /判断该终结符在当前结构体中是否已存在if (gp->Vtnum = ch)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"

37、;) != 0) /只读方式打开文件printf("file can not open!n");/打开文件出错提示exit(0);/安全退出程序struct grammar g, *gp;gp = &g;/定义结构体及其指针/读取第一个大写字母作为开始符号char ch;do ch = GetBC(fpi); while (ch <= 'A' | ch >= 'Z');gp->S = ch;fseek(fpi, -1L, 1);/搜索指示器回调一个字符while (!feof(fpi) /从文本文件中读入产生式得到文

38、法四个部分，并存入结构体中scanP(fpi,gp);fclose(fpi);/关闭fpi指向的文件fpi = NULL;/避免指向非法内存remove_left_recursion(gp);remove_left_gene(gp);err = fopen_s(&fpo,"C:UsersAdministratorDesktopnewg.txt", "w"); /只写方式打开文件，不存在则自动建立if (err != 0) printf("file can not open!n");/打开文件出错提示exit(0);/安全退出程

39、序int i;for (i = 0; i < m; i+) /输出处理后的文法到文本中fputs(gp->Pi.data(), fpo);fputs("n", fpo);fclose(fpo);/关闭fpi指向的文件fpo = NULL;/避免指向非法内存5、 整个测试程序的流程；向g.txt中输入文法启动程序main()反复调用scanP()到达文件尾完成文法输入调用remove_left_recursion()调用remove_left_gene()将文法输出到newg.txt程序结束查看结果文法6、 程序的测试结果和问题；实验源文法：其它文法：书上的文法，

40、不过调换了顺序，且改变开始符号为R，结果会删除关于Q的无用产生式：实验中遇到的问题：1. 开始设计程序的时候，并没有很好的运用数据结构来简化问题，只是使用了实验一的数据结构，构造了一个结构体。实验大部分的处理过程需要用到文法的产生式，但是结构体中产生式只是用字符串数组存储，其中夹杂着”->”和”|”，分析时要将这些符号去除（迭代时前面有过变化，还要重新分割得到候选），得到候选，给处理过程增加了复杂度，如果能对产生式另外设计一个结构体，只将左部的非终结符和右部的所有候选及候选的个数进行封装，将极大地简化代码，又或者将其直接定义为类，这样还可以使用其中的成员函数，过程将更加清晰有条理。2.

41、代码的重用性问题，由于缺乏对C+编程的经验，几乎没有使用类、对象这些更优越的技术来实现。另外有些地方的，诸如重新对候选进行分割，另外设置存储位置作为缓冲等等，没有设置子函数去处理，使得主过程变得冗余。3. 对C的字符数组运用的不熟练，用其来存储字符串时，不能灵活的使用相应的库函数来处理问题，不得已使用了C+的string类，其实关于字符数组的许多库函数非常有用，高效。4. 编程时使用的VS2015，由于之前一直使用DevC+，所以编程时对一些软件功能不熟悉，浪费了时间在查看说明，认识快捷键上。今后还是需要多在VS下编写C。5. 编程经验不足导致的查阅或者大量修改，降低了效率。6. 调试程序时变量太多，查错费了不少时间，这也是没有多多使用子函数带来的弊端。7、 实验总结。 实验本身是比较麻烦的，好在关键的remove_left_recursion（）和remove_left_gene（）两个子函数提供了算法再加上本身理论课提供