一个LR(1) 项目可以看成哪两个部分组成 A. 心 B. 向前搜索符集合 C. 分析表 D. 分析函数
前面所介绍的SLR(1)分析法是一种较实用的方法。其优点是状态数目少，造表算法简单，大多数程序设计语言基本上都可用SLR(1)文法来描述。然而，也的确存在这样的文法，其项目集的“移进归约”冲突不可能通过SLR(1)规则得到解决。试看下面的例子。例4?8考察文法G[S′]=({S′,S,A,B,C,D}, {a,b},,P,S′)其中，P由如下的产生式组成：0? S′→S4?B→C1?S→CbBA5?B→Db2?A→Aab6?C→a3?A→ab7?D→a识别此文法的全部活前缀的DFA见图418。其中项目集I10={S→CbBA·,A→A·ab}存在“移进归约”冲突，但因FOLLOW(S)={#}，故上述冲突可通过SLR(1)规则得到解决。然而，在项目集I8={C→a·,D→a·}中，由于FOLLOW(C)={a,b}，FOLLOW(D)={b}，即FOLLOW(C)∩FOLLOW(D)≠?，故用SLR(1)规则解决上述“归约归约”冲突无效。而且还可验证，对于任何K>0，上述文法也是非SLR(k)的，故不能通过任何SLR(k)规则使项目集I8中的“归约归约”冲突得到解决 [2]。因此，我们需要更强的LR分析法，即LR(1)分析方法来解决这一问题。对SLR(1)规则稍作分析即可发现，它对某些文法失效的原因，在于当所给的文法出现冲突的分析动作时，SLR(1)规则仅孤立地考察输入符号是否属于与归约项目A→α·相关联的集合FOLLOW(A)，以确定是否应按产生式A→α进行归约，而没有考察符号串α所在规范句型的“环境”，即没有考察α在规范句型中的“上下文”，这就具有一定的片面性。因为一旦α出现在分析栈的顶部 (设分析栈当前所存放的符号串为#δα)，且当前的输入符号a也属于FOLLOW(A)，就贸然将α归约为A，此时分析栈中的符号串将变成#δA，但若文法中并不存在以δAa为前缀的规范句型，那么，这种归约无效。例如，对于上述文法中的规范句型Cbabab，当分析达到格局I0I2I4I8[]#Cbabab(4?50)时，如果仅根据当前输入符号b∈FOLLOW(C)，就将栈顶符号a按产生式C→a归约为C，则有如下的格局：I0I2I4I6[]#CbCbab但在该文法中，根本不存在以CbCb为前缀的规范句型，因此在执行下一动作将b移进之前，分析器将报告“出错”。由此可见，在分析过程中，当试图用某一产生式A→α归约栈顶符号串α时，不仅应查看栈中符号串δα，还应向前扫视一输入符号a (我们将a称为向前搜索符号)，只有当δAa的确构成文法某一规范句型的前缀时，才能用此产生式进行归约。为了指明上述事实，应当在原来的每一LR(0)项目[A→α·β]中放置一个向前搜索符号a，使之成为[A→α·β,a]的形式，我们将此种项目称为一个LR(1)项目。同时，为了使分析的每一步都能在栈中得到一个规范句型的活前缀，还应要求每一个LR(1)项目对相应的活前缀都是有效的 (其定义在下面给出)。此外，为了克服分析动作的冲突，在必要时，我们还可将某些项目集进行分解，以便使每一个状态都能确切地指明： 当α已出现在栈顶，且面临哪些输入符号时，才能按产生式A→α将α归约为A。所谓一个LR(1)项目[A→α·β，a]对活前缀γ=δα有效，是指存在规范推导S?*δAy?δαβyy∈V*T且满足下列条件：(1) 当y≠ε时，a是y的首符号；(2) 当y=ε时，a=#。例如，对于例4?8所给文法，因有S?CbBA?CbBab?CbDbab其中，δ=Cb,α=D,β=b,y=ab,A=B，故LR(1)项目[B→D·b,a]对活前缀γ=CbD有效。又因S?*CbDbab?Cbabab其中，δ=Cb,A=D,α=a,β=ε,y=bab,故LR(1)项目[D→a·,b]对活前缀γ=Cba有效。由此也可看出，当分析器所处的格局为式(4?50)时，应当将栈顶符号a归为D，而不应将它归约为C。与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) 设项目[A→α·Bβ，a]∈CLOSURE(I)，并假设它对活前缀γ=δα有效，则对文法中所有形如B→η的产生式和每一个b∈FIRST(βa)，形如[B→·η,b]的全部项目也都对γ有效，故若[B→·η,b]原不在CLOSURE(I)中，则应将其放入。事实上，因为[A→α·Bβ，a]对γ=δα有效，则由定义我们有：s?*δAy?δαBβyy∈V*T且a∈FIRST(y)∪{#}，故可将上面的推导写成S?*δAy?δαBβaωω∈V*T∪{#}现设文法已经过化简，故不论β是否为ε，从βaω总能推出终结符号串，于是可假定βaω?*bω′又因a≠ε，有FIRST(βaω)=FIRST(βa)，从而就得到推导S?*δαBbω′由此可见，一切形如[B→·η,b]的项目也对活前缀γ=δα有效。(3) 重复步骤(2)直到没有新的项目加入为止。至于函数GO(I，X)，其中I为一LR(1)项目集，X为某一文法符号，与LR(0)文法类似，我们也将它定义为：GO(I,X)=CLOSURE(J)其中J是由这样的一些LR(1)项目组成： 对I中所有圆点在X左边形如[A→α·Xβ,a]的项目，其后继项目[A→αX·β,a]∈J。注意，每一LR(1)项目与其后继项目有相同的向前搜索符号。有了上述CLOSURE(I)和GO(I，X)的定义之后，采用与LR(0)类似的方法，可构造出所给文法G的LR(1)项目集族C及状态转换图。例如，对于上述文法，其LR(1)项目集及状态转换图如图419所示。对于给定的文法G，当相应的LR(1)项目集族C及GO函数构造出来之后，便可按如下的算法构造它的LR(1)分析表：(1) 对于每个项目集Ii中形如[A→α·Xβ,b]的项目，若GO(Ii,X)=Ij，且当X为一终结符号a时，置ACTION[i,a]=sj。但若X为一非终结符号时，则置GOTO[i,X]=j。(2) 若归约项目[A→α·,a]∈Ii，A→α为文法的第j个产生式，则置ACTION[i,a]=rj。(3) 若项目[S′→S·,#]∈Ii，则置ACTION[i,#]=acc。(4) 在分析表中，凡不能照上述规则填入信息的元素，均置为“出错”。对于一个文法G来说，若按上述算法所构造的分析表不含有多重定义的元素，则称此分析表为G的LR(1)分析表。凡具有LR(1)分析表的文法称为LR(1)文法。例如，上述文法的LR(1)分析表见表416，所以它是一个LR(1)文法。
上述每个LR(1)项目均由两部分组成： 第一部分是一个LR(0)项目，称为LR(1)项目的核；第二部分则是一个向前搜索符号集。对于移进项目而言，搜索符号对分析表的构造无影响；但对归约项目而言，则仅在当前输入符号属于该搜索符号集时，才能用相应的产生式进行归约。LR(1)分析表的这种机理，较圆满地解决了SLR(1)分析所难以解决的某些“移进归约”或“归约归约”冲突，从而使LR(1)的分析能力比SLR(1)分析有明显的提高。然而，LR(1)分析的主要缺点在于，对同一个文法而言，LR(1)分析表的规模将远远大于相应的SLR(1)或LR(0)分析表。例如，为一个C语言构造LR(0)分析表，一般大约设置300个状态即可，而构造LR(1)分析表则需上千个状态，即后者将导致时间和内存空间开销的急剧上升。因此，就有必要寻求一种其分析表的规模与SLR(1)相当，但其分析能力又不比LR(1)相差太大的LR分析方法，这就是下面我们要介绍的LALR(1)分析技术。下面，我们首先对造成LR(1)项目集族规模大幅度上升的原因进行分析，然后再设法从中找出构造高效LR分析表 (即LALR(1)分析表)的方法。为此，试看下面的例子。再考察文法G[E]：0?S→E4?T→F1?E→E+T5?F→(E)2?E→T6?F→ID3?T→T*F利用上面所给算法，为G[E]构造的LR(1)项目集族和识别活前缀的DFA如图420(a)，(b)所示 (请注意，由于图幅较大，这里将其划分为(a)，(b)两部分)。对比这两幅图我们立即就会发现，除其中的状态0和状态3之外，对于(a)中的每一状态 (LR(1)项目集)，在(b)中都有一个状态 (LR(1)项目集)与其相似。例如，比较状态7和16：在这两个项目集中，除搜索符号集不同外，各个LR(1)项目的核都彼此相同 (即产生式相同，且产生式中圆点的位置也相同)，我们把具有这种特点的两个LR(1)项目集称为同心集。所以，在图420(a)和(b)中，7/16，5/12，10/17，4/13，8/18，2/14，11/19，6/20，1/15和9/21都是同心集。显然，在LR(0)分析器中，每个“心”仅对应一个LR(0)项目集；但在LR(1)分析器中，由于向前搜索符号的不同，同一个“心”将会派生出多个同心集。这就是对同一文法而言，LR(1)项目集族远大于LR(0)项目集规范族的原因。7E→E+·T[]#+T→·T*FT→·FF→·(E)F→·ID〖〗#+*#+*#+*#+*[][]16E→E+·T[]+)T→·T*FT→·FF→·(E)F→·ID〖〗+)*+)*+)*+)*为解决上述问题，F?DeRemer提出了LALR(1)分析法。这种方法的基本思想是将LR(1)项目集族中的同心项目集加以合并，以削减项目集的个数。所谓合并同心集，实际上也就是将其中的每个LR(1)项目的向前搜索符集对应地合并在一起。例如，对于文法G[E]的同心项目集4和13，设合并后的新项目集为4/13，则有4E→T·T→T·*F〖〗#+#+*[][]13E→T·T→T·*F〖〗+)+)*[][]4/13E→T·T→T·*F〖〗#+)#+)*由于同心集的合并，对原来识别活前缀的DFA也须作相应的修改。对于LALR(1)项目集族，我们须着重指出如下几点：(1) 合并同心集也就是将同心集中每个LR(1)项目的两个组成部分 (核及向前搜索符号集)分别、对应地合并在一起。设I1,I2,…,Im为同心项目集，J是合并之后的新的项目集，显然J与Ii同心；再设X∈V∪{#}，则GO(I1,X),GO(I2,X)，…，GO(Im,X)也必然同心，若把这m个同心项目集合并后的新项目集记为K，则有GOTO(J，X)=K。可见前面定义的GOTO函数在这里仍然适用。(2) 尽管原来各LR(1)项目集均不存在冲突，但合并同心集后就有可能出现冲突。换言之，即LR(1)文法未必总是LALR(1)文法。不过，由此引入的冲突只能是“归约归约”冲突，而决不会是“移进归约”冲突。事实上，设原LR(1)项目集族中有如下两个项目集Ik：[A→α·，W1][B→β·aγ,b]Ij:[A→α·,W2][B→β·aγ，c]并设Ik与Ij均无冲突，故有W1∩{a}=?W2∩{a}=?从而(W1∪W2)∩{a}=?现将Ik与Ij合并，有Ik/j:[A→α·,W1∪W2][B→β·aγ，{b}∪{c}]若此时Ik/j有“移进归约”冲突，则必有(W1∪W2)∩{a}≠?这就与Ik与Ij无冲突的假设相矛盾。因此，合并同心集不会引入新的“移进归约”冲突。(3) 对同一个语法上正确的输入符号串而言，不论用LALR(1)分析表还是用LR(1)分析表进行分析，所经历的移进、归约序列总是相同的 (仅状态名可能不同)。然而，当输入符号串有错时，LALR分析器可能会比LR(1)分析器多进行几步归约才能报错，但决不会比LR分析器多移进输入符号。也就是说，LALR分析器虽然可能延迟了发现出错的时间，但对错误的准确定位不产生影响。(4) LALR(1)项目集族总是与同一文法的SLR(1)项目集族有同样个数的项目集。但是构造LALR项目集族的开销比SLR大。实现LALR分析对文法的要求比LR(1)严、比SLR(1)宽，但开销远小于LR(1)。权衡利弊的结果，LALR堪称为当前实现自底向上语法分析，特别是构造分析器自动生成工具的最为适用的技术。综上所述，可给出构造LALR(1)分析表的算法如下。1? 对已给的拓广文法G′，构造相应的LR(1)项目集族C={I0,I1,…,In}。2? 对于C，将各LR(1)项目集按同心关系进行分组，并将同组的同心集加以合并，设所得的新项目集族为C′={J0,J1,…,Jm}，其中含有项目[S′→·S,#]的项目集对应于初态。3? 若C′中的项目集含有冲突项目，则G′不是LALR(1)文法。否则，可按如下法则构造LALR(1)分析表：(1) 用构造LR(1)分析表类似的方法构造ACTION表；(2) 对于某个X∈VN，若有GO(Jk,X)=Jt，则置GOTO(k,X)=t。上述通过构造LR(1)项目集族和合并同心集来构造LALR分析表的方式仅有理论意义而无实用价值。因为构造完整的LR(1)项目集族的时间和空间开销都很大，故应首先设法予以解决。迄今已有多种高效构造LALR分析表的算法，其共同的特点都是不从直接构造完整的LR(1)项目集入手，而是通过构造LR(0)项目集并添加相应的向前搜索符号来形成LALR(1)项目集 (请注意，对同一个文法而言，LALR(1)项目集与同心的LR(0)项目集一一对应)。例如，OCCS/YACC构造LALR(1)项目集所采用的策略是，每当创建一新的项目集时，就检查目前是否已存在与之同心的项目集，若有这样的项目集，则只需将向前搜索符号加入其中，而不再建立新的项目集。一种更为有效的方法甚至无需构造完整的LALR(1)项目集，而仅通过各个项目集中的“核心项目”便能构造相应的LALR(1)分析表。这里所说的核心项目是指形如[S′→·S，#]的项目 (其中，S′→S是拓广文法的第1个产生式)，或者是形如[A→α·Xβ,a]的项目 (其中，α≠ε，即圆点不出现在产生式右部的最左位置)，亦即那些用于构造本项目集闭包的“基本项目”。例如，对于文法G[E]，各项目集的核心项目如图422所示。下面，我们对利用项目集的核心项目构造LALR分析表的原理进行说明。 构造ACTION表的关键在于确定“归约”和“移进”两种动作。(1) 归约动作的确定由核心项目的定义可知，任何归约项目都必然会出现在某个项目集的核心项目之中，现设项目集I的核心为K，若[A→α·,a]∈K (其中α≠ε，搜索符号如何配置下面再介绍)，我们立即可以确定： 在当前状态下所面临的输入符号为a时，应按产生式A→α进行归约，即有ACTION[I,a]=rj若α=ε，则当且仅当[B→γ·Cδ， b]∈KC?*[]rAη且a∈FIRST(ηδb)时，才能确定面临输入符号a时用产生式A→ε进行归约。由于对任何C∈VN，满足C?*[]rAη的所有非终结符号A预先能完全确定，故项目集I所引发的归约动作，仅由其核心K即能完全确定。(2) 移进动作的确定若[A→α·Xβ,b]∈KX?*[]raη(a∈VT)且上述推导的最后一步未使用ε产生式，则可确定： 状态I面临输入符号a时的动作为“移进”。其中，终结符号a可通过预先计算FIRST(X)加以确定。 对于任何项目[B→γ·Xδ,b]∈K，相应的项目[B→γX·δ,b]显然必属于某个项目集J=GO(I，X)的核心L。另外，若[B→γ·Cδ,b]∈KC?*[]rAη且A→Xβ是文法中的一个产生式，则对于任何a∈FIRST(ηδb)[A→X·β,a]∈L由于对每一对非终结符号(C，A)，是否存在关系C?*[]rAη，可采用类似于计算FIRST集的方法预先求出，故仅从I的核心同样可构造出GOTO表。 上面的讨论，是在假定每个核心项目都已配置了搜索符号的情况下进行的。现在，再回头讨论： 如何为每个LR(0)项目集的核心项目配置搜索符号，使之成为LALR项目集的核心项目。为此，我们首先考察搜索符号从项目集I传播到项目集GO(I，X)的规律。再设项目集I的核心为K，若有[B→γ·Cδ,b]∈KC?*[]rAη且A→Xβ是文法中的一个产生式，则根据上面的讨论有[A→X·β,a]∈La∈FIRST(ηδb)其中L是项目集J的核心，且J=GO(I,X)。现分如下两种情况讨论搜索符号a和b间的关系。(1) 当ηδ?*ε时，显然也有[A→X·β,b]∈L。此时，我们就说项目[A→X·β,b]中的搜索符号b是从项目[B→γ·Cδ,b]中传递过来的 (propagate)。(2) 当ηδ不能推导出ε时，a仅取决于η或δ，而与b无关，此时我们就说搜索符号a是自生的 (spotaneous)。无论a是传递的还是自生的，它总能根据项目[B→γ·Cδ,b]中的有关信息，通过上述计算获得，这便是搜索符号从项目集I传播到项目集J的规律。其次，在同一项目集中，核心项目中的搜索符号向非核心项目传播的规律与上述规律极为相似。事实上，设[B→γ·Cδ,b]∈K，而C→α是文法中的一个产生式，则[C→·α，c]是I的一个非核心项目。其中，搜索符c∈FIRST(δb)，且按如下方法确定： 若δ不能推出ε，则c是自生的；否则，c=b，即c是从上面的项目传递下来的。类似地，也可讨论搜索符号在非核心项目间的传播规律。例如，对于文法G[E]，从核心项目[S→·E，#]开始，向前搜索符号在I0中的传递和自生的情况如图423所示。设K是LR(0)项目集I的核心，X是某个文法符号，则对GO(I，X)的核心中的每一项目A→αX·β，通过程序47描述的操作 (请注意，这里使用了一个虚拟搜索符号lookahead)，可由I中的项目确定其全部自生的搜索符号，并能确定K中的哪些项目将其搜索符号传递给GO(I，X)中的项目A→αX·β。程序47确定自生搜索符号和传递搜索符号的项目for (K中的每个项目B→γ·δ){J′=CLOSURE ([B→γ·δ,lookahead]);/*计算GO函数之值 */for (J′中的每一项目[A→α·Xβ,a]){if(a!=lookahead)确定GO(I，X)核心项目[A→αX·β,a]之搜索符号a是自生的if(a==lookahead)确定GO(I，X)核心项目[A→αX·β，a]之搜索符号a是从K中项目B→γ·δ传递过来的；}}最后，我们再考虑如何给每个LR(0)项目集的核心中的各个项目都配置一个搜索符号集，以获得各个LALR(1)项目集的核心。完成此项任务的大致过程如下。(1) 为拓广文法G′构造全部LR(0)项目集的核心。(2) 首先从初始项目集I0惟一的核心项目S′→·S (其搜索符号显然为#)开始，对每个LR(0)项目集的核心和每个文法符号X，利用上面的算法，确定GO(I，X)各核心项目的自生搜索符号集，并确定从I的哪些项目将搜索符号传递到GO(I，X)的核心项目。(3) 按某种便于操作的结构，建立一张核心项目表，此项目表记录了每个项目集的各个核心项目及其相应的搜索符号集。开始时，这些搜索符号集仅是由第(2)步所确定的自生搜索符号集 (若该核心项目无自生向前搜索符号则为空)。(4) 传递每个核心项目中的自生搜索符号，直到无法再进行传递为止。即反复扫视各项目集的每个核心项目，每当访问一个核心项目i时，便根据第(2)步所获的信息，将i当前要传递的搜索符号添加到承接它的那个核心项目之中，直至没有新的搜索符号要传递为止。对一个给定的文法G而言，当它的各个LALR(1)项目集的核心构造出来之后，就能根据上面所描述的原理，为G构造相应的LALR(1)分析表。不过，尽管上述构造LALR分析表的方法效率较高，但对于常见的程序设计语言，企图用手工的方式来建立LALR分析表仍几乎是不可能的。所幸的是，目前已有一些自动生成LALR分析表的工具可资使用(如YACC)。还应当指出，在构造LR语法分析器时，尚有若干技术问题需予以考虑，如二义性文法的处理，避免按单产生式的归约，等等。前者我们将在第5章介绍语法分析器自动生成工具时再进行讨论；至于后者，由于需涉及一些语义处理及其信息传递的细节，故就不再讨论了。在结束本章时，我们还要给出如下的结论，这些结论的证明读者可参阅有关的文献(1，2，8，15)。(1) 任何LR(K)，LL(K)及简单优先文法类都是无二义性的；对于算符优先文法，如果不考虑归约所得非终结符号的名字，也可认为是无二义性的。(2) 任何二义性的文法都不可能是LR(1)(或LL(1))文法，但可借助于其它因素，如算符的优先级和结合规则以及某些语义解释等等，来构造无冲突的分析表。(3) 每个SLR(K)文法都是LR(K)文法，但却存在这样的LR(1)文法，它对任何K而言均不是SLR(K)文法。
所以为A，B
钱伊瑞杉： LL(1)就是向前只搜索1个符号,即与FIRST()匹配,如果FIRST为空则还要考虑FELLOW. LR需要构造一张LR分析表,此表用于当面临输入字符时,将它移进,规约(即自下而上分析思想),接受还是出错. LR(0)找出句柄前缀,构造分析表,...
大名县18894914441： 编译原理 A产生空和B的规约在一个项目集里是规约冲突吗 - ？
钱伊瑞杉： 如果一个项目集里有两个以上的归约项目,就是归约-归约冲突.空产生式只有一个项目,如A->. 这是一个归约项目,若集合中还有关于B的归约项目,就是归约-归约冲突
大名县18894914441： 编译原理中LR(1) 那个向前搜索符怎么求的 跪求高手解答(别只是按照书抄) - ？
钱伊瑞杉： 初始项目集中,约定第一个项目S′→ ·S,# 向前搜索符为#(#是句子结束标志,有的书采用的是其他符号) 其他项目的向前搜索符同CLOSURE有关,需要求FIRST集合. 详细内容只能先去看书,然后看例题,再做些习题
大名县18894914441： 一道构造LALR分析表的题 - ？
钱伊瑞杉： 现在来讨论构造分析表的LALR方法.这本质上是一种折衷方法.LALR分析表比规范LR分析表要小得多,能力也差一点,但它却能对付一些SLR所不能对付的情形.例如,文法(5.9)的情形. 对于同一个文法,LALR分析表和SLR分析表永远...
大名县18894914441： 怎么证明一个文法是LR(1)文法啊 - ？
钱伊瑞杉： 应该是构造的项目集规范族里没有归约归约冲突和移进规约冲突
大名县18894914441： 1、\x05移进 - 规约中,规约是的逆过程.DA.最左推导 B.移进C.接受D.最右推导2、\x05在LR(1)项目[A → .k]中,搜索符k是 .CA.终结符... - ？
钱伊瑞杉：[答案] 习题一、单项选择题 1、将编译程序分成若干个“遍”是为了 . a.提高程序的执行效率 b.使程序的结构更加清晰 c.利用有限... 可重定位指令代码 c.绝对指令代码\x05\x05\x05d.中间代码 6、使用 可以定义一个程序的意义. a.语义规则\x05\x05\x05\x05b.词...
大名县18894914441： 编译原理课程设计:证明一个文法是LR(0)文法 求大神帮忙啊 - ？
钱伊瑞杉： 这个很简单呀,如果一个项目集中不存在既含移进项目又含规约项目或者含有多个规约项目的情况,则该文发是一个LR(0)文法.多以就是要先构造你面临的项目的项目集.然后逐个检查项目集中的各个项目.有不会的继续追问.
大名县18894914441： 同一个圆中弧长比等于面积比吗,为什么 - ？
钱伊瑞杉： 同一个圆中弧长比等于弦的比,等于圆心角的比,不等于面积比.面积比有个r²的.线的比都没有平方.
大名县18894914441： 创建一个图形类rectanglr ,该类有(1)两个公有字段:length(长)和width(宽) - ？
钱伊瑞杉： 类: class Rectanglr { private double length; private double width; public Rectanglr(double length,double width) { this.length = length; this.width = width; } public double area() { return this.length* this.width; } } 实例: public static void main(String[] ...
