编译原理课件-7

第7章自下而上的LR(k)分析方法

LR(k)分析器是这样一种分析程序：它总是按从左至右方式扫描输入串，并按自下而上方式进行规范归约。在这种分析过程中，它至多只向前查看k个输入符号就能确定当前的动作是移进还是归约；若动作为归约，则它还能唯一地选中一个产生式去归约当前已识别出的句柄（这里称为活前缀）。若该输入串是给定文法的一个句子，则它总可以把这个输入串归约到文法的开始符号；否则报错，指明它不是该文法的一个句子。7.1LR(k)文法和LR(k)分析方法7.2LR(0)分析表的构造7.3SLR分析表的构造7.4规范LR(1)分析表的构造7.5LALR分析表的构造7.6无二义性规则的使用7.7小结7.1LR(k)文法和LR(k)分析器给定文法G，S是其开始符号。考虑该文法中一个终结符号串w的一个规范推导

S=>w1=>w2=>…=>w

假定uAv=>uxv

是上述推导中的一个推导步。A::=x是用于该推导步的产生式。对于每一个这样的推导和推导步，仅通过扫描ux和查看v中开始的k个符号就能唯一确定选用产生式A::=x，我们就称G为LR(k)文法。

LR分析器的逻辑结构

一个输入、一个输出、一个栈、一个驱动程序和一张分析表。id+id*id$SmXmSm-1Xm-1…S0LR驱动程序动作转移actiongoto输出分析动作表（ACTION）：

移进ai

和s=goto[sm,ai]进栈action[sm,ai]=归约rj

:A::=Xm-r+1Xm-r+2…Xm

接收s=goto[sm-r

,A]

错误处理LR分析器的分析表：分析动作表和goto函数表GOTO函数表：GOTO[si,xj]规定了当状态si面临文法符号xj时所应到达的下一状态。格局（构形）：（栈中符号序列，剩余输入符号串）开始：（s0,a1a2……an$)

中间：（s0x1s1x2s2…xmsm,aiai+1…an$)LR分析器的工作过程1.若action[sm

,ai]=si

则把ai,si=action[sm,ai]推进栈。格局：（s0x1s1x2s2…xmsm

aisi,ai+1…an$)2.若action[sm

,ai]=r

(A::=xm-r+1xm-r+2…xm),则格局：（s0x1s1x2s2…xm-rsm-rAs,aiai+1…an$)其中，s=goto[sm-r,A]3.若action[sm

，$]=accept,则分析结束。4.若action[sm,ai]=error,则转出错处理程序。状态ACTIONGOTOid+*()＄ETF0S5S41231S6acc2R2S7R2R23R4R4R4R44S5S48235R6R6R6R66S5S4937S5S4108S6S119R1S7R1R110R3R3R3R311R5R5R5R51E::=E+T2E::=T3T::=T*F4T::=F5F::=(E)6F::=id7.2LR(0)分析表的构造

LR分析方法的基本原理是：把每个句柄（某个产生式的右部）的识别过程划分为若干状态，每个状态从左至右识别句柄中的一个符号，若干个状态就可识别句柄左端的一部分符号。识别了句柄的这一部分就相当于识别了当前规范句型的左起部分——规范句型的活前缀。因而，对句柄的识别就变成了对规范句型活前缀的识别。

LR(0)分析程序，即在分析的每一步，仅根据当前的栈顶状态就能确定应执行何种分析动作，而无须向前查看任何输入符号。规范句型的活前缀

活前缀（ViablePrefix）是指规范句型的一个前缀，它不包含该句型的句柄右边的任何符号。活前缀和句柄的关系：1.活前缀不含有句柄的任何符号，

；2.活前缀含有句柄的部分符号，1

；3.活前缀已含有句柄的全部符号，。LR(0)项目

用圆点“”表示识别一个产生式右部符号到达的位子，若有规则AXYZ,则有下面四个项目：

AXYZ

AXYZ

AXYZ

AXYZ

另：A,A

以上项目称作LR(0)项目。项目指明在分析过程的某一时刻，已经看到一个产生式的多少。文法G的拓广文法给定文法G，S是其开始符号，我们构造一个与S相关的文法G’：它包含整个G，而且外加一个新产生式S’::=S。其中，S’是G’的开始符号，称G’为G的拓广文法。AaaVT

移进项目ABBVN待归约项目A归约项目S´S接收项目CLOSURE(I)函数设I是文法G的一个LR(0)项目集合

closure(I)是从I出发用下面三个规则构造的项目集:

1．I中每一个项目都属于closure(I)。

2．若项目A→α·Bβ

closure(I)且B→γP

则将B→·γ加进closure(I)中。

3．重复执行(2)直到closure(I)不再增大为止。goto(I,X)函数若I是G的一个LR(0)项目集,X

{VT∪VN}

则goto(I,X)=closure(J)

其中,

J={A→αX·β|当A→α·Xβ

I时}

goto(I,X)称为转移函数。项目A→αX·β称为A→α·Xβ的后继。I:A→α·XβJ:A→αX·βXLR(0)项目集规范族LR(0)项目集规范族的构造

PROCEDUREITEMS(G);BEGINC:={closure(S→S)};REPEATFORIC和X{VT

∪VN}

把goto(I,X)加入到C中

UNTILC不再增大END;最后得到的C就是拓广文法G’的LR(0)项目集规范族。DFAm=(VT∪VN∪{S},Q{项目集规范族}，

q0=closure{S→S},Q,=go(I,X))它识别文法G的所有活前缀。有效项目一个项目[A→x.y]称为对某个活前缀ux是有效的，当且仅当存在某个规范推导

S=>uAv=>uxyv其中，xy是规范句型uxyv的句柄，v是一个终结符号串。*项目A→x.y对活前缀ux有效的情况可用于判断：当发现ux已呈现于栈顶时，是应该进行归约还是进行移进。一个活前缀w的有效项目集正是从项目集规范族对应的DFA初态出发，经由标记为w的路径所到达的那个项目集。E→E+TT→T*FT→FF→(E)F→id对于活前缀w＝E+T*，从初态I0出发，经过E+T*路径到达状态集I7I7：

T→T*.FF→.(E)

F→.id①E’=>E=>E+T=>E+T*F=>E+T*id=>E+T*F*id②E’=>E=>E+T=>E+T*F=>E+T*(E)③E’=>E=>E+T=>E+T*F=>E+T*idI0:S’→.SS→.A

A→.aAb

A→.cS→.B

B→.aBb

B→.dI1:S’→S.I2:S→A.I3:S→B.I5:A→c.I6:B→d.I7:A→aA.bI8:A→aAb.I9:B→aB.bI10:B→aBb.I4:

A→a.Ab

A→.aAb

A→.cB→a.Bb

B→.aBb

B→.dSABacdcdabABb文法G(S)：S→A|BA→aAb|cB→aBb|d拓广文G’(S)：0S’→S1S→A2S→B3A→aAb4A→c5B→aBb6B→d识别活前缀的DFALR(0)文法如果文法G’的项目集规范族的每个项目集中不存在下述任何冲突项目：①移进项目和归约项目并存；②多个归约项目并存；则称文法G’为LR(0)文法。当且仅当一个文法是LR(0)文法时，才能构造出它的不含冲突动作的LR(0)分析表。构造LR(0)分析表的算法设一文法G‘的项目集规范族C＝{I0,I1,…,In},令其中每个项目集Ii的下标作为分析器的状态，令包含项目S’→.S的项目集Ik的下标k为分析器的初态，则构造LR(0)分析表的步骤为：若项目A→α.xβ∈Ii且goto(Ii,x)=Ij,x∈∑,则置ACTION[i,x]=Si，即“将状态j、符号x移进栈”；但若x∈VN，则仅置GOTO[i,x]=j。若项目A→α.∈Ii，对于任何输入符号a∈(∑∪{$})，则置ACTION[i,a]=rj，即“用第j条产生式A→α进行归约”。若项目S’→S.∈Ik，则置ACTION[k,$]=“接收”。分析表中凡不能用规则①～③填入信息的元素均置上ERROR（用空白表示）。构造LR(0)分析表的步骤小结①写出给定文法G的拓广文法G’；②写出文法G’的基本LR(0)项目——G’的LR(0)项目集；③利用CLOSURE和GOTO函数，求出相应的LR(0)项目集规范族C；④构造识别该文法全部活前缀的DFA；⑤根据算法构造LR(0)分析表。7.3SLR分析表的构造LR(0)文法所构造出来的识别活前缀的DFA中每个状态（每个项目集）不能包含冲突项目。许多冲突动作都可以通过考察有关非终结符的FOLLOW集而得到解决，即通过向前查看一个输入符号来协助解决冲突。例如：冲突项目集合Ii：

{A→α.bβ,B→γ.,C→γ.}一般，设LR(0)项目集规范族的某个项目集I中含有i个移进项目

A1→α1.a1β1A2→α1.a2β2…Ai→αi.aiβi

和j个归约项目

B1→γ1.B2→γ2.…Bj→γj.

若已知集合{a1,a2,…,ai}，FOLLOW(B1)，…，FOLLOW(Bj)两辆不相交，且没有两个FOLLOW集含有$，则I中的冲突动作可通过查看当前输入符号a属于上述j+1个集合中的哪一个集合而获得解决，即若a∈{a1,a2,…,ai}，则移进a；若A∈FOLLOW(Bk），k=1,2,…,j，则用产生式Bk进行归约；其它则报错。这种解决冲突动作的方法成为SLR(1)解决方法。构造SLR(1)分析表的算法设一文法G‘的项目集规范族C＝{I0,I1,…,In},令其中每个项目集Ii的下标作为分析器的状态，令包含项目S’→.S的项目集Ik的下标k为分析器的初态，则构造SLR(1)分析表的步骤为：若项目A→α.xβ∈Ii且goto(Ii,x)=Ij,x∈∑,则置ACTION[i,x]=Si，即“将状态j、符号x移进栈”；但若x∈VN，则仅置GOTO[i,x]=j。若项目A→α.∈Ii，对于任何输入符号a∈FOLLOW(A)，则置ACTION[i,a]=rj，即“用第j条产生式A→α进行归约”。若项目S’→S.∈Ik，则置ACTION[k,$]=“接收”。分析表中凡不能用规则①～③填入信息的元素均置上ERROR（用空白表示）。能够构造出SLR分析表的文法G称为SLR(1)文法7.4规范LR(1)分析表的构造（略）重新定义项目，使得每个项目包含两个部分，第一部分就是原来的项目本身，第二部分是由一个终结符号（可能为$）组成。重新定义后的项目称为LR(1)项目，其一般形式为

[A→α.β,a]

项目中第二部分称为向前看符号。对于β＝ε的项目[A→α.,a]，其作用在于：当相应的状态呈现于栈顶且下一个输入符号为a时，才可选用产生式A→α，将栈顶的α规约到A。构造规范LR(1)分析表的算法设一文法G‘的LR(1)项目集族C＝{I0,I1,…,In},令其中每个项目集Ii的下标作为分析器的状态，令包含项目[S’→.S,$]的项目集Ik的下标k为分析器的初态，则构造规范LR(1)分析表的步骤为：若项目[A→α.xβ,b]∈Ii且goto(Ii,x)=Ij,x∈∑,则置ACTION[i,x]=Si，即“将状态j、符号x移进栈”；但若x∈VN，则仅置GOTO[i,x]=j。若项目[A→α.,a]∈Ii，则置ACTION[i,a]=rj，即“用第j条产生式A→α进行归约”。若项目[S’→S.,$]∈Ik，则置ACTION[k,$]=“接收”。分析表中凡不能用规则①～③填入信息的元素均置上ERROR（用空白表示）。能够构造出规范LR分析表的文法G称为规范LR(1)文法7.5LALR分析表的构造（略）

LALR（向