合肥工业大学编译原理LL自上而下文法分析

1、合肥工业大学计算机与信息学院计算机系2013级编译原理课程设计报告姓 名：马骏专业年级：信息安全13-1学 号:2013211869提交时间：2016年07月一、实验题目自上而下的 LL(1) 文法分析二、实验目的了解掌握自上而下的 LL (1 )文法分析过程。二、实验内容与要求 从语法分析树构造句型所有的推导的程序实现，接受用户任意输入的一个句型的语法分析 树(其表示存于指定文件中) ，生成该语法分析树中包含的该句型的所有推导(显示输出)。构造一程序，实现教材P78的FIRST(X集合的构造算法。对任一给定的文法G,程序输出所有非终结符 P的FIRST(P。构造一程序，实现教材P78的FIR

2、ST(X集合的构造算法。对任一给定的文法 G,程序输出所有非终结符P的FIRST(P。在此基础上，构造一程序，实现教材P79的FOLLOW(A集合的构造算法。对任一给定的文法G,程序输出所有非终结符A的FOLLOW (A)。对于给定的一个LL(1)文法，假定所有非终结符号P的集合FIRST(P和集合FOLLOW(P都已知，构造其预测分析表(实现教材P79给出的预测分析表构造算法)。对教材 P.79 给出的例 4.7 构造出预测分析表。程序显示输出预测分析表或输出到指定文件中。首先实现集合FIRST(X构造算法和集合FOLLOW(A构造算法，再实现教材 P79给出的预测 分析表构造算法。程序显示

3、输出预测分析表或输出到指定文件中。对文法按教材 P76表4.1构造出G的预测分析程序，程序显示输出如P.78那样的匹配过程。三、实验环境与工具操作系统： Windows 7开发语言： C+四、开发过程1 ) 字符要求： 你的程序必须能够根据以下字符来处理语法：-终端字符：字母，数字，符号例如“+”，“ 一 ”，；- 非终端字母表中的大写字母。符号“ =”，“|”和“ #” (替换“ £ ”，因为它更容易输入到文本文件)被保留用于语 法的描述中，因此不能被用作终端。2) 初始状态您的程序通过读取一个文件中的“文本”格式开始。 这个文件的结构可以随意构建，不做要求，但建议做成简单的<

4、;simple>。例如，程序描述以下语句：E = E + T |T T = T * F |F F =( E) | 0 |1 在这种情况，我们可以很容易确定E, T和F是非终端，而符号“(” ,“)”，“*”和“ +”和数字“ 0”和“ 1 ”是在终端。第一个非终端(第一衍生物)被认为是语法的公理。结果必须存储在内存中，是一个您所选择的数据结构。 然后，使用一个函数再取出数据, 存储在内存中并屏幕上显示（以你选择的格式）。Structures de donnees frep胆sEntatiDn e电mol呻 文本结构(在 内存中)Traitements过程TGrammare rnitial

5、cma grartun.d Lre . txLE-E+T|TT=T*F|FF=(E)：.Di&Traces d'execution靑打卡门于尸£ JriiH "；厂八门!|显示在屏幕E E+TTFF (E)0在上面的图中，并在下文中，右列显示的程序的执行的过程， 并左栏表示中使用的数据结构。 这些都是明显的例子。你可以使用任何你想要的格式。3 ）消除传递判断你的程序是否包含一个传递关系或没有。如果包含，递归应该被消除。没有传递关系的语句指向自己的判断：您可以创建一个新的数据结构语句来表示其中传递关系已被删除，这有利于进-步加工。在这种情况下，如果语法不包含判

6、定递归的语句，程序当然必须使用第二数据结 构的副本。“第一个”和“其后”的集合3）计算“ first集”和“ follow集”的集合 为了产生一个分析器，你现在必须计算，每个分支, 结果被存储在数据结构，再次“你的选择。”然后，这些集合被显示在屏幕上EnsemDies P / 5图注释：Calcul des ensembles ? premiers ? et ? suivants ?计算 第一个 和 其后 的集合Affichage des ensembles 显示集合 premiers 第一个 suivants 其后4）分析表的结构具有非递归语法以及“第一个”和“其后”的集合，你的程序现在可以

7、建立预测分析表。 结果以表的形式显示在屏幕上。Table d'andlyseConstfuetiiDnde Ilatable d'anlyseE|E->TA|T|叭A.)Affichage de 方 table d'analyseBja分析表的结构图注释：Con struction de la table d'显示a分析表table d ' an al分析表 Affichage de la table d输入字符串的分析最后一步：你的程序读取输入（键盘）的表达和分析。指出，结果是否符合语法。 你要尽可能准确的鉴定结果：定位错误在没有辨认出表达式的情

8、况下。其次，你的程序必须能够完成对输入多个字符串作为输入，不要忘记重新启动你的程序。Affichage selon le 显示分析结果 resultat de I'analyse五、程序实现 magrarrmaira dI 3tWl>jfl(L 'M+T TT=T*j rF-(E)if ilv叶否命 性丄诵归?XMM耳9(其.VMX M N-MKM4 MMK：l-TAFBE CiT ci F CiA it；+ *沖,i- j弔l|比wwhfiH*y hum;x humwaratiMMSeftn fesi军决左递归 WXX MXXXXXXXXXXX XXXXXXXXXXXX

9、XyE TA T PRF <E>n *TfittR *FRttXxMXXXXXXXMXXf ir S t XXXXXX XXX XXX XXXf XXXX X X X*W)O<X E <ir <ib *n*£ olio w宾 XX XXX XXX XM XX XXX XX XXX XXX XM XX XXE $r 3F $«Ob $B $巧wxxxx in ittable*rieal begin :LL<1>tableE4-E：*E：<E：>E：iE：$rT：*T：<T：>T：ir：$FF：*F：<F：

10、>F：iF：$A:*A：<A:>A:iA:$B4-B：*B：<B：>B：iB：$Fmaltable；MS<；i；$t' e >*>*o >*!er>*ot*!E->Tfi!E->TASerroi*r 'error'error!T->FB.error:T->FBien*or1 'error'error!F-XE> error:F->i errorerrorerror!A->nerror5A->B i!B->*FBSerroriert*orii

11、1 1 1 4 、2yy2y2wjwjyjxy2yy2yyyQD <<XyS Ocontinuo? y/n J：5please enter：<i«i>*<i*i><i«i>*<i*i><- natch 3ucc33cd?岭号找输入串产生式$EE->TA$mT->FDABF$AD>E<F-XE>iAD>E<E->TA$AD>ftT<T->FD$AD>ftDF<P>i5AB>ftBl<$AB>ftB<1B-

12、>*FB$AB>ftBF*<1$AB>ABF<1*F->i$AB>ftBl<1*$AB>ftB<1*1B->tt$AB>ft<1*1R->U$AB><1*1$AB<1*1>B->tt$A<i*i>R->*IA$AT*<i*i>$AIT->FB$ABFF-XE>$AB>H<$AB>EE->1A$AB>UTT->FB$AB>ftBEF->i$AB>DBi$AB>AB<i*i>

13、;*<iB->tt$AB>ft<i*i>*<iA->+TA$AB>ftT*<i*i>*<i$AB>ftTT->FB$AB>ftBFF->i$AB>ftBi$AB>ftBB->tt$AB>ftA->tt$AB><i*i>*<i*i$AB<i*i>Ki*i>B->tt$A<i*i>Ki*i> <i*i>Ki*i> analize successed /n：A->ttcontinue? yIc

14、on LInuc?1 yZri iyplease enter：(i<一 match suiccsEed!输入串产生式$EE->TftSATT->FBCftBFF-XE>&AB>EcE->Tft<T->FB&ftB>AEFF-XE>$AB>AB>E(<AB>AB>E«E->Tfi$AB>AB>ATT->FBF-XE>««<E->Tft<(<T->FB«<F->i$AB>AB&

15、gt;AB>ABi$AB>AB>AB>ABB->i$AD>nB>AD>fl«<ift->*<(<i(<<-error :no natcti unendsin六、程序代码/*不支持规则源文件中有空格注意使用#表示空产生式使用$表示结束符#*/#in clude<iostream>#in clude<stri ng>#in clude<fstream>#in clude<wi ndows.h>using n amespace std;const char*

16、sourcefile="ma_grammaira.txt" / 定义源文件 /con st i nt max=100;#defi ne max 100class sig npublic:sig n()sig n(i nt check,char fu)if(check!=0&&check!=1)/ 符号属性只有 0 和 1cout<<"error sig n creat!"<<e ndl;elseide ntity=check;/设置符号属性id=fu;/设置非终结符符号funnumber=0;/ 设置符号规则数为

17、0 firstnumber=0;follownumber=0;void add(string sl)/ 添加产生规则funfunnumber=sl; funnumber+;void pop(int q)/ 删除某一规则if(q>=funnumber|q<0)cout<<"error wrong delete fun in sign!" return;for(int x=q;x<funnumber-1;x+) funx=funx+1;funnumber-;void pop_first(char q)/ 从 first 集删除某一节点for(int

18、 x=0;x<firstnumber;x+)if(firstx=q)for(int y=x;y<firstnumber-1;y+) firsty=firsty+1;firstnumber-;x-;/ 为了接着上次检查点void pop_follow(char q)/ 从 first 集删除某一节点for(int x=0;x<follownumber;x+)if(followx=q)for(int y=x;y<follownumber-1;y+) followy=followy+1;follownumber-;void add_first(char q)/ 向 first

19、 添加元素for(int x=0;x<firstnumber;x+)if(firstx=q)return; firstfirstnumber=q; firstnumber+;void add_follow(char q)/ 向 follow 添加元素for(int x=0;x<follownumber;x+)if(followx=q)return; followfollownumber=q; follownumber+;int identity; / 符号属性 0为非终结符 1为终结符 char id; / 符号 string funmax;/ 符号产生规则int funnumbe

20、r; / 符号产生规则数量 char firstmax;/first 集 int firstnumber;char followmax;/follow 集int follownumber;class cell / 分析表的单元格结构public: char cell_unendsign;/ 终结符char cell_endsign;/ 非终结符 string cell_fun;/ 产生式;cell tablemaxmax; / 分析表数据结构 int table_unend_number;/ 非终结符数 int table_end_number;/ 终结符数sign unendsignmax;

21、/ 非终结点集合 int unendsignnumber=0;sign endsignmax;/ 终结点集合int endsignnumber=0;void readsource(const char*sf) / 读取源文件 ma_grammaira.txtint x;unendsignnumber=0; endsignnumber=0;ifstream ifs;ifs.open(sourcefile);char bufmax;for(x=0;x<max;x+)bufx='0' while(ifs.getline(buf,sizeof(buf) / 一行一行读取unend

22、signunendsignnumber=sign(0,buf0);unendsignnumber+;string rule;for(int x=2;x<max;x+)if(bufx='0')break;if(bufx='|')/ cout<<rule<<endl;unendsignunendsignnumber-1.fununendsignunendsignnumber-1.funnumber=rule;/ 则放在每个非终结符实例中unendsignunendsignnumber-1.funnumber+;rule="&q

23、uot;continue;rule+=bufx;char kk=bufx; unendsignunendsignnumber-1.fununendsignunendsignnumber-1.funnumber=rule; unendsignunendsignnumber-1.funnumber+;/ cout<<rule<<endl;void addendsign(char sg) / 添加终结符for(int x=0;x<endsignnumber;x+)if(endsignx.id=sg) return; endsignendsignnumber.id=sg;

24、 endsignendsignnumber.identity=1; endsignnumber+;void dealend()/ 由非终结符产生式得到终结符for(int x=0;x<unendsignnumber;x+)for(int y=0;y<unendsignx.funnumber;y+)for(int z=0;z<unendsignx.funy.length();z+)到 Z 为非终结符char kk=unendsignx.funyz; if(int(kk)>=65&&int(kk)<=90)continue; /A else adden

25、dsign(kk);bool exit_endsign(char sg) / 终结符表是否有 sgint x; for(x=0;x<endsignnumber;x+) if(endsignx.id=sg)return true;return false;bool exit_unendsign(char sg) / 非终结符表是否有 sgfor(int x=0;x<unendsignnumber;x+)if(unendsignx.id=sg)return true;return false;sign get_unendsign(char sg)/ 从非终结符表中得到非终结符为 sg

26、的实例for(int x=0;x<unendsignnumber;x+)if(unendsignx.id=sg)return unendsignx;cout<<"error get no unend sign!"<<endl;sign er;return er;int get_unendsign_number(char sg)/ 从非终结符表中得到非终结符为sg 的下标for(int x=0;x<unendsignnumber;x+)if(unendsignx.id=sg)return x;cout<<"error

27、get no unend sign!"<<endl;return 0;int get_endsign_number(char sg)/ 从非终结符表中得到终结符为 sg 的下标for(int x=0;x<endsignnumber;x+)if(endsignx.id=sg)return x;cout<<"error get no end sign!"<<endl;return 0;sgbool rule_first_check(sign m_sign,char sg)/ 查看非终结符实例 m_sign 产生式首是否为int

28、 y;for(y=0;y<m_sign.funnumber;y+)if(m_sign.funy0=sg) return true;int check=0; for(y=0;y<m_sign.funnumber;y+) if(exit_unendsign(m_sign.funy0) sign msg=get_unendsign(m_sign.funy0); if(rule_first_check(msg,sg)check=1;break;if(check)return true;else return false;false 表示bool check_L_recursion()/ 检

29、查是否含有直接左递归和传递左递归 true 表示有 没有int x,y;for(x=0;x<unendsignnumber;x+) / 检查直接左递归 for(y=0;y<unendsignx.funnumber;y+) if(unendsignx.funy0=unendsignx.id) return true;for(x=0;x<unendsignnumber;x+) / 检查传递左递归 if(rule_first_check(unendsignx,unendsignx.id) return true;return false;sign new_unendsign() /

30、 创建一个新非终结符 即用于规则 p=p 需要 p'char a=65;while(1)if(a>90|unendsignnumber>26) cout<<"error no more size for unend sign!"<<endl; break;int check=1;for(int x=0;x<unendsignnumber;x+)if(unendsignx.id=a)a+; check=0; break;if(check) unendsignunendsignnumber.id=a; unendsignunen

31、dsignnumber.identity=0; unendsignnumber+;break;return unendsignunendsignnumber-1;void pop_unendsign(char sg) / 删除某一非终结符for(int x=0;x<unendsignnumber;x+)if(unendsignx.id=sg)for(int y=x;y<unendsignnumber-1;y+)unendsigny=unendsigny+1;unendsignnumber-;return;cout<<"error no unend sign f

32、or pop"<<endl; return;void deal_direct_L_recursion(int thisnumber) / 消除 unendsignthisnumber 的直接左递归 在 deal_L_total_recursion() 中调用int i;if(!check_L_recursion()return;int check=0;for(i=0;i<unendsignthisnumber.funnumber;i+) / 先检查 unendsignthisnumber 是否 存在 直接左递归if(unendsignthisnumber.funi0

33、=unendsignthisnumber.id)check=1;break;if(check)new_unendsign();增加int kp=unendsignnumber-1;for(i=0;i<unendsignthisnumber.funnumber;i+)/ 增加 p' 的规则 a0p'|a1p'|#p->b0p'|b1p' if(unendsignthisnumber.funi0=unendsignthisnumber.id) string ss=""for(int x=1;x<unendsignthis

34、number.funi.length();x+) ss+=unendsignthisnumber.funix;if(ss="#")cout<<"error can't deal whith P->P#"<<endl;return; ss=ss+unendsignkp.id; unendsignkp.add(ss);else if(unendsignthisnumber.funi!="#") unendsignthisnumber.funi=unendsignthisnumber.funi+unen

35、dsignkp.id;if(unendsignthisnumber.funi="#")string ss="" ss+=unendsignkp.id; unendsignthisnumber.add(ss);unendsignkp.add("#");/ 为 p' 增加 p-># 的规则 for(i=0;i<unendsignthisnumber.funnumber;i+) / 删除 p->p. 的产生式 if(unendsignthisnumber.funi0=unendsignthisnumber.id)

36、unendsignthisnumber.pop(i); i=0;void deal_L_total_recursion()/ 消除所有左递归int i,j,t,k,qq;for(i=0;i<unendsignnumber;i+)for(j=0;j<i;j+)for( t=0;t<unendsigni.funnumber;t+)if(unendsigni.funt0=unendsignj.id)string say=""for( k=1;k<unendsigni.funt.length();k+)say+=unendsigni.funtk;unends

37、igni.pop(t);for( qq=0;qq<unendsignj.funnumber;qq+)string sp=unendsignj.funqq; if(sp!="#") sp+=say;unendsigni.add(sp);deal_direct_L_recursion(i); / 消除 Pi 的直接左递归void deal_first_club()/ 求各节点的 first 集int x,t;for(x=0;x<endsignnumber;x+)endsignx.add_first(endsignx.id);int check=1;while(che

38、ck)check=0;for(x=0;x<unendsignnumber;x+)int oldnumber=unendsignx.firstnumber; / 用于记录 first 集是否再增大 for(t=0;t<unendsignx.funnumber;t+)unendsignx.add_first(unendsignx.funt0);for(t=0;t<unendsignx.firstnumber;t+)if(exit_unendsign(unendsignx.firstt)int kp=get_unendsign_number(unendsignx.firstt);f

39、or(int q=0;q<unendsignkp.firstnumber;q+)if(unendsignkp.firstq!='#') unendsignx.add_first(unendsignkp.firstq);if(unendsignx.firstnumber!=oldnumber)check=1;check=1;while(check)check=0;for(x=0;x<unendsignnumber;x+) / 判断 first 是否应包含 #for(int y=0;y<unendsignx.funnumber;y+)int overcheck=1

40、;for(int t=0;t<unendsignx.funy.length();t+) if(exit_unendsign(unendsignx.funyt)continue; elseovercheck=0;break;if(overcheck)/ 如果存在 P->ABCDint thischeck=1;for(int t=0;t<unendsignx.funy.length();t+)int oop=get_unendsign_number(unendsignx.funyt);int incheck=0;for(int z=0;z<unendsignoop.firs

41、tnumber;z+)if(unendsignoop.firstz='#')incheck=1;break;if(incheck) continue;elsethischeck=0;break;if(thischeck)int sp=unendsignx.firstnumber;unendsignx.add_first('#');if(sp!=unendsignx.firstnumber) check=1;for(x=0;x<unendsignnumber;x+)/ 消除 first 集中的非终结符for(int y=0;y<unendsignx.f

42、irstnumber;y+)if(exit_unendsign(unendsignx.firsty)unendsignx.pop_first(unendsignx.firsty);y-;void deal_follow_club() / 求每个非终结符的 follow 集int x,y,z,t;unendsign0.add_follow('$');/ 在开始符号的 follow 集中添加结束符 $ int check=1;while(check) / 循环至 follow 集不在增大check=0;for(x=0;x<unendsignnumber;x+)for( y=0

43、;y<unendsignx.funnumber;y+)for( z=0;z<unendsignx.funy.length();z+)if(exit_unendsign(unendsignx.funyz)&&z<unendsignx.funy.length()-1)/p->.A kp=get_unendsign_number(unendsignx.funyz);int ss=unendsignkp.follownumber;if(unendsignx.funyz+1!='#')unendsignkp.add_follow(unen

44、dsignx.funyz+1); if(unendsignkp.follownumber!=ss)check=1;if(z=unendsignx.funy.length()-1&&exit_unendsign(unendsignx.funyz) /p->Bint kp=get_unendsign_number(unendsignx.funyz);for(t=0;t<unendsignx.follownumber;t+)int ssp=unendsignkp.follownumber; unendsignkp.add_follow(unendsignx.followt

45、); if(unendsignkp.follownumber!=ssp)check=1;if(exit_unendsign(unendsignx.funyz)&&z<unendsignx.funy.length()-1)int thischeck=1; / 判断 p->SABC 其中 #在 ABC 的 first 集中for(int i=z+1;i<unendsignx.funy.length();i+)if(exit_unendsign(unendsignx.funyi)int thisthischeck=0;int kp=get_unendsign_num

46、ber(unendsignx.funyi); for(int pp=0;pp<unendsignkp.firstnumber;pp+) if(unendsignkp.firstpp='#')thisthischeck=1; break;if(thisthischeck)continue;elsethischeck=0;break;thischeck=0;break;if(thischeck)int kp=get_unendsign_number(unendsignx.funyz);for(t=0;t<unendsignx.follownumber;t+)int ss

47、p=unendsignkp.follownumber;unendsignkp.add_follow(unendsignx.followt); if(unendsignkp.follownumber!=ssp) check=1;for(x=0;x<unendsignnumber;x+) / 非终结点在 follow 集则要把 其 first 集除 #放入 follow 集for(y=0;y<unendsignx.follownumber;y+)if(exit_unendsign(unendsignx.followy)int kp=get_unendsign_number(unends

48、ignx.followy);for(t=0;t<unendsignkp.firstnumber;t+)if(unendsignkp.firstt='#')continue;elseint oop=unendsignx.follownumber;unendsignx.add_follow(unendsignkp.firstt); if(unendsignx.follownumber!=oop)check=1;for(x=0;x<unendsignnumber;x+) / 删除 follow 集中的非终结点for(int y=0;y<unendsignx.foll

49、ownumber;y+) if(exit_unendsign(unendsignx.followy) unendsignx.pop_follow(unendsignx.followy); y-;void init_LL_table() / 分析表初始化int x,y;addendsign('$'); table_unend_number=0;table_end_number=0; for(x=0;x<unendsignnumber;x+) for(y=0;y<endsignnumber;y+) tablexy.cell_endsign=endsigny.id; ta

50、blexy.cell_unendsign=unendsignx.id;cout<<"init table begin:"<<endl; for(x=0;x<unendsignnumber;x+)for(y=0;y<endsignnumber;y+)cout<<tablexy.cell_unendsign<<":"<<tablexy.cell_endsign<<"cout<<endl;void deal_LL_table()产生LL文法分析表int x

51、,j,y,t; init_LL_table();for(x=0;x<unendsignnumber;x+)for(y=0;y<unendsignx.funnumber;y+)int check=1;int i=0; while(check) /P->A#一直属于 Aif(i=unendsignx.funy.length()break;check=0;if(exit_unendsign(unendsignx.funyi) /P->A 将 A 的 first 集的终结符 单元格 赋值 P->Aint kp=get_unendsign_number(unendsignx

52、.funyi); for(t=0;t<unendsignkp.firstnumber;t+) if(unendsignkp.firstt='#')check=1;i+;elseif(unendsignkp.firstt!='#')j=get_endsign_number(unendsignkp.firstt); tablexj.cell_fun=unendsignx.funy;else /p->a a 是非终结符if(unendsignx.funyi!='#') j=get_endsign_number(unendsignx.funy

53、i); tablexj.cell_fun=unendsignx.funy;if(unendsignx.funyi='#'&&i=0)check=1;break;if(check) /P->A 如果 #属于 Afor(t=0;t<unendsignx.follownumber;t+)if(unendsignx.followt!='#')j=get_endsign_number(unendsignx.followt);tablexj.cell_fun=unendsignx.funy;for(x=0;x<unendsignnumber

54、;x+) / 没有产生式的单元格标记为错误for(y=0;y<endsignnumber;y+)if(tablexy.cell_fun.length()>0)continue;else tablexy.cell_fun="error"void analizeLL_1() / 预测分析程序string putin;char stackmax;int stacknumber=0;stackstacknumber='$'stacknumber+;stackstacknumber=unendsign0.id;stacknumber+;cout<<"please enter:"cin>>putin;int x;for(x=0;x<putin.lengt