编译原理课程设计报告——LL(1)分析

1、南开大学计算机科学与技术学院 课程设计报告南开大学计算机科学与技术学院课程设计报告 （ 2010 2011 学年度 第 一 学期 ）课程名称编译原理 设计题目LL(1)分析姓名学号专业班级地点教师1.需求分析语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图1所示：图1 语法分析器在编译程序中的地位语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。对一个文法，当给你一

2、串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。自顶向下分析法就是语法分析办法中的一类。顾名思义，自顶向下就是从文法的开始符号出发，向下推导，推出句子。这种方法是带“回溯”的。自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递

3、归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。对于给定的分析文法对象，构造它的预测分析程序；并任意给一算术表达式进行分析测试，本预测分析程序能够使用分析表和栈联合控制实现LL(1)分析，本文将就编译原理中比较常用的一个表达式文法，通过递归下降语法分析法来编写分析器。文中将为您提供如何通过FIRST、FOLLOW和SELECT集合来判断LL(1)方法，然后如何用递归下降语法分析法分析LL(1)方法的基本递归流程，以及用C+语言来编程实现分析器。本程序需要首先构造文法，根

4、据文法判断是否正确，消除左递归，判断是否为LL（1） 文法，然后用户输入句型，根据句型判断是否为该文法的句型。2.概要设计自顶向下的分析算法通过在最左推导中描述出各个步骤来分析记号串输入。之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根到叶自顶向下的分析程序有两类：回溯分析程序（backtracking parser）和预测分析程序（predictive parser）。预测分析程序试图利用一个或多个先行记号来预测出输入串中的下一个构造，而回溯分析程序则试着分析其他可能的输入，当一种可能失败时就要求输入中备份任意数量的字符。虽然回溯分析程序比预测分析

5、程序强大许多，但它们都非常慢，一般都在指数的数量级上，所以对于实际的编译器并不合适。递归下降程序分析和LL(1)分析一般地都要求计算先行集合，它们分别称作First集合和Follow集合。由于无需显式地构造出这些集合就可以构造出简单的自顶向下的分析程序。2.1 LL(1)文法设计2.1.1 LL(1)文法定义LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。就是要求描述语言的文法是无左递归的和无回溯的。根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A:=a和A:=b，都要满足：SELECT(A：=a )SELECT(A:=b)=Ø。这样，当前非终结符A面临输入符

6、a时，如果aSELECT(A：=a)，则可以选择产生式A:=a去准确匹配。如本程序中举例说明的a.txt的文法就是一个LL（1）文法： S:=aBc|bABA:=aAb|bB:=b|02.1.2文法的左递归当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法中对任一非终结符A有推导AÞA，则称该文法是左递归的。左递归又可以分为直接左递归和间接左递归。2.1.3直接左递归若文法中的某一产生式形如AA，V*，则称该文法是直接左递归的。消除直接左递归的方法：设有产生式是关于非终结符A的直接左递归：A

7、A| （,V*，且不以A开头）对A引入一个新的非终结符A，把上式改写为：A A AA| 2.1.5间接左递归若文法中存在某一非终结符A，使得AÞA至少需要两步推导，则称该文法是间接左递归的。消除间接左递归的方法：【方法一】采用代入法把间接左递归变成直接左递归。 【方法二】直接改写文法：设有文法G10S： SA| AS 因为SÞAÞS，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将式代入式，即可得到与原文法等价的文法（可以证明）： SS| 式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：SSSS|2.2 设计数据结构

8、2.2.1 FIRST、FOLLOW集合的存储 由于FIRST集合和FOLLOW集合里都是一个一个的字符，所以用字符数组来存储比较合适。具体如下： char FIRSTNUMVN; char FOLLOWNUMVN; 2.2.2 终结符集合的存储 该集合存储着文法中一个一个的终结符，为了便于某一个终结符集中的查找定位，采用字符数组来存放是做适当不过的。具体如下： char VTSETNUMVT; 2.2.3 文法产生式的存储 文法的产生式都是形如A->a|b,因此比较复杂，此处，我自定义了一个结点类型。具体如下： Struct VNNODE char v; char firstexpre

9、ssMAX; char rightexpressMAX;char *firstptr;char *followptr;其中v存放着产生式左部的非终结符；字符数组firstptr和rightptr分别存放该终结符的两个产生式，若只有一个产生式，则rightexpress 为“ERROR”若该非终结符有产生式则将产生式固定的存放在rightexpress中。 字符指针firstptr、followptr分别指向该非终结符的FIRST集合和FOLLOW集合；MAX 为常数255； 2.2.4 文法的存储 在此考虑到一般文法的产生式不是很多，采用数组存放是比较方便的。文法的基本单位是产生式。因此数组的

10、每一个元素为上述的VNNODE类型。 具体如下： VNNODE GrammerNUMVN+1; 至此，我们可以看到设计这样的存储结构，便于算法的实现，但是也存在着一些局限性。即每个非终结符的产生式的个数最多只允许两个. 2.2.5 预测分析表的存储预测分析表可以被视为一个二维数组，它的每一行与文法的一个非终结符号相关联，而其每一列则与一个终结符号或界符#相关联。而数组中的每一个元素又是一个复合结构类型，为了将数组的第一行（终结符或#）和第一列（非终结符）与数组内部的产生式相协调，我将数组的每一个元素定义为字符指针。具体如下：char *MNUMVN+1NUMVT+1；其中NUMVN 、 NUM

11、VT分别为文法的非终结符、终结符的最大个数，在此用CONST 修饰并定义为254； 2.3 LL(1)文法的判别：一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自顶向下分析法，对此结论可以证明。然而，某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中不含左递归和左公共因子，只是LL(1)文法的必要条件。2.4 预测分析程序张表(分析表)，一个栈：预测分析表是一个MA, a形式的矩阵，a是终结符或“#” (结束符),文法E->E+T|T,T->T*F|F,F->(E

12、)|i是LL(1)分析表，栈STACK存放文法符号，栈底先放一个“#”，每个输入串后接一个“#”，设当前栈顶符号为X，当前输入符号为a，则对应的LL(1)预测分析表如下：  i+*()#EE ®TE¢ E®TE¢E¢E®¢+TE¢ E®¢ eE®¢ eTT ®FT¢ T ®FT¢T¢ T®¢ eT ®¢*FT¢T®&#

13、162; eT®¢ eFF®i   F®(E)若X=a=#，则分析成功，并停止分析过程；若X=a¹#，则把X从STACK栈顶逐出，让a指向下一个输入符号；若X是一个非终结符，则查表M。若MA,a中存在产生式，则逐出X，然后把产生式右部符号串反序入栈(若右部符号为e，则意味不推什么东西进栈)，同时应做这个产生式相应的语义动作(目前暂且不管)。若MA,a中存放出错标志，则调用ERROR。2.5 程序流程图3.详细设计3.1 预测分析表的构造对G中每个文法符号XÎVTVN，构造 FIRST(X)。连续使用下述规则，直至每

14、个FIRST集合不再增大：若XÎVT，则FIRST(X)=X；若XÎVN，且有产生式X®a，则把a加入FIRST(X) ；若Xe®也是一条产生式，则把e也加入；若X®Y是一个产生式且YÎVN，则把FIRST(Y)中的所有非e元素都加入FIRST(X)中；若X®Y1Y2Yk是一个产生式，Y1,Y2,Yi1都是非终结符，而且，对任意j(1ji1)，FIRST(Yj)都含有e，则把FIRST(Yi)中的所有非e元素加入FIRST(X)中；特别是，若所有的FIRST(Yj)均含有e，j=1, 2, ,k, 则把e加入FIRST(X)

15、中。构造MA, a对文法G的每个产生式Aa®，执行第2步和第3步；对每个终结符aÎFIRST(a)，把Aa®加入M；若ÎeFIRST(a)，则对任何bÎFOLLOW(A)把Aa®加入M；所有无定义的MA, a标上“出错标志”。程序模块实现如下： void Make_M() int i,j,k,m;for(i=0;i<=19;i+)for(j=0;j<=19;j+)Mij=-1; i=strlen(termin); termini='#' /*将#加入终结符数组*/ termini+1='0'

16、for(i=0;i<=count-1;i+) for(m=0;m+)if(non_term=lefti)break; /*m为产生式左部非终结符的序号*/for(j=0;j<=strlen(selecti)-1;j+)if(in(selectij,termin)=1)for(k=0;k+)if(termink=selectij)break; /*k为产生式右部终结符的序号*/ Mmk=i;3.2 构造FOLLOW(A)对G中每个非终结符A，构造FOLLOW(A)。连续使用下述规则，直至每个FOLLOW不再增大。对文法的开始符号S，置#于FOLLOW(S)中；若Aa®Bb是

17、一个产生式，则把FIRST(b)e加入FOLLOW(B)；若Aa®B是一个产生式，或Aa®Bb是一个产生式而eÞb，则把FOLLOW (A)加入FOLLOW(B)。对文法(: E®TE¢T®FT¢ E®¢+TE¢|e F®(E)|i T*®¢FT¢|e 其first和follow集如下：FIRST(E)=(, iFOLLOW(E)=), #FIRST(E¢)=+, eFOLLOW(E¢)=), #FIRST(T)=(, iFOLLOW(

18、T)=+, ), #FIRST(T¢)=*, eFOLLOW(T¢)=+, ), #FIRST(F)=(, iFOLLOW(F)=*, +, ), #程序代码模块实现如下：void FOLLOW(int i)int j,k,m,n,result=1;char c,temp20;c=non_teri; /*c为待求的非终结符*/temp0=c;temp1='0'merge(fo,temp,1);if(c=start) /*若为开始符号*/temp0='#'temp1='0'merge(followi,temp,1); for(j

19、=0;j<=count-1;j+)if(in(c,rightj)=1) /*找一个右部含有c的产生式*/for(k=0;k+)if(rightjk=c)break; /*k为c在该产生式右部的序号*/ for(m=0;m+)if(vm=leftj)break; /*m为产生式左部非终结符在所有符号中的序号*/if(k=strlen(rightj)-1) /*如果c在产生式右部的最后*/if(in(vm,fo)=1)merge(followi,followm,1);continue; if(Fm='0')FOLLOW(m);Fm='1'merge(follo

20、wi,followm,1);else /*如果c不在产生式右部的最后*/for(n=k+1;n<=strlen(rightj)-1;n+)empt0='0'result*=_emp(rightjn);if(result=1) /*如果右部c后面的符号串能推出*/ if(in(vm,fo)=1) /*避免循环递归*/merge(followi,followm,1);continue;if(Fm='0') FOLLOW(m); Fm='1' merge(followi,followm,1);for(n=k+1;n<=strlen(righ

21、tj)-1;n+) tempn-k-1=rightjn; tempstrlen(rightj)-k-1='0'FIRST(-1,temp);merge(followi,TEMP,2);Fi='1'3.3 构造First集模块设计FIRST()=a|=*=>a,aVT，,V*若=*=>,则规定FIRST() 当一个文法中相同左部非终结符的右部存在能=*=>的情况则必须知道该非终结符的后跟符号的集合中是否含有其它右部开始符号集合的元素。本程序设计代码如下：void first2(int i) /*i为符号在所有输入符号中的序号*/ char c,t

22、emp20;int j,k,m;char ch=''c=vi;emp(ch);if(in(c,termin)=1) /*若为终结符*/ first1i0=c; first1i1='0' else if(in(c,non_ter)=1) /*若为非终结符*/for(j=0;j<=count-1;j+) if(leftj=c) if(in(rightj0,termin)=1|rightj0='') temp0=rightj0; temp1='0'merge(first1i,temp,1);else if(in(rightj0,n

23、on_ter)=1)if(rightj0=c)continue;for(k=0;k+)if(vk=rightj0)break;if(fk='0') first2(k); fk='1'merge(first1i,first1k,2); for(k=0;k<=strlen(rightj)-1;k+)empt0='0'if(_emp(rightjk)=1&&k<strlen(rightj)-1) for(m=0;m+)if(vm=rightjk+1)break;if(fm='0')first2(m);fm=&

24、#39;1'merge(first1i,first1m,2);else if(_emp(rightjk)=1&&k=strlen(rightj)-1)temp0=''temp1='0'merge(first1i,temp,1);else break;fi='1'3.4 消除左递归模块设计欲构造行之有效的自上而下分析器，必须消除回溯。为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。在本程序里的设计思路如下：vo

25、id recur(char *point) /*完整的产生式在point中*/ int j,m=0,n=3,k;char temp20,ch;ch=c(); /*得到一个非终结符*/k=strlen(non_ter);non_terk=ch;non_terk+1='0' cout<<"此文法含有左递归，现在开始分改此含左递归的产生式："<<endl;for(j=0;j<=strlen(point)-1;j+)if(pointn=point0) /*如果|后的首符号和左部相同*/for(j=n+1;j<=strlen(poi

26、nt)-1;j+) while(pointj!='|'&&pointj!='0') tempm+=pointj+;leftcount=ch;memcpy(rightcount,temp,m);rightcountm=ch;rightcountm+1='0'm=0;count+;if(pointj='|')n=j+1;break;else /*如果|后的首符号和左部不同*/leftcount=ch;rightcount0=''rightcount1='0'count+;for(j=n;

27、j<=strlen(point)-1;j+) if(pointj!='|') tempm+=pointj; else leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1='0'printf(" count=%d ",count);m=0; count+; leftcount=point0; memcpy(rightcount,temp,m); rightcountm=ch; rightcountm+1='0'count+;

28、m=0;3.5 判断文法是否为LL（1）文法一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自顶向下分析法，对此结论可以证明。然而，某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中不含左递归和左公共因子，只是LL(1)文法的必要条件。本程序设计过程如下：int ll1() int i,j,length,result=1;char temp50;for(j=0;j<=49;j+) /*初始化*/firstj0='0' followj0='0'fi

29、rst1j0='0'selectj0='0'TEMPj='0'tempj='0'fj='0'Fj='0'for(j=0;j<=strlen(v)-1;j+) first2(j); /*求单个符号的FIRST集合*/printf("nfirst1:");for(j=0;j<=strlen(v)-1;j+)printf("%c:%s ",vj,first1j); printf("nempty:%s",empty);printf(&q

30、uot;n:n_emp:");for(j=0;j<=strlen(v)-1;j+) printf("%d ",_emp(vj);for(i=0;i<=count-1;i+) FIRST(i,righti); /*求FIRST*/printf("n");for(j=0;j<=strlen(non_ter)-1;j+) /*求FOLLOW*/if(foj=0)fo0='0' FOLLOW(j); printf("nfirst:");for(i=0;i<=count-1;i+) printf

31、("%s ",firsti);printf("nfollow:"); for(i=0;i<=strlen(non_ter)-1;i+) printf("%s ",followi);for(i=0;i<=count-1;i+) /*求每一产生式的SELECT集合*/ memcpy(selecti,firsti,strlen(firsti); selectistrlen(firsti)='0'for(j=0;j<=strlen(righti)-1;j+)result*=_emp(rightij);if(s

32、trlen(righti)=1&&righti0='')result=1;if(result=1)for(j=0;j+)if(vj=lefti)break;merge(selecti,followj,1);printf("nselect:");for(i=0;i<=count-1;i+) printf("%s ",selecti);memcpy(temp,select0,strlen(select0);tempstrlen(select0)='0'for(i=1;i<=count-1;i+) /

33、*判断输入文法是否为LL(1)文法*/ length=strlen(temp);if(lefti=lefti-1)merge(temp,selecti,1);if(strlen(temp)<length+strlen(selecti)return(0);elsetemp0='0' memcpy(temp,selecti,strlen(selecti);tempstrlen(selecti)='0'return(1);3.6 判断输入的句型是否为给用户所输入文法的句型 void syntax()/总控算法int i,j,k,m,n,p,q;int w=1;

34、char ch;char S50,str50; printf("请输入该文法的句型：");scanf("%s",str);getchar();i=strlen(str);stri='#'stri+1='0'S0='#'S1=start;S2='0'j=0;ch=strj; while(1)if(in(Sstrlen(S)-1,termin)=1) if(Sstrlen(S)-1!=ch)printf("n该符号串不是文法的句型！"); return;else if(Sst

35、rlen(S)-1='#') printf("n该符号串是文法的句型."); return;else Sstrlen(S)-1='0'j+;ch=strj;else for(i=0;i+)if(non_teri=Sstrlen(S)-1)break;for(k=0;k+)if(termink=ch)break;if(k=strlen(termin)printf("n词法错误！");return;if(Mik=-1)printf("n语法错误！");return;else m=Mik; if(rightm

36、0='')Sstrlen(S)-1='0'else p=strlen(S)-1; q=p; for(n=strlen(rightm)-1;n>=0;n-) Sp+=rightmn; Sq+strlen(rightm)='0'if(flag=1)cout<<"步骤"<<" "<<"符号栈"<<" "<<"输入串"<<endl; flag=0;printf("%d

37、%s ",w,S);w+; / cout<<S<<" "for(p=j;p<=strlen(str)-1;p+)/cout<<strp;printf("%c",strp);printf(" n");3.7 LL(1)分析中的错误处理出现下列两种情况时，说明出错a栈顶的终结符与当前输入符号不匹配；bMA, a为空发现错误，要尽快从错误中恢复过来，以便分析继续下去，跳过输入串中的一些符号直至遇到“同步符号”为止，这就涉及到同步符号集的选择问题。同时形成诊断信息、报告。4 . 程序调试程序运行说明：适应的文法类型：a、一切LL(1)文法b、含有直接左递归但可以转化为LL(1)文法的文法c、含有间接左递归但可