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

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

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

3、，对于同一非终结符 A的任意两 个产生式 A:=a 和 A:=b，都要满足：SELECT： =a) n SELECT(A:=b)=?( 1)文法的左递归 当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之 中。所以采用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法 中对任一非终结符A有推导A A，则称该文法是左递归的。A-Aa,a V*，则称该文法是直接左递归的。A的直接左递归：A A a | p (a V*，且p不以A左递归又可以分为直接左递归和间接左递归。 直接左递归 若文法中的某一产生式形如 消除直接左递归的方法： 设有产生式是关于非终结符开头)A ,

4、把上式改写为:对A引入一个新的非终结符A,使得A A至少需要两步推导，则称该文法是间接Ap A， A，Ta AT £ 间接左递归 若文法中存在某一非终结符 左递归的。消除间接左递归的方法： 【方法一】采用代入法把间接左递归变成直接左递归。【方法二】直接改写文法：设有文法 G10S：S A a | p A Sy因为S Aa Sya,所以S是一个间接递归的非终结符。为了消除这种间接左递归， 将式代入式，即可得到与原文法等价的文法(可以证明)： S S Ya | p(3)式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行 改写后可得文法：S-P S'S'

5、Ya S | £2.计算 First 集若 X Vt,贝U First(X)=X(2) 若 X Vn,且有产生式 X a;a Vt则 First(X)=X(3) 若 X Vn,且有产生式 X£ ；则 First(X)=X(4) 若 X,Yi,Y2,，Yn都VN,而由产生式XY1Y2Yn。当Yi,Y2,，Y-1都能推导出 £ 时，(其中 Ki<n)，则 First(Y)- £ hFirsMY)-" ,FirsMY)都包含在 First(X) 中当中所有 Y都能推导出 £, (i=1, 2,，n),贝U First(X)=First

6、(Y) U First(Y>) UFirst(Yi)U £反复使用上述步骤直到每个符合的First集合不再增大为止。3. 计算 Follow 集对文法中的每个A Vn,计算Follw(A):(1)设S为文法的开始符合，把#加入Follow(S冲；若Aa BP是一个产生式，则把 First(p )的非空元素加入Follow(B)中，如果P 能推导出£，则把Follow(A)也加入(B)中；(3)反复使用以上步骤直到每个非终结符号的Follow集不再增大为止。4. 预测分析方法预测分析方法是自顶向下分析的另一种方法， 一个预测分析器是由三个部分组成： 预测分析程序；先进后

7、出栈；预测分析表。预测分析程序的框图如下： 目录1 系统分析选题要求预期目标2. 程序流程图 1总流程图 1集和 Follow 集 2预测分析表流程 33. 代码编写 3检查左递归 3集合 5集合 6分析表输出 84. 程序调试 105. 总结 116. 指导教师评语 127. 源码 13正文:1. 系统分析选题要求根据某一文法编制调试LL(1)文法语法分分析程序，以便对任意输入的符号串进 行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。预期目标构造LL(1)文法语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并

8、按照预测分析算法对输入串进行语 法分析，判别程序是否符合已知的语法规则，如果不符合(编译出错)，则输出错误信 息。2. 程序流程图2. 1.总流程图集和Follow集的流程图.预测分析表流程：3. 代码编写检查左递归:P arser&Parser:DelLe1t(i nti) intn=StrNum (con te nti);charc=Ra ndChar();charz=c onten ti0;in ts=0;for(i ntk=1;k<=n ;k+) stri ngtm p=GetSub(k,co nten ti，T);if(z=t mp 0)s=1;if(s=0)retur

9、n*this;cout<<"文法句"<<contenti<<"含有直接左递归,"while(1) if(Fin dchar(c, non)=-1)break;elsec=Ra ndChar();cout<<"随机产生非终结符为:"<<c<<endl;(1,c);stri ngte mp;temp+=z;temp+="->"； stri ngn ext;n ext+=c;n ext+="->"for(i ntk=1

10、;k<=n ;k+) strin gt=GetSub(k,co nte nti,T);if(z=t0)(0,1);t+=c;n ext+=t;n ext+=T;elseif(t= = "A")()t+=c;temp+=t;temp+=T；n ext+-A'()-1,1)；con te nti=te mp;num=nu m+1;conten t num =e nd;for(i ntj=nu m-1;j>i;j-)conten tj=c onten tj-1;conten ti+1=n ext;return*this;集合stri ngP arser:Fir

11、st(charx)stri ngch=""if(Fi ndchar(x,ter)!=-1)(1,x);(1,'');elseif(Fi ndchar(x, non )!=-1)in ti=Fi ndid(x);if(i!=-1)stri ngq=c onten ti;un sig nedin tk=3;while(k<()if(qk-1=T|k=3)if(Fi ndchar(qk,ter)!=-1|qk='A')(1，qk)；(1，'')；elseif(k=3|qk+1=T|k=()-1)ch+=First(qk);el

12、sestri ngte mp=First(qk-1);if(Fi ndchar('A',tem p)!=-1)ch+=First(qk);k+;elsek+;returnch;集合stri ngP arser:Follow(charx)stri ngch;if(Fin dchar(x ,non )!=-1) if(!Fi ndid(x) ch+="$"ch+=”;in ti=0;while(i< num) stri ngq=c onten ti;un sig nedin tk=3;charc=c onten ti0;while(k<() whil

13、e(qk=x) if(k<()-1 &&qk+1!=T) strin gtem p=Delchar('A',First(qk+1);if(te mp)=stn ng: npo s)ch+=te mp;if(Fi ndchar('A',First(qk+1)!=-1) stri ngfollow_c=Follow(c);if(ch!=follow_c&&( follow_c)=std:stri ng: npos) ch+=follow_c;elseif(k=()-1) stri ngfollow_c=Follow(c);if(

14、follow_c)=std:stn ng: npo s)ch+=follow_c;k+;k+;i+;returnch;分析表输出intP arser:A nalysis()("$");charchose;cout<<"是否输入分析串(yorn):"cin> >chose;while(chose='y')stack+=non 0;cout<<"请输入分析串 <退出(q)>:"cin>>in stack;if(in stack="q")exit

15、(0);if(in stack()-1!='$')i nstack+="$”;in tk=1,flag=0;charx=T op();charc= IpO;cout<<"分析栈t当前输入t动作"<<endl;while(x!='$')x=To p();c=lp()； cout<<stack<<"t"<<i nstack<<"tt"if(Fi ndchar(x,ter)!=-1)if(Mate(x,c)k+;cout<

16、<"匹配"<<c<<endl;elsecout<<T<<k<<"出错（终结符不匹配）！ "<<endl;flag=1;if(x=')') Pop();(0,1);k+;elseif(Fi ndchar(x, non )!=-1)in tidf= Fin dchar(x ,non);in tidz=Fin dchar(c,ter);if(idz=-1)idz=in t();stri ngte mp=tableidfidz;if()k+;elsek+;cout<

17、;<T<<k<<"出错("<<c<<"不属于 FIRST("<<x<<")! "<<endl;flag=1;(0,1)；Pop ()；if(tem p!="")Push(te mp);cout<<x<<"->"<<tem p<<en dl;elsecout<<x<<"->"<<te mp<

18、;<en dl;elseif(x='$'&&c='$')elseif(flag=0)cout<<"正确"<<endl;elsecout<<"错误"<<endl;cout<<T<<k<<"出错(未能识别的字符)! "<<endl;flag=1;(0,1);4. 程序调试导入正确的文法: 符合文法的串 不符合文法的串 导入有左递归的文法: 串分析:总结FIRST集合和通过这次课程设计，对于L

19、L1文法的认识有了进一步的提升，特别是对于FOLLOW集合的求取，前面对于求取者两个集合理解还不是很好，经过这次课程设计，逐渐理解了求解的过程，并且懂得了如何通过代码，自动生成某LL1文法的FIRST集合和FOLLOWS合,在刚开始做时，根本不知道求，通过网上查找资料，同学的请教，慢慢地懂得了如何做，最终正确地求岀FIRST集合和FOLLOV集合。并且能够使用者两个集合构建预测分析表以及对一段输入的串进行分析是否是该文法的串，岀错的地方能够做岀错处理，总的来说,完成了课程设计要求的大部分内容，对于GUI的使用没有能够实现，暴露了自身在这方面的不足,需要在以后的学习和工作中进行沉入学习提高。在实

20、现的功能中还有存在着，对于不含直接左递归的文法没法正确找岀,提示错误。在判断是否是LL1文法上还有很大的不足，没法使用代码实现当两个FIRST有存在交集判断不是LL1文法的功能，这点要求自己对于代码的编程能力有着必要的提高。这次课程设计使用 C+来实现LL1文法分析的功能，自己对于C+语言的使用有了很大的提高。特别是对于一些 C+的语法要求，有了很大的认识。但存在的不足还是比较多的。都是需要在今后的学习中认真总结，以使自己能更好地语言的使用，提升自身的技能。这次课程设计总的收获是不少的。每一次的实践都是提高自身能力的机会，在今后的生活中,要抓住实践的机会， 实践是验证真理最好的途径。对于一个计

21、算机专业的学生来说，更应该注重实践的机会，只有实践多了，一些理论知识才能被自己正真的认识，不然，值懂理论，没有对于正确性进行验证，还是会有问题的，特别是计算机机器，总存在未知的错误，只有不断地探索,才能更好地去使用我们的工具。指导教师评语源码：#in cludeviostream>#in clude<cstri ng>#include<cstdlib>#include<fstream> usingnamespacestd;classParserpublic:Parser();Parser(constParser&); friendostream

22、&operator<<(ostream&output,constParser&rs); friendistream&operator>>(istream&input,Parser&rs); intFindid(char);intCheck();stringCheckstr(string&); stringDelchar(char,string); intFindchar(char,string); intStrNum(conststring&);charRandChar(); stringGetSub(in

23、t,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&);intAnalysis();private: intnum; st

24、ringter,non,end,stack,instack; string*content;string*first; string*follow; string*table;#include"" Parser:Parser()content=newstring255;first=newstring255;follow=newstring255;table=newstring*255;Parser:Parser(constParser&rs)ter=;non=;end=;num=;content=newstring255; first=newstring255; f

25、ollow=newstring255; table=newstring*255;for(inti=0;i<=num;i+) contenti=i;FirstAndFollow();CreateTable(); ostream&operator<<(ostream&output,constParser&rs) output<<"文法内容(共"<<<<"条):"vvendl;inti=0;while(i<output<<i+<<endl;outputw

26、"结终符:"<<<<endl;output<<"非结终符："vvvvendl;coutvv"非终结符的FIRST集合"<<endl; for(unsignedintcout<<"FIRST("<<j<<")="<<j<<"t"<<endl; coutvv"非终结符的FOLLOW集合"<<endl; for(unsignedin

27、tcoutvv"FOLLOW("vvjvv")="vvjvv"t"vvendl; outputvv"预测分析表："vvendlvv%" for(unsignedintoutputvvjvv"t"outputvv"$"vvendl;for(unsignedintoutputvvjvv"t"for(unsignedint coutvvjkvv"t"outputvvendl;returnoutput;istream&oper

28、ator>>(istream&input,Parser&rs) unsignedintj=0；charfilename255；coutvv"请输入文件名："；input>>filename； ifstreaminfile(filename,ios：in)；if(!infile)coutvv"无法打开文件！ "<<e ndl;exit(0)；while(1)unsignedinti=0； infile>>； j+=； if()break；ifi=TIIi='A')；elseif

29、(i=1|i=2)i+;elseifi>='A'&&i<='Z') elsei+；=j-1；if()=0)exit(0)；()；()；returninput；intParser：Findid(chara)inti=0；while(ivnum)if(contenti0=a)returni；i+；return-1；charParser：RandChar() switch(rand()%3)case0:return'A'case1:return'B'case2:return'C'case3:r

30、eturn'D'return'D' intParser:Check() unsignedintj=0; inti=0; while(i<num)if(contenti.size()<=3)coutvv"文法句"vvcontentivv"长度不对!"<<endl; return0;if(contenti1!='-'|contenti2!='>')coutvv"文法句"vvcontenti<<"未来使用推导符 "-

31、>"!"vvendl; return0;intn=StrNum(contenti);ints=0;charz=contenti0;intm=0;for(intk=1;kv=n;k+) stringtmp=GetSub(k,contenti,'|'); if(z=tmp0)s=1;m+; if(m=n)coutvv"文法句"vvcontentivv"将形成无穷推导！"vvendl;return0;if(s=1)DelLeft(i);i+;return1;Parser&Parser:DelLeft(inti)

32、 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;coutvv"文法句"vvcontentivv"含有直接左递归,"while(1) if(Findchar(c,non)=-1)break; elsec=RandChar();coutvv"随机产生非终结符为："

33、vvcvvendl;(1,c); stringtemp;temp+=z; temp+="->"stringnext;next+=c; next+="->"for(intk=1;kv=n;k+) stringt=GetSub(k,contenti,'|');if(z=t0)(0,1);t+=c;next+=t;next+='|'elseif(t= = "A")()；t+=c;temp+=t;temp+='|'n ext+='A'()-1,1);contenti=

34、temp;num=num+1;contentnum=end;for(intj=num-1;j>i;j-)contentj=contentj-1;contenti+1=next;return*this;stringParser:Checkstr(string&a)unsignedinti=0,j=0; for(;i<();i+) for(j=i+1;j<();j+) if(ai=aj)(j,1);returna; stringParser:Delchar(charx,stringa)intj,i=int();for(j=0;j<i;j+)if(aj=x)(j,1)

35、;returna;intParser:Findchar(charx,stringa)unsignedinti=0;while(i<()if(ai=x)returni;i+;return-1;stringParser:GetSub(inti,conststring&a,charc='|') stringch;intj255;intn=1;j0=2;if(i>=int()returnch;for(unsignedintk=3;k<();k+)if(ak=c)jn+=k;for(unsignedintk=ji-1+1;k<();k+)if(ak=c)b

36、reak;elseif(std:string:npos=(ak)(1,ak);returnch;intParser:StrNum(conststring&a)intn=0;for(unsignedinti=3;i<();i+)if(ai='|')n+;returnn+1;stringParser:First(charx)stringch=""if(Findchar(x,ter)!=-1)(1,x);(1,'');elseif(Findchar(x,non)!=-1)inti=Findid(x);if(i!=-1)stringq=

37、contenti;unsignedintk=3;while(k<()if(qk-1='|'|k=3)if(Fi ndchar(qk,ter)!=-1|qk='A')(1,qk);(1,'');elseif(k=3|qk+1='|'|k=()-1)ch+=First(qk); elsestringtemp=First(qk-1);if(Fi ndchar('A',tem p)!=-1)ch+=First(qk);k+;elsek+;returnch;stringParser:First(conststring&

38、amp;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<()while(qk=x)if(k<()-1&&qk+1!='|')stri ngte mp=Delchar('A',First (q

39、k+1); if(temp)=string:npos)ch+=temp;if(Fi ndchar('A',First(qk+1)!=-1)stringfollow_c=Follow(c);if(ch!=follow_c&&(follow_c)=std:string:npos) ch+=follow_c; elseif(k=()-1) stringfollow_c=Follow(c); if(follow_c)=std:string:npos)ch+=follow_c;k+;k+;i+;returnch;Parser&Parser:FirstAndFoll

40、ow() unsignedinti=0; while(i<() firsti=First(noni); followi=Follow(noni); i+;return*this;Parser&Parser:CreateTable() for(unsignedinti=0;i<=();i+) tablei=newstring255; for(unsignedinti=0;i<();i+)stringtemp=contenti; intw=Findchar(temp0,this->non); intn=StrNum(temp);for(intk=1;k<=n;

41、k+) stringtmp=GetSub(k,temp); stringfir=First(tmp); for(unsignedintj=0;j<();j+) intidz=Findchar(firj,ter); if(idz!=-1) tablewidz=tmp;if(Fi ndchar('A',fir)!=-1|tm 卩0='八')stringfol=Follow(temp0); for(unsignedintj=0;j<();j+)intz=Findchar(folj,ter);if(z=-1)z=int(); tablewz=tmp;retu

42、rn*this;Parser:Parser()deletecontent;deletefirst;deletefollow; deletetable;charParser:Pop()charx=stack()-1;()-1,1);returnx;intParser:Mate(charx,charip)if(Findchar(x,ter)!=-1)if(x=ip)Pop();(0,1);return1;elsereturn0;return0;charParser:Top()returnstack()-1;charParser:Ip() returninstack0;Parser&Parser:Push(c