第五章 语法分析—自下而上分析 自下而上分析法：即是从输入串开始，逐步进行 “归约”，直至归约到文法的开始符号； 第五章　语法分析—自下而上分析 自下而上分析法：即是从输入串开始，逐步进行 “归约”，直至归约到文法的开始符号； 或者说，从语法树的末端开始，逐步向 上“归约”，直到根结点。

第五章 语法分析—自下而上分析 5.1 自下而上分析基本问题 5.2 算符优先分析 5.3 LR分析法 5.4 语法分析器的自动产生工具YACC

5.1 自下而上分析基本问题 一、归约 1.“移进—归约”的思想： 用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分替换成（归约为）该产生式的左部符号。

5.1 自下而上分析基本问题 举例：已知文法G为(1)SaAcBe (2)Ab (3)AAb (4)Bd 及输入串abbcde 归约过程如下: e B c A a 进 9 a 进 1 b a 进 2 A a 归 3 b A a 进 4 A a 归 5 c A a 进 6 d c A a 进 7 B c A a 归 8 S 归 10 动作: 步骤:

5.1 自下而上分析基本问题 2.自下而上分析的关键: “可归约串”——如何精确定义？ 例： 从上例的步骤（５）可发现 “可归约串”的不同定义，形成了不同的自下而上的分析方法。 例： “算符优先分析”中：“最左素短语”——“可归约串” “规范归约分析”中：“句柄”——“可归约串”

5.1 自下而上分析基本问题 ３.自下而上分析的中心问题： 怎样判断栈顶的符号串的可归约性以及如何归约。 各种自下而上分析法的共同特点： 边输入单词符号（移进符号栈），边归约。 即：在从左到右移进输入串的过程中，一旦发现栈顶呈现可归约串就立即进行归约。

5.1 自下而上分析基本问题 二.规范归约简述 １.定义：令Ｇ是一个文法，Ｓ是Ｇ的开始符号， 假定αβδ是文法Ｇ的一个句型， 即Ｓ αβδ 即Ｓ αβδ * ⇒ (1)短语：若Ｓ⇒αＡδ且Ａ⇒β,则称β是句型αβδ相对 于非终结符Ａ的短语。 *　　 + (2)直接短语：若Ａ⇒β，则称β是句型αβδ相对于规则 Ａβ的直接短语。 (3)句柄：一个句型的最左直接短语称为该句型的句柄。

5.1 自下而上分析基本问题 规范归约中的概念 短语： 直接短语： 句柄： S A=>β ............... β是句型αβγ的短语仅当 S αAγ 且A β A=>β S 最左直接短语 ............... ....... ....... A γ α ................ β β

例1： E→E+T | T T→T*F | F F→(E) | i i1*i2+i3 短语： i1，i2，i3，i1*i2，i1*i2+i3 直接短语： 句柄： i1，i2，i3，i1*i2，i1*i2+i3 i1，i2，i3 i1

练习： E→E+T | T T→T*F | F F→(E) | i E+T*F+i 短语： 直接短语： 句柄： E+T*F+i, E+T*F, T*F, i T*F, i T*F

5.1 自下而上分析基本问题 例2：利用句柄对句子进行归约 对文法(1)SaAcBe (2)Ab (3)AAb (4)Bd 的句子abbcde进行归约。 句型 归约规则 abbcd e (2)Ab aAbcde (3)AAb aAcde (4)Bd aAcBe (1)SaAcBe S

5.1 自下而上分析基本问题 2.规范归约 (1)定义：设α是文法G的一个句子，那么我们称序列αn, α0=S，S为文法开始符号； 对任何i，0＜i≤n,αi-1是经把αi的句柄替换为 相应产生式的左部符号而得到的。 规范归约是关于α的一个最右推导的逆过程。 例: S ⇒ aAcBe ⇒ aAcde ⇒ aAbcde ⇒ abbcde (1) (2) (3) (4)

5.1 自下而上分析基本问题 2.规范归约 (2)规范推导：即最右推导。 规范句型：由规范推导所得到的句型，称为规范句型。 若文法G是无二义的，则规范推导(最右推导)的逆过程必然是规范归约(最左归约)。 (3)规范归约的实质：在移进过程中，当发现栈顶呈现句柄时， 就用相应产生式的左部符号进行替换。 规范归约的中心问题：如何寻找或确定一个句型的句柄。 给出了寻找句柄的不同算法就给出了不同的规范归约方法。

5.1 自下而上分析基本问题 三、符号栈的使用 1.与LL(1)方法区别： LL(1)分析: 符号栈 输入串 开始 # W# 分析成功 #S

5.1 自下而上分析基本问题 2.举例：——规范归约（课本88页例5.3） 语法分析对符号栈的使用有四类操作： “移进”——指把输入串的一个符号移进栈。 “归约”——指发现栈顶呈可归约串，并用适当的相应符号 去替换这个串。 “接受”——指宣布最终分析成功。 “出错处理” ——指发现栈顶的内容与输入串相悖，分析 工作无法正常进行，此时需调用出错处 理程序。

5.1 自下而上分析基本问题 例2：有文法： 对输入串 i1+i2*i3 的规范归约过程： E->E+T|T T->T*F|F F->(E)|i 对输入串 i1+i2*i3 的规范归约过程：

所得的结果是：用产生式序列表示语法分析树 E->E+T|T T->T*F|F F->(E)|i 动作 栈 输入缓冲区 1) 准备 # i1+i2*i3# 2) 移进 #i1 +i2*i3# 3) 归约 F→i #F +i2*i3# 4) 归约 T→F #T +i2*i3# 5) 归约 E→T #E +i2*i3# 6) 移进 #E+ i2*i3# 7) 移进 #E+i2 *i3# 8) 归约 F→i #E+F *i3# 9) 归约 T→F #E+T *i3# 10) 移进 #E+T* i3# 11) 移进 #E+T*i3 # 12) 归约 F→i #E+T*F # 13) 归约 T→T*F #E+T # 14) 归约 E→E+T #E # 15) 接受 E T E T T F F F i1 + i2 * i3 所得的结果是：用产生式序列表示语法分析树

5.2 算符优先分析 算符优先分析： 不是一种规范归约法，是一种自下而上的语法分析法，关键在于规定算符（即终结符）之间的优先顺序和结合性质，借助这种优先关系寻找“可归约串”进行归约。 特点：有利于表达式分析，宜于手工实现。

5.2 算符优先分析 算符优先分析法是自底向上分析方法中的一种，虽然它不是规范归约，但它具有分析速度快，特别适合表达式分析的特点，因而得到普遍应用。

5.2 算符优先分析 在算术表达式的运算过程中，为了确保计算过程和结果的唯一性，规定了四则运算法则，实际上就是规定了运算之间的优先顺序，如：先乘除后加减；同级运算从左向右；有括号先做括号内的运算；一目运算减(负号)的优先级高于加减低于乘除。 所谓算符优先分析法就是仿照上述算术四则运算的运算过程，而设计的一种语法分析方法。它首先要规定运算符之间的优先关系，然后利用这种关系确定句型的“可归约串”，并进行归约。

5.2 算符优先分析 一、算符优先文法及优先表构造 1.算符优先文法 算符文法：一个文法，如果它的任一产生式的右部都不 含两个相继（并列）的非终结符，即不含如 式 的产生式右部： …ＱＲ… 则我们称该文法为算符文法。

5.2 算符优先分析 一、算符优先文法及优先表构造 1.算符优先文法   实际上，在真正的算符优先分析方法中，需定义任意两个相继出现的终结符号a和b之间的优先关系(a与b之间可有一个非终结符)，一旦确定了这种优先关系，就可以用它来确定“可归约串”进行归约。

5.2 算符优先分析 1.优先关系，两个相继出现的终结符之间的优先关系有三种：

2、优先关系矩阵 + * ↑ i ( ) # ⋗ ⋖ ≖

5.2 算符优先分析 假定Ｇ是一个不含ℇ-产生式的算符文法。对于任何一对 终结符a、b，我们说： a≖ b 当且仅当 文法G中含有形如 P…ab…或Ｐ…aQb…的产生式； + (2) a⋖ b　当且仅当 G中含有形如 P…aR… 的产生式， 而R⇒b…或R⇒ Qb…； FIRSTVT(R) (3) a⋗ b　当且仅当 G中含有形如 P…Rb…的产生式， 而R⇒ …a或R⇒ …aQ 。 + LASTVT(R) 算符优先文法：如果一个算符文法G中的任何终结符对(a,b) 至多只满足下述三关系之一： a≖ b，a⋖ b，a⋗ b 则称G是一个算符优先文法。

5.2 算符优先分析 构造集合FIRSTVT(P): 构造集合LASTVT(P): 按定义，我们用以下两条规则构造集合FIRSTVT(P)： (1)若有产生式Pa…或PQa…，则a∈FIRSTVT(P)； (2)若a∈FIRSTVT(Q), 且有产生式PQ…, 则a∈FIRSTVT(P)。 构造集合LASTVT(P): 按定义，我们用以下两条规则构造集合LASTVT(P)： (1)若有产生式P…a或P…aQ，则a∈LASTVT(P)； (2)若a∈LASTVT(Q), 且有产生式P…Q，则a∈LASTVT(P)。 返回

5.2 算符优先分析 FIRSTVT(E)= FIRSTVT(T)= FIRSTVT(F)= FIRSTVT(P)= {+, 文法G：(1)EE+T|T (2)TT*F|F (3)FP↑F|P (4)P(E)|i FIRSTVT(E)= FIRSTVT(T)= FIRSTVT(F)= FIRSTVT(P)= {+, *,↑,(,i} LASTVT(E)= LASTVT(T)= LASTVT(F)= LASTVT(P)= {+, *,↑,),i} {*, ↑,(,i} {*, ↑,),i} {↑, (,i} {↑, ),i} {(,i} { ),i}

5.2 算符优先分析 2.构造优先表 （1）a≖b：找出满足“≖ ”的所有终结符对。 （2）a⋖b，a⋗b：找出满足“⋖”和“⋗”的所有终结符对。 (借助于FIRSTVT(P)和LASTVT(P)实现) a⋖b：有形如…aP…的候选,且∀b∈FIRSTVT(P)； a⋗b：有形如…Pb…的候选,且∀a∈LASTVT(P)。 （3）构造出优先表

5.2 算符优先分析 另:“＃”是作为语句的起始和结束标记，认为存在候选式： #开始符号# （1）# ≖ # （2）# ⋖ FIRSRVT(开始符号） （3）LAVTVT(开始符号） ⋗ #

5.2 算符优先分析 例：优先关系和优先表 考虑文法G：(1)EE+T|T (2)TT*F|F (3)FP↑F|P (4)P(E)|i FIRSTVT(E)= FIRSTVT(T)= FIRSTVT(F)= FIRSTVT(P)= {+, {*, {↑, {(,i} (,i} ↑,(,i} *,↑,(,i} LASTVT(E)= LASTVT(T)= LASTVT(F)= LASTVT(P)= { ),i} ),i} ↑,),i} *,↑,),i}

5.2 算符优先分析 按定义，我们可得文法G终结符对的优先关系表,如下所示: + * ↑ i ( ) # (1)EE+T|T (2)TT*F|F (3)FP↑F|P (4)P(E)|i

1)‘=’关系 由产生式(0)和(6),得 #=#， ( = ) FIRSTVT(E)= FIRSTVT(T)= FIRSTVT(F)= FIRSTVT(P)= {+, {*, {↑, {(,i} (,i} ↑,(,i} *,↑,(,i} LASTVT(E)= LASTVT(T)= LASTVT(F)= LASTVT(P)= { ),i} ),i} ↑,),i} *,↑,),i} (0)E’→#E# (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→PF|P (6) P→(E) (7) P→i 1)‘=’关系 由产生式(0)和(6),得 #=#， ( = ) 2）‘<’关系 找形如A→…aB…的产生式 #E：则 #<FIRSTVT(E) +T: 则 +<FIRSTVT(T) *F: 则 *<FIRSTVT(F) F: 则 <FIRSTVT(F) (E: 则 (<FIRSTVT(E) 3)‘>’关系 找形如：A→…Bb…的产生式 E#: 则 LASTVT(E)># E+: 则 LASTVT(E)>+ T*: 则 LASTVT(T)>* P: 则 LASTVT(P)> E): 则 LASTVT(E)>)

返回 按定义,我们可得文法G终结符对的优先关系表,如下所示: + * ↑ i ( ) # ⋗ ⋖ ≖ 对于G的任何终结对(a,b)，至多只有一种关系成立。 因此，G是一个算符优先文法。 返回

5.2 算符优先分析 练习：现有文法如下，判断该文法是不是算符优先文法。 (1)SV (2)VT|ViT (3)TF|T+F (4)F)V*|( FIRSTVT(S)= FIRSTVT(V)= FIRSTVT(T)= FIRSTVT(F)= {i,+ ,),(} {+,),(} {),(} LASTVT(S)= LASTVT(V)= LASTVT(T)= LASTVT(F)= { *,(} {i,+,*,(} {+,*,( } {i,+ ,),(}

5.2 算符优先分析 (1)S#V# (2)VT (3)VViT (4)TF (5)TT+F (6)F( (7)F)V* i FIRSTVT(S)= FIRSTVT(V)= FIRSTVT(T)= FIRSTVT(F)= {i,+ ,),(} {+,),(} {),(} LASTVT(E)= LASTVT(T)= LASTVT(F)= LASTVT(P)= { *,(} {i,+,*,(} {+,*,( } {i,+ ,),(} (1)S#V# (2)VT (3)VViT (4)TF (5)TT+F (6)F( (7)F)V* i + * ( ) # ⋗ ⋖ ≖

5.2 算符优先分析 二、算符优先分析算法 1.最左素短语 素短语：是指这样的一个短语，它至少含有一个终结符， 并且, 除它自身之外不再含任何更小的素短语。 最左素短语：指处于句型最左边的那个素短语。

文法G[E]： (1) E→E+T (2) E→T (3) T→T 文法G[E]： (1) E→E+T (2) E→T (3) T→T*F (4) T→F (5) F→PF|P (6) P→(E) (7) P→i E E + T F E + T T T * F i 素短语为：T*F， i 句型T+T*F+i 其短语有： T+T*F+i T+T*F T T*F i 最左素短语为：T*F

练习１： 练习２： E→E+T | T T→T*F | F F→(E) | i (1)EE+T|T (2)TT*F|F Ｔ＋Ｔ＊Ｆ 练习２：　　　　　　　 (1)EE+T|T (2)TT*F|F (3)FP↑F|P (4)P(E)|i Ｐ＊Ｐ＋ｉ

5.2 算符优先分析 一个算符优先文法G的任何句型的最左素短语是满 足如下条件的最左子串：Njaj…NiaiNi+1 aj-1⋖ aj 句型的一般形式： #N1a1N2a2… aj-1 Njaj…NiaiNi+1　ai+1 … NnanNn+1# #N1a1N2a2… aj-1 　　Ｎ　　　 ai+1 … NnanNn+1# 一个算符优先文法G的任何句型的最左素短语是满 足如下条件的最左子串：Njaj…NiaiNi+1 aj-1⋖ aj aj≖ aj+1,… ,ai-1≖ ai ai⋗ ai+1

5.2 算符优先分析 2.算法 过程：读入一个输入符号a, 然后比较栈顶终结符—a。 S［］—存放“文法符号”的分析栈 ｊ—始终指向VT符号 ｋ—始终指向栈顶 ａ—存放“输入符号”的字符变量 Ｑ—用于存放待比较的终结符号：Ｓ［j］⋖Ｑ

aj-1⋖ aj≖ aj+1,……,ai-1≖ ai ⋗ ai+1 k:=1; S[k]:=‘#’; REPEAT 把下一个输入符号读进a中； IF S[k]∈VT THEN j:=k ELSE j:=k-1; aj-1⋖ aj≖ aj+1,……,ai-1≖ ai ⋗ ai+1 S[j] Q S[k]=Q a WHILE S[j]⋗a DO BEGIN REPEAT Q:=S[j]; IF S[j-1]∈VT THEN j:=j-1 ELSE j:=j-2 UNTIL S[j] ⋖ Q; 把 S[j+1]…S[k]归约为某个N； k:=j+1; S[k]:=N END OF WHILE; 使得Q不断向左移,指向新终结符 IF S[j]⋖ a OR S[j]≖a THEN BEGIN k:=k+1; S[k]:=a END ELSE ERROR; 使得j指向VT UNTIL a=‘#’

5.2 算符优先分析 REPEAT Q:=S[ j]; IF S[j-1] ∈ VT THEN j:=j-1 ELSE j:=j-2 UNTIL S[j] ⋖ Q 使得j指向VT 左符号S[j]与右符号Q之间还可能满足: S[j]⋗ Q 不可能出现,若成立则前　　　　　面已经归约过了; S[j]≖ Q 此时,符合“最左素短语” 定义,一直repeat; S[j]与Q无优先关系不可能出现, 若成立则前面已经报告“Error”

5.2 算符优先分析 1 # i+i*i↑i# 2 #i +i*i↑i# 3 #P +i*i↑i# 6 #P+P *i↑i# (1)EE+T|T (2)TT*F|F (3)FP↑F|P (4)P(E)|i 步骤 分析栈 剩余输入串 动作 1 # i+i*i↑i# 2 #i +i*i↑i# 移进 #<i 3 #P +i*i↑i# + * ↑ i ( ) # ⋗ ⋖ ≖ 4 #P+ i*i↑i# 5 #P+i *i↑i# 6 #P+P *i↑i# 7 #P+P* i↑i# 8 #P+P*i ↑i# 9 #P+P*P ↑i#

5.2 算符优先分析 9 #P+P*P ↑i# 10 #P+P*P↑ i# 11 #P+P*P↑i # 12 #P+P*P↑P # (1)EE+T|T (2)TT*F|F (3)FP↑F|P (4)P(E)|i 步骤 分析栈 剩余输入串 所用产生式 9 #P+P*P ↑i# 10 #P+P*P↑ i# + * ↑ i ( ) # ⋗ ⋖ ≖ 11 #P+P*P↑i # 12 #P+P*P↑P # 13 #P+P*F # 14 #P+T # 15 #E #

5.2 算符优先分析 三、优先函数 1.定义：利用使每个终结符θ对应两个优先函数f(θ)，g(θ) 来表达终结符之间的优先关系，从而实现算符优先 分析算法。 2.优点：便于作比较运算，并且节省存储空间。 (优先关系表占用的存储量比较大) 缺点：原先不存在优先关系的两个终结符，由于与自然数 相对应变成可比较的了。因而，可能会掩盖输入串 的某些错误。

5.3 LＲ分析法 引言： 1.LR分析（1965年Knuth提出） 著有《计算机程序设计艺术》书，被誉为“计算机的圣经”，目前有4卷。 高德纳

5.3 LＲ分析法 LR分析法：是另一种有效的自下而上的分析方法， L——从左向右扫描输入串， R——构造最右推导的逆过程

5.3 LＲ分析法 LR分析根据当前分析栈中的符号串和向右顺序查看输入串的K(K≥0)个符号就可以唯一确定分析的动作是移进还是归约。 向前查看0个符号，就是LR(0)分析方法，向前查看1个符号，就是LR(1)方法。

5.3 LＲ分析法 优点： 缺点： 手工构造分析表工作量太大。必须使用自动生成器。 比其他“移进-归约”分析法，如算符优先分析法使用更加广泛，识别效率高 能用LL(1)分析法分析的所有文法都能使用LR方法来进行分析。 LR分析法在自左至右扫描输入串的过程中就能发现其中的任何错误，并能准确地指出出错位置。 缺点： 手工构造分析表工作量太大。必须使用自动生成器。

5.3 LＲ分析法 关键问题是如何确定句柄。 在算符优先分析中，通过算符的优先关系得到句柄——“最左素短语”。 LR方法中句柄是通过求活前缀而求得。

记 住 历 史 立 足 现 实 展 望 未 来 5.3 LＲ分析法 一、LR分析器 记 住 历 史 立 足 现 实 展 望 未 来 1.LR方法的基本思想 在规范归约过程中，一方面记住已移进和归约出的整个符号串(即“历史”)，另一方面根据所用的产生式推测未来可能碰到的输入符号(即对未来进行“展望”)。 当一串貌似句柄的符号串呈现于分析栈的顶端时，我们希望能根据所记载的“历史”和“展望”以及“现实”的输入符号等三方面的材料，来确定栈顶的符号串是否构成相对某一产生式的句柄。

文法符号：X1X2…Xm是目前已移进并归约出的句型部分。其实它是多余的，已经概括到状态里。 状态栈：(S0,#)为预先放到栈中的初始状态和符号。 分析器实际上是一个带有先进后出栈的确定的有穷自动机。将“历史”和“展望”综合成“状态”，分析栈用来存放状态，状态概括了从分析开始直到某一归约阶段的全部历史和展望资料，不必象算符优先分析法中要翻阅栈中的内容才能决定是否要进行归约。只需根据栈顶状态和输入符号就可以唯一决定下一个动作。 一个LR分析器由3个部分组成： LR分析程序，又称总控程序。所有的LR分析器都是相同的。 分析表(分析函数)，不同的文法分析表不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表(ACTION)和状态转换(GOTO)表两个部分，它们都可用二维数组表示。 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。

2. 分析表的组成： a1 a2 at … S0 S1 Sn (1) 分析动作表Action是一个二维数组 符号 状态 a1 a2 … at S0 action[S0 , a1] action[S0 , a2] action[S0 , at] S1 action[S1 , a1] action[S1 , a2] action[S1 , at] Sn action[Sn , a1] action[Sn , a2] action[Sn , at] 表中action[Si,aj]，指出如果当前栈顶为状态Si，输入符号为aj时应执行的动作。其动作有四种可能，分别为：移进(S)、归约(r)、接受(acc)、出错(error)。

x1 x2 … xt S0 S1 Sn (2) 状态转换表goto 也是一个二维数组 符号 状态 x1 x2 … xt S0 goto[S0 , x1] goto[S0 , x2] goto[S0 , xt] S1 goto[S1 ,x1] goto[S1 , x2] goto[S1 , xt] Sn goto[Sn , x1] goto[Sn , x2] goto[Sn , xt] 表中goto[Si,xj]指出栈顶状态为Si，碰到文法符号为Xj时应转到的下一状态。 显然：分析表定义了一个以文法符号为字母表的DFA

Si表示把当前输入符号移进栈，第i个状态进状态栈。 例：LR的Action和GoTo表 状态 Action GoTo i + * ( ) # E T F S5 S4 1 2 3 S6 acc r2 S7 r4 4 8 5 r6 6 r1 9 7 10 S11 r3 11 r5 设文法为G[L]： Si表示把当前输入符号移进栈，第i个状态进状态栈。 (1) E E+T (2) E T (3) T T*F (4) T F (5) F (F) (6) F i i表示转第i个状态，即第i个状态进状态栈。 产生式的序号 空白表示分析动作出错 ri表示按第i个产生式进行归约

(状态栈，符号栈，输入符号串) 3、LR分析过程： 用三元式: 表示分析过程中状态栈，符号栈，输入符号串的变化 初始时，将状态S0和#进分析栈。三元式为： (S0, # , a1a2…an#) 任一时刻的三元式为： (S0S1…Sm, #X1X2…Xm, aiai+1…an#) 分析器的下一步动作是由栈顶状态Sm和当前面临的输入符号ai唯一确定的。

(S0S1 … Sm-r S, # X1X2…Xm-rA, aiai+1…an #) 根据栈顶状态Sm和输入符号ai查action表, 根据表中的内容不同完成不同的动作，若action[Sm, ai]为： 移进：当前输入符号ai进符号栈，下一输入符号变成当前输入符号，将action表中指出的状态S进状态栈。三元式变为： (S0S1…SmS, # X1X2…Xmai, ai+1…an#) 归约：按某个产生式A→β进行归约，若产生式的右端长度为r，则两个栈顶的r个元素同时出栈。将归约后的符号A进符号栈; 根据新栈顶状态Sm-r和归约符号A查GOTO表， S=goto[Sm-r, A]进状态栈。三元式变为： (S0S1 … Sm-r S, # X1X2…Xm-rA, aiai+1…an #) 接受：分析成功，终止分析。三元式不再变化。 出错：报告出错信息。三元式的变化过程终止。

例：LR的具体分析过程： 状态 ACTION GoTo i + * ( ) # E T F S5 S4 1 2 3 S6 acc r2 S7 S5 S4 1 2 3 S6 acc r2 S7 r4 4 8 5 r6 6 r1 9 7 10 S11 r3 11 r5 设文法为G[L]： (1) E E+T (2) E T (3) T T*F (4) T F (5) F (F) (6) F i 为了介绍LR分析过程，直接给出该文法的分析表，以后再介绍如何生成

1 # i*i+i# 0和#进栈 2 05 #i *i+i# i和S5进栈 3 03 #F Fi *i+i# i和S5退栈, F和S3进栈 序号 状态栈 符号栈 产生式 输入串 说明 1 # i*i+i# 0和#进栈 2 05 #i *i+i# i和S5进栈 3 03 #F Fi *i+i# i和S5退栈, F和S3进栈 4 02 #T TF *i+i# F和S3退栈, T和S2进栈 5 027 #T* i+i# *和S7进栈 6 0275 #T*i +i# i和S5进栈 7 02710 #T*F Fi +i# i和S5退栈, F和S10进栈 8 02 #T TT*F +i# F*T和S10,7,2退栈, T和S2进栈 9 01 #E ET +i# T和S2退栈, E和S1进栈 10 016 #E+ i# +和S6进栈 11 0165 #E+i # i和S5进栈 12 0163 #E+F Fi # i和S5退栈, F和S3进栈 13 0169 #E+T TF # F和S3退栈, T和S9进栈 14 01 #E E E+T # T+E和S9,6,1退栈, E和S1进栈

5.3 LＲ分析法 LR文法：对一个文法，如果能够构造一个分析表，且它的每个入口均是唯一的 如何构造LR分析表？

5.3 LＲ分析法 3.LR(0)表构造法：最简单，局限性大(绝大多数高级语言的语 法分析器均不适用)，但却是建立其它较一 SLR表构造法：一种较易实现又极有使用价值的方法，对某 些文法不适用。 规范LR表构造法：能力最强，能适用一大类文法，但实现代 价过高(分析表体积太大)。 LALR表构造法：能力介于SLR和规范LR之间，稍加努力，即可 高效实现。

5.3 LＲ分析法 二、LR(0)分析表的构造 1.思想：只概括“历史”材料而不包括推测性“展望” 材料的“状态”。 2.前缀：字的任意首部。 例：字abc－前缀：ℇ ，a，ab或abc 活前缀：指规范句型的一个前缀，不含句柄之后的 任何符号。 在右部增添一些终结符之后,就可使之成为一个规范句型。 对于文法G，若 S，Vt* ，则称为活前缀。 *

5.3 LＲ分析法 注: 在LR分析工作过程中，栈里的文法符号(自栈底向上)X1X2 …Xm应构成活前缀(在任何时候)，把输入串的剩余部分配 上之后即成为规范句型(若整个输入串确实构成一个句子)。 即：只要输入串的已扫描部分保持可归约成一个活前缀，那就意味着所扫描过的部分没有错误。

5.3 LＲ分析法 3.LR(0)项目 项目：文法产生式的右部添加一个圆点，称为项目。 含义：指明了在分析过程的某时刻我们看到产生式多 例： A•XYZ, AX•YZ, AXY•Z, AXYZ• 含义：指明了在分析过程的某时刻我们看到产生式多 大一部分。 例: A• XYZ 我们希望能从后面输入串中看到可以从XYZ推出的符号串。 AX• YZ 我们已经从输入串中看到能从X推出的符号串，希望能进一步看到可以从YZ推出的符号串。

5.3 LＲ分析法 例如：产生式 SXYZ 对应有4个项目： [0] S·XYZ [1] SX·YZ 产生式A ε只对应一个项目： A · 项目指明了在分析过程的某时刻，已看到的产生式部分 项目集：若干个项目组成的集合。 例如：对于上述产生式的4个项目即构成一个项目集。

5.3 LＲ分析法 归约项目： A α• 接受项目(唯一)：S’ α• 移进项目：Ａ α•ａβ(a∈VT) 待约项目：A α•Bβ (B∈VN) 后继符号为空 归约项目的左边是文法的开始符号 后继符号为终结符 后继符号为非终结符 是哪一款项目与后继符号有关，后继符号：在项目中紧跟在符号“·”后面的符号称为该项目的后继符号。 表示下一时刻遇到的符号。

5.3 LＲ分析法 构造NFA的方法： 将文法的所有项目都写出，每个项目是一个状态 规定项目1为NFA的唯一初态 如果状态i和状态j出自同一产生式，而且状态j的圆点只落后于状态i一个位置: 如果i的这个位置是终结符a，从状态i画一条弧到状态j，标记为a 如果i的这个位置是非终结符A，则连两种弧，(1)从状态i画ε弧到所有的A→ · β的状态。(2)从状态i画一条弧到状态j，标记为A 归约项目表示结束状态(句柄识别态)，用双圈表示

构造识别活前缀的NFA 若 i：X→X1…Xi-1·Xi…Xn j：X→X1…Xi-1 Xi ·…Xn 若 Xi是非终结符，且有： k1: Xi→·α1 … km: Xi→·αm Xi i j ε ε k1 ε ... km

求文法对应的NFA P106 例 5.8 S' E E aA | bB A cA | d B cB | d 1) 列出该文法的项目，有： 1. S' ·E 2. S' E · 3. E ·aA 4. E a·A 5. E aA· 6. A  · cA 7. A c · A 8. A cA · 9. A ·d 10. A  d· 11. E ·bB 12. E  b·B 13. E  bB· 14. B ·cB 15. B c·B 16. B cB · 17. B ·d 18. B  d·

2)画出NFA 识别活前缀的NFA 然后再用第三章学的方法去确定化以及化简

太麻烦！下面介绍一种直接构造识别活前缀DFA的方法！ 总结： 构造LR（0）分析表的过程： 拓广文法 写出文法的所有LR（0）项目 构造识别活前缀的NFA 对其进行确定化，得到DFA 从DFA构造LR（0）分析表 太麻烦！下面介绍一种直接构造识别活前缀DFA的方法！ 拓广文法：为了使接受状态易于识别，总是把文法G进行拓广。假定文法G是一个以S为开始符号的文法，那么我们构造一个文法G’，它包含了整个文法G，但有引进了一个没有出现在G中的非终结符S’，并加进一个新的产生式 S’—>S，而这个S’是文法G’的开始符号，那么，就称G’是G的拓广文法。

5.3.2 LR(0)项目集规范族和LR(0)分析表的构造 二、构造识别活前缀的DFA LR(0)项目集规范族：识别活前缀的DFA的状 态集。（其中，该DFA的状态是LR(0)项目集） 构造方法有两种： 1) 使用第三章的子集法将NFA确定化 2) 直接使用闭包和状态转换函数进行计算

1)使用第三章的子集法将NFA确定化，得到一个识别该文法的确定的有穷自动机，其每个状态是项目集 识别活前缀的DFA

5.3 LＲ分析法 I的闭包——ClOSURE(I)： 假定I是文法G’的任一项目集，定义和构造I的闭包CLOSURE(I)的方法是： (2)若Aα•Bβ属于CLOSURE(I)，那么，对任何B的产生式Bγ，项目B•γ也属于CLOSURE(I)； (3)重复执行上述两步骤直至CLOSURE(I)不再增大为止。

例: (0)S’E (1)EE+T (2)ET (3)TT*F (4)TF (5)F(E) (6)Fi 假设I：{F (•E) } 则： CLOSURE(I)= { F (•E) E•E+T E•T T•T*F T•F F•(E) F•i }

例: (0)S’E (1)EE+T (2)ET (3)TT*F (4)TF (5)F(E) (6)Fi I：{S’ •E } 则： CLOSURE(I)= { S’ •E E•E+T E•T T•T*F T•F F•(E) F•i }

5.3 LＲ分析法 2.构造LR(0)项目集规范族 1)文法拓广： S’S 2)构造项目集族:I0，…，In 其中I0=closure({ S’•S }) (1)I为G’的任一项目集 (2)构造GO(I,X)，GO(I,X)=closure(J) J={ AαX•β| Aα•Xβ∈I } 3)画出相应的DFA (可边求项目集族和GO函数边画DFA)

状态转换函数GO(I,X)的计算： GO(I,X) = Closure(J) I是一个项目集，X是一个文法符号 其中J = {任何形如A  X·的项目| A·X I} GO函数实际就是检查I中的每一个后继符号为X的项目，将这个圆点向后移动一个位置，得到项目集J，再对项目集J求闭包。

... GO(I,X) = CLOSURE(J) A→α·Xβ∈I A→α1·Xβ1∈I A→α2·Xβ2∈I A→αX·β∈J

例： S’→ E E → aA | bB A → cA | d B → cB | d I0, I1, I2, I3, I4, I5, I6, I5: A c • A A • cA A • d A I10: A cA • c c d I6: A d • d I2: E a • A A • cA A • d a A I4: E aA • I0: S’ • E E • aA E • bB E I1: S’ E • I3: E b • B B • cB B •d I7: E bB • B b c d I0, I1, I2, I3, I4, I5, I9: B d • d I8: B c • B B • cB B • d I6, I7, I8, I9, I10, c I11 B I11: B cB •

5.3 LＲ分析法 3.构造LR(0)分析表 ① Aα•aβ∈Ik 且 GO(Ik,a)=Ij, a∈VT， 则置ACTION[k,a]=“Sj”； ②Aα•∈Ik ,则对∀a∈VT和#,置ACTION[k,a]=“rj”； ③S’S•∈Ik，则置ACTION[k,#]=“acc”； ④GO(Ik,A)=Ij,A∈VN，则置GOTO[k,A]=j； ⑤否则，置“报错标志”。

状态 ACTION GOTO a b c d # E A B 1 2 3 4 5 6 7 8 9 10 11

状态 ACTION GOTO a b c d # E A B 2 3 5 6 8 9 s2 s3 1 acc s5 s6 4 s8 s9 7 s2 s3 1 acc 2 s5 s6 4 3 s8 s9 7 r1 5 10 6 r4 r2 8 11 9 r6 r3 r5

5.3 LＲ分析法 4.LR(0)文法 LR(0)文法的判别:LR(0)文法规范族的每个项目集不 包含任何冲突项目。 假若一个文法G的拓广文法G’的活前缀识别自动机中的每个状态不存在： ①既含移进项目又含归约项目； ②或者含有多个归约项目； 则称G是一个LR(0)文法。

5.3 LＲ分析法 练习：考察下面的拓广文法: 构造其LR(0)项目集规范族，并判断该文法是否是LR(0)的？ (0)S’E (1)EE+T (2)ET (3)TT*F (4)TF (5)F(E) (6)Fi 构造其LR(0)项目集规范族，并判断该文法是否是LR(0)的？

5.3 LＲ分析法 (0)S’E (1)EE+T (2)ET (3)TT*F (4)TF (5)F(E) (6)Fi I0：

5.3 LＲ分析法 LR(0)分析表构造时没有任何展望，只要在当前状态有一个归约项目，不管后面的输入符号是什么（即面临任何输入符号），都要求在当前状态下执行归约操作。 然而，若一个输入串语法正确的话，活前缀加上剩余的输入串应形成一个句型，因此，在当前状态中若有一个归约项目（A α• ），应当面临Follow(A)中符号时，才在当前状态下执行归约操作。 SLR(1 )分析表

5.3 LＲ分析法 三、SLR分析表的构造 答： 该文法不是LR(0)的。因为同时存在了移进-归约，和归约-归约项目。 例：假定一个文法的LR(0)规范族中含有如下的一个项目集(状态)I： I={ Xα•bβ，Aα•，Bα• } 问：该文法是LR(0)的吗？什么情况下是SLR(1)的？ 答： 该文法不是LR(0)的。因为同时存在了移进-归约，和归约-归约项目。 当FOLLOW(A) ∩ FOLLOW(B) ∩ {b}={ } 时，该文法是SLR(1)文法，此时，若输入符号为a，则： 若a=b，则移进； 若a∈FOLLOW(A)，则用产生式Aα进行归约； 若a∈FOLLOW(B)，则用产生式Bα进行归约。

5.3 LＲ分析法 三、SLR分析表的构造 1、步骤： (1)文法拓广：S’S； (2)构造S’的LR(0)项目集规范族C； (3)利用C和S’，按下述算法构造S’的SLR分析表。

5.3 LＲ分析法 构造S’的SLR分析表: A.移进项目：Aα• aβ∈Ik ，Go(Ik,a)=Ij ， 则置ACTION[k,a]=“Sj”； B.归约项目：Aα•∈Ik ，则对∀a∈FOLLOW(A)， 则置ACTION[k,a]=“rj”； C.接受项目：若S’S•∈Ik ,则置ACTION[k,#]=“acc”； D.待约项目：若GO(Ik,A)=Ij ，A∈VN ， 则置GOTO[k,A]=j 。

例如、试构造表达式文法的SLR分析表 解：按照求LR(0)项目集规范族的算法，求得G(E)文法的项目集族如下图：

状态 ACTION GOTO + * （ ） i # E T F 1 2 3 4 5 6 7 8 9 10 11 1 2 3 4 5 6 7 8 9 10 11 FOLLOW(S')={#} FOLLOW(E)={+, ), #} FOLLOW(T)={*, +, ), #} FOLLOW(F)={*, +, ), #}

状态 ACTION GOTO + * （ ） i # E T F 4 5 6 7 11 s4 s5 1 2 3 s6 acc r2 s7 s4 s5 1 2 3 s6 acc r2 s7 r4 4 8 5 r6 6 9 7 10 s11 r1 r3 11 r5 FOLLOW(S')={#} FOLLOW(E)={+, ), #} FOLLOW(T)={*, +, ), #} FOLLOW(F)={*, +, ), #}

从这里开始

5.3 LＲ分析法 SLR分析表的构造 1、步骤： (1)文法拓广：S’S； (2)构造S’的LR(0)项目集规范族C； (3)利用C和S’，按下述算法构造S’的SLR分析表。

5.3 LＲ分析法 构造S’的SLR分析表: A.移进项目：Aα• aβ∈Ik ，Go(Ik,a)=Ij ， 则置ACTION[k,a]=“Sj”； B.归约项目：Aα•∈Ik ，则对∀a∈FOLLOW(A)， 则置ACTION[k,a]=“rj”； C.接受项目：若S’S•∈Ik ,则置ACTION[k,#]=“acc”； D.待约项目：若GO(Ik,A)=Ij ，A∈VN ， 则置GOTO[k,A]=j 。

对SLR分析的思考：在构造SLR分析表的方法中 ，若项目集Ik中含有 Aα• ，那么在状态k时，只要面临输入符号a∈FOLLOW(A) ，就确定用产生式 Aα进行归约。 但是，在某些情况下，当状态k呈现于栈顶时，栈里符号串所构成的活前缀未必允许把α规约成A，因为可能没有一个规范句型含有前缀βAa，因此，此时用产生式 Aα进行归约未必有效。

非SLR文法示例：考虑如下文法： 计算FOLLOW集合所得到的超前符号集合可能大于实际能出现的超前符号集。 (0) S→S (2) S→R (3) L→*R (4) L→i (5) R→L

这个文法的LR(0)项目集规范族为： I6：S→L=·R R→·L L→·*R L→·i I0：S→·S S→·L=R S→·R S→·*R L→·i R→·L I2：S→L·=R R→L· I3：S→R· I4：L→*·R R→·L L→·*R L→·i I7：L→*R· I1：S→S· I8：R→L· I9：S→L=R· I5：L→i·

I2含有“移进－归约”冲突。 FOLLOW(R)＝{#, =}， I2：S→L·=R R→L·

当状态2显现于栈顶而且面临输入符号为‘=’时，实际上不能用对栈顶L进行归约。 不含“R=”为前缀的规范句型 有含“*R=”为前缀的规范句型 考虑如下文法： (0) S→S (1) S→L=R (2) S→R (3) L→*R (4) L→i (5) R→L 当状态2显现于栈顶而且面临输入符号为‘=’时，实际上不能用对栈顶L进行归约。 不含“R=”为前缀的规范句型 有含“*R=”为前缀的规范句型 I2：S→L·=R R→L·

SLR在方法中,如果项目集Ii含项目A SLR在方法中,如果项目集Ii含项目A.而且下一输入符号aFOLLOW(A),则状态i面临a时,可选用“用A归约”动作。但在有些情况下,当状态i显现于栈顶时,栈里的活前缀未必允许把归约为A，因为可能根本就不存在一个形如“Aa”的规范句型。因此，在这种情况下，用“ A ”归约不一定合适。 FOLLOW集合提供的信息太泛！

5.3.4 规范LR分析表的构造 我们需要重新定义项目，使得每个项目都附带有k个终结符。每个项目的一般形式是[A→·, a1a2…ak] ，这样的一个项目称为一个LR(k)项目。项目中的 a1a2…ak 称为它的向前搜索符串(或展望串)。 向前搜索符串仅对归约项目[A→·，a1a2…ak]有意义。对于任何移进或待约项目[A→·, a1a2…ak], ，搜索符串 a1a2…ak 没有作用。

LR(0)分析表构造时没有任何展望，只要在当前状态有一个归约项目，不管后面的输入符号是什么（即面临任何输入符号），都要求在当前状态下执行归约操作。 SLR(1)分析表：若一个输入串语法正确的话，活前缀加上剩余的输入串应形成一个句型，因此，在当前状态中若有一个归约项目（A α • ），应当面临Follow(A)中符号时，才在当前状态下执行归约操作。 规范LR分析表：若一个输入串语法正确的话，活前缀加上剩余的输入串应形成一个规范句型，因此，在当前状态中若有一个归约项目（A α • ），应当面临在规范句型中可以跟在A后的符号时，才在当前状态下执行归约操作。 LR(1 )分析表

基本概念 LR(0)项目：A→α·β LR(K)项目: A→α·β, a1a2…ak 向前搜索符串 ,仅对归约项目有影响 LR(1)项目： A→α·β, a LR(1)项目集规范族

归约项目[A→·, a1a2…ak]意味着：当它所属的状态呈现在栈顶且后续的k个输入符号为 a1a2…ak 时，才可以把栈顶上的归约为A。 形式上我们说一个LR(1)项目[A→·, a]对于活前缀是有效的，如果存在规范推导 其中，1) ＝；2) a是的 第一个符号，或者a为#而为。

为构造有效的LR(1)项目集族我们需要两个函数CLOSURE和GO。

[A→·B, a]对活前缀＝是有效的，则对于每个形如B的产生式， 对任何bFIRST(a)，[B→·, b]对也是有效的。 ζ [zi:tə] η [i:tə] ξ [ksai] φ [fai] χ [kai] ψ [psai]

项目集I 的闭包CLOSURE(I)构造方法： 2. 若项目[A→·B, a]属于CLOSURE(I)，B→ 是一个产生式，那么，对于FIRST(a) 中的每个终结符b，如果[B→·, b]原来不在CLOSURE(I)中，则把它加进去。 3. 重复执行步骤2，直至CLOSURE(I)不再增大为止。

LR(1)项目集规范族构造 （1）CLOSURE(I): ① I中的项目 ② [A→α·Bβ, a ]∈CLOSURE(I) [B →·γ, ] β, a b ? b∈First(β a) => * R => R S δAω δ αBβ ω => * R => R S δA aλ δ αBβ aλ

构造LR(1)分析表的算法。 令每个Ik的下标k为分析表的状态，令含有[S→·S, #]的Ik的k为分析器的初态。

例： (0)S’→S (1)S→BB (2)B→aB (3)B→b I1: S’→S·, # I6: B→a·B, # B→·aB, I2: S→B·B, # B→·aB, B→·b, # # I7: B→b·, # # I8: B→aB·, a/b I3: B→a·B,a/b B→·aB, B→·b, LR(1)项目集规范族： I0: S’→·S, # S→·BB, B→·aB, B→·b, a/b I9: B→aB·, # a/b # a/b I4: B→b·, a/b a/b I5: S→BB·, #

令I是一个项目集，X是一个文法符号，函数GO(I，X)定义为： GO(I，X)＝CLOSURE(J) 其中 J＝{任何形如[A→X·, a]的项目 | [A→·X, a]I}

GO(I,X) = CLOSURE(J) [A→α·Xβ, a ]∈I [A→αX·β, a ]∈J

动作ACTION和状态转换GOTO构造如下： 1. 若项目[A→·a, b]属于Ik且GO(Ik, a)＝Ij， a为终结符，则置ACTION[k, a]为 “sj”。 2. 若项目[A→·，a]属于Ik，则置ACTION[k, a]为 “rj”；其中假定A→为文法G的第j个产生式。 3. 若项目[S→S·, #]属于Ik，则置ACTION[k, #]为 “acc”。 4. 若GO(Ik，A)＝Ij，则置GOTO[k, A]=j。 5. 分析表中凡不能用规则1至4填入信息的空白栏均填上“出错标志”。

按上述算法构造的分析表，若不存在多重定义的入口(即，动作冲突)的情形，则称它是文法G的一张规范的LR(1)分析表。 具有规范的LR(1)分析表的文法称为一个LR(1)文法。 LR(1)状态比SLR多， LR(0)SLR  LR(1) 无二义文法

例5.13 (5.10)的拓广文法G( S) (0) S→S (1) S→BB (2) B→aB (3) B→b

LR(1)的项目集C和函数GO I0: S’•S, # S•BB, # B•aB, a B•aB, b B •b, a I5: SBB•, # B a B I2: SB • B, # B•aB, # B •b, # I6: Ba•B, # B•aB, # B •b, # a a b I4: B b •, a/b b b B b a I3: Ba•B, a/b B•aB, a/b B •b, a/b I7: B b •, # I9: B aB•, # B LR(1)的项目集C和函数GO I8: B aB•, a/b

LR(1)分析表为:

例: 按上表对aabab进行分析 步骤 状态 符号 输入串 0 0 # aabab# 1 03 #a abab# 步骤 状态 符号 输入串 0 0 # aabab# 1 03 #a abab# 2 033 #aa bab# 3 0334 #aab ab# 4 0338 #aaB ab# 5 038 #aB ab# 6 02 #B ab# 7 026 #Ba b# 8 0267 #Baa # 9 0269 #BaB # 10 025 #BB # 11 01 #S # acc

例: 按上表对abab进行分析 步骤 状态 符号 输入串 0 0 # abab# 1 03 #a bab# 2 034 #ab ab# 3 038 #aB ab# 4 02 #B ab# 5 026 #Ba b# 6 0267 #Bab # 7 0269 #BaB # 8 025 #BB # 9 01 #S # acc

5.3 LＲ分析法 五、LALR分析表的构造 1、SLR－LR(1)－LALR(1)之间的关系 LALR(1)－一种折衷的方法

5.3 LＲ分析法 2、同义集合并 (1)同心集：若两个LR(1)项目集,除去搜索符外,这两 (2)引出的问题 个集合相同,则称它们是同心集 A.同心集合并不会产生“移进－归约”冲突 B.同心集合并会产生“归约－归约”冲突

5.3 LＲ分析法 例:考虑文法 (0)S’S (1)SaAd|bBd|aBe|bAe (2)Ac (3)Bc 项目集 {[Ac• ,d],[Bc• ,e]}和 {[Ac• ,e],[Bc• ,d]}同心 ⇒(合并){[Ac• ,d/e],[Bc• ,d/e]} 问题:面临d/e时,采用哪一个归约?

5.3 LＲ分析法 3、构造LALR(1)分析表的步骤: A.从C’构造Action表 (1)文法拓广:GG’ (2)构造G’的LR(1)项目集族C={I0,I1,…,In} (3)合并同心集  C’={J0,J1,…,Jm} [S’• S,#] ∈Jk,则Jk为初态 (4)若合并后的C’不存在“归约－归约”冲突,则: A.从C’构造Action表 B.从C’构造Goto表 (5)空白格“出错”

5.3 LＲ分析法 例:文法5.10的LALR分析表 状态 ACTION GOTO a b # S B 1 2 36 47 5 89

5.3 LＲ分析法 例:文法5.10的LALR分析表 状态 ACTION GOTO a b # S B s36 s47 1 2 acc 5 s36 s47 1 2 acc 5 36 89 47 r3 r1 r2

5.3 LＲ分析法 六、二义文法的应用 1、定理:任何二义文法决不是一个LR文法,因而也 2、解决二义文法语法分析问题的方法: 不是SLR或LALR文法 ⇒但是,某些二义文法是非常有用的,那么,对二义文 法我们如何进行语法分析呢? 2、解决二义文法语法分析问题的方法: (1)借助于消除二义性的“规定”来解决 (2)不需对文法改写,只需据“规定”解决项目集 　 中的冲突

5.3 LＲ分析法 例:文法5.11

LR分析表总结： LR(0)项目集规范族 分析表的构造 LR(0)分析表 移进 归约 SLR分析表 归约利用follow集 LR分析表 LALR分析表 LR(1)同心集合并

练习：若有文法G[S]， S→S;M|M M→MbD|D D→D(S)|ε （1）证明G[S]是SLR文法，并构造它的分析表； （2）给出G[S]的LR(1)项目集规范族中的I0。