基于VC++的LL(1)语法分析器设计与实现.doc

基于VC+的LL（1）语法分析器设计与实现 学号：070108109基于VC+的LL（1）语法分析器设计与实现作者姓名：晏丽智 指导老师：王一宾摘要：语法分析是编译过程的核心部分，可以粗略的分为自上而下分析法和自下而上分析法。LL（1）文法是一类可以进行确定的自上而下语法分析的文法。本文首先阐述了LL（1）文法的基本理论，然后着重讨论了LL（1）语法分析器的设计，最后用VC+实现了LL（1）语法分析器。关键词：LL（1）文法，FIRST集，FOLLOW集，预测分析表0引言语法分析是编译过程的核心部分，它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。LL（1）文法是一类可以进行确定的自上而下语法分析的文法。本文讨论了LL（1）语法分析器的工作原理和过程，重点说明了FIRST集、FOLLOW集以及预测分析表的构造。1 LL（1）语法分析器的基本理论1.1 理论基础语法分析是编译过程的核心部分，它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。 语法分析器工作本质：按文法的产生式，识别输入符号串是否为一个句子，判断是否能从文法的开始符号出发推导出这个输入串。LL（1）文法是一类可以进行确定的自上而下语法分析的文法。自上而下分析方法的基本思想是从文法的开始符号出发，向下推导，推出句子；即对任何输入串，试图用一切可能的办法，从文法开始符号出发，自上而下地为输入串建立一棵语法树1。实现这种自上而下分析法存在许多困难，首先是递归问题，一个文法是含有左递归的，如果存在非终结符P，有P Pa，则含有左递归的文法将使上述的自上而下的分析过程陷入无限循环。因此，使用自上而下分析法必须消除文法的左递归。其次是回溯问题。由于回溯造成的匹配虚假现象，把已经做的一大堆语义工作推倒重来。这些事情既麻烦又费时间，所以，最好应设法消除回溯。1.2 左递归的消除直接消除见诸于产生式中的左递归是比较容易的。假定关于非终结符P的规则为P P| 其中，不以P开头。那么我们可以把P的规则改写为如下的非直接左递归形式：PPP P| (为空字)这种形式和原来的形式是等价的，也就是说，从P推出的符号串是相同的。一般而言，假定关于P的全部产生式是 PP1|P2|Pm|1|2|n 其中都不等于 ，且每个不以P开头。则改写后为 P 1P|2P|nP P 1P|2P|mP| 使用这个方法，我们容易把见诸于表面的所有直接左递归都消除掉，也就是说，把直接左递归都改成直接右递归。对于间接左递归的消除可以采用代人法把间接左递归变成直接左递归2。下面给出消除左递归的算法：如果一个文法不含回路,也不含以为右部的产生式。(1) 排序 把文法G的所有非终结符按任一种顺序排列P1、P2、P n按序执行。 (2) 代入及消除左递归for(i=1; i=n; i+)for(j=1; j ，则规定FIRST（）。对于文法符号串X(VNVT)，其办法是连续使用下面的规则，直至没个集合不在增大为止。（1） 若XVT，则FIRST（X）=X。（2）若XVN，且有产生式Xa,则把a加入到FIRST(X)中；若X也是一条产生式则把也加到FIRST（X）中。（3）若X-Y是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中；若XY1 Y2Yk是一个产生式，Y1Yi-1都是非终结符，而且，对于任何j，1ji-1，FIRST（Yj）都含有，则把FIRST（Yj）中的所有非元素都加到FIRST（X）中；特别是，若所有的FIRST（Yj）均含有，j=1，2，,k，则把加到FIRST（X）中4。2.2 构造FOLLOW集根据定义:FOLLOW（A）=a|S Aa,a VT,特别是,若S A，则规定#FOLLOW（A）。对文法中每一非终结符A，构造FOLLOW（A）的算法如下：反复使用如下产生式，直至FOLLOW集不在增大为止。(1) 对于文法的开始符号S，置#于FOLLOW(S)中(2) 若AB是一个产生式，则把FIRST()加到FOLLOW(B)中。(3) 若AB是一个产生式，或AB且=时 （即FIRST()）则把FOLLOW(A)加到FOLLOW(B)中。(4) 重复(2)、（3），直到FOLLOW集不再增大为止。在构造FOLLOW集的算法中，将第（3）条产生式解释一下：如果有句型Ba,显然a是B的后随符号，aFOLLOW（B），而AB，用它进行推导有S=Aa=Ba,于是a也是B的后随符号,a FOLLOW（B）,即FOLLOW(A)中的后随符号都是FOLLOW（B）中的后随符号。通过上面一系列讨论，我们可以找出满足构造不带回溯的LL（1）文法的条件：（1）文法不含左递归。（2）对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A1|2|n则 FIRST(i)FIRST（j）= (ij)(3)对文法中的每个非终结符A,若它存在某个候选首符集包含,则FIRST(A) FOLLOW(A) =如果一个文法G满足以上条件,则称该文法G为LL(1)文法。2.3预测分析表的构造LL(1)分析表可用一个矩阵（或二维数组）来表示，它概括了相应文法的全部信息。LL（1）分析表的每一行对应文法的一个非终结符，而每一列对应一个终结符或输入结束符“#”。LL（1）分析表可用数组MA，a表示，其中A表示非终结符（即为分析栈中的符号），a表示终结符或“#”（即为输入符号）。数组的各个入口MA，a中存放着面临输入符号a时，所应选择A的某条产生式，即指出当前推导所使用的产生式。数组中的空白入口中应填入适当的出错子程序名或编号，即此中情况下存在语法错误。数组的大小为mn，其中m是文法中非终结符，n是终结符数（外加一个结束符“#”）。预测分析程序对每个输入串的分析在总控程序控制之下进行。具体分析时是根据当前输入符号ai和分析栈顶符号Xj来决定是否查LL（1）分析表，从而根据LL（1）表决定所选的产生式，以及应该进行的相应操作5。预测分析表的构造:预测分析法的实现关键在于预测分析表，预测分析表是指分析栈中的文法符号与输入串中的符号的一种匹配关系记为MA，a其中A为分析栈中的符号，a为输入符号。构造预测分析表算法的基本思想并不复杂。例如，设A-是一个产生式，aFIRST（）。那么，当A呈现于分析栈栈顶，且a是当前的输入符号时，应当是A唯一合适的候选式。因此，MA，a中应放进产生式A。若=，而当前面临的输入符号a属于FOLLOW（A），那么，A就认为已自动得到匹配，因而，应把A放在MA，a中。根据这个基本思想，对于给定的LL（1）文法，在求出其各个产生式的可选集之后，可以按照如下的方法构造预测分析表，其构造算法是：（1）对文法G的每个产生式A执行第2步和第3步；（2）对每个终结符aFIRST（），把A加至MA，a中；（3）若FIRST（），则对任何bFOLLOW（A）把A加至MA，a中；（4）把所有无定义的，MA，a均填上“出错标志”。上述算法可用于任何文法G以构造它的分析表M。但对于某些文法，有些MA，a中可能有若干个产生式，或者说有些MA，a可能是多重定义的。如果G是左递归的或回溯的，那么M至少含有一个多重定义人口。因此，消除左递归和提取公共左因子将有助于获得无多重定义的分析表M6。2.4预测分析程序LL（1）语法分析器的核心是预测分析程序。一个预测分析程序是由三个部分组成：总控程序；预测分析表；先进后出的语法分析栈。预测分析程序实际上是一个下推自动机，其中，输入串是待分析的符号串，“#”作为其结束符号。分析栈中存放当前句型中尚待分析的文法符号，包括终结符和非终结符。栈底用“#”标记结束。在各种分析技术的实现中，总是让输入符号串后面紧跟一个“#”号，标志输入串的结束。在输入符号串之前也有标志符号“#”，预测分析程序的总控程序将把“#”事先推人分析栈。因此“#”被称为左右端标志符号，它不是文法符号，是由分析程序自动添加的7。预测分析的工作流程如下：分析开始时，首先将栈底符号“#”及文法的开始符号S依次推人分析栈的栈底，并对各条指示器置初值，此时分析栈和输入串的格局为（用箭头表示输入串指针和栈顶指针当前所指向的位置）。#S a1aiai+1an#此时，可根据栈顶的文法符号Xm的不同情况，分别处理：（1）若Xm为终结符，即XmVT，且Xm=ai“#”时，则表明栈顶符号已与当前正扫视的输入符号想匹配，此时应将Xm从栈中弹出，而且将输入指针向前移动一个位置至ai+1，从而得到如下格局： #X1X2Xm-1 a1aiai+1an#（2）若Xm为非终结符，即XmVN，则以Xm及ai组成符号对（Xm，ai）查分析表M，假设MXm，ai中存放着关于Xm的一个产生式Xm-ABC，此时，首先将Xm从分析栈中弹出，并将该产生式右部ABC的逆替换栈顶符号，即把ABC按逆序推人栈中（此即用该产生式推导了一步）。输入指针不动，从而得到新的如下： #X1X2Xm-1CBA a1aiai+1an#否则出错，即MXm，ai=“ERROR”，则调用出错程序来进行处理或宣告分析失败。（3）若Xm= ai=“#”，即输入串与分析栈均为空，则表明输入符号串已完全得到匹配，此时可宣告分析成功，结束工作，接受输入串。此时的格局如下： # a1aiai+1an#若用算法来描述，则预测分析程序的总控程序的算法如下8：BEGIN 首先把#然后把文法开始符号推进STACK栈； 把第一个输入符号读进a； FLAG：=TRUE； WHILE FLAG DO BEGIN 把STACK栈顶符号上托出去并放在X中； IF XVT THEN IF X=a THEN把下一个输入符号读进a ELSE ERROR ELSE IF X=# THEN IF X=a THEN FLAG：=FALSE ELSE ERROR ELSE IF MA，a=XX1X2XkTHEN 把Xk,Xk-1,X1一一推进STACK栈 ELSE ERROR END OF WHILE；STOPEND2.5 预测分析方法举例把上述算法应用于下列文法，可以为该文法构造预测分析表，并且对该文法利用预测分析法进行语法分析。文法G： E-E+T|T T-T*F|FF-i|（E）用预测分析法分析的步骤如下：（1）构造FIRST集和FOLLOW集由于上述文法中含有左递归，所以必须先消除左递，使文法改写为： E-TE E-+T E| T-FT T-*F T| F-i|（E）各非终结符的FIRST集如下：FIRST（E）=（，i）FIRST（E）=+FIRST（T）=（，iFIRST（T）=*FIRST（F）=（，i各非终结符的FOLLOW集为：FOLLOW（E）=#，)FOLLOW（E）=#，)FOLLOW（T）=+，)，#FOLLOW（T）=+，)，#FOLLOW（F）=*，+，)，#（2）构造预测分析表根据构造预测分析表的算法，可得上述文法的预测分析表如表1所示：表1 LL（1）预测分析表i+*（)#EE-T EE-T EEE-+ T EE-E-TT- FTT- FTTT-T-*F TT-T-FF-iF-(E)（3）对输入串进行分析下面用预测分析法的总控程序、分析栈和预测分析表对输入串i+i*i进行分析，给出输入串T的分析过程如表2所示：表2 输入串i+i*i的分析过程步骤分析栈（栈顶符号，当前输入符）剩余输入串所用产生式1#E（E，i） 查表i+i*i#E-TE2#ET（T，i） 查表i+i*i#T-FT3#ETF（F，i） 查表i+i*i#F-i4#ETi（i，i） i匹配i+i*i#5#ET（T，+） 查表+i*i#T-6#E（E，+） 查表+i*i#E-+T E7# ET+（+，+）+匹配+i*i#8# ET（T，i） 查表i*i#T-FT9#ETF（F，i） 查表i*i#F-i10#ETi（i，i） i匹配i*i#11#ET（T，*） 查表*i#T-*F T12#ETF*（*，*） *匹配*i#13#ETF（F，i） 查表i#F-i14#ETi（i，i） i匹配i#15#ET（T，#） 查表#T-16#E(E,#) 查表#E-17#3 LL（1）语法分析器的实现3.1总体设计该程序可分为如下几步，流程图如图1：（1）读入文法； （2）判断正误； （3）若无误，判断是否为LL(1)文法； （4）若是，构造分析表；（5）由总控算法判断输入符号串是否为该文法的句型。开始读入文法有效？是LL(1)文法？是是报错判断句型结束图1 程序流程图主函数设计如下：void main()int i,j;start=grammer(termin,non_ter,left,right); /*读入一个文法*/ printf(count=%d,count);printf(nstart:%c,start);strcpy(v,non_ter);strcat(v,termin);printf(nv:%s,v);printf(nnon_ter:%s,non_ter); printf(ntermin:%s,termin);printf(nright:);for(i=0;i=count-1;i+) printf(%s ,righti); printf(nleft:);for(i=0;i=count-1;i+)printf(%c ,lefti); if(validity=1) validity=judge();printf(nvalidity=%d,validity);if(validity=1) printf(n文法有效);ll=ll1();printf(nll=%d,ll);if(ll=0)printf(n该文法不是一个LL1文法！);else MM(); printf(n); for(i=0;i=19;i+) for(j=0;j=0) printf(M%d%d=%d ,i,j,Mij); printf(n); menu(); 3.2详细设计主要的程序代码说明：（1）文法的存储类型int count=0; /*分解的产生式的个数*/int number; /*所有终结符和非终结符的总数*/char start; /*开始符号*/char termin50; /*终结符号*/char non_ter50; /*非终结符号*/char v50; /*所有符号*/char first5050,follow5050; /*各产生式右部的FIRST和左部的FOLLOW集合*/char first15050; /*所有单个符号的FIRST集合*/char select5050; /*各单个产生式的SELECT集合*/char f50,F50; /*记录各符号的FIRST和FOLLOW是否已求过*/char empty20; /*记录可直接推出的符号*/char TEMP50; /*求FOLLOW时存放某一符号串的FIRST集合*/int validity=1; /*表示输入文法是否有效*/int ll=1; /*表示输入文法是否为LL(1)文法*/int M2020; /*分析表*/char choose; /*用户输入时使用*/char empt20; /*求_emp()时使用*/char fo20; /*求FOLLOW集合时使用*/文法的终结符和非终结符分别存放在termin50和non_ter50中，number是所有非终结符合终结符个数总和，start存放文法的开始符号，产生式个数存放在count中。（2）产生式存储类型char left50; /*左部*/char right5050; /*右部*/文法产生式的左部非终结符存放在字符型数组left50中，产生式右部符号串存放在字符型数组right5050中。读入一个文法时将产生式放在P5050数组中，传值到形参point中，分解产生式时完整的产生式在point中。（3）FIRST和FOLLOW集的构造void first2(int i)和void FIRST(int i,char *p)分别是求单个符号的FIRST和各产生式右部的FIRST。这里因为前面已有一个first数组，而且又用first1数组存放所有单个符号的FIRST集合，为了避免重名，命名first2。求各产生式左部的FOLLOW用void FOLLOW(int i)。其中i为符号在所有输入符号中的序号。（4）LL（1）分析表的构造void MM() 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;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;（4）其他函数设计void recur(char *point)用于分解含有左递归的产生式；void emp(char c)是用于求所有能直接推出 的符号；int _emp(char c)用于求某一符号能否推出 ，若能推出，返回1，否则返回0； int judge() 用于判断读入的文法是否正确；void syntax()是总控程序；3.3相关的运行界面截图及说明本程序的运行坏境为VC+,执行文件为LL(1).exe。进入程序后即提示信息：请输入文法的非终结符，等待用户输入文法的所有非终结符，然后按enter弹出下一个提示信息，依次要用户根据要求输入。第一阶段输入到把产生式输入完成即会出现相应的判断命令。如图2：图2 第一阶段运行界面第二阶段输入的是句型，会出现相应的预测分析并判断是否为该文法的句型。同时还有程序提示信息：是否继续（y or n）,用户输入y则继续执行，否则程序结束。如图3：图3 第二阶段运行界面4结束语本文介绍了LL（1）语法分析器的设计与实现，其主体有三个部分组成，非终结符的首终结符集、后随符号集和预测分析表，讨论了LL（1）语法分析器的工作原理和过程，重点说明了FIRST集、FOLLOW集以及预测分析表的构造，最后对语法分析器的实现程序进行分析。致谢本文能够顺利的完成，我衷心地感谢指导老师王一宾老师的悉心指导！同时也对在论文撰写过程中帮助过我的同学们致以最诚挚的谢意！参考文献1陈火旺,刘春林,谭庆平,等.程序设计语言编译原理M.北京:国防工业出版社,20042陈意云,张昱.编译原理M.北京:高等教育出版社,20033吕