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

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

2、别是否为给定文法的句子，并给出推导过程。4、对输入给定的文法，由程序自动构造FIRST、FOLLOW集合。5、对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程。 关键词：语法分析；FIRST集合；FOLLOW集合；分析表一、设计内容及要求(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 )SELECT(A:=b)=Ø。（1）文法的左递归当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法中对任一非终结符A有推导AÞA，则称该文法是左递归的。左递归又可以分为直接左递归和间接左递归。 直接左递归若文法中的某一产生式形如AA，V*，则称该文法是直接左递归的。消除直接左递归的方法：设有产生式是关于非终结符A的直接左递归：AA| （,V*，且不以A开头）对A引入一

4、个新的非终结符A，把上式改写为：A A AA| 间接左递归若文法中存在某一非终结符A，使得AÞA至少需要两步推导，则称该文法是间接左递归的。消除间接左递归的方法：【方法一】采用代入法把间接左递归变成直接左递归。 【方法二】直接改写文法：设有文法G10S： SA| AS 因为SÞAÞS，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将式代入式，即可得到与原文法等价的文法（可以证明）： SS| 式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：SSSS|2. 计算First集(1) 若XVT ，则First(X)=X(2)

5、若XVN ，且有产生式Xa, aVT则First(X)=X(3) 若XVN ，且有产生式X,则First(X)=X(4) 若X，Y1 ，Y2 ，Yn 都VN，而由产生式XY1 Y2 Yn 。当Y1 ，Y2 ，Yi-1都能推导出时，（其中1in），则First(Y1)-, First(Y2)-, First(Yi)都包含在First(X)中(5)当(4)中所有Yi都能推导出，（i=1，2，n），则First(X)=First(Y1)First(Y2)First(Yn)反复使用上述步骤直到每个符合的First集合不再增大为止。3. 计算Follow集对文法中的每个AVN，计算Follw(A)：(1

6、) 设S为文法的开始符合，把#加入Follow(S)中；(2) 若AB是一个产生式，则把First()的非空元素加入Follow(B)中，如果能推导出，则把Follow(A)也加入(B)中；(3) 反复使用以上步骤直到每个非终结符号的Follow集不再增大为止。4. 预测分析方法预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成：预测分析程序；先进后出栈；预测分析表。预测分析程序的框图如下：目录1系统分析11.1选题要求11.2预期目标12.程序流程图12.1总流程图12.2First集和Follow集22.3预测分析表流程33.代码编写33.1检查左递归33.2first

7、集合53.3follow集合63.4分析表输出84.程序调试105.总结116.指导教师评语127.源码13正文：1.系统分析 1.1选题要求根据某一文法编制调试LL(1) 文法语法分分析程序，以便对任意输入的符 号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。 1.2预期目标构造LL(1)文法语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合（编译出错），则输出错误信息。2. 程序流程图 21.总流程图2.2.First集和F

8、ollow集的流程图2.3.预测分析表流程：3. 代码编写 3.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=tmp0) s=1; if(s=0) return *this; cout<<"文法句"<<contenti<<&

9、quot;含有直接左递归," while(1) if(Findchar(c,non)=-1) break; else c=RandChar(); cout<<"随机产生非终结符为:"<<c<<endl; non.append(1,c); string temp; temp+=z; temp+="->" string next; next+=c; next+="->" for(int k=1;k<=n;k+) string t=GetSub(k,contenti,'

10、|'); if(z=t0) t.erase(0,1); t+=c; next+=t; next+='|' else if(t="") t.clear(); t+=c; temp+=t; temp+='|' next+='' temp.erase(temp.size()-1,1); contenti=temp; num=num+1; contentnum=end; for(int j=num-1;j>i;j-) contentj=contentj-1; contenti+1=next; return *this;3

11、.2 first集合string Parser:First(char x) string ch="" if(Findchar(x,ter)!=-1) ch.append(1,x); ch.append(1,' '); else if(Findchar(x,non)!=-1) int i=Findid(x); if(i!=-1) string q=contenti; unsigned int k=3; while(k<q.size() if(qk-1='|'|k=3) if(Findchar(qk,ter)!=-1|qk='

12、9;) ch.append(1,qk); ch.append(1,' '); else if(k=3|qk+1='|'|k=q.size()-1) ch+=First(qk); else string temp=First(qk-1); if(Findchar('',temp)!=-1) ch+=First(qk); k+; else k+; return ch;3.3 follow集合string Parser:Follow(char x) string ch; if(Findchar(x,non)!=-1) if(!Findid(x) ch+

13、="$" ch+=' ' int i=0; while(i<num) string q=contenti; unsigned int k=3; char c=contenti0; while(k<q.size() while(qk=x) if(k<q.size()-1&&qk+1!='|') string temp=Delchar('',First(qk+1); if(ch.find(temp)=string:npos) ch+=temp; if(Findchar('',Fir

14、st(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;3.4 分析表输出int Parser:Analysis() stack.append("$")

15、;char chose;cout<<"是否输入分析串(y or n):"cin>>chose;while(chose='y')stack+=non0;cout<<"请输入分析串<退出(q)>："cin>>instack;if (instack="q") exit(0);if(instackinstack.size()-1!='$') instack+="$"int k=1,flag=0; char x=Top();char

16、c=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<<""<<k<<&q

17、uot;出错(终结符不匹配)！"<<endl;flag=1;if(x=')') Pop();else instack.erase(0,1); k+;else if(Findchar(x,non)!=-1)int idf=Findchar(x,non);int idz=Findchar(c,ter);if(idz=-1) idz=int(ter.size();string temp=tableidfidz;if(temp.empty() cout<<""<<k<<"出错（"<&

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

19、#39;&&c='$')if(flag=0) cout<<"正确"<<endl;else cout<<"错误"<<endl;elsecout<<""<<k<<"出错(未能识别的字符)！"<<endl;flag=1;instack.erase(0,1); k+;4. 程序调试导入正确的文法：符合文法的串不符合文法的串导入有左递归的文法：串分析： 总 结通过这次课程设计，对于LL1文法的认识有

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

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

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

23、自己的独到见解。306文献引用是否合理、充分、真实。57答辩情况： 自我陈述、回答问题的正确性、用语准确性、逻辑思维、是否具有独到见解等。25合计指导教师（签章）： 年 月 日 源码：LL1.h#include <iostream>#include <cstring>#include <cstdlib>#include <fstream>using namespace std;class Parserpublic: Parser(); Parser(const Parser&); friend ostream& operator&

24、lt;<(ostream& output,const Parser& rs); friend istream& operator>>(istream& input,Parser& rs); int Findid(char); int Check(); string Checkstr(string&); string Delchar(char,string); int Findchar(char,string); int StrNum(const string&); char RandChar(); string GetS

25、ub(int,const string&,char); Parser& DelLeft(int); string First(char); string First(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 Anal

26、ysis();private: int num; string ter,non,end,stack,instack; string *content; string *first; string *follow; string *table;LL1.cpp#include "LL1.h"Parser:Parser() content=new string255; first=new string255; follow=new string255; table=new string *255;Parser:Parser(const Parser& rs) ter=rs

27、.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;i+) contenti=rs.contenti; FirstAndFollow(); CreateTable();ostream& operator<<(ostream& output,const Parser& rs)output<<&quo

28、t;文法内容(共"<<rs.num<<"条):"<<endl;int i=0;while(i<rs.num)output<<rs.contenti+<<endl;output<<"结 终 符:"<<rs.ter<<endl;output<<"非结终符:"<<rs.non<<endl;cout<<"非终结符的FIRST集合 "<<endl;for(

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

30、lt;<") = "<<rs.followj<<"t"<<endl;output<<"预测分析表:"<<endl<<"t"for(unsigned int j=0;j<rs.ter.size();j+)output<<rs.terj<<"t"output<<"$"<<endl;for(unsigned int j=0;j<rs.non.si

31、ze();j+)output<<rs.nonj<<"t"for(unsigned int k=0;k<=rs.ter.size();k+)cout<<rs.tablejk<<"t"output<<endl;return output;istream& operator>>(istream& input,Parser& rs)unsigned int j=0;char filename255;cout<<"请输入文件名:"i

32、nput>>filename;ifstream infile(filename,ios:in);if(!infile)cout<<"无法打开文件！"<<endl;exit(0);while(1) unsigned int i=0;infile>>rs.end; rs.contentj+=rs.end;if(infile.eof() break;while(i<rs.end.size()if(rs.endi='|'|rs.endi='');else if(i=1|i=2) i+;else i

33、f(rs.endi>='A'&&rs.endi<='Z')if(std:string:npos=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

34、(char a) int i=0; while(i<num) if(contenti0=a) return i; i+; return -1;char Parser: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(i<num) if

35、(contenti.size()<=3) cout<<"文法句"<<contenti<<"长度不对!"<<endl; return 0; if(contenti1!='-'|contenti2!='>') cout<<"文法句"<<contenti<<"未来使用推导符"->"!"<<endl; return 0; int n=StrNum(conten

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

37、t 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=tmp0) s=1; if(s=0) return *this; cout<<"文法句"<<contenti<<"含有直接左递归," while(1) if(Findchar(c,non)=-1) break; else c=RandChar(

38、); cout<<"随机产生非终结符为:"<<c<<endl; non.append(1,c); string temp; temp+=z; temp+="->" string next; next+=c; next+="->" for(int k=1;k<=n;k+) string t=GetSub(k,contenti,'|'); if(z=t0) t.erase(0,1); t+=c; next+=t; next+='|' else if(t=

39、"") t.clear(); t+=c; temp+=t; temp+='|' next+='' temp.erase(temp.size()-1,1); contenti=temp; num=num+1; contentnum=end; for(int j=num-1;j>i;j-) contentj=contentj-1; contenti+1=next; return *this;string Parser:Checkstr(string & a) unsigned int i=0,j=0; for(;i<a.siz

40、e();i+) for(j=i+1;j<a.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;j<i;j+) if(aj=x) a.erase(j,1); return a;int Parser:Findchar(char x,string a) unsigned int i=0; while(i<a.size() if(ai=x) return i; i+; return -1;string Pars

41、er:GetSub(int i,const string& a,char c='|') string ch; int j255; int n=1; j0=2; if(i>=int(a.size() return ch; for(unsigned int k=3;k<a.size();k+) if(ak=c) jn+=k; for(unsigned int k=ji-1+1;k<a.size();k+) if(ak=c) break; else if(std:string:npos=ch.find(ak) ch.append(1,ak); return

42、ch;int Parser:StrNum(const string& a) int n=0; for(unsigned int i=3;i<a.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 if(Findchar(x,non)!=-1) int i=Findid(x); if(i!=-1) str

43、ing q=contenti; unsigned int k=3; while(k<q.size() if(qk-1='|'|k=3) if(Findchar(qk,ter)!=-1|qk='') ch.append(1,qk); ch.append(1,' '); else if(k=3|qk+1='|'|k=q.size()-1) ch+=First(qk); else string temp=First(qk-1); if(Findchar('',temp)!=-1) ch+=First(qk); k+

44、; else k+; return 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(i<num) string q=contenti; unsigned int k=3; char c=contenti0; while(k<q.size() while(qk=x) if(k<q.s