《编译原理课程设计LL文法分析器设计C语言实现》由会员分享，可在线阅读，更多相关《编译原理课程设计LL文法分析器设计C语言实现（27页珍藏版）》请在金锄头文库上搜索。
1、集美大学计算机工程学院编译原理课程设计报告选题名称:LL（1）文法分析院（系）:计算机工程学院专业:计算机科学与技术班级:计算1412指导教师:付永刚学年学期:20162017学年第2学期2017年06月29日摘要：选题要求：根据某一文法编制调试LL(1)文法语法分分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法语法分析法的理解。具体如下：1、对语法规则有明确的定义；2、编写的分析程序能够对给定文法进行正确的语法分析；3、对输入给定的文法，手工计算FIRST、FOLLOW集合和select集合，应能判断识别是否为给定文法的句子，并给出推导过程。4、
2、对输入给定的文法，由程序自动构造FIRST、FOLLOW集合。5、对于遇到的语法错误，能够做出简单的错误处理，给出简单的错误提示，保证顺利完成语法分析过程。?关键词：语法分析；FIRST集合；FOLLOW集合；分析表一、设计内容及要求(1)基于PL/0语言，通过编程判断该文法是否为LL(1)文法；(2)计算出文法的First()Follow()(3)构造相应文法的预测分析表(4)对某个输入句子进行语法分析二、实现原理1LL(1)文法LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。就是要求描述语言的文法是无左递归的和无回溯的。根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式
3、A:=a和A:=b，都要满足：SELECT(A：=a)SELECT(A:=b)=?。（1）文法的左递归当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法中对任一非终结符A有推导A?A，则称该文法是左递归的。左递归又可以分为直接左递归和间接左递归。直接左递归若文法中的某一产生式形如AA，V*，则称该文法是直接左递归的。消除直接左递归的方法：设有产生式是关于非终结符A的直接左递归：AA|（,V*，且不以A开头）对A引入一个新的非终结符A，把上式改写为：AAAA|间接左递归若文法中存在某一非终结符A，使得A
4、?A至少需要两步推导，则称该文法是间接左递归的。消除间接左递归的方法：【方法一】采用代入法把间接左递归变成直接左递归。【方法二】直接改写文法：设有文法G10S：SA|AS因为S?A?S，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将式代入式，即可得到与原文法等价的文法（可以证明）：SS|式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：SSSS|2.计算First集(1)若XVT，则First(X)=X(2)若XVN，且有产生式Xa,aVT则First(X)=X(3)若XVN，且有产生式X,则First(X)=X(4)若X，Y1，Y2，Yn都VN，
5、而由产生式XY1Y2Yn。当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)设S为文法的开始符合，把#加入Follow(S)中；(2)若AB是一个产生式，则把First()的非空元素加入Follow(B)中，如果能推导出，则把Follow(A)也加
6、入(B)中；(3)反复使用以上步骤直到每个非终结符号的Follow集不再增大为止。4.预测分析方法预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成：预测分析程序；先进后出栈；预测分析表。预测分析程序的框图如下：目录1系统分析1选题要求1预期目标12.程序流程图1总流程图1集和Follow集2预测分析表流程33.代码编写3检查左递归3集合5集合6分析表输出84.程序调试105.总结116.指导教师评语127.源码13正文：1.系统分析选题要求根据某一文法编制调试LL(1)文法语法分分析程序，以便对任意输入的符号串进行分析。本次课程设计的目的主要是加深对预测分析LL(1)文法
7、语法分析法的理解。预期目标构造LL(1)文法语法分析程序，任意输入一个文法符号串，并判断它是否为文法的一个句子。程序要求为该文法构造预测分析表，并按照预测分析算法对输入串进行语法分析，判别程序是否符合已知的语法规则，如果不符合（编译出错），则输出错误信息。2. 程序流程图21.总流程图集和Follow集的流程图.预测分析表流程：3. 代码编写检查左递归：Parser&Parser:DelLeft(inti)intn=StrNum(contenti);charc=RandChar();charz=contenti0;ints=0;for(intk=1;k=n;k+)stringtmp=GetSu
8、b(k,contenti,|);if(z=tmp0)s=1;if(s=0)return*this;cout文法句contenti含有直接左递归,;while(1)if(Findchar(c,non)=-1)break;elsec=RandChar();cout随机产生非终结符为:c;stringnext;next+=c;next+=-;for(intk=1;ki;j-)contentj=contentj-1;contenti+1=next;return*this;集合stringParser:First(charx)stringch=;if(Findchar(x,ter)!=-1)(1,x);
9、(1,);elseif(Findchar(x,non)!=-1)inti=Findid(x);if(i!=-1)stringq=contenti;unsignedintk=3;while(k()if(qk-1=|k=3)if(Findchar(qk,ter)!=-1|qk=)(1,qk);(1,);elseif(k=3|qk+1=|k=()-1)ch+=First(qk);elsestringtemp=First(qk-1);if(Findchar(,temp)!=-1)ch+=First(qk);k+;elsek+;returnch;集合stringParser:Follow(charx)s
10、tringch;if(Findchar(x,non)!=-1)if(!Findid(x)ch+=$;ch+=;inti=0;while(inum)stringq=contenti;unsignedintk=3;charc=contenti0;while(k()while(qk=x)if(k()-1&qk+1!=|)stringtemp=Delchar(,First(qk+1);if(temp)=string:npos)ch+=temp;if(Findchar(,First(qk+1)!=-1)stringfollow_c=Follow(c);if(ch!=follow_c&(follow_c)
11、=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;分析表输出intParser:Analysis()($);charchose;coutchose;while(chose=y)stack+=non0;cout请输入分析串：;cininstack;if(instack=q)exit(0);if(instack()-1!=$)instack+=$;intk=1,flag=0;charx=Top
12、();charc=Ip();cout分析栈t当前输入t动作endl;while(x!=$)x=Top();c=Ip();coutstacktinstacktt;if(Findchar(x,ter)!=-1)if(Mate(x,c)k+;cout匹配cendl;elsecoutk出错(终结符不匹配)！endl;flag=1;if(x=)Pop();(0,1);k+;elseif(Findchar(x,non)!=-1)intidf=Findchar(x,non);intidz=Findchar(c,ter);if(idz=-1)idz=int();stringtemp=tableidfidz;if()cout
