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

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

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

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

4、 ,V*，且B不以 A 开头)对A引入一个新的非终结符 A,把上式改写为：a tb aAa A | e 间接左递归若文法中存在某一非终结符 A,使得A A至少需要两步推导，则称该文法是间 接左递归的。消除间接左递归的方法：【方法一】采用代入法把间接左递归变成直接左递归。【方法二】直接改写文法：设有文法 G10S ：S t Aa | B A tSy因为S Aa SYa，所以S是一个间接递归的非终结符。为了消除这种间接左 递归，将式代入式，即可得到与原文法等价的文法(可以证明) ：S t Sya | B 式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进 行改写后可得文法：SB s

5、St ya S | e2. 计算 First 集(1) 若 X VT，J则 First(X)二X(2) 若 X Vn，且有产生式 Xta,a VT则 First(X)=X(3) 若 X Vn，且有产生式 Xt ,则 First(X)=X(4) 若X, Yi , 丫2 ,，都 Vn,而由产生式X Yi Y2Yn。当Y , 丫2 ,，Y-i 都能推导出 时，(其中 1i n),则 First(Y i)- , First(Y2)- ,First(Y i ) 都包含在 First(X) 中(5) 当中所有Y都能推导出, (i=1 , 2,，n),贝V First(X)=First(Y i) U Fir

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

7、表。预测分析程序的框图如下:目录i 系统分析 i1.1 选题要求i1.2 预期目标i2. 程序流程图 i2.i 总流程图 i2.2FIRST 集和 FOLLOW 集 22.3 预测分析表流程 33. 代码编写3.1 检查左递归 33.2 FIRST 集合53.3 FOLLOW 集合 63.4 分析表输出 810124. 程序调试5. 总结 116. 指导教师评语7. 源码 13正文:1. 系统分析1.1 选题要求根据某一文法编制调试LL(1)文法语法分分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解o1.2预期目标构造LL(1)文法

8、语法分析程序，任意输入一个文法符号串，并判断它是否为 文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合(编译出错)，则输出错误信息。2. 程序流程图2 . 1.总流程图2.2. First集和Follow集的流程图2.3. 预测分析表流程：3. 代码编写3.1检查左递归：Parser& Parser:DelLeft(int i)int n=StrNum(c onten ti); char c=Ra ndChar();char z=c onten ti0;int s=0;for(i nt k=1;k=n; k+)s

9、tri ng tmp=GetSub(k,co nte nti，T); if(z=tmp0)s=1;if(s=0) return *this;cout文法句contenti含有直接左递归, while(1)if(Fin dchar(c ,non)=-1) break;else c=Ra ndChar();cout随机产生非终结符为：c;stri ng n ext;n ext+=c;next+=-;for(i nt k=1;ki;j-)conten tj=con te ntj-1;conten ti+1=n ext;return *this;3.2 first 集合stri ng Parser:F

10、irst(char x)stri ng ch=;if(Fi ndchar(x,ter)!=-1)ch.appe nd(1,x);ch.appe nd(1,);else if(Fin dchar(x ,non )!=-1)int i=Fin did(x);if(i!=-1)string q=contenti;un sig ned int k=3;while(kq.size()if(qk-1=|k=3)if(Fi ndchar(qk,ter)!=-1|qk=z)ch.appe nd(1,qk);ch.appe nd(1,); elseif(k=3|qk+1=|k=q.size()-1)ch+=Fi

11、rst(qk);elsestring temp=First(qk_1);if(Fi ndchar(A,temp)!=-1) ch+=First(qk);k+;else k+;return ch;3.3 follow 集合string Parser:Follow(char x) stri ng ch;if(Fin dchar(x ,non )!=-1)if(!Fi ndid(x)ch+=$; ch+=;int i=0;while(i num)string q=contenti;un sig ned int k=3;char c=c onten ti0;while(kq.size()while(q

12、k=x)if(kq.size()-1 &qk+1!=T)string temp=Delchar(A,First(qk+1);if(ch.find(temp)=string:npos) ch+=temp;if(Fi ndchar(A,First(qk+1)!=-1)stri ng follow_c = Follow(c);if(ch!=follow_c&ch.fi nd(follow_c)=std:stri ng: npos)ch+=follow_c;else if(k=q.size()-1)stri ng follow_c =Follow(c);if(ch.fi nd(follow_c)=st

13、d:stri ng: npos) ch+=follow_c;k+;k+;i+;return ch;3.4分析表输出int Parser:A nalysis()stack.appe nd($);char chose;cout chose;while(chose=y)stack+=non 0;cout请输入分析串 :;cinin stack;if (in stack=q) exit(0);if(i nstacki nstack.size()-1!=$) in stack+=$”;int k=1,flag=0;char x=Top();char c=Ip();cout分析栈t当前输入t动作endl;

14、while(x!=$)x=Top();c=Ip();coutstackti nstacktt;if(Fi ndchar(x,ter)!=-1)if(Mate(x,c)k+;cout匹配cendl;elsecoutk出错(终结符不匹配)！ endl;flag=1;if(x=) Pop();else in stack.erase(0,1);k+;else if(Fi ndchar(x, non )!=-1)int idf= Fin dchar(x ,non);int idz=Fin dchar(c,ter);if(idz=-1) idz=in t(ter.size();string temp=ta

15、bleidfidz;if(temp.empty()e ndl;coutk出错(c不属于 FIRST(x)!flag=1;in stack.erase(0,1);k+;elsePop();if(temp!=人)Push(temp);coutxtempe ndl;else coutxtempe ndl;else if(x=$&c=$)if(flag=0) cout正确endl;else cout错误endl;elsecoutTk出错(未能识别的字符 )! endl;flag=1;in stack.erase(0,1);k+;4. 程序调试导入正确的文法:符合文法的串不符合文法的串导入有左递归的文法

16、:串分析:FIRST集合和通过这次课程设计，对于LL1文法的认识有了进一步的提升，特别是对于FOLLOW集合的求取，前面对于求取者两个集合理解还不是很好，经过这次课程设计，逐渐理解 高。特别是对于一些 C+的语法要求，有了很大的认识。但存在的不足还是比较多的。都是需要 在今后的学习中认真总结，以使自己能更好地语言的使用，提升自身的技能。了求解的过程，并且懂得了如何通过代码，自动生成某LL1文法的FIRST集合和FOLLOWS合,在刚开始做时，根本不知道求，通过网上查找资料，同学的请教，慢慢地懂得了如何做，最终正确地求岀FIRST集合和FOLLOV集合。并且能够使用者两个集合构建预测分析表以及对

17、一段输入的串进行分析是否是该文法的串，岀错的地方能够做岀错处理，总的来说,完成了课程设计要求的大部分内容，对于GUI的使用没有能够实现，暴露了自身在这方面的不足,需要在以后的学习和工作中进行沉入学习提高。在实现的功能中还有存在着，对于不含直接左递归的文法没法正确找出,提示错误。在判断是否是LL1文法上还有很大的不足，没法使用代码实现当两个FIRST有存在交集判断不是LL1文法的功能，这点要求自己对于代码的编程能力有着必要的提高。这次课程设计使用 C+来实现LL1文法分析的功能，自己对于C+语言的使用有了很大的提这次课程设计总的收获是不少的。每一次的实践都是提高自身能力的机会，在今后的生活中，要

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

19、；主题是否鲜明、重心是否突出、论述是否充 分、结论是否正确；是否提出了自己的独到见解。306文献引用是否合理、充分、真实。57答辩情况：自我陈述、回答问题的正确性、用语准确性、逻辑思维、是否具有独到见解等。25合计指导教师（签章）：年月日源码：LLl.h#i nclude #in elude #in elude #in elude using n amespace std;class Parserpublic:Parser。；Parser(c onst Parser&);friend ostrea m& operator(ostream& output,c onst Parser & rs);

20、friend istrea m& operator(istream& in put,Parser& rs);int Fin did(char);int Check();stri ng Checkstr(stri ng&);string Delchar(char,string);int Fin dchar(char,str in g);int StrNum(c onst stri ng&);char RandChar();string GetSub(int,const string&,char);Parser& DelLeft(int);string First(char);string Fir

21、st(const string&);string Follow(char);Parser& FirstAndFollow();Parser& CreateTable();Parser();char Pop();int Mate(char,char);char Top();char Ip();Parser& Push(const string&);int Analysis();private:int num;string ter,non,end,stack,instack;string *content;string *first;string *follow;string *table;LL1

22、.cpp #include LL1.hParser:Parser()content=new string255;first=new string255;follow=new string255;table=new string *255;Parser:Parser(const Parser& rs)ter=rs.ter;non=rs.non;end=rs.end;num=rs.num;content=new string255; first=new string255; follow=new string255; table=new string *255;for(int i=0;i=num;

23、i+) contenti=rs.contenti;FirstAndFollow();CreateTable();ostream& operator(ostream& output,const Parser& rs)outputvv文法内容(共rs.num条):endl;int i=0;while(irs.num)outputrs.contenti+endl;outputvv结终符:vvrs.tervvendl;output 非结终符 :rs.nonendl;coutvv 非终结符的 FIRST 集合 vvendl;for(unsigned int j=0;jvrs.non.size();j+)

24、coutvvFIRST(vvrs.nonjvv) = vvrs.firstjvvtvvendl; coutvv非终结符的 FOLLOW合endl;for(unsigned int j=0;jvrs.non.size();j+)coutvvFOLLOW(vvrs.nonjvv) = vvrs.followjvvtvvendl; outputvv 预测分析表 :vvendlvvt;for(unsigned int j=0;jvrs.ter.size();j+)outputvvrs.terjvvt;outputvv$vvendl;for(unsigned int j=0;jvrs.non.size(

25、);j+)outputrs.nonjt;for(unsigned int k=0;k=rs.ter.size();k+)coutrs.tablejkt;output(istream& input,Parser& rs)unsigned int j=0;char filename255;coutfilename;ifstream infile(filename,ios:in);if(!infile)cout 无法打开文件！ rs.end;rs.contentj+=rs.end; if(infile.eof() break;while(i=A&rs.endi=Z) if(std:string:np

26、os=rs.non.find(rs.endi) rs.non.append(1,rs.endi);else if(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();return input;int Parser:Findid(char a)int i=0;while(inum)if(contenti0=a) return i; i+;return -1;char Parse

27、r:RandChar()switch(rand()%3)case 0:return A;case 1:return B;case 2:return C;case 3:return D;return D;int Parser:Check()unsigned int j=0;int i=0;while(inum)if(contenti.size()=3)长度不对 !endl;未来使用推导符cout 文法句 contenti)cout 文法句 contenti!endl;return 0;int n=StrNum(contenti);int s=0;char z=contenti0;int m=0;

28、for(int k=1;k=n;k+)string tmp=GetSub(k,contenti,|);if(z=tmp0)s=1;m+;if(m=n)endl;cout 文法句 contenti 将形成无穷推导！ return 0;if(s=1)DelLeft(i);i+;return 1;Parser& Parser:DelLeft(int i)int n=StrNum(contenti);char c=RandChar();char z=contenti0;int s=0;for(int k=1;k=n;k+)string tmp=GetSub(k,contenti,|);if(z=tmp

29、0) s=1;if(s=0) return *this;cout 文法句 contenti 含有直接左递归 ,while(1)if(Findchar(c,non)=-1) break;else c=RandChar();cout 随机产生非终结符为 :c;string next;next+=c;next+=-;for(int k=1;ki;j-)contentj=contentj-1;contenti+1=next;return *this;string Parser:Checkstr(string & a)unsigned int i=0,j=0;for(;ia.size();i+)for(

30、j=i+1;ja.size();j+)if(ai=aj)a.erase(j,1);return a;string Parser:Delchar(char x,string a)int j,i=int(a.size();for(j=0;ji;j+)if(aj=x)a.erase(j,1);return a;int Parser:Findchar(char x,string a)unsigned int i=0;while(i=int(a.size() return ch;for(unsigned int k=3;ka.size();k+) if(ak=c) jn+=k;for(unsigned

31、int k=ji-1+1;ka.size();k+)if(ak=c) break;else if(std:string:npos=ch.find(ak) ch.append(1,ak); return ch;int Parser:StrNum(const string& a)int n=0;for(unsigned int i=3;ia.size();i+)if(ai=|) n+;return n+1;string Parser:First(char x)string ch=;if(Findchar(x,ter)!=-1) ch.append(1,x);ch.append(1, );else

32、if(Findchar(x,non)!=-1)int i=Findid(x);if(i!=-1)string q=contenti; unsigned int k=3; while(kq.size()if(qk-1=|k=3)if(Fi ndchar(qk,ter)!=-1|qk=z)ch.append(1,qk);ch.append(1, );elseif(k=3|qk+1=|k=q.size()-1)ch+=First(qk);elsestring temp=First(qk-1);if(Fi ndchar(A,temp)!=-1)ch+=First(qk);k+; else k+;ret

33、urn ch;string Parser:First(const string& a)return First(a0);string Parser:Follow(char x)string ch;if(Findchar(x,non)!=-1)if(!Findid(x)ch+=$;ch+= ;int i=0;while(inum)string q=contenti;unsigned int k=3;char c=contenti0;while(kq.size()while(qk=x)if(kq.size()-1&qk+1!=|)stri ng temp二Delchar(A,First(qk+1)

34、;if(ch.find(temp)=string:npos) ch+=temp;if(Fi ndchar(A,First(qk+1)!=-1)string follow_c = Follow(c);if(ch!=follow_c&ch.find(follow_c)=std:string:npos)ch+=follow_c;else if(k=q.size()-1)string follow_c = Follow(c);if(ch.find(follow_c)=std:string:npos)ch+=follow_c;k+;k+;i+;return ch;Parser& Parser:First

35、AndFollow()unsigned int i=0;while(inon.size()firsti=First(noni); followi=Follow(noni);i+;return *this;Parser& Parser:CreateTable()for(unsigned int i=0;i=non.size();i+)tablei=new string255;for(unsigned int i=0;inon);int n=StrNum(temp);for(int k=1;k=n;k+)string tmp=GetSub(k,temp);string fir=First(tmp)

36、;for(unsigned int j=0;jfir.size();j+)int idz=Findchar(firj,ter);if(idz!=-1)tablewidz=tmp;if(Fi ndchar(A,fir)!=-1|tmp0=z)string fol=Follow(temp0);for(unsigned int j=0;jfol.size();j+)int z=Findchar(folj,ter);if(z=-1) z=int(ter.size();tablewz=tmp;return *this;Parser:Parser()delete content;delete first;delete follow;delete table;char Parser:Pop()char x=stackstack.size()-1;stack.erase(stack.size()-1,1);return x;int Parser:Mat