编译原理课程设计-LL1文法分析器设计C++语言实现

1、集美大学计算机工程学院编译原理课程设计报告选题名称:LL(1)文法分析院(系)：计算机工程学院专业:计算机科学与技术班级:计算1412指导教师:付永冈【J学年学期:20162017学年第2学期2017年06月29日摘要：选题要求：根据某一文法编制调试LL(1)文法语法分分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。具体如下：1、对语法规则有明确的定义；2、编写的分析程序能够对给定文法进行正确的语法分析；3、对输入给定的文法，手工计算FIRSTFOLLOWS合和select集合，应能判断识别是否为给定文法的句子，并给出推导过程。4

2、、对输入给定的文法，由程序自动构造FIRSTFOLLOWS合。5、对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程。关键词：语法分析；FIRST集合；FOLLOWS合；分析表一、设计内容及要求(1) 基于PL/0语言，通过编程判断该文法是否为LL(1)文法;(2) 计算出文法的First()Follow()(3) 构造相应文法的预测分析表(4) 对某个输入句子进行语法分析、实现原理1. LL(1文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。就是要求描述语言的文法是无左递归的和无回溯的。根据LL(1)文法的定义，对于同一非终结符A的任意两个

3、产生式A:=a和A:=b，都要满足：SELECT(A=a)nSELECT(A:=b)=?(1) 文法的左递归当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法中对任一非终结符A有推导AA，则称该文法是左递归的。 直接左递归若文法中的某一产生式形如消除直接左递归的方法：设有产生式是关于非终结符对A引入一个新的非终结符A3A'A'fA'I& 间接左递归若文法中存在某一非终结符的。消除间接左递归的方法：左递归又可以分为直接左递归和间接左递归。AtAa，aV*，则称该文法是直接

4、左递归的。A的直接左递归：AtAa|3(a,3V*，且3不以A开头)A'，把上式改写为：A，使得AA至少需要两步推导，则称该文法是间接左递归方法一】采用代入法把间接左递归变成直接左递归。方法二】直接改写文法：设有文法G10S：StAaI3AtSy代入式，即可得到与原文法等价的文法(可以证明)：SSya|3式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：S3S'S'tYaS'|e2. 计算First集(1) 若XVt,贝UFirst(X)=X(2) 若XVn,且有产生式Xta,SEVt则First(X)=X(3) 若XEVn,且

5、有产生式,则First(X)=X(4) 若X,Y1,Y2，-,Yn都EVn,而由产生式Xt丫1YYn。当Yi,丫2,，Yi-i都能推导出e时，(其中Kiwn),则First(Yi)-£,First(Y2)-e,First(Y)都包含在First(X)中(5) 当中所有丫都能推导出e,(i=1,2,，n),则First(X)=First(Y1)UFirst(Y2)UFirst(Yn)Ue反复使用上述步骤直到每个符合的First集合不再增大为止。对文法中的每个AEVn，计算(1) 设S为文法的开始符合，把(2) 若ATaB3是一个产生式，e,则把Follow(A)也加入(B)中；3. 计

6、算Follow集Follw(A):#加入Follow(S)中；则把First(3)的非空元素加入Follow(B)中，如果3能推导出(3) 反复使用以上步骤直到每个非终结符号的Follow集不再增大为止。4. 预测分析方法预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成：预测分析程序；先进后出栈；预测分析表。预测分析程序的框图如下：MIX直是产生式吗V岀错V花'进栈，当前线结符送a若产生式为：实fm按逵序SUHX«K1A1r曰曰读入下_符号(XCVtCX=a?>+是否上托栈顶符号旗入養否+是目录1系统分析1.1.1 选题要求1.1.2 预期目标1.

7、2. 程序流程图1.2.1 总流程图1.2.2FIRST集和FOLLOW集2.2.3 预测分析表流程3.3. 代码编写33.1 检查左递归3.3.2 FIRST集合5.3.3FOLLOW集合6.3.4 分析表输出8.4. 程序调试1.0.5. 总结1.1.6. 指导教师评语1.2.7. 源码1.3.正文:1. 系统分析1.1选题要求根据某一文法编制调试LL(1)文法语法分分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。1.2预期目标构造LL(1)文法语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文

8、法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合(编译出错)，则输出错误信息。2. 程序流程图2.1.总流程图何输人出进行语汁5?flrst集合和follow集令T构造预测分析是J消除左递归甌飯右产主ib直囱時肓亦产牛式津加眸II，曲FOLLCTt無合i|i堆罰的吃LLDHFOIIM尉将£尉将的FiRSTSiiXFOLLOWS2.2.First集和Follow集的流程图23预测分析表流程：1P3. 代码编写3.1检查左递归：Parser&Parser:DelLeft(inti)intn=StrNum(contenti);ch

9、arc=RandChar();charz=contenti0;ints=0;for(intk=1;k<=n;k+)stringtmp=GetSub(k,contenti,'|');if(z=tmpO)s=1;if(s=0)return*this;cout<<"文法句"<<contenti<<"含有直接左递归,"while(1)if(Findchar(c,non)=-1)break;elsec=RandChar();cout<<"随机产生非终结符为："<<

10、c<<endl;non.append(1,c);stringtemp;temp+=z;temp+="->"stringnext;next+=c;next+="->"for(intk=1;k<=n;k+)stringt=GetSub(k,contenti,'|');if(z=t0)t.erase(0,1);t+=c;next+=t;next+='|'elseif(t="A")t.clear();t+=c;temp+=t;temp+='|：next+='A

11、9;temp.erase(temp.size()-1,1);contenti=temp;num=num+1;contentnum=end;for(intj=num-1;j>i;j-)contentj=contentj-1;contenti+1=next;return*this;3.2first集合stringParser:First(charx)stringch=""if(Findchar(x,ter)!=-1)ch.append(1,x);ch.append(1,'');elseif(Findchar(x,non)!=-1)inti=Findid(x

12、);if(i!=-1)stringq=contenti;unsignedintk=3;while(k<q.size()if(qk-1='|'|k=3)if(Findchar(qk,ter)!=-1|qk=z)ch.append(1,qk);ch.append(1,'');elseif(k=3|qk+1='|'|k=q.size()-1)ch+=First(qk);elsestringtemp=First(qk_1);if(Findchar('A',temp)!=-1)ch+=First(qk);k+;elsek+;retur

13、nch;3.3follow集合stringParser:Follow(charx)stringch;if(Findchar(x,non)!=-1)if(!Findid(x)ch+="$"ch+=''inti=0;while(i<num)stringq=contenti;unsignedintk=3;charc=contenti0;while(k<q.size()while(qk=x)if(k<q.size()-1&&qk+1!=T)stringtemp=Delchar('A',First(qk+1);if(c

14、h.find(temp)=string:npos)ch+=temp;if(Findchar('A',First(qk+1)!=-1)stringfollow_c=Follow(c);if(ch!=follow_c&&ch.find(follow_c)=std:string:npos)ch+=follow_c;elseif(k=q.size()-1)stringfollow_c=Follow(c);if(ch.find(follow_c)=std:string:npos)ch+=follow_c;k+;k+;i+;returnch;3.4分析表输出intParse

15、r:Analysis()stack.append("$");charchose;cout<<"是否输入分析串(yorn):"cin>>chose;while(chose='y')stack+=non0;cout<<"请输入分析串<退出(q)>:"cin»instack;if(instack="q")exit(0);if(instackinstack.size()-1!='$')instack+="$“;intk=1,

16、flag=0;charx=Top();charc=Ip();cout<<"分析栈t当前输入t动作"<<endl;while(x!='$')x=Top();c=Ip();cout<<stack<<"t"<<instack<<"tt"if(Findchar(x,ter)!=-1)if(Mate(x,c)k+;cout<<"匹配"<<c<<endl;elsecout<<T<<

17、k<<"出错(终结符不匹配)！"<<endl;flag=1;if(x=')')Pop();elseinstack.erase(0,1);k+;elseif(Findchar(x,non)!=-1)intidf=Findchar(x,non);intidz=Findchar(c,ter);if(idz=-1)idz=int(ter.size();stringtemp=tableidfidz;if(temp.empty()"<<endl;cout<<T<<k<<"出错(&

18、quot;<<c<<"不属于FIRST("<<x<<")!flag=1;instack.erase(0,1);k+;elsePop();if(temp!="人")Push(temp);cout<<x<<"->"<<temp<<endl;elsecout<<x<<"->"<<temp<<endl;elseif(x='$'&&

19、;c='$')if(flag=0)cout<<"正确"<<endl;elsecout<<"错误"<<endl;elsecout<<""<<k<<"出错（未能识别的字符）！"<<endl;flag=1;instack.erase(0,1);k+;4. 程序调试导入正确的文法:-*cppFiies(/LLiPr$er请輪入文件名:5ne文法内E->TXX->+TXlAT->FYFOLLOW(

20、E)=FOLLOW(T)=FOLLOH(X)-FOLLOW(F)=FOLLCM(Y)=稠灌分折義:)$)+$)$)Y-XF¥*F->(£)H结终袴：卄(1非绪纬符讣TKN非奠緬荷的FIRST集合FIRST(E)=(iFIR£T(T=(iFIRST(X)=+AFIRST(F)=(1FIRST(Y)*非线结符的FOLLX墓合<$*+ETXFTXFV+TX*FY符合文法的串虚香擒入井折睾（yorn）;y诸输入势新事u岂出山）八i*t+i分祈栈当的输入动作$EE->7X$XTT->F¥$XVFF->i$X¥1匹BdP$xv

21、*-i+i$V->*F¥$X¥F*Hiit匹配育$XYFi+i$IXYi1+ij匹配苗$X¥v->*$x+i$)(->+TX$XT*+1$匹記+$XTT*>F¥i$XYFF->1$加i$匹配T$XY$¥->*林*x->*h_$正为不符合文法的串|iB輪入分析事退出g）：i+ii*(i+T井析樸当前辅入朗作轩E->TX$XTT->FY$X¥Fi+iT*(i+iiF->ii+ii*(4+4$匹配屮$XYY->A$xX->+7I$XT+匹E+$XT2出帮(+TS?fir

22、st(t)!$XTT-?rY$XYFii*(i+i$F->i$X¥i匹配P、X¥G军属=J-FIRST(V)1$XYY->*FY!$xyf*匹配*$XVFF->(E)$XV)E(匹配（$XY)E1+1$E->TX$XY)XTi+i$T->FYl$XV)KVFi+i$F->t:$XV)X¥li+i$匹配节$XY)XY+i$XY)X+i$X->+TX$X¥)KT+汴£532+i$XY)XTT->F¥$X¥)X¥F1$F->1iX¥)X¥i齐匹配$

23、X¥)XV$Y->$X¥)X$x->*$X¥)$HjffitS（线绪祐平匹配）！XV$导入有左递归的文法:谄拚入文件名Hnl文法旬丁含有直接左谨E,Rt机产生非毘综荐为泪咬沬旬T>T-FFW直核左谨且，施机产生非线纯苻为臥文(MSft)；E->TBB->+TB|AT->FA|A*>*FA|*7曰H桂慢15：+*()-i非缩线符:E1FBA非蜒结持的F工腊T集合FlftST(E)=(I>FIRST(T)-(iFIRST(F)=(iFIRST(B)=+AFTRST(A)*非蛉结符的FOLLOWft合FOLLOW(E)=$

24、)FOLLQW(T)=+$)FQLLOW(FJ=*+$FOLLON(B)=$)FOLLOW(A)=+J)隼漏分析丢:4*()1$ETBTBTFAFAF(E)1B+TBAAAA*FAAA随舌射入分斩事¥打nE串分析:ii输入箱斯事I述岀：i*i+i当前辅入动作$EE->TB|$BTi*i+5$TTFA$BAFF->i$血i*4+4$匹配Vi$BA*i+i$A->*FA$BAF*i*i$匹配*(BAFF->i|BA1匹配f$BA+i$A->*$B+i$B->+TB$BT*+i$匹配+i$BT1$T->FA$BAFiSF->i$BA-i匹配&

25、#163;$BA$B$£芷确诒輪入分析卑或迟出q)>:q->CppFlles通过这次课程设计，对于LL1文法的认识有了进一步的提升，特别是对于FIRST集合和FOLLOW集合的求取，前面对于求取者两个集合理解还不是很好，经过这次课程设计，逐渐理解了求解的过程，并且懂得了如何通过代码，自动生成某LL1文法的FIRST集合和FOLLOW合，在刚开始做时，根本不知道求，通过网上查找资料，同学的请教，慢慢地懂得了如何做，最终正确地求岀FIRST集合和FOLLOV集合。并且能够使用者两个集合构建预测分析表以及对一段输入的串进行分析是否是该文法的串，岀错的地方能够做岀错处理，总的来说

26、，完成了课程设计要求的大部分内容，对于GUI的使用没有能够实现，暴露了自身在这方面的不足，需要在以后的学习和工作中进行沉入学习提高。在实现的功能中还有存在着，对于不含直接左递归的文法没法正确找出，提示错误。在判断是否是LL1文法上还有很大的不足，没法使用代码实现当两个FIRST有存在交集判断不是LL1文法的功能，这点要求自己对于代码的编程能力有着必要的提高。这次课程设计使用C+来实现LL1文法分析的功能，自己对于C+语言的使用有了很大的提高。特别是对于一些C+啲语法要求，有了很大的认识。但存在的不足还是比较多的。都是需要在今后的学习中认真总结，以使自己能更好地语言的使用，提升自身的技能。这次课

27、程设计总的收获是不少的。每一次的实践都是提高自身能力的机会，在今后的生活中，要抓住实践的机会，实践是验证真理最好的途径。对于一个计算机专业的学生来说，更应该注重实践的机会，只有实践多了，一些理论知识才能被自己正真的认识，不然，值懂理论，没有对于正确性进行验证，还是会有问题的，特别是计算机机器，总存在未知的错误，只有不断地探索，才能更好地去使用我们的工具。指导教师评语学号姓名班级选题名称序号评价内容权重（%）得分1考勤记录、学习态度、工作作风与表现。52自学情况：上网检索机时数、文献阅读情况（笔记）。103论文选题是否先进，是否具有前沿性或前瞻性。54成果验收：是否完成设计任务；能否运行、可操作

28、性如何等。205报告的格式规范程度、是否图文并茂、语言规范及流畅程度；主题是否鲜明、重心是否突出、论述是否充分、结论是否正确；是否提出了自己的独到见解。306文献引用是否合理、充分、真实。57答辩情况：自我陈述、回答问题的正确性、用语准确性、逻辑思维、是否具有独到见解等。25合计指导教师（签章）：年月日源码：LL1.h#include<iostream>#include<cstring>#include<cstdlib>#include<fstream>usingnamespacestd;classParserpublic:Parser();Pa

29、rser(constParser&);friendostream&operator<<(ostream&output,constParser&rs);friendistream&operator>>(istream&input,Parser&rs);intFindid(char);intCheck();stringCheckstr(string&);stringDelchar(char,string);intFindchar(char,string);intStrNum(conststring&);

30、charRandChar();stringGetSub(int,conststring&,char);Parser&DelLeft(int);stringFirst(char);stringFirst(conststring&);stringFollow(char);Parser&FirstAndFollow();Parser&CreateTable();Parser();charPop();intMate(char,char);charTop();charIp();Parser&Push(conststring&);intAnalysi

31、s();private:intnum;stringter,non,end,stack,instack;string*content;string*first;string*follow;string*table;LL1.cpp#include"LL1.h"Parser:Parser()content=newstring255;first=newstring255;follow=newstring255;table=newstring*255;Parser:Parser(constParser&rs)ter=rs.ter;non=rs.non;end=rs.end;n

32、um=rs.num;content=newstring255;first=newstring255;follow=newstring255;table=newstring*255;for(inti=0;i<=num;i+)contenti=rs.contenti;FirstAndFollow();CreateTable();ostream&operator<<(ostream&output,constParser&rs)output<<"文法内容(共"<<rs.num<<"条):&quo

33、t;<<endl;inti=0;while(i<rs.num)output<<rs.contenti+<<endl;output<<"结终符:"<<rs.ter<<endl;output<<"非结终符:"<<rs.non<<endl;cout<<"非终结符的FIRST集合"<<endl;for(unsignedintj=0;j<rs.non.size();j+)cout<<&quo

34、t;FIRST("<<rs.nonj<<")="<<rs.firstj<<"t"<<endl;cout<<"非终结符的FOLLOW集合"<<endl;for(unsignedintj=0;j<rs.non.size();j+)cout<<"FOLLOW("<<rs.nonj<<")="<<rs.followj<<"t"

35、<<endl;output<<"预测分析表:"<<endl<<"t"for(unsignedintj=0;j<rs.ter.size();j+)output<<rs.terj<<"t"output<<"$"<<endl;for(unsignedintj=0;j<rs.non.size();j+)output<<rs.nonj<<"t"for(unsignedintk

36、=0;k<=rs.ter.size();k+)cout<<rs.tablejk<<"t"output<<endl;returnoutput;istream&operator>>(istream&input,Parser&rs)unsignedintj=0;charfilename255;cout<<"请输入文件名:"input>>filename;ifstreaminfile(filename,ios:in);if(!infile)cout<<

37、;"无法打开文件！"<<endl;exit(0);while(1)unsignedinti=0;infile>>rs.end;rs.contentj+=rs.end;if(infile.eof()break;while(i<rs.end.size()if(rs.endi='|'|rs.endi='A');elseif(i=1|i=2)i+;elseif(rs.endi>='A'&&rs.endi<='Z')if(std:string:npos=rs.no

38、n.find(rs.endi)rs.non.append(1,rs.endi);elseif(std:string:npos=rs.ter.find(rs.endi)rs.ter.append(1,rs.endi);i+;rs.num=j-1;if(rs.Check()=0)exit(0);rs.FirstAndFollow();rs.CreateTable();returninput;intParser:Findid(chara)inti=0;while(i<num)if(contenti0=a)returni;i+;return-1;charParser:RandChar()swit

39、ch(rand()%3)case0:return'A'case1:return'B'case2:return'C'case3:return'D'return'D'intParser:Check()unsignedintj=0;inti=0;while(i<num)if(contenti.size()<=3)cout<<"文法句"<<contenti<<"长度不对!"<<endl;return0;if(contenti

40、1!='-'|contenti2!='>')cout<<"文法句"<<contenti<<"未来使用推导符"->"!"<<endl;return0;intn=StrNum(contenti);ints=0;charz=contenti0;intm=0;for(intk=1;k<=n;k+)stringtmp=GetSub(k,contenti,'|');if(z=tmp0)s=1;m+;if(m=n)"<&

41、lt;endl;cout<<"文法句"<<contenti<<"将形成无穷推导！return0;if(s=1)DelLeft(i);i+;return1;Parser&Parser:DelLeft(inti)intn=StrNum(contenti);charc=RandChar();charz=contenti0;ints=0;for(intk=1;k<=n;k+)stringtmp=GetSub(k,contenti,'|');if(z=tmp0)s=1;if(s=0)return*this;c

42、out<<"文法句"<<contenti<<"含有直接左递归,"while(1)if(Findchar(c,non)=-1)break;elsec=RandChar();cout<<"随机产生非终结符为:"<<c<<endl;non.append(1,c);stringtemp;temp+=z;temp+="->"stringnext;next+=c;next+="->"for(intk=1;k<=n;k+

43、)stringt=GetSub(k,contenti,'|');if(z=t0)t.erase(0,1);t+=c;next+=t;next+='|'elseif(t="A")t.clear();t+=c;temp+=t;temp+='|'next+='A：temp.erase(temp.size()-1,1);contenti=temp;num=num+1;contentnum=end;for(intj=num-1;j>i;j-)contentj=contentj-1;contenti+1=next;retur

44、n*this;stringParser:Checkstr(string&a)unsignedinti=0,j=0;for(;i<a.size();i+)for(j=i+1;j<a.size();j+)if(ai=aj)a.erase(j,1);returna;stringParser:Delchar(charx,stringa)intj,i=int(a.size();for(j=0;j<i;j+)if(aj=x)a.erase(j,1);returna;intParser:Findchar(charx,stringa)unsignedinti=0;while(i<

45、;a.size()if(ai=x)returni;i+;return-1;stringParser:GetSub(inti,conststring&a,charc='|')stringch;intj255;intn=1;j0=2;if(i>=int(a.size()returnch;for(unsignedintk=3;k<a.size();k+)if(ak=c)jn+=k;for(unsignedintk=ji-1+1;k<a.size();k+)if(ak=c)break;elseif(std:string:npos=ch.find(ak)ch.a

46、ppend(1,ak);returnch;intParser:StrNum(conststring&a)intn=0;for(unsignedinti=3;i<a.size();i+)if(ai='|')n+;returnn+1;stringParser:First(charx)stringch=""if(Findchar(x,ter)!=-1)ch.append(1,x);ch.append(1,'');elseif(Findchar(x,non)!=-1)inti=Findid(x);if(i!=-1)stringq=con

47、tenti;unsignedintk=3;while(k<q.size()if(qk-1='|'|k=3)if(Findchar(qk,ter)!=-1|qk='Tch.append(1,qk);ch.append(1,'');elseif(k=3|qk+1='|'|k=q.size()-1)ch+=First(qk);elsestringtemp=First(qk-1);if(Findchar('A',temp)!=-1)ch+=First(qk);k+;elsek+;returnch;stringParser:F

48、irst(conststring&a)returnFirst(a0);stringParser:Follow(charx)stringch;if(Findchar(x,non)!=-1)if(!Findid(x)ch+="$"ch+=''inti=0;while(i<num)stringq=contenti;unsignedintk=3;charc=contenti0;while(k<q.size()while(qk=x)if(k<q.size()-1&&qk+1!='|')stringtemp=De

49、lchar('A',First(qk+1);if(ch.find(temp)=string:npos)ch+=temp;if(FindcharQ',First(qk+1)!=-1)stringfollow_c=Follow(c);if(ch!=follow_c&&ch.find(follow_c)=std:string:npos)ch+=follow_c;elseif(k=q.size()-1)stringfollow_c=Follow(c);if(ch.find(follow_c)=std:string:npos)ch+=follow_c;k+;k+;

50、i+;returnch;Parser&Parser:FirstAndFollow()unsignedinti=0;while(i<non.size()firsti=First(noni);followi=Follow(noni);i+;return*this;Parser&Parser:CreateTable()for(unsignedinti=0;i<=non.size();i+)tablei=newstring255;for(unsignedinti=0;i<non.size();i+)stringtemp=contenti;intw=Findchar(t

51、emp0,this->non);intn=StrNum(temp);for(intk=1;k<=n;k+)stringtmp=GetSub(k,temp);stringfir=First(tmp);for(unsignedintj=0;j<fir.size();j+)intidz=Findchar(firj,ter);if(idz!=-1)tablewidz=tmp;if(FindcharQ',fir)!=-1|tmp0='A')stringfol=Follow(temp0);for(unsignedintj=0;j<fol.size();j+)

52、intz=Findchar(folj,ter);if(z=-1)z=int(ter.size();tablewz=tmp;return*this;Parser:Parser()deletecontent;deletefirst;deletefollow;deletetable;charParser:Pop()charx=stackstack.size()-1;stack.erase(stack.size()-1,1);returnx;intParser:Mate(charx,charip)if(Findchar(x,ter)!=-1)if(x=ip)Pop();instack.erase(0,1);return1;elsereturn0;return0;charParser:Top()returnstackstack.size(