《基于vc++的ll(1)语法分析器设计与实现》由会员分享，可在线阅读，更多相关《基于vc++的ll(1)语法分析器设计与实现（12页珍藏版）》请在金锄头文库上搜索。
1、基于VC+的LL（1）语法分析器设计与实现 学号：基于VC+的LL（1）语法分析器设计与实现作者姓名：晏丽智 指导老师：王一宾摘要：语法分析是编译过程的核心部分，可以粗略的分为自上而下分析法和自下而上分析法。LL（1）文法是一类可以进行确定的自上而下语法分析的文法。本文首先阐述了LL（1）文法的基本理论，然后着重讨论了LL（1）语法分析器的设计，最后用VC+实现了LL（1）语法分析器。关键词：LL（1）文法，FIRST集，FOLLOW集，预测分析表0引言语法分析是编译过程的核心部分，它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。LL（1）文法是一类可以
2、进行确定的自上而下语法分析的文法。本文讨论了LL（1）语法分析器的工作原理和过程，重点说明了FIRST集、FOLLOW集以及预测分析表的构造。1 LL（1）语法分析器的基本理论1.1 理论基础语法分析是编译过程的核心部分，它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。 语法分析器工作本质：按文法的产生式，识别输入符号串是否为一个句子，判断是否能从文法的开始符号出发推导出这个输入串。LL（1）文法是一类可以进行确定的自上而下语法分析的文法。自上而下分析方法的基本思想是从文法的开始符号出发，向下推导，推出句子；即对任何输入串，试图用一切可能的办法，从文法开
3、始符号出发，自上而下地为输入串建立一棵语法树1。实现这种自上而下分析法存在许多困难，首先是递归问题，一个文法是含有左递归的，如果存在非终结符P，有P Pa，则含有左递归的文法将使上述的自上而下的分析过程陷入无限循环。因此，使用自上而下分析法必须消除文法的左递归。其次是回溯问题。由于回溯造成的匹配虚假现象，把已经做的一大堆语义工作推倒重来。这些事情既麻烦又费时间，所以，最好应设法消除回溯。1.2 左递归的消除直接消除见诸于产生式中的左递归是比较容易的。假定关于非终结符P的规则为P P| 其中，不以P开头。那么我们可以把P的规则改写为如下的非直接左递归形式：PPP P| (为空字)这种形式和原来的
4、形式是等价的，也就是说，从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
5、; 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
6、，则把加到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集的算法中，将第
7、（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满足以上条件,则称
8、该文法G为LL(1)文法。2.3预测分析表的构造LL(1)分析表可用一个矩阵（或二维数组）来表示，它概括了相应文法的全部信息。LL（1）分析表的每一行对应文法的一个非终结符，而每一列对应一个终结符或输入结束符“#”。LL（1）分析表可用数组MA，a表示，其中A表示非终结符（即为分析栈中的符号），a表示终结符或“#”（即为输入符号）。数组的各个入口MA，a中存放着面临输入符号a时，所应选择A的某条产生式，即指出当前推导所使用的产生式。数组中的空白入口中应填入适当的出错子程序名或编号，即此中情况下存在语法错误。数组的大小为mn，其中m是文法中非终结符，n是终结符数（外加一个结束符“#”）。预测分析
9、程序对每个输入串的分析在总控程序控制之下进行。具体分析时是根据当前输入符号ai和分析栈顶符号Xj来决定是否查LL（1）分析表，从而根据LL（1）表决定所选的产生式，以及应该进行的相应操作5。预测分析表的构造:预测分析法的实现关键在于预测分析表，预测分析表是指分析栈中的文法符号与输入串中的符号的一种匹配关系记为MA，a其中A为分析栈中的符号，a为输入符号。构造预测分析表算法的基本思想并不复杂。例如，设A-是一个产生式，aFIRST（）。那么，当A呈现于分析栈栈顶，且a是当前的输入符号时，应当是A唯一合适的候选式。因此，MA，a中应放进产生式A。若=，而当前面临的输入符号a属于FOLLOW（A），
10、那么，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至少含有一个多重定义人口。因此
11、，消除左递归和提取公共左因子将有助于获得无多重定义的分析表M6。2.4预测分析程序LL（1）语法分析器的核心是预测分析程序。一个预测分析程序是由三个部分组成：总控程序；预测分析表；先进后出的语法分析栈。预测分析程序实际上是一个下推自动机，其中，输入串是待分析的符号串，“#”作为其结束符号。分析栈中存放当前句型中尚待分析的文法符号，包括终结符和非终结符。栈底用“#”标记结束。在各种分析技术的实现中，总是让输入符号串后面紧跟一个“#”号，标志输入串的结束。在输入符号串之前也有标志符号“#”，预测分析程序的总控程序将把“#”事先推人分析栈。因此“#”被称为左右端标志符号，它不是文法符号，是由分析程序
12、自动添加的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从
