词法和语法.doc

4语法分析和语法分析程序4.1 重点和难点4.1.1 语法分析程序的功能语法分析程序又简称称为分析器，它以单词串形式的源程序作为输入或分析的对象，其基本任务是：根据程序设计语言的语法规则（即定义该语言的前后文无关文法），分析源程序的语法结构，即分析如何由这些单词组成该源程序的各种语法成分（如下标变量、函数、各种表达式、各程语句等等），并在分析过程中进行语法正确性检查，产生内部形式的中间代码，供编译程序后续阶段处理。目前，已存在许多语法分析方面的方法，但就产生语法树的方向而言，可大致把它们分为自顶向下分析和自底向上分析两大类。4.1.2 自顶向下的语法分析所谓自顶向下的语法分析，是指对于给定输入串w，试图为其构造一个从文法开始符号到w的最左推导，或为w自上而下地构造一棵以S为根结点的语法树。如果这一尝试得到成功，则证明w是相应文法的一个句子；反之，则不是。在进行自顶向下的语法分析时，通常有下列两个障碍须加以解决：（1）由于采取了最左推导，故当相应方法法G中含有左递归的非终结符号时，便会使语法分析过程陷入循环不已的状况。（2）采用最左推导以实现对符号串w的匹配，实际上是一个用文法产生式的诸候选式反复进行试探的过程，这势必会出现大量的回溯，从而导致语法分析效率的大幅度下降。因此，欲实现自顶向下的语法分析，其首要任务是改造程序设计语言的文法，以消除其中的左递归和避免回溯的出现。1消除文法的左递归如果一个文法GS=(VN，VT，P，S)中的A-产生式具有如下的形式：AA1|A2|An|1|2|m其中每个i均不以A打头，则A是一个直接左递归的非终结符号。为消除此种左递归，可引入一个新的非终结符号A，并将上述A-产生式改写为A1A|2A|mAA1 A|2 A|n A即可。如果一个非终结符号A是经多步推导而出现的左递归，则可对相关产生式作代入操作，将A-产生式化成直接左递归的，再按上面的方法将左递归消除。下面，再给出一种通过将文法G=(VN，VT，P，S)表示成矩阵形式而一次消除G的全部左递归的方法。首先，令VN=X1，X2，Xn，且对G的每个产生式Xi1|2|m （i=1,2,n）可将其写成Xi=X11i+X22i+Xnni+i （i=1,2,n）其中：“=”和“+”分别代表原产生式中的“”和“|”；若原产生式中不含以Xj开头的候选式，则相应的ji=；i是原产生式中以终结符号开头的诸候选式之“和”。于是，文法G的诸产生式便可写成如下的矩阵方程或X=AB+B此方程有形如X=BA*的最小解，由于A*=I+AA*，若令A*=Z=则有X=BZZ=I+AZ其中将上述两矩阵式写成分量式，便得到一组新的产生式，设它们所构成的文法为G，则有L(G)=L(G)。另外，由于向量B的各元素的每一项均是以终结符号打头的符号串，故矩阵式X=BZ相应的各产生式不含左递归的非终结符号；与矩阵式Z=I+AZ相应的各产生式显然也不是左递归的。也就是说，通过两述两矩阵式，我们已消除了原文法G的一切左递归。2消除回溯对于给定的文法GS=(VN，VT，P，S)和给定的输入符号串w=a1a2an（aiVT），为判断w是否为L(G)中的句子，现试图为w建立一个从S出发的最左推导，设经过若干步推导后，得到 AVN (VNVT)*其中w1=a1a2ai-1，即w的一个前缀w1已从上面的推导得到匹配，现需对A继续进行推导，以期使余下的输入串aiai+1an也获得匹配。此时应使用A-产生式进行推导，现设G中的全部A-产生式为A1|2|m且对这m个候选式k（1km），要么全部k均不能推出以ai打头的符号串（此时wL(G)），要么若存在一个j，能使j推导出以ai打头的符号串，而其余的k（1km，kj）则不能推出，这样，上述推导过程在产生式选择上的试探将可避免。如果文法G中的全部产生式均满足上述要求，则消除回溯的问题自然就解决了。可见，要实现无回溯的自顶向下语法分析，对相应文法须有一定的要求。为导出文法应满足的条件，需定义候选式的终结首符集和非终结符号A的后继终结符号集如下：FIRST()=a|a，且aVT，V*FOLLOW(A)=a|S#，且aVT#；，V*于是，对于一个已化简的非左递归文法G，在进行自顶向下语法分析时，不出现回溯的必要充分条件是，对于G中的每个产生式A1|2|m，其各候选式均应满足：（1）不同的候选式不能推出以同一终结符号打头的符号串，即FIRST(i)FIRST(j)=（1i，jm；ij）（2）若有j，则其余候选式i所能推出的符号串不能以FOLLOW(A)中的终结符号开始，即有FIRST(i)FOLLOW(A)=（i1,2,m；ij）通常，我们将满足上述条件的文法称为LL(1)文法。即对于此种文法，可采用自左至右扫视源程序P，并按最左推导的方式求得与P中各符号的匹配，而且每步推导只需查看一个输入符号，就可准确地选择所用的产生式。下面，给出对给定文法G求出各个FIRST集和FOLLOW集的算法。由于每个产生式的各候选式均是一个由文法符号所组成的符号串，因此仅须给出对单个文法符号求这两个集合的方法即可。构造FIRST集合的算法对于G中的每一个文法符号XVNVT，为求FIRST(X)，可反复应用如下的规则，直到所求的FIRST集不再增大为止。（1）若XVT，则FIRST(X)=X。（2）若XVN，且有XaP(aVT)，则令aFIRST(X)；若有XP，则令FIRST(X)。（3）若XY1Y2YkP，且Y1VN，则令FIRST(Y1)FIRST(X)；而对任意的j（1ji1），YjVN，且Yje，则令FIRST(Y1)FIRST(X) （1ji）特别当FIRST(Yj) （1jk）时，令FIRST(X)。 构造FOLLOW集的算法对于G中的每一AVN，为构造FOLLOW(A)，可反复使用如下的规则，直到每个FOLLOW集不再增大为止。（1）对于文法的开始符号S，令#FOLLOW(S)。（2）对于每一ABP，令FIRST()FOLLOW(B)。（3）对于每一ABP或ABP，且FIRST(B)，则令FOLLOW(A)FOLLW(B)。用来对LL(1)文法进行自顶向下语法分析的方法主要有两种，即递归下降分析法和预测分析法。3递归下降分析法设G=(VN，VT，P，S)为LL(1)文法，并设VN=X1，X2，Xn，所谓递归下降法，是指对G的每个非终结符号Xi，都根据相应产生式各候选式的组成结构，为其构造一个子程序（或函数）Pi（），用于识别Xi所表示的语法成分。这组子程序便组成了所需的分析器。构造子程Pi（）的方法如下：（1）对于形如Xi1|2|m的产生式，在相应子程序Pi（）中，应含有判断当前输入符号a属于哪个候选式j的FIRST集，并转入该候选式相应代码段继续识别的功能。对候选式的选择可用if语句或case语句实现。（2）于形如XiY1Y2Yk（YjVNVT）的产生式，相应子程Pi（）是一个依次识别其右部各符号Yj（j=1,2,k）的过程：如果YjVT，则判断当前输入符号是否与Yj匹配；若YjVN则应有调用相应于Yj的子程序的代码。（3）对于形如Xi的产生式，在相应的子程序Pi（）中，应含有判断当前输入符号a是否属于集合FOLLOW(Xi)而决定是从Pi（）返回还是报错的代码。（4）在各个子程序Pi（）中，均应含有进行语法检查的代码。4预测分析法预测分析法是一种比递归下降法更为有效的自顶向下的语法分析方法。预测分析器由一张预测分析表（也称为LL(1)分析表）、一个表驱动程序及一个分析栈组成，其输入是一个以右界符#结尾的符号率。分析器在驱动程序的控制下，根据预测分析表的指示来完成对输入符号串的分析。对不同的文法而言，驱动程序均一样，仅预测分析表不同。因此，设计预测分析器的关键，在于根据给定文法构造其预测分析表。预测分析表可视为一个二维数组，它的每一行与文法的一个非终结符号相关联，而其每一列则与一个终结符号或界符井相关联。对于一个已给的LL(1)文法G，首先按前面所给出的算法分别求出各非终结符号的FIRST集和FOLLOW集，然后再按如下规则确定预测分析表的各个元素MA，a（AVN，aVT#）。对于文法中的每个产生式A1|2|m：（1）若aFIRST(i)，则置MA，a=“Ai”，即当当前分析栈的栈顶符号为A，而正扫视的输入符号为a时，按产生式Ai进行推导；（2）若FIRST(vj)且aFOLLOW(A)，则置MA，a=“Aj”，即在此情况下按产生式Aj进行推导；（3）除上述两种情况外，其余的一切表元素均置为“出错”。采用预测分析表的语法分析过程大致是：在分析开始时，首先将界符#和文法的开始符号S置于栈中，并使输入指示器指向输入串的首符号；然后按预测分析表的指示，逐步对栈顶非终结符号进行推导，直到所推导出的终结符号串与输入符号串完全匹配（分析成功），或分析器报错（输入串有语言错误）为止。4.1.3 自底向上的语法分析所谓自底向上的语法分析，是指从给定的输入串w=a1a2an出发，试图利用相应文法中的产生式，逐步将其归约为文法的开始符号S，即从叶结点a1,a2,an出发，试图逐步向上构造一个语法树，而其根结点恰好为S。由于上述分析过程通常采用的是最左归约（即规范归约），所以实现此种语法分析的关键，是在分析的每一步，如何寻找或确定当前句型的句柄（或应最先归约的子串），以及确定将其归约为什么非终结符号。和自顶向下的分析过程一样，实现自底向上的分析，通常也需使用一个分析栈来存放分析过程中所得的文法符号。分析开始时，在栈底放置一个界符#，然后将输入符号逐个推入栈内，一旦在分析栈的栈顶出现句柄，就用相应产生式的左部去替换这个句柄，即进行一次归约。由于归约，便得到了新的栈顶，此时再查看栈的顶部是否形成新的句柄：若是，再进行归约；反之，则继续将后续的输入符号移入栈内，并重复上述过程。若最终能将全部输入符号（不包括它的右界符#）移掉，且分析栈中只留下栈底符号#及最后一步归约所得的文法开始符号，则表明对输入串的分析已经成功。但若全部输入符号已被移掉，而分析栈却不能出现上述格局，则表明输入符号串不是文法的一个句子，其中必定存在语法错误。通常将上述过程称为“移进一归约”分析，它是最基本的自底向上的分析过程。在此基础上，依寻找句柄策略的不同，便形成了不同的自底向上的语法分析方法，如优先分析法和LR分析法等。4.1.3.1 优先分析法所谓优先分析，是指对可能在句型中相邻出现的任意两个文法符号U，R之间，都建立所谓优先关系（即UR三种关系至多有一种成立），从而可构造一个优先矩阵，尔后在分析一个句型（指规范句型）=X1X2Xi1XiXi+1Xi+kXi+k+1Xm XiVNVT时，将从左至右依次扫视中的符号，且每扫视一个符号Xi都以其后继符号Xi+1查优先矩阵，判明它们之间的优先关系，以期找到的句柄之尾符号，然后再从尾符号开始进行反向扫描，且每扫视一个符号都检查它和其前符号间的优先关系，直至找到的句柄之头符号为止。可以证明，此时中满足Xi1Xi+k+1的最左子串XiXi+1Xi+k便是规范句型的句柄。于是，按相应的产生式AXiXi+1XI+k将句柄归约为A，则得新的句型=X1X2Xi1AXi+k+1Xm再对重复进行上述操作，便可最终将其归约为文法的开始符号S。显然，如果一个文法G满足如下条件：（1）每一对文法符号U和R之间，至多只有一种优先关系；（2）任意两个不同的产生式均无相同的右部；则上述语法分析过程可按一种确定的方式来进行。此时，我们将文法G称为简单优先文法。如果我们不是考虑字汇表V中的全部文法符号，而仅考虑VT中任意两符号a和b间的优先关系（），此时的语法分析便称为算符优先分析。如果一个文法G中不含形如UAB （A，BVN）的产生式，则称G为算符文法。对一个算符文法G而言，如果它的任意两个终结符之间至多只有一种优先关系（此时称为算符优先关系），则称文法G为算符优先文法。在用算符优先分析方法进行语法分析时，每次归约的不再是句型的句柄，而是它的最左素短语。所谓素短语，是指其中至少含有一个终结符号，且不再含有其它的素短语的短语。可以证明，对于G的句型=#N1a1N2a2NjajNj+1Gj+1Nj+kaj+kNnanNn+1#其中：#为界符，aiVN，NiVT，它的最左素短语是满足关系aj1aj+k+1的最左子串NjajNj+1aj+1Nj+kaj+kNj+k+1因此，可按与简单优先分析相类的过程找到一个句型的最左素短语。然而，在寻找最左素短语的过程中，并不考虑相邻两终结符号之间可能出现的非终结符号是什么；在确定归约最左素短语所用的产生式时，也仅着眼于最左素短语中的终结符号与产生式右部相应位置上的终结符号间的匹配，但对与各非终结符号相关联的语义信息则应做相应的处理。4.1.3.2 LR分析法所谓LR分析法，乃是自左至右扫视输入符号串，并按最左归约（最右推导的逆过程）的方式来进行语法分析的方法。LR分析器由一张LR分析表、一个表驱动程序和一个分析栈组成。分析表又由动作表ACTION和状态转移表GOTO两部分组成，它们的每一行都和分析器的一个状态Si相关联。ACTION表的每一列都与一个终结符号或界符#相关联，表的元素ACTIONSi，a（aVT#）指明，当分析栈的栈顶为状态Si，且当前扫视的输入符号为a时分析器要完成的动作。GOTO表的每一列都与一个非终结符号相关联，它的元素GOTOSi，A（AVN）指明，当把出现在分析栈栈顶的句柄按一个A-产生生式归约之后所须转移到的下一状态。LR分析器在开始工作时处于它的初态S0，其分析栈的栈顶项为初始状态S0和句子左界符#，然后在驱动程序的控制下自左至右依次扫视输入串的各个符号，并根据当前分析栈栈顶所存放的状态Sm及注视的输入符号ai，按分析表元素ACTIONSm，ai的指示完成相应的动作。概括地讲，分析器共有如下四种动作：（1）ACTIONSm，ai=sj其中，s表示“移进”，j表示状态的编号，意即将当前输入符号及下一状态j入栈。（2）ACTIONSm，ai=rj其中r表示“归约”，j是所用产生式的编号，意即把在栈顶形成的句柄Xmk+1Xmk+2Xm S0S1S2SmkSmk+1Smaiai+1an#X1X2XmkXmk+1Xm用第j号产生式AXmk+1Xmk+2Xm进行归约，归约之后分析栈的内容为 S0S1S2Smkaiai+1an#X1X2XmkA再以（Smk，A）查GOTO表，设GOTOSmk，A=Sr，将此新状态入栈，便完成了一个归约动作，此时分析栈的内容为 S0S1S2SmkSraiai+1an#X1X2XmkA（3）若ACTIONSm，ai=“接受”，则表明当前已将输入串成功地分析完毕，应中止分析器的工作。（4）若ACTIONSm，ai=ERROR，则表明当前的输入串有语法错误，应由出错处理程序进行处理。可见，LR分析器的驱动程序应能正确地完成上述操作。对不同的LR分析器而言，其驱动程序都是相同的，不同的只是分析表的内容。因此，实现LR分析器的关键，就在于对给定的文法构造相应的LR分析表。根据文法特性的不同，可以有四类不同的LR分析表，即LR(0)，SLR(1)，LALR(1)和LR(1)分析表。这四类LR分析表有相内的结构，只是造表原理有所区别。此外，就语法分析的能力而言，相应的四类LR分析器也有区别，即按上述顺序依次递增。一、LR(0)分析表的构造所谓LR(0)分析，是指在语法分析的每一步，只要根据当前的栈顶状态（即根据当前分析栈中已移进或经归约所得的全部文法符号），就能确定采取何种分析动作，而无须查看输入符号。LR(0)分析器的分析能力虽然较弱，但其中所引入的概念（如活前缀、LR(0)项目等等）和方法却是构造其它几类LR分析表的基础。1规范句型的活前缀所谓活前缀，是指规范句型这样的前缀，其中不含有该句型句柄右边的任何符号。即若有最右推导：SAw=w （V*，AVN，V+，wV*T）则的任何前缀都是规范句型w的活前缀。在进行LR分析时，如果输入串无语法错误，则在分析的每一步，当前分析栈中已被移进和归约出的文法符号所组成的符号串都应是某个规范句型的一个活前缀（并且用一个置于栈顶的状态与之关联）。此句型就是该活前缀和余留输入符号相连接而形成的符号串。因此，一个LR分析器的工作过程，也就在其分析栈逐步产生规范句型活前缀的过程。一旦句型的句柄在栈顶形成，就必须用相应的产生式进行归约，从而形成新的活前缀和新的状态。可见，根据这一机制，我们便可构造一个识别给定文法全部活前缀的DFA，并据此构造相应的LR分析表。2LR(0)项目为了表征句柄与活前缀间的关系，即句柄是否已在当前活前缀中出现，以及已有多少句柄符号在其中出现，需引入LR(0)项目的概念。通过在一个产生式的右部的不同位置上加一个标记符号“”，便构成了不同的LR(0)项目。（1）当句柄已完全出现在规范句型的活前缀之中，即作为活前缀的一个后缀出现于分析栈的栈顶，则相应的LR(0)项目为“A”，并将其称为归约项目，因为此时应按产生式A归约活前缀中的句柄。（2）当句柄的一个真前缀1已出现于分析栈的栈顶，即活前缀中仅含有句柄的一部分符号，则相应的LR(0)项目为A12，此时自然期望能从余留的输入串形成句柄的后缀2。于是，若令2=X，当XVT时，相应的分析动作自然是将正扫视的输入符号移进栈中，故将相应的LR(0)项目AiX称为移进项目；而当XVN时，我们自然期望通过从余留的输入符号中归约出非终结符号X，故将相应的LR(0)项目A1X称为待约项目。（3）当活前缀中全然不含有句柄的任何符号时，相应的LR(0)项目为A，显然它是上述第二类LR(0)项目当1=时的特殊情形。通常，若一个产生式的右部有m个符号，则相应的LR(0)项目共有m+1个；但对产生式A，则相应的LR(0)项目只有一个，即“A”。另外，对一个文法GS而言，为了对各个规范句型的分析都能在同一状态下结束，通常在G中引入一新的开始符号S，且将SS作为0号产生式加入到G中，从而得到拓广的文法GS，此时项目“SS”表征G的开始符号S作为句柄已出现在栈顶，即已将输入符号串归约为S，故将此项目称为接受项目。3识别全部活前缀的DFA由于每个LR(0)项目都表征了规范句型活前缀与其句柄间的关系，因此，我们自然会想到，识别一个文法G的全部活前缀的DFA的各个状态，都可由若干个LR(0)项目所组成的项目集来定义。首先定义初态I0，因为此时分析栈的栈顶为符号S，故应将项目SS列入I0，意即期望把输入串逐步归约为开始符号S，但由于不能从输入串直接读出S，故应将一切形如S的项目也列入I0；如果的首符号仍为非终结符号A，则再将一切形如A的项目也列入I0，如此等等，直到最后列入I0的都是圆点之后为终结符号的项目为止。上述求项目集（状态）I0的过程，实际上是由I0的基本项目集SS求其闭包的过程，可记为I0=CLOSURE(SS)一般而言，设I为一项目集，则构造I的闭包CLOSURE(I)的算法如下：（1）I的每一项目都属于CLOSURE(I)；（2）若形如AX的项目属于CLOSURE(I)，且X为非终结符号，则对文法中的全部X-产生式X，项目X也属于CLOSURE(I)；（3）重复上述过程，直到CLOSURE不再增大为止。同时，为了对某一文法符号XVNVT确定状态Ii的后继状态Ij，不妨用AX代表Ii中圆点在X左边的全部项目，当分析器从余留输入串识别（即移进或归约出）X后，项目集AX必在Ij中，而且是Ij的基本项目集。于是，可定义Ij=GO(Ii，X)=CLOSURE(AX|AXIi)其中，GO称为转态函数。运用上述算法，可求出给定文法GS的项目（状态）集C=I0，I1，In，称之为项目集规范族，而且利用GO函数可确定状态间的转移，从而便能构造出识别文法GS全部活前缀的DFA如下：M=（C，VNVT，GO，I0，C）由于项目集中的每一项目与某一种分析动作（移进、归约等）相关联，因此我们自然应要求所构造的每一项目集均不含冲突的项目，即不出现下列两种情况：（1）移进项目和归约项目并存；（2）多种归约项目并存。前者称为“移进一归约”冲突，后者则称为“归约一归约”冲突。如果一个文法G的每个LR(0)项目集中均不含冲突的项目，则称G为LR(0)文法，也只有对LR(0)文法才能构造出不含冲突动作的LR(0)分析表。4构造LR(0)分析表的算法设GS为一拓广的LR(0)文法，其全部产生式从SS开始分别用整数0，1，2，进行编号；并设相应的识别全部活前缀的DFA业已作出，其各个状态I0，I1，I2，也用整数0，1，2，表示，则构造LR(0)分析表的算法如下：（1）对于每个项目集Ii中形如AX的项目，若G0(Ii，X)=Ij，且X为一终结符号a时，置ACTIONi，a=sj。但若X为非终结符号时，则仅置GOTOi,X=j。（2）若归约项目A属于Ii，设A为文法的第j个产生式，则对文法的任何终结符号或句子的右界符#（将它们统一地记为a），置ACTIONi，a=rj。（3）若接受项目SS属于Ii，则置ACTIONi,#=acc。（4）在分析表中，凡不能按上述规则填入信息的元素，均置为“出错”。二、SLR(1)分析表的构造对于给定的文法GS，如果它的某个项目集中含有突冲的项目，例如I=A1a11，A2a22，Amamm，B1，B2，Bn则当分析器处于状态I时，就会出现“移进一归约”冲突和“归约一归约”冲突。然而，若集合a1,a2,am，FOLLW(B1)，FOLLOW(B2)，FOLLOW(Bn)两两不相交，则可根据当前正扫视的输入符号a的不同，对状态为I时的冲突动作进行区分：即当a=aj时，将aj移进分析栈；当aFOLLOW(j)时，按产生式Bj将栈顶的符号串归约为Bj。上述解决冲突的规则称为SLR(1)规则，并将具有此种特性的文法称为SLR(1)文法。有了SLR(1)规则之后，只须对前述构造LR(0)分析表的算法中的规则（2）作如下的修改：“（2）若归约项目A属于Ii，设A为文法的第j个产生式，则对于任何属于FOLLOW(A)的输入符号a，置于ACTIONi，a=rj”，且其余的规则仍保持不变，就得到了构造SLR(1)分析表的算法。三、LR(1)分析表的构造1LR(1)项目前面所介绍的SLR(1)分析方法是一种比较实用的方法，其优点是状态数目少，造表算法简单易行。然而也的确存在这样的一些文法，其项目集中的“移进一归约”冲突并不能通过SLR规则得到有效的解决。其原因就在于，当一个项目集中同时出现项目A和Ba，而当前分析栈中的符号串为#时，SLR规则规定：对于当前的任何输入符号b，只要ba，且bFOLLOW(A)，就将栈顶符号串归约为A，此时分析栈的符号串为#A，然而，若文法中根本不存在以Ab为前缀的规范句型，则这种归约显然无效。因此，为了更有效地解决分析动作间的冲突，在分析过程中，当试图用产生式A归约出现在栈顶的句柄时，还应查看当前的输入符号ai，只有Aai的确是文法某一规范句型的前缀时，才允许进行这种归约。通常，我们将该输入符号ai称为向前搜索称号。为了刻画上述事实，现在需要在原来的每个LR(0)项目A中都放置一个向前搜索符号a，使之成为A，a的形式，称之为LR(1)项目。应当指出，向前搜索符号a仅对形如A，a的归约项目有意义，它表明当分析器处于该归约项目所在项目集对应的状态时，若当前的输入符号ai为a时，才能将归约为A，否则，即使aiFOLLOW(A)，也不能将归约A。对于其它非归约项目，向前搜索符号a仅起传递信息的作用。此外，为了使语法分析的每一步都能在分栈中得到一个规范句型的活前缀，还应要求每个LR(1)项目对相应的活前缀都是有效的。所谓一个LR(1)项目A，a对活前缀=有效，是指存在规范推导S*Aww wV*T且满足下列条件： （1）当w时，a是w的首符号；（2）当w=时，a是输入符号串右界符#。2识别文法全部活前缀的DFA与LR(0)文法的情况相类似，识别文法全部活前缀的DFA的每一个状态也是用一个LR(1)项目集来表示，而每一个项目集又是由若干个对相应活前缀有效的LR(1)项目组成。为了构造LR(1)项目集族，我们同样需要用到两个函数，即CLOSURE(I)及GO(I，X)。对每一LR(1)项目集I，相应的CLOSURE(I)的定义如下：（1）I中的任何LR(1)项目都属于CLOSURE(I)；（2）设项目AB，aCLOSURE(I)，并假设它对话前缀=有效，则对文法中所有形如B的产生式和每一个bFIRST(a)，形如B，b的全部项目也都对有效，故若B，b原不在CLOSURE(I)中，则应将其放入；（3）重复步骤（2），直到没有新的项目加入为止。至于函数CO(I，X)，其中I为一LR(1)项目集，X为某一文法符号，与LR(0)文法类似，我们也将它定义为：GO(I，X)=CLOSURE（J）其中J是由这样的一些LR(1)项目组成：对I中所有圆点在X左边形如AX，a的项目，其中继项目AX，aJ。注意，每一LR(1)项目与其后继项目有相同的向前搜索符号。有了上述CLOSURE(I)和GO(I，X)的定义之后，采用与LR(0)类似的方法，可构造出所给文法G的LR(1)项目集族C及状态转换图。3构造LR(1)分析表的算法对于给定的文法G，当相应的LR(1)项目集族C及GO函数构造出来之后，便可按如下的算法构造它的LR(1)分析表：（1）对于每个项目集Ii中形如AX，a的项目，若GO(Ii，X)=Ij，且当X为一终结符号a时，置ACTIONi，a=sj。但若X为一非终结符号时，则置GOTOi，X=j。（2）若归约项目A，aIi，A为文法的第j个产生式，则置ACTIONi,a=rj。（3）若项目SS，#Ii，则置ACTIONi,#=acc。（4）在分析表中，凡不能照上述规则填入信息的元素，均置为“出错”。对于一个文法G来说，若按上述算法所构造的分析表不含有多重定义的元素，则称此分析表为G的LR(1)分析表。凡具有LR(1)分析表的文法称为LR(1)文法。四、LALR(1)分析表的构造LR(1)分析方法虽然较圆满地解决了SLR(1)分析法难以解决的某些“移进一归约”和“归约一归约”冲突，可是对同一个文法而言，由于LR(1)分析表的规模远远大于相应的SLR(1)或LR(0)分析表，在具体构造LR(1)分析器时，将会遇到很大的困难。因此，就有必要寻求一种其分析表的规模与SLR(1)分析表相当，但其分析能力又不和LR(1)分析法相差太大的LR分析方法，这就是所谓的向前LR分析法，即LALR(1)分析法。如前所述，每个LR(1)项目均由两部分组成：第一部分是一个LR(0)项目，称为该LR(1)项目的核；第二部分是一个向前搜索符号的集合。当为一个文法G构造出它的LR(1)项目集族C=I0,I1,In之后，若对C中的各个项目集作一番审视就会发现，在其中有这样一些项目集，它们除向前搜索符号不同之外，各个LR(1)项目的核都彼此相同（即产生式相同，且产生式中圆点的位置也相同），我们把具有此种特性的两个LR(1)项目集称为同心集。LALR(1)分析法的基本思想是将LR(1)项目集族C中的同心项目集加以合并，以削减项目集（状态）的个数。所谓合并同心集，实际上就是将同心集中的每个LR(1)项目的向前搜索符号集对应地加以合并。对一个LR(1)文法G的项目集族C合并同心集后，便得到了新的项目集族C。对于C，我们要指出如下的事实：（1）C与同一文法的LR(0)（和SLR(1)）项目集规范族有相同的状态数。（2）设I1,I2,Im为同心的项目集，J为将其合并之后的新项目集，显然J必与它们同心；再设XVNVT#，则项目集GO(I1，X)，GO(I2，X)，GO(Im，X)也必然同心，若设这m个集合合并之后的新项目集为K，则有GO(J，X)=K，可见前面所定义的GO函数这里仍然适用。不过，合并同心集之后，向前搜索符号集已发生了变化，故在构造ACTION表时应考虑到这一点。（3）尽管C的每个项目集均不存在冲突，但经合并同心集后就有出能冲突（仅可能引入“归约一归约”冲突），此时，将不可能为文法G构造LALR(1)分析表；若C的每个项目集均不存在冲突，则相应的LALR(1)分析表可造出，此时称G为LALR(1)文法。可见，每个LALR(1)文法必然是LR(1)文法，反之则不然。综上所述，可给出构造LALR(1)分析表的算法如下。（1）对已给的拓广文法G，构造相应的LR(1)项目集族C=I0，I1，In。（2）对于C，将各LR(1)项目集按同心关系进行分组，并将同组的同心集加以合并，设所得的新项目集族为C=J0，J1，Jm，其中含有项目SS，#的项目集对应于初态。（3）若C中的项目集含有冲突项目，则G不是LALR(1)文法；否则，可按如下法则构造LALR(1)分析表； 用构造LR(1)分析表类似的方法构造ACTION表； 对于某个XVN，若有GO(Jk，X)=Jt，则置GOTO(k，X)=t。上述通过构造LR(1)项目集族和合并同心集来构造LALR(1)分析表的方式仅有理论意义而无实用价值。因为构造完整的LR(1)项目集族的时间和空间开销都很大，故应设法予以解决。迄今已有多种高效构造LALR(1)分析表的算法，其共同的特点都不是从直接构造完整的LR(1)项目集入手，而是通过构造LR(0)项目集并添加相应的向前搜索符号来形成LALR(1)项目集（请注意，对同一个文法而言，LALR(1)项目集与同心的LR(0)项目集一一对应）。这些方法已在一些语法分析器自动生成工具（如YACC，OCCS等）中得到应用。4.2 例题精选例41消除文法GS ：SSa | Ab | a ASc 的左递归解：显然，其中S，A都是左递归的非终结符号。将此文法表示为矩阵形式：令则有及展开上述矩阵式，得文法Saz11 Aa z12 z11a z11 | c z21 | e z12a z12 | c z22 z21b z11 z22bz12 | e 删除其中的无用产生式，我们有Saz11 z11a z11 | c z21 | e z21b z11 例42 已给文法 GB: B b D L eD D ; d | d L L ; s | s试构造识别L(GB)的递归下降程序。解 首先消除文法的左递归，得BbDLe DdD D;dD | e SsL L;sL | e相应的递归子程序如下：#define TOKEN_B 300/ b#define TOKEN_E 301/ e#define TOKEN_D302/ d#define TOKEN_S 303/ s#define SEMICOLON;#define TRUE1#define FALSE0int c;int B()/* for BbDLe */c= NextToken();if(c!= TOKEN_B) return FALSE;if(D()if(L() c=NextToken();if(c=TOKEN_E) return TRUE;return FALSE;int D() /* for DdD*/c=NextToken();if( c=TOKEN_D)if(Dp() return TRUE;return FALSE;int Dp() /* for D;dD | epsilon */c=NextToken();if(c=SEMICOLON)c=NextToken();if(c!=TOKEN_D) return FALSE;c=NextToken();if(Dp() return TRUE;elseif(inFollow(c,Dp) return TRUE;else return FALSE;int Lp() /* for L;sL | epsilon */c=NextToken();if(c=SEMICOLON)c=NextToken();if(c!=TOKEN_S) return FALSE;c=NextToken();if(Lp() return TRUE;elseif(inFollow(c,Lp) return TRUE;else return FALSE; int L() /* for LsL*/c=NextToken();if( c=TOKEN_S)if(Lp() return TRUE;return FALSE;例43 给定文法GE：ETEEATE | eTFTTMFT | eF(E) | iA+ | -M* | /试构造相应的LL（1）分析表，并出对句子i+i*i的LL(1)分析过程。解： 首先计算出各候选式的FIRST集及各非终结符号的FOLLOW集：产生式FIRSTFOLLOWETE (,i ,# EATEe+,-e),#TFT (,i +,-,),#T MFTe*, /e+,-,),#F(E) i ( i +,-,*, /, ),#A+-+- (,i M*/*/ (,i 相应的LL（1）分析表为i+-*/()#ETETEEATEATEeeTFTFTTeeMFTMFTeeFi(E)A+-M*/上表中，因为只填写产生式右部符号串即可表示产生式，我们省略了产生式左部符号。对i+i*i进行预测分析的过程如下：步骤分析栈余留输入串所用产生式1.#Ei+i*i#ETE2.#ETi+i*i#TFT3.#ETFi+i*i#Fi4.#ETii+i*i#5.#ET+i*i#Te6.#E+i*i#EATE7.#ETA+i*i#A+8.#ET+i*i#9.#ETi*i#TFT10.#ETFi*i#Fi11.#ETii*i#12.#ET*i#TMFT13.#ETFM*i#M*14.#ETF*i#15.#ETFi#Fi16.#ETii#17.#ET#Te18.#E#Ee19.#分析成功例44 给定文法 SAc AAS AAa Ab试构造相应的简单优先矩阵，并判断其是否为简单优先文法。若是，则用该矩阵分析句子babcc。解：首先我们指定文法符号在简单优先矩阵中的顺序为：S,A,a,b,c。1.“=”关系阵：2.作矩阵。为此，（1）作布尔矩阵（2）由BLEAD矩阵计算出BLEAD+矩阵（3）作B，为此（1）作布尔矩阵（2）计算（3）作布尔矩阵（4）计算（5）由于关系只用于栈内符号与输入符号（终结符）比较，因此，A=bc显然，该矩阵无冲突项，因此，原文法是简单优先文法。分析句子babcc的过程如下：分析栈优先关系余留输入串句柄所用产生式#babcc#abcc#bAb#A=abcc#bcc#AaAAa#Abcc#Acc#bAb#AA=cc#Ac#AcSAc#c