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

南开大学计算机科学与技术学院课程设计报告（2010~2011学年度第一学期）课程名称编译原理设计题目LL(1)分析姓名学号专业班级地点教师南开大学计算机科学与技术学院课程设计报告1.需求分析语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图1所示：图1语法分析器在编译程序中的地位语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。自顶向下分析法就是语法分析办法中的一类。顾名思义，自顶向下就是从文法的开始符号出发，向下推导，推出句子。这种方法是带“回溯”的。自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。对于给定的分析文法对象，构造它的预测分析程序；并任意给一算术表达式进行分析测试，本预测分析程序能够使用分析表和栈联合控制实现LL(1)分析，本文将就编译原理中比较常用的一个表达式文法，通过递归下降语法分析法来编写分析器。文中将为您提供如何通过FIRST、FOLLOW和SELECT集合来判断LL(1)方法，然后如何用递归下降语法分析法分析LL(1)方法的基本递归流程，以及用C++语言来编程实现分析器。本程序需要首先构造文法，根据文法判断是否正确，消除左递归，判断是否为LL（1）文法，然后用户输入句型，根据句型判断是否为该文法的句型。南开大学计算机科学与技术学院课程设计报告2.概要设计自顶向下的分析算法通过在最左推导中描述出各个步骤来分析记号串输入。之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根到叶自顶向下的分析程序有两类：回溯分析程序（backtrackingparser）和预测分析程序（predictiveparser）。预测分析程序试图利用一个或多个先行记号来预测出输入串中的下一个构造，而回溯分析程序则试着分析其他可能的输入，当一种可能失败时就要求输入中备份任意数量的字符。虽然回溯分析程序比预测分析程序强大许多，但它们都非常慢，一般都在指数的数量级上，所以对于实际的编译器并不合适。递归下降程序分析和LL(1)分析一般地都要求计算先行集合，它们分别称作First集合和Follow集合。由于无需显式地构造出这些集合就可以构造出简单的自顶向下的分析程序。2.1LL(1)文法设计2.1.1LL(1)文法定义LL(1)文法是一类可以进行确定的自顶向下语法分析的文法。就是要求描述语言的文法是无左递归的和无回溯的。根据LL(1)文法的定义，对于同一非终结符A的任意两个产生式A:=a和A:=b，都要满足：SELECT(A：=a)∩SELECT(A:=b)=Ø。这样，当前非终结符A面临输入符a时，如果a∈SELECT(A：=a)，则可以选择产生式A:=a去准确匹配。如本程序中举例说明的a.txt的文法就是一个LL（1）文法：S:=aBc|bABA:=aAb|bB:=b|02.1.2文法的左递归当一个文法是左递归文法时，采用自顶向下分析法会使分析过程进入无穷循环之中。所以采用自顶向下语法分析需要消除文法的左递归性。文法的左递归是指若文法中对任一非终结符A有推导AA…，则称该文法是左递归的。左递归又可以分为直接左递归和间接左递归。2.1.3直接左递归若文法中的某一产生式形如A→Aα，α∈V*，则称该文法是直接左递归的。消除直接左递归的方法：设有产生式是关于非终结符A的直接左递归：A→Aα|β（α,β∈V*，且β不以A开头）对A引入一个新的非终结符A′，把上式改写为：A→βA′A′→αA′|ε2.1.5间接左递归若文法中存在某一非终结符A，使得AA…至少需要两步推导，则称该文法是间接左递归的。消除间接左递归的方法：【方法一】采用代入法把间接左递归变成直接左递归。【方法二】直接改写文法：设有文法G10[S]：南开大学计算机科学与技术学院课程设计报告S→Aα|β⑴A→Sγ⑵因为SAαSγα，所以S是一个间接递归的非终结符。为了消除这种间接左递归，将⑵式代入⑴式，即可得到与原文法等价的文法（可以证明）：S→Sγα|β⑶⑶式是直接左递归的，可以采用前面介绍的消除直接左递归的方法，对文法进行改写后可得文法：S→βS′S′→γαS′|ε2.2设计数据结构2.2.1FIRST、FOLLOW集合的存储由于FIRST集合和FOLLOW集合里都是一个一个的字符，所以用字符数组来存储比较合适。具体如下：charFIRST[NUMVN];charFOLLOW[NUMVN];2.2.2终结符集合的存储该集合存储着文法中一个一个的终结符，为了便于某一个终结符集中的查找定位，采用字符数组来存放是做适当不过的。具体如下：charVTSET[NUMVT];2.2.3文法产生式的存储文法的产生式都是形如A-a|b,因此比较复杂，此处，我自定义了一个结点类型。具体如下：StructVNNODE{charv;charfirstexpress[MAX];charrightexpress[MAX];char*firstptr;char*followptr;};其中v存放着产生式左部的非终结符；字符数组firstptr和rightptr分别存放该终结符的两个产生式，若只有一个产生式，则rightexpress为“ERROR”若该非终结符有ε产生式则将ε产生式固定的存放在rightexpress中。字符指针firstptr、followptr分别指向该非终结符的FIRST集合和FOLLOW集合；MAX为常数255；2.2.4文法的存储在此考虑到一般文法的产生式不是很多，采用数组存放是比较方便的。文法的基本单位是产生式。因此数组的每一个元素为上述的VNNODE类型。具体如下：南开大学计算机科学与技术学院课程设计报告VNNODEGrammer[NUMVN+1];至此，我们可以看到设计这样的存储结构，便于算法的实现，但是也存在着一些局限性。即每个非终结符的产生式的个数最多只允许两个.2.2.5预测分析表的存储预测分析表可以被视为一个二维数组，它的每一行与文法的一个非终结符号相关联，而其每一列则与一个终结符号或界符‘#’相关联。而数组中的每一个元素又是一个复合结构类型，为了将数组的第一行（终结符或‘#’）和第一列（非终结符）与数组内部的产生式相协调，我将数组的每一个元素定义为字符指针。具体如下：char*M[NUMVN+1][NUMVT+1]；其中NUMVN、NUMVT分别为文法的非终结符、终结符的最大个数，在此用CONST修饰并定义为254；2.3LL(1)文法的判别：一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自顶向下分析法，对此结论可以证明。然而，某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中不含左递归和左公共因子，只是LL(1)文法的必要条件。2.4预测分析程序——张表(分析表)，一个栈：预测分析表是一个M[A,a]形式的矩阵，a是终结符或“#”(结束符),文法E-E+T|T,T-T*F|F,F-(E)|i是LL(1)分析表，栈STACK存放文法符号，栈底先放一个“#”，每个输入串后接一个“#”，设当前栈顶符号为X，当前输入符号为a，则对应的LL(1)预测分析表如下：i+*()#EETEETEEE+TEEETTFTTFTTTT*FTTTFFiF(E)若X=a=‘#’，则分析成功，并停止分析过程；若X=a‘#’，则把X从STACK栈顶逐出，让a指向下一个输入符号；若X是一个非终结符，则查表M。若M[A,a]中存在产生式，则逐出X，然后把产生式右部符号串反序入栈(若右部符号为，则意味不推什么东西进栈)，同时应做这个产生式相应的语义动作(目前暂且不管)。若M[A,a]中存放出错标志，则调用ERROR。南开大学计算机科学与技术学院课程设计报告2.5程序流程图南开大学计算机科学与技术学院课程设计报告3.详细设计3.1预测分析表的构造对G中每个文法符号XVT∪VN，构造FIRST(X)。连续使用下述规则，直至每个FIRST集合不再增大：若XVT，则FIRST(X)={X}；若XVN，且有产生式Xa…，则把a加入FIRST(X)；若X也是一条产生式，则把也加入；若XY…是一个产生式且YVN，则把FIRST(Y)中的所有非元素都加入FIRST(X)中；若XY1Y2…Yk是一个产生式，Y1,Y2,…,Yi–1都是非终结符，而且，对任意j(1≤j≤i–1)，FIRST(Yj)都含有，则把FIRST(Yi)中的所有非元素加入FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j=1,2,…,k,则把加入FIRST(X)中。构造M[A,a]对文法G的每个产生式A，执行第2步和第3步；对每个终结符aFIRST()，把A加入M；若FIRST()，则对任何bFOLLOW(A)把A加入M；所有无定义的M[A,a]标上“出错标志”。程序模块实现如下：voidMake_M(){inti,j,k,m;for(i=0;i=19;i++)for(j=0;j=19;j++)M[i][j]=-1;i=strlen(termin);termin[i]='#';/*将#加入终结符数组*/termin[i+1]='\0';for(i=0;i=count-1;i++){for(m=0;;m++)if(non_ter[m]==left[i])break;/*m为产生式左部非终结符的序号*/for(j=0;j=strlen(select[i])-1;j++){if(in(select[i][j],termin)==1){for(k=0;;k++)if(termin[k]==select[i][j])break;/*k为产生式右部终结符的序号*/M[m][k]=i;}}}}3.2构造FOLLOW(A)对G中每个非终结符A，构造FOLLOW(A)。连续使用下述规则，直至每个FOLLOW不再增大。对文法的开始符号S，置#于FOLLOW(S)中；若AB是一个产生式，则把FIRST()\{}加入FOLLOW(B)；若AB是一个产生式，或AB是一个产生式而，则把FOLLOW(A)加入FOLLOW(B)。对文法(:ETETFTE+TE|F(E)|iTFT|其first和follow集如下：FIRST(E)={(,i}FOLLOW(E)={),#}南开大学计算机科学与技术学院课程设计报告FIRST(E)={+,}FOLLOW(E)={),#}FIRST(T)={(,i}FOLLOW(T)={+,),#}FIRST(T)={*,}FOLLOW(T)={+,),#}FIRST(F)={(,i}FOLLOW(F)={,+,),#}程序代码模块实现如下：voidFOLLOW(inti){intj,k,m,n,result=1;charc,temp[20];