LR分析法的LR分析器的逻辑结构及工作原理

LR分析法的LR(0)分析表的构造~

顾名思义，LR(0)分析就是LR(K)分析当K=0的情况，亦即在分析的每一步，只要根据当前的栈顶状态 (或者说根据当前分析栈中已移进或归约出的全部文法符号)就能确定应采取何种分析动作，而无须向前查看输入符号。为了给出构造LR分析表的算法，我们首先需要引入一些非常重要的概念和术语。 由例4?6对输入串“a,b,a”的分析过程容易看出，如果所分析的输入串没有语法错误，则在分析的每一步，若将分析栈中已移进和归约出的全部文法符号与余留的输入符号串拼接起来，就形成了所给文法的一个规范句型。换言之，也就是在分析的每一步，如输入串已被扫视的部分无语法错误，则当前分析栈中的全部文法符号应当是某一规范句型的前缀。而且还不难看出，此种规范句型的前缀决不会含有句柄右边的任何符号，这是因为一旦句型的句柄在栈的顶部形成，将会立即被归约之故。以后，我们将把规范句型具有上述性质 (即不含句柄之右的任何符号)的前缀称为它的活前缀。例如，对于文法G[L]的规范句型“E,b,a” (见表412分析过程第5步)，其句柄为“b”，栈中的符号串为“E，b”，此句型的活前缀为ε，“E”，“E，”，“E,b”等。由此可见，一个LR分析器的工作过程，实质上也就是一个逐步产生 (或识别)所给文法的规范句型之活前缀的过程。同时，在分析的每一步，分析栈中的全部文法符号 (如果输入串无语法错误)应是当前规范句型的活前缀，并且与此时的栈顶状态相关联。因此，我们自然会想到，如果能构造一个识别所给文法的所有活前缀的有限自动机，那么就能很方便地构造出相应的LR分析表来。稍后我们将讨论这一问题。 上面我们已经说过，在一个规范句型的活前缀中决不含有句柄右边的任何符号。因此，活前缀与句柄的关系不外下述三种情况：(1) 其中已含有句柄的全部符号 (句柄的最右符号即为活前缀的最右符号)；(2) 其中只含句柄的一部分符号 (句柄开头的若干符号与活前缀最右的若干个符号一致)；(3) 其中全然不含有句柄的任何符号。第一种情况表明，此时某一产生式A→β的右部符号串β已出现在栈顶，因此相应的分析动作应是用此产生式进行归约。第二种情况意味着形如A→β1β2的产生式的右部子串β1已出现于栈顶，正期待着从余留输入串中看到能由β2推出的符号串。而第三种情况则意味着期望从余留输入串中能看到由某一产生式A→α的右部，即α所推出的符号串。为了刻画在分析过程中，文法的一个产生式右部符号串已有多大一部分被识别，我们可在该产生式的右部的某处加上一个圆点“·”来指示位置。例如，对于上述三种情况，标有圆点的产生式分别为A→β·，A→β1·β2以及A→·α。我们把右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。特别，对形如A→ε的产生式，相应的LR(0)项目为A→·。显然，不同的LR(0)项目反映了分析过程中栈顶的不同情况。下面我们就会看到，文法的全部LR(0)项目，将是构造识别其全部活前缀的有限自动机的基础。 在作出文法的全部LR(0)项目之后，现在用它们来构造识别全部活前缀的DFA。这种DFA的每一个状态由若干个LK(0)项目所组成的集合 (称为项目集)来表示。下面以例4?7所给出的文法为例来说明构造此种DFA的方法。首先，我们用I0表示这个DFA的初态，它预示着分析过程的开始，并且期待着将给定的输入符号串逐步归约为文法的开始符号S′。或者反过来说，我们所期待的是，从使用产生式S′→S开始，能够逐步推导出所给的输入符号串。因此，我们应将项目S′→·S列入状态I0中。换言之，也就是我们期待着将要扫视的输入串正好就是能由S推出的任何终结符号串。然而，由于不能从输入串中直接读出非终结符号S，因此我们也应当把项目S→·A以及S→·B列入到I0中。由于A和B同样是非终结符号，所以又应当将A→·aAb，A→·c和B→·aBb，B→·d列入I0中。由于最后列入I0的项目中，圆点之后都是终结符号，故I0已经“封闭”，构造项目集I0宣告结束。这样，表示初态的项目集I0由如下的项目组成：I0: S′→·SS→·AA→·aAbS→·BB→·aBbB→·dA→·c我们将项目S′→·S称为项目集I0的基本项目。上述从项目S′→·S出发构造项目集I0的过程，可用一个对其基本项目集{S′→·S}的闭包运算，即CLOSURE({S′→·S})来表示。一般地，设I为一项目集，则构造I的闭包CLOSURE(I)的算法如下：(1) I中每一项目都属于CLOSURE(I)；(2) 若形如A→α·Xβ的项目属于CLOSURE(I)，且X为非终结符号，则文法中任何X产生式的一切圆点在最左边的项目X→·γ也都属于CLOSURE(I)；(3) 重复上述过程，直至不再有新的项目加入CLOSURE(I)为止。有了初态I0之后，我们来说明如何确定从I0可能转移到的下一个状态。设X为一个文法符号 (终结符号或非终结符号)，若I0中有圆点位于X左边的项目A→α·Xβ (其中α可以为ε)，则当分析器从输入串识别出 (即移进或归约出)文法符号X后，分析器将进入它的下一个状态。设此状态为Ii，显然Ii中必含有全部形如A→αX·β的项目，我们将这样的项目称为A→α·Xβ的后继项目。对于每一文法符号X，如果存在这样的后继项目，则可能不止一个，设其组成的集合为J,J中的每个项目也就是项目集Ii的基本项目。因此，按照与上面构造项目集I0相类似的讨论，我们就有Ii=CLOSURE(J)为了指明Ii是“I0关于文法符号X的后继状态”这一事实，我们可定义一个状态转移函数GO(I,X)=CLOSURE(J)其中，I为当前状态，X为文法符号，J为I中所有形如A→α·Xβ的项目的后继项目所组成的集合，而CLOSURE(J)就是项目集I (即状态I)关于X的后继项目集 (即后继状态)。例如，对于上例，我们有：I1=GO(I0,S)=CLOSURE({S′→S·})={S′→S·}I2=GO(I0,A)=CLOSURE({S→A·})={S→A·}I3=GO(I0,B)=CLOSURE({S→B·})={S→B·}I4=GO(I0,a)=CLOSURE({A→a·Ab,B→a·Bb})={A→a·Ab, B→a·Bb, A→·aAb, B→·aBb, A→·c, B→·d}I5=GO(I0,c)=CLOSURE({A→c·})={A→c·}I6=GO(I0,d)=CLOSURE({B→d·})={B→d·}请注意，由于I0中无圆点在b之前的项目，故GO(I0,b)无定义。这样，我们求出了I0的全部后继项目集I1,I2,I3,I4,I5,I6。容易看出，由于I1,I2,I3,I5,I6诸项目集中的项目均无后继项目，因此它们都没有后继状态。对于项目集I4，我们再仿此求出它的后继状态，这些后继状态是：I7=GO(I4,A)=CLOSURE({A→aA·b})={A→aA·b}I9=GO(I4,B)=CLOSURE({B→aB·b})={B→aB·b}此外，由于GO(I4,a)=I4GO(I4,c)=I5GO(I4,d)=I6故它们均不产生新的项目集。最后，再求出I7,I9的后继项目集。它们分别是I8=GO(I7,b)=CLOSURE({A→aAb·})={A→aAb·}I10=GO(I9,b)=CLOSURE({B→aBb·})={B→aBb·}由于I8和I10已无后继项目集，所以至此我们已求出所给文法G[S]的全部项目集I0~I10，通常，我们将这些项目集的全体称为文法G[S]的LR(0)项目集规范族，并记为C={I0,I1,I2,I3,…,I10}于是，我们所要构造的识别文法G[S]全部活前缀的DFA为M=(C,V,GO,I0,C)其中： M的状态集也就是文法的LR(0)项目集规范族C={I0,I1,…,I10}；M的字母表也就是文法的字汇表V={S′，S，A，B，a,b,c,d}；M的映像也就是如上定义的状态转换函数GO；M的终态集也是C，这表明M的每一状态都是它的终态。对于上述文法G[S]，如上构造的识别其全部活前缀的DFA的状态转换图如图416所示。由于状态转换图416中的每一个状态都是终态，因此在上述DFA工作的过程中，从初态I0出发，沿着有向边所指示的方向前进，可以使DFA在所经历的任何状态上中止它的工作。当DFA到达某一状态时，我们把从初态I0出发，到达该状态所经过的全部有向边上的标记符号依次连接起来，就得到了DFA在到达该状态时，所识别出的某规范句型的一个活前缀。例如：当上述DFA处于初态I0时，它所识别的活前缀为ε；当M处于状态I3时，它所识别的活前缀为B；当M处于I4时，它所识别的活前缀为aa*；而达到I9时，它所识别的活前缀为aa*B等等。需要注意的是，对那些只含有归约项目的项目集，即M的I1,I2,I3,I5,I6,I8和I10，当M到达这些状态时，表明活前缀中已含有相应句柄的全部符号 (即句柄已在栈顶形成)，因此，我们将这些状态称为句柄识别状态。特别是当M处于状态I1时，M所识别的活前缀为S，这意味着已将所给的输入串归约为S，如果再按产生式S′→S归约一步，就得到了拓广文法G′的开始符号S′。因此，我们将状态I1称为“接受状态”，它预示着对输入串的分析已成功地完成。对于一个给定文法G的拓广文法G′，当识别它的全部活前缀的DFA作出之后，我们就可据此构造相应的LR(0)分析表了。然而，应当首先注意的是，用前述方法所构造的每一个LR(0)项目集，实质上表征了在分析过程中可能出现的一种分析状态；再根据前面对LR(0)项目的分类，项目集中的每一个项目又与某一种分析动作相关联，因此，我们自然会提出这样的要求，即每一项目集中的诸项目应当是相容的。所谓相容，是指在一个项目集中，不出现这样的情况：(1) 移进项目和归约项目并存；(2) 多个归约项目并存。如果一个文法G满足上述条件，也就是它的每个LR(0)项目集中都不含冲突项目，则称G为LR(0)文法。显然，只有当一个文法是LR(0)文法时，才能构造出不含冲突动作的LR(0)分析表来。从前面的讨论和分析，我们将不难得出构造LR(0)分析表的算法。为方便起见，我们用整数0，1，2，…表示状态I0,I1,…，而且如表411那样，也将GOTO子表中有关终结符号的各列并入ACTION子表相应的各列中去，此外，算法中形如sj和rj等记号的含义同前，此算法如下：(1) 对于每个项目集Ii中形如A→α·Xβ的项目，若GO(Ii,X)=Ij，且X为一终结符号a时，置ACTION[i,a]=sj。但若X为非终结符号时，则仅置GOTO[i,X]=j。(2) 若归约项目A→α·属于Ii，设A→α为文法的第j个产生式，则对文法的任何终结符号或句子的右界符# (将它们统一地记为a)，置ACTION[i,a]=rj。(3) 若接受项目S′→S·属于Ii，则置ACTION[i,#]=acc。(4) 在分析表中，凡不能按上述规则填入信息的元素，均置为“出错”。

1、构造它的LR(0)项目集合的DFA（即识别该文法全部活前缀的DFA）；
2、根据该DFA画出该文法的LR(0)分析表；
3、在分析表中，每格要么只有一个内容，要么没有内容，（即无冲突）则为LR(0)文法。

在逻辑上，一个LR分析器有一个输入符号串，一个下推分析栈，以及一个总控程序和分析表。LR分析器在总控程序的控制下自左至右扫视输入串的各个符号，并根据当前分析栈中所存放之文法符号的状况及正注视的输入符号，按分析表的指示完成相应的分析动作。在分析的每一时刻，分析栈中记录了迄今为止所移进或归约出的全部文法符号，即记录了从分析开始到目前为止的整个历程。因此，为了方便，对于分析过程的每一步，我们可将分析栈中所存放的全部文法符号用一种“状态”来刻画，且将此状态名置于分析栈的栈顶所示。分析刚开始时，栈中仅有一个句子的左界符#，此时分析器处于初始状态S0，它不仅刻画了分析栈中当前仅有一个符号#这一事实，而且还预示着即将扫视的输入符号应当是可作为句子首符号的那些符号。类似地，状态S1刻画了分析栈中已有符号#X1的情况，…，栈顶状态Sm则刻画了分析栈中已存在符号串#X1X2…Xm的情况，等等。此外，根据分析栈的栈顶状态，还可对当前可能遇到的输入符号进行预测。例如，对于前面所述的文法G[E]，设分析栈中已移进和归约出的符号串为#E+T时的栈顶状态为Si，则Si不仅表征了迄今扫描过的输入串部分已被归约成#E+T，而且由Si还可以作这样的预测： 若输入符号串无语法错误，则当前可遇到的输入符号仅能是+,*,)或#。显然，在栈顶状态为上述Si的情况下，若当前所扫视到的符号为*，则应将*移进栈中；当所扫视到的符号为+,)或#时，则应将E+T归约为E；若所扫视到的符号不是上述四种符号之一，则应按语法错误处理。由此可见，知道了栈顶状态Sm和正扫视到的输入符号ai，就知道了当前所需的全部有用信息，从而也就可惟一地确定当前LR分析器所应采取的动作。所以，在具体实现时，并不需要将文法符号记入分析栈中。
LR分析器的核心是一张分析表，它由两个子表组成： 其一是分析动作表；另一个为状态转移表。其中： S1,S2,…,Sn为分析器的各个状态；a1,a2,…,al为文法的全部终结符号和句子界符；X1,X2,…,Xp为文法字汇表中的全部文法符号。分析动作表中的每一个元素ACTION[Sm,ai]指明，当栈顶状态为Sm且正扫视的输入符号为ai时要完成的分析动作。状态转移表中的元素GOTO[Sm,Xi]则指明，当向分析栈中移进一个输入符号或按某一产生式进行归约之后所要转移到的下一状态。
LR分析器的工作在总控程序的控制下进行，其过程如下 (为书写方便，我们将分析栈按顺时针旋转90度)：
1?分析开始时，首先将初始状态S0及句子左界符#推入分析栈。
2?设在分析的某一步，分析栈和余留输入符号串处于如下格局：
S0S1S2…S↓m[]#X1X2…Xma↓iai+1…an#
则用当前栈顶的状态Sm及正扫视的输入符号ai组成符号对(Sm,ai)去查分析动作表，并根据分析表元素ACTION[Sm,ai]的指示采取相应的分析动作，每一分析表元素所指示的仅能是下列四种动作之一：
(1) 若ACTION[Sm,ai]=“移进”，则表明句柄尚未在栈顶部形成，正期待继续移进输入符号以形成句柄，故将当前的输入符号ai推入栈中，即
S0 S1 S2 … S↓m[]# X1 X2 … Xm aia↓i+1ai+2…an#
然后，以符号对(Sm,ai)查状态转移表，设相应的表元素GOTO[Sm,ai]=Sm+1，再将此新的状态Sm+1 (即要转移到的下一状态)推入栈中，则有如下格局：
S0 S1 S2 … Sm S↓m+1[]# X1 X2 … Xm aia↓i+1ai+2…an#
(2) 若ACTION[Sm,ai]=rj，其中rj意指按文法的第j个产生式A→Xm-r+1Xm-r+2…Xm进行归约。这表明栈顶部的符号串Xm-r+1Xm-r+2…Xm已是当前句型 (对非终结符号A)的句柄。按第j个产生式进行归约，也就是将分析栈从顶向下的r个符号 (因为该产生式右部符号串的长度为r)退出，然后再将文法符号A推入栈中，此时分析栈的格局为
S0 S1 S2 … S↓m-r[]# X1 X2 … Xm-r Aa↓iai+1…an#
然后再以(Sm-r,A)查状态转移表，设GOTO[Sm-r,A]=SK，将此新状态推入栈中，则有如下的格局：
S0S1S2…Sm-rS↓K[]#X1X2…Xm-rAa↓iai+1…an#
必须注意的是，当完成归约动作之后，输入串指示器不向前推进，它仍然指向动作前的位置。
(3) 若ACTION[Sm,ai]=“接受”则表明当前的输入串已被成功地分析完毕，应中止分析器的工作。
(4) 若ACTION[Sm,ai]=ERROR，则表明当前的输入串中有语法错误，此时应调用出错处理程序进行处理。
3?重复步骤2的工作，直到在分析的某一步，栈顶出现“接受状态”为止。此时，分析栈的最终格局应为
S0S↓z[]#Z#↓
其中，Z为文法的开始符号，Sz则为使ACTION[Sz,#]=“接受”的惟一状态 (即接受状态)。
上述所列的三个步骤，实质上是对LR分析器总控程序的一个非形式化的描述，它对任何不同的LR分析表都是适用的。顺便提及，LR分析器的输出是在用某个产生式进行归约之后，通过执行相应的语义子程序来实现的，我们将在第5章再讨论这一问题。

---

千山区14728186508： 语法分析最常用的两类方法 - ？
宾华灵津： LL分析法和LR分析法. 1、自上而下语法分析方法(LL分析法) 给定文法G和源程序串r.从G的开始符号S出发,通过反复使用产生式对句型中的非终结符进行替换(推导),逐步推导出r . 是一种产生的方法,面向目标的方法.分析的主旨为...

千山区14728186508： LR(0),SLR(1),LR(1)及LALR(1)等四种LR分析器的构造方法的区别 - ？
宾华灵津： 区别主要是构造的方法不同,以及分析能力的强弱也不一样

千山区14728186508： 编译原理中 “句子”的概念? LR(1)分析法中“L” “ R”的含义分别是? - ？
宾华灵津： 字母表上符合某种规则构成的串称作句子. L:自左至右扫描,R:最右推倒的逆过程.

千山区14728186508： 编译原理LR(1)中的R和1分别是什么意思 - ？
宾华灵津： LR分析法是一种自下而上进行规范归约的语法分析法,L指从左到右扫描输入符号串,R是指构造最右推导的逆过程.LR(1)中的1是每次搜索符号需要向前参考一步,即参考下一个符号确定当前构造.

千山区14728186508： 说明该文法是何种lr文法,并给出其相应的lr分析表 - ？
宾华灵津： 1、构造它的LR(0)项目集合的DFA(即识别该文法全部活前缀的DFA); 2、根据该DFA画出该文法的LR(0)分析表; 3、在分析表中,每格要么只有一个内容,要么没有内容,(即无冲突)则为LR(0)文法.

千山区14728186508： LR分析器的栈由状态栈和输入栈组成.() - 上学吧技能鉴定？
宾华灵津： 50岁到号月经没来过了10天有少量的血非常少正常的,有可能是绝经的前兆

千山区14728186508： 家里去除煤油烟味可以怎么做呢? ？
宾华灵津： 用煤油炉或蜂窝煤做饭, 在燃烧过程中,要产生黑色浓烟,若在煤油中 或蜂窝煤上加几滴醋,烟味即可减少或消除.