《编译原理-LR分析法.ppt》由会员分享，可在线阅读，更多相关《编译原理-LR分析法.ppt（54页珍藏版）》请在金锄头文库上搜索。
1、7 自底向上分析自底向上分析 (Bottom-up Parsing) LR分析器分析器7.1 LR分析器分析器 自底向上分析自底向上分析 (Bottom-up Parsing)“ “L”: left-to-right scanning L”: left-to-right scanning 自左向右扫描自左向右扫描自左向右扫描自左向右扫描“ “R”: rightmost derivation in reverse R”: rightmost derivation in reverse 最右推导的最右推导的最右推导的最右推导的逆逆逆逆5.3.4.1 LR分析方法概述分析方法概述5.3.4.2 LR
2、(0)分析器分析器5.3.4.3 SLR(1)分析器分析器5.3.4.4 LR(1)分析器分析器5.3.4.5 LALR(1)分析器分析器7.1.1 LR(0)分析器分析器例：例：考虑文法考虑文法GS S aA A cA | d 识别识别accd是否该文法的句子。是否该文法的句子。A Ac.Ac.AA A.cA.cAA A.d.d s s2 2S Sa.Aa.AA A.cA.cAA A.d.d s s1 1 S S.aA.aA s s0 0startstartA AcAcA. . s s4 4S SaAaA. . s s5 5A Ad.d. s s3 3A Ad dd dA Ac ca ac
3、cA Ac.Ac.AA A.cA.cAA A.d.d s s2 2S Sa.Aa.AA A.cA.cAA A.d.d s s1 1 S S.aA.aA s s0 0startstartA AcAcA. . s s4 4S SaAaA. . s s5 5A Ad.d. s s3 3A Ad dd dA Ac ca ac cs s0 0 accdaccd# shift# shifts s0 0a as s1 1 ccdccd# shift# shifts s0 0a as s1 1c cs s2 2 cdcd# shift# shifts s0 0a as s1 1c cs s2 2c cs s2
4、 2 d# shiftd# shifts s0 0a as s1 1c cs s2 2c cs s2 2d ds s3 3 # reduce # reduce A Ad d s s0 0a as s1 1c cs s2 2c cs s2 2A As s4 4 # reduce # reduce A AcAcA s s0 0a as s1 1c cs s2 2A As s4 4 # reduce # reduce A AcAcA s s0 0a as s1 1A As s5 5 # reduce # reduce S SaAaA s s0 0S S # accept # accept动作动作动作
5、动作actonacton栈栈栈栈GS:GS:1: S 1: S aAaA 2: A 2: A cAcA3: A 3: A d daccdaccdL(GSL(GS ) ? ) ?根据上述例子，可以总结如下：根据上述例子，可以总结如下：根据上述例子，可以总结如下：根据上述例子，可以总结如下：一、概念一、概念 产生式右部符号被识别的多少产生式右部符号被识别的多少产生式右部符号被识别的多少产生式右部符号被识别的多少, , 在产生式右部加在产生式右部加在产生式右部加在产生式右部加上上上上 . 指示位置。指示位置。指示位置。指示位置。项目项目：在文法产生式右部某个位置标有在文法产生式右部某个位置标有在文法
6、产生式右部某个位置标有在文法产生式右部某个位置标有 . 的产的产的产的产生式，称为文法的一个生式，称为文法的一个生式，称为文法的一个生式，称为文法的一个LR(0)LR(0)项目项目项目项目 。 为了叙述方便，为了叙述方便，为了叙述方便，为了叙述方便， 形如形如形如形如 A A . . 的项目称为的项目称为的项目称为的项目称为归约项目归约项目归约项目归约项目； 形如形如形如形如 A A . B . B 的项目称为的项目称为的项目称为的项目称为待约项待约项待约项待约项目目目目( (基本项目基本项目基本项目基本项目) )； 形如形如形如形如 A A . a . a 的项目称为的项目称为的项目称为的项
7、目称为移进项目移进项目移进项目移进项目。 定义定义(有效项目有效项目)：项目项目项目项目A A1 1. . 2 2对对对对活前缀活前缀活前缀活前缀 = = 1 1 是有效的，如果存在规范推导是有效的，如果存在规范推导是有效的，如果存在规范推导是有效的，如果存在规范推导 S S * * Aw Aw 1 1 2 2w w。 若项目若项目若项目若项目 A A1 1.B.B 2 2 对活前缀对活前缀对活前缀对活前缀 = = 1 1 是有效的，是有效的，是有效的，是有效的，且且且且 B B 是产生式，则项目是产生式，则项目是产生式，则项目是产生式，则项目 B B . . 对活前缀对活前缀对活前缀对活前缀
8、 = = 1 1 也是有效的。也是有效的。也是有效的。也是有效的。据假设，存在一个规范推导据假设，存在一个规范推导据假设，存在一个规范推导据假设，存在一个规范推导S S * * Aw Aw 1 1 B B 2 2w w设设设设 2 2w w * * xwxw, , 则对任何则对任何则对任何则对任何B B 有规范推导有规范推导有规范推导有规范推导 rmrm S S * * Aw Aw 1 1 B B 2 2w w 1 1 B B xwxw 1 1 xwxw所以所以所以所以 B B . . 对活前缀对活前缀对活前缀对活前缀 1 1 也是有效的。也是有效的。也是有效的。也是有效的。 ：伽马伽马伽马伽
9、马 ：艾塔：艾塔：艾塔：艾塔定义定义 (有效项目集有效项目集，项目集规范族项目集规范族)： 文法文法文法文法GG的某个活前缀的某个活前缀的某个活前缀的某个活前缀 的所有有效项目组成的集合，的所有有效项目组成的集合，的所有有效项目组成的集合，的所有有效项目组成的集合，称为活前缀称为活前缀称为活前缀称为活前缀 的的的的LR(0)LR(0)有效项目集。有效项目集。有效项目集。有效项目集。 文法文法文法文法GG的所有有效项目集组成的集合，称为的所有有效项目集组成的集合，称为的所有有效项目集组成的集合，称为的所有有效项目集组成的集合，称为GG的的的的LR(0)LR(0)项目集规范族。项目集规范族。项目集
10、规范族。项目集规范族。定义定义 (项目闭包项目闭包)：设设设设I I是文法是文法是文法是文法GG的一个的一个的一个的一个LR(0)LR(0)项目集合，项目集合，项目集合，项目集合，I I的项目闭包的项目闭包的项目闭包的项目闭包closureclosure(I)(I)定义如下：定义如下：定义如下：定义如下：1 1、I I closureclosure(I)(I)。2 2、若项目若项目若项目若项目A A . . B B closureclosure(I)(I)，且且且且 B B 是是是是GG的的的的产生式，则项目产生式，则项目产生式，则项目产生式，则项目B B . . closureclosure
11、(I)(I)。3 3、closureclosure(I)(I)仅包含上述两条规则确定的仅包含上述两条规则确定的仅包含上述两条规则确定的仅包含上述两条规则确定的LR(0)LR(0)项目。项目。项目。项目。定义定义 (转移函数转移函数)： 若若若若I I是文法是文法是文法是文法GG的一个的一个的一个的一个LR(0)LR(0)项目集，项目集，项目集，项目集，X X是是是是GG中的文法中的文法中的文法中的文法符号。定义符号。定义符号。定义符号。定义 gogo(I, X) = (I, X) = closureclosure(J)(J)其中其中其中其中 J =J =A A X . X . | A | A
12、. X . X I I 称函数称函数称函数称函数gogo(I, X)(I, X)为转移函数。为转移函数。为转移函数。为转移函数。 项目项目项目项目A A X . X . 称为项目称为项目称为项目称为项目A A . X . X 后继。后继。后继。后继。二、识别句柄和二、识别句柄和活前缀活前缀的自动机的自动机 若文法若文法若文法若文法G = G = ( V( VT T, V, VN N, S, P), S, P)，则，则，则，则识别识别识别识别GG的句柄的自的句柄的自的句柄的自的句柄的自动机为动机为动机为动机为DFA MDFA M = ( = ( = = V VT T V VN N， Q = GQ
13、 = G的的的的LR(0)LR(0)项目集规范项目集规范项目集规范项目集规范族族族族, , q q0 0 = = closureclosure( S( S.S ).S )， F = F = 所有含归约项目的有效项目集组成的集合，所有含归约项目的有效项目集组成的集合，所有含归约项目的有效项目集组成的集合，所有含归约项目的有效项目集组成的集合， = = gogo(I,X) )(I,X) )。 若将所有状态均视为终态，则若将所有状态均视为终态，则若将所有状态均视为终态，则若将所有状态均视为终态，则识别活前缀的自动识别活前缀的自动识别活前缀的自动识别活前缀的自动机机机机DFA MDFA M = ( =
14、 ( = = V VT T V VN N, , Q = G Q = G的的的的LR(0)LR(0)项目集规范族项目集规范族项目集规范族项目集规范族, , q q0 0 = = closureclosure(S(S.S).S)， F = QF = Q， = = gogo (I,X) ) (I,X) )。定理：定理：对于拓广文法对于拓广文法对于拓广文法对于拓广文法GG 的每一个的每一个的每一个的每一个活前缀活前缀活前缀活前缀 ，它的，它的，它的，它的有效项目有效项目有效项目有效项目集集集集恰好是从识别恰好是从识别恰好是从识别恰好是从识别 GG 活前缀的自动机的初态出发，活前缀的自动机的初态出发，活
15、前缀的自动机的初态出发，活前缀的自动机的初态出发，经过经过经过经过 路径路径路径路径所到达的那个状态所代表的项目集合。所到达的那个状态所代表的项目集合。所到达的那个状态所代表的项目集合。所到达的那个状态所代表的项目集合。例：设拓广例：设拓广例：设拓广例：设拓广文法文法文法文法GG SS 的产生式为：的产生式为：的产生式为：的产生式为： S S S S S S aAaA | | bBbB A A cAcA | d | d B B cBcB | d | dLR(0)项目集规范族项目集规范族I0: S.S S.aA S.bBI1: (I0,S) SS.I2: (I0,a) Sa.A A.cA A.d
16、 I3: (I0,b) Sb.B B.cB B.dI4: (I2,c) (I4,c) Ac.A A.cA A.dI5: (I3,c) (I5,c) Bc.B B.cB B.dI6: (I2,A) SaA.I7: (I3,B) SbB.I8: (I4,A) AcA.I9: (I5,B) BcB.I10: (I4,d) Ad.I11: (I3,d) Bd.Ac.AA.cAA.d I4Sa.AA.cAA.d I2Sb.BB.cBB.d I3Bc.BB.cBB.d I5S.SS.aAS.bB I0startSS. I1AcA. I8SaA. I6Ad. I10AddAcabSSbB. I7BcB. I
17、6Bd. I11BddBccc识别文法识别文法识别文法识别文法活前缀的活前缀的活前缀的活前缀的DFADFALR(0)分析表分析表三、三、LR分析器的结构和工作过程分析器的结构和工作过程LRLR分析器的结构如分析器的结构如分析器的结构如分析器的结构如图图图图，它的工作过程由算法，它的工作过程由算法，它的工作过程由算法，它的工作过程由算法1 1描述。描述。描述。描述。 输入输入输入输入 a a1 1 . . a ai i . a . an n # #LRLR驱动程序驱动程序驱动程序驱动程序分析表分析表分析表分析表输出输出输出输出栈栈栈栈s smmX Xmms sm-1m-1X Xm-1m-1. .
18、s s0 0图图图图4.19 4.19 一个一个一个一个LRLR分析器的模型分析器的模型分析器的模型分析器的模型action action gotogoto算法算法1: LR分析算法分析算法输入：一个输入串输入：一个输入串输入：一个输入串输入：一个输入串w w和文法和文法和文法和文法GG的一张的一张的一张的一张LRLR分析表分析表分析表分析表MM。输出：若输出：若输出：若输出：若w w L(G),L(G),输出输出输出输出w w的一个自底向上的分析；的一个自底向上的分析；的一个自底向上的分析；的一个自底向上的分析； 否则，输出一个出错表示。否则，输出一个出错表示。否则，输出一个出错表示。否则，
19、输出一个出错表示。方法：分别置放方法：分别置放方法：分别置放方法：分别置放s s0 0到栈中和到栈中和到栈中和到栈中和w#w#到输入缓冲器中到输入缓冲器中到输入缓冲器中到输入缓冲器中; ; 置置置置ipip指向指向指向指向w#w#的第一个符号；的第一个符号；的第一个符号；的第一个符号； repeat forever beginrepeat forever begin 令令令令s s是栈顶状态且是栈顶状态且是栈顶状态且是栈顶状态且a a是是是是ipip所指向的符号所指向的符号所指向的符号所指向的符号 if if actions,a = shift sactions,a = shift s the
20、n begin then begin 将将将将a a和和和和s s 先后先后先后先后压入栈内；压入栈内；压入栈内；压入栈内； 使使使使ipip指向输入串中的下一个符号；指向输入串中的下一个符号；指向输入串中的下一个符号；指向输入串中的下一个符号； endend算法算法1: LR分析算法分析算法 else if else if actions,a = reduce actions,a = reduce A A then begin then begin 从栈顶弹出从栈顶弹出从栈顶弹出从栈顶弹出2*|2*| | |个符号；个符号；个符号；个符号； 令令令令s s 是当前是当前是当前是当前栈顶状态；
21、栈顶状态；栈顶状态；栈顶状态； 把把把把A A和和和和gotosgotos ,A,A 先后入栈；先后入栈；先后入栈；先后入栈； 输出产生式输出产生式输出产生式输出产生式A A end end else if else if actions,a = acceptactions,a = accept then then return return else else error( ) error( ) end end 7.1.2 SLR(1)分析分析若有效项目集中存在冲突动作若有效项目集中存在冲突动作若有效项目集中存在冲突动作若有效项目集中存在冲突动作: :I = X I = X . b . b
22、, , A A . , . , B B . . 将将将将b b移进栈移进栈移进栈移进栈将将将将 归约为归约为归约为归约为A A将将将将 归约为归约为归约为归约为B B设当前输入符号为设当前输入符号为设当前输入符号为设当前输入符号为a, a,1. 1. 若若若若a = b, a = b, 则移进则移进则移进则移进; ;2. 2. 若若若若a a Follow(A), Follow(A), 则用则用则用则用A A 进行归约进行归约进行归约进行归约; ;3. 3. 若若若若a a Follow(B), Follow(B), 则用则用则用则用B B 进行归约进行归约进行归约进行归约; ;4. 4. 其
23、余情况报错其余情况报错其余情况报错其余情况报错. .SLR分析算法分析算法算法算法算法算法2 2 ( (构造构造构造构造SLRSLR分析表分析表分析表分析表) )输入：一个拓广文法输入：一个拓广文法输入：一个拓广文法输入：一个拓广文法GG 输出：对于输出：对于输出：对于输出：对于GG 的分析表的的分析表的的分析表的的分析表的action action 子表和子表和子表和子表和gotogoto子表子表子表子表方法：方法：方法：方法：1. 1. 构造构造构造构造GG 的的的的LR(0)LR(0)项目集规范族。项目集规范族。项目集规范族。项目集规范族。2. 2. 对于状态对于状态对于状态对于状态I
24、Ii i的分析动作如下：的分析动作如下：的分析动作如下：的分析动作如下： (a) (a) 若若若若A A . . aBaB I Ii i且且且且 go (Igo (Ii i ,a)=,a)= I Ij j actioni,a = shift jactioni,a = shift j (b) (b) 若若若若A A . . I Ii i, , 对于所有对于所有对于所有对于所有a a Follow(A) Follow(A) actioni,a = reduce Aactioni,a = reduce A , A , A S S (c) (c) 若若若若S SS. S. I Ii i, action
25、i, #= accept, actioni, #= accept3. 3. 若若若若go(Igo(Ii i, A) = , A) = I Ij j, A, A V VN N , , 则则则则 gotoi,Agotoi,A = j = j4. 4. 分析表其余位置为分析表其余位置为分析表其余位置为分析表其余位置为errorerrorSLR(SLR(1)算法算法：如果文法如果文法如果文法如果文法GG按按按按上述算法构上述算法构上述算法构上述算法构造出的分析表不存在冲突动作，则称造出的分析表不存在冲突动作，则称造出的分析表不存在冲突动作，则称造出的分析表不存在冲突动作，则称GG为为为为SLRSLR文
26、法。文法。文法。文法。类似地，不难定义类似地，不难定义类似地，不难定义类似地，不难定义LR(0)LR(0)文法。文法。文法。文法。 若将上述算法的若将上述算法的若将上述算法的若将上述算法的2(b)2(b)步中的步中的步中的步中的a a Follow(A)Follow(A)改为改为改为改为a a V VT T #，则由此修改后的算法所定义的文法，则由此修改后的算法所定义的文法，则由此修改后的算法所定义的文法，则由此修改后的算法所定义的文法，称为称为称为称为LR(0)文法文法。问题问题问题问题. . 如何定义如何定义如何定义如何定义LR(0)LR(0)文法？文法？文法？文法？例：例： 设文法设文法
27、GE的产生式为的产生式为EE+T | T TT*F | F F (E) | id 并用并用SLR(1)方法分析方法分析id*id+idL(GE) ?G的拓广文法的拓广文法G E ：(0) E E (4) TF (1) EE+T (5) F (E) (2) ET (6) F id(3) TT*F I I0 0:E:E.E.E E E.E+T.E+T E E.T.T T T.T*F.T*F T T.F.F F F.(E).(E) F F.id.idI I1 1(I (I0 0 E): E): E EE.E. E EE.+TE.+TI I2 2(I (I0 0 T) T) (I (I4 4 T):
28、T): E ET.T. T TT.*FT.*FI I3 3(I (I0 0 F) F) (I (I4 4 F) F) (I (I6 6 F): F): T TF.F.I I4 4(I (I0 0 ( ) ( ) (I (I4 4 ( ) ( ) (I (I6 6 ( ) ( ) (I (I7 7 ( ): ( ): F F(.E)(.E) E E.E+T.E+T E E.T.T T T.T*F.T*F T T.F.F F F.(E).(E) F F.id.idI I5 5(I (I0 0 id) id) (I (I4 4 id) id) (I (I6 6 id) id) (I (I7 7 id
29、): id): F Fid.id.I I6 6(I (I1 1 +) +) (I (I8 8 +) +) E EE+.TE+.T T T.T*F.T*F T T.F.F F F.(E).(E) F F.id.id I I7 7(I (I2 2 *) *) (I (I9 9 *): *): T TT*.FT*.F F F.(E).(E) F F.id.idI I8 8(I (I4 4 E): E): F F(E.)(E.) E EE.+TE.+TI I9 9(I (I6 6 T): T): E EE+T.E+T. T TT.*FT.*FI I1010(I (I7 7 F): F): T TT*F
30、.T*F.I I1111(I (I8 8 ): ): F F(E).(E).GG ： (0) E(0) E E (4) T E (4) TF F (1) (1) E EE+T (5) FE+T (5) F (E) (E) (2) (2) E ET (6) FT (6) F id id(3) T(3) TT*F T*F E E E EE E E+TE+TE E T TT T T*FT*FT T F FF F (E)(E)F F ididE EE E E E E E E E +T+TT TE E T T T T T T *F*F( (F F ( ( E) E) E E E+TE+TE E T TT
31、 T T*FT*FT T F F F F (E)(E) F F ididI I0 0I I1 1I I2 2I I6 6F FT T F F I I3 3F F idid ididI I5 5T TI I2 2F FI I3 3ididI I5 5( (E E E+ E+ T TT T T*FT*FT T F F F F (E)(E) F F idid+ +* *T T T* T* F F F F (E)(E) F F ididI I7 7F F (E (E ) ) E E E E +T +T E EI I8 8T TE E E+ T E+ T T T T T *F*FI I9 9F FI I
32、3 3ididI I5 5( (F FT T T* F T* F I I1010ididI I4 4( (I I4 4* *I I7 7) )F F (E) (E) + +I I6 6I I1111E E E EE E E+TE+TE E T TT T T*FT*FT T F FF F (E)(E)F F ididE EE E E E E E E E +T+TT TE E T T T T T T *F*F( (F F ( ( E) E) E E E+TE+TE E T TT T T*FT*FT T F F F F (E)(E) F F ididI I0 0I I1 1I I2 2I I6 6F
33、 FT T F F I I3 3F F idid ididI I5 5T TI I2 2F FI I3 3ididI I5 5( (E E E+ E+ T TT T T*FT*FT T F F F F (E)(E) F F idid+ +* *T T T* T* F F F F (E)(E) F F ididI I7 7F F (E (E ) ) E E E E +T +T E EI I8 8T TE E E+ T E+ T T T T T *F*FI I9 9F FI I3 3ididI I5 5( (F FT T T* F T* F I I1010ididI I4 4( (I I4 4*
34、*I I7 7) )F F (E) (E) + +I I6 6I I1111I I0 0I I1 1I I6 6I I9 9E E+ +T T* *to Ito I7 7F Fto Ito I3 3( (to Ito I4 4ididto Ito I5 5I I2 2I I7 7I I1010T T* *F F( (to Ito I4 4ididto Ito I5 5I I3 3F FI I4 4I I8 8I I1111( (E E) )+ +to Ito I6 6T Tto Ito I4 4F Fto Ito I5 5I I5 5idididid( (图图图图4.24 4.24 识别文法识
35、别文法识别文法识别文法(4.22)(4.22)的活前缀的的活前缀的的活前缀的的活前缀的 DFADFAI I1 1:E:EE E I I2 2: E : E T T I I9 9: E : E E+T E+T E E E E +T T +T T T T *F T *F T T T *F *FI=X I=X b b , A , A , B , B 若若若若 b b FOLLOW(A) FOLLOW(A) FOLLOW(B)= FOLLOW(B)=则，面对当前读入符号则，面对当前读入符号则，面对当前读入符号则，面对当前读入符号a a，状态状态状态状态I I的解决方法：的解决方法：的解决方法：的解决方
36、法： 1. 1. 若若若若a=a=b b, ,则移进。则移进。则移进。则移进。 2. 2. 若若若若a a b b, , 且且且且a a FOLLOW(A),FOLLOW(A),则用则用则用则用A A 进行归约。进行归约。进行归约。进行归约。 3. 3. 若若若若a a b b, , 且且且且a a FOLLOW(B),FOLLOW(B),则用则用则用则用B B进行归约。进行归约。进行归约。进行归约。 4. 4. 此外，报错。此外，报错。此外，报错。此外，报错。这种解决方法是比较简单的，因此称作这种解决方法是比较简单的，因此称作这种解决方法是比较简单的，因此称作这种解决方法是比较简单的，因此称
37、作SLRSLR分析，由此构造的分析表，称作分析，由此构造的分析表，称作分析，由此构造的分析表，称作分析，由此构造的分析表，称作SLRSLR分析表分析表分析表分析表。对于表达式文法的例子，对于表达式文法的例子，对于表达式文法的例子，对于表达式文法的例子，FOLLOWFOLLOW集如下：集如下：集如下：集如下：I I1 1: E: E E E E EE E +T+TI I2 2:E:ET T T T T T *F *FI I9 9:E :E E+T E+T T T T T *F*FGG ： (0) E(0) E E (4) T E (4) TF F (1) (1) E EE+T (5) FE+T
38、(5) F (E) (E) (2) (2) E ET (6) FT (6) F id id(3) T(3) TT*F T*F I I1 1:FOLLOW(E:FOLLOW(E)+=+=I I2 2: : FOLLOW(EFOLLOW(E)*)*=I I9 9: : FOLLOW(EFOLLOW(E)* *=可用可用可用可用SLR(1)SLR(1)方法实现方法实现方法实现方法实现FOLLOWFOLLOW集集集集EE# #E E# #，），），），），+ +T T# #，），），），），+ +，* *F F# #，），），），），+ +，* *表表表表4.11 4.11 文法文法文法文法(4.22
39、)(4.22)的的的的SLRSLR分析表分析表分析表分析表Follow(E)=#, +,)Follow(E)=#, +,)ACTIONACTIONGOTOGOTO+ +* *( () )idid# #E ET TF F0 0S4S4S5S51 12 23 31 1S6S6ACCACC2 2R2R2S7S7R2R2R2R23 3R4R4R4R4R4R4R4R44 4S4S4S5S58 82 23 35 5R6R6R6R6R6R6R6R66 6S4S4S5S59 93 37 7S4S4S5S510108 8S6S6S11S119 9R1R1S7S7R1R1R1R11010R3R3R3R3R3R3R
40、3R31111R5R5R5R5R5R5R5R5表：关于表：关于表：关于表：关于id*id+idid*id+id的的的的LRLR分析过程分析过程分析过程分析过程7.1.3 LR(1)分析分析例：设文法例：设文法例：设文法例：设文法GG的产生式为的产生式为的产生式为的产生式为(1) S (1) S L=R L=R(2) S (2) S R R拓广文法拓广文法拓广文法拓广文法GG的的的的LR(0)LR(0)项目集规范族为项目集规范族为项目集规范族为项目集规范族为: :I I0 0= S= S.S, .S, S S.L=R, S.L=R, S.R, L.R, L.*R, L.*R, L.id, R.i
41、d, R.L .L I I1 1= S= SS. S. I I2 2= S SL.=RL.=R, , R RL .L . I I3 3= S= SR . R . I I4 4= L= L*.R, R*.R, R.L , L.L , L.*R, L.*R, L.id .id I I5 5= L= Lid . id . I I6 6= = S SL=.R, RL=.R, R.L , L.L , L.*R, L.*R, L.id .id I I7 7= L= L*R.*R.I I8 8= R= RL.L.I I9 9= S= SL=R.L=R.(3) L (3) L *R *R(4) L (4) L
42、 id id(5) R (5) R L LI I1 1I I0 0I I3 3I I2 2I I6 6I I9 9I I8 8I I7 7I I5 5I I4 4startstartS SR RL Lidid* *= =ididididL LL LR R* * *R R图图图图: : 识别文法识别文法识别文法识别文法GSGS活前缀的活前缀的活前缀的活前缀的DFADFAI I2 2=S=SL.=R L.=R R RL.L.Follow(R) = = , # Follow(R) = = , # Action2,= = shift 6Action2,= = shift 6Action2,= = re
43、duce Action2,= = reduce R RL L移进移进移进移进归约冲突归约冲突归约冲突归约冲突GS: (0) SGS: (0) SS S (1) S (1) S L=R L=R (2) S (2) S R R(3) L (3) L *R *R(4) L (4) L id id(5) R (5) R L LLR(1)分析表的构造分析表的构造问题分析：问题分析：当识别出句柄时，活前缀中与句柄相当识别出句柄时，活前缀中与句柄相当识别出句柄时，活前缀中与句柄相当识别出句柄时，活前缀中与句柄相关的非终结符号关的非终结符号关的非终结符号关的非终结符号A A的后继符号集合，一般是非终结符的后继
44、符号集合，一般是非终结符的后继符号集合，一般是非终结符的后继符号集合，一般是非终结符号号号号A A的的的的FollowFollow集合的真子集。集合的真子集。集合的真子集。集合的真子集。 例如在例如在例如在例如在前前前前例例例例中，若活前缀中，若活前缀中，若活前缀中，若活前缀L L是句柄，则它的后继是句柄，则它的后继是句柄，则它的后继是句柄，则它的后继符号集合为符号集合为符号集合为符号集合为#，而，而，而，而Follow(L) = =, # Follow(L) = =, # 。所以，只有所以，只有所以，只有所以，只有在输入符号为在输入符号为在输入符号为在输入符号为# #时时时时, , 用用用用
45、R RL L进行归约进行归约进行归约进行归约, , 而输入符号为而输入符号为而输入符号为而输入符号为= =时时时时, , 移进。移进。移进。移进。 可见可见可见可见用用用用FollowFollow集合来消除分析表的多重入口还是集合来消除分析表的多重入口还是集合来消除分析表的多重入口还是集合来消除分析表的多重入口还是略嫌粗糙。略嫌粗糙。略嫌粗糙。略嫌粗糙。LR(1)LR(1)项目项目项目项目: : 由由由由LR(0)LR(0)项目项目项目项目和一个和一个和一个和一个lookaheadlookahead符号符号符号符号组成组成组成组成 A A . . , a , a LR(1)分析法的思想分析法的
46、思想：用活前缀中与句柄相关的非终结符号用活前缀中与句柄相关的非终结符号用活前缀中与句柄相关的非终结符号用活前缀中与句柄相关的非终结符号A A的后继符号的后继符号的后继符号的后继符号 ( (亦称为搜索符亦称为搜索符亦称为搜索符亦称为搜索符) )集合，而不是集合，而不是集合，而不是集合，而不是Follow(A)Follow(A)，来避免分析来避免分析来避免分析来避免分析表的多重入口。表的多重入口。表的多重入口。表的多重入口。 重新定义项目，重新定义项目，重新定义项目，重新定义项目， 使每个项目附带一个向前搜索符使每个项目附带一个向前搜索符使每个项目附带一个向前搜索符使每个项目附带一个向前搜索符定义
47、定义 (LR(1)有效项目有效项目)：LR(1)LR(1)项目项目项目项目AA . . , a (a, a (a V VT T #)#)对活前缀对活前缀对活前缀对活前缀是是是是有效的，如果存在规范推导有效的，如果存在规范推导有效的，如果存在规范推导有效的，如果存在规范推导 S S * * AwAww w 且且且且a a First(w#)First(w#)。定理：定理：若若若若LR(1)LR(1)项目项目项目项目AA . B . B , a, a对活前缀对活前缀对活前缀对活前缀是有效的，是有效的，是有效的，是有效的，且且且且 B B 是一个产生式，则对任何是一个产生式，则对任何是一个产生式，则
48、对任何是一个产生式，则对任何b b First(First( a)a)，项项项项目目目目B B . . , b, b也是活前缀也是活前缀也是活前缀也是活前缀的有效项目。的有效项目。的有效项目。的有效项目。 例例例例. . 构造构造构造构造文法文法文法文法GGSS的的的的LR(1)LR(1)分析表。分析表。分析表。分析表。LR(1)LR(1)项目集规范族项目集规范族项目集规范族项目集规范族I I0 0: : S S.S .S # # S S.L=R #.L=R # S S.R #.R # L L.*R =/#.*R =/# L L.id =/#.id =/# R R.L #.L #I I1 1:
49、(I:(I0 0 S) S) S SS. #S. #I I2 2:(I:(I0 0 L) L) S SL.=R #L.=R # R RL. #L. #I I3 3:(I:(I0 0 R) R) S SR. #R. # I I4 4:(I:(I0 0 *)(I *)(I4 4 *) *) L L*.R *.R = =/#/# R R.L =/#.L =/# L L.*R =/#.*R =/# L L.id =/#.id =/#I I5 5:(I:(I0 0 id)(I id)(I4 4 id) id) L Lid. id. = =/#/#I I6 6:(I:(I2 2 =) =) S SL=.R
50、 #L=.R # R R.L #.L # L L.*R #.*R # L L.id #.id #I I7 7:(I:(I4 4 R) R) L L*R. =/#*R. =/#I I8 8:(I:(I4 4 L) L) R RL. =/#L. =/# I I9 9: :(I (I6 6 R) R) S SL=R. #L=R. #I I1010:(I:(I6 6 L)(I L)(I1111 L) L) R RL. #L. #I I1111:(I:(I6 6 *)(I *)(I1111 *) *) L L*.R #*.R # R R.L #.L # L L.*R #.*R # L L.id #.id
51、 #I I1212:(I:(I6 6 id)(I id)(I1111 id) id) L Lid. #id. #I I1313:(I:(I1111 R) R) L L*R. #*R. #GS: (0) SGS: (0) SS S (1) S (1) S L=R L=R (2) S (2) S R R(3) L (3) L *R *R(4) L (4) L id id(5) R (5) R L Lactionactiongotogoto状状状状态态态态 = * id # S L R= * id # S L R0 s4 s5 1 2 30 s4 s5 1 2 31 acc 1 acc 2 s6 r
52、52 s6 r53 r2 3 r2 4 s4 s5 8 74 s4 s5 8 75 r4 r45 r4 r46 s11 s12 10 9 6 s11 s12 10 9 7 r3 r3 7 r3 r3 8 r5 r58 r5 r59 r19 r110 r5 10 r5 11 s11 s12 10 13 11 s11 s12 10 13 12 r412 r413 r3 13 r3 例：例：例：例：构造文法构造文法构造文法构造文法 S S C C C C C C c C | d c C | d的的的的LR(1)LR(1)和和和和LALRLALR分析表。分析表。分析表。分析表。S S.S,.S,# #
53、S S.CC,#.CC,#C C.cC,c/d.cC,c/dC C.d,c/d.d,c/d I I0 0S SC.C,#C.C,#C C.cC.cC,# ,#C C.d,#.d,# I I2 2S SS.,#S.,# I I1 1S SCC.,#CC.,# I I5 5S SC CC CC Cc.C,#c.C,#C C.cC.cC,# ,#C C.d,#.d,# I I6 6C CcCcC.,#.,# I I9 9C Cc cC Cd.,#d.,# I I7 7d dc cC Cc.C, c.C, c/dc/dC C.cC.cC, c/d, c/dC C.d.d, c/d, c/d I I3
54、3C CcC.,c/dcC.,c/d I I8 8C Cc cC Cd.,d.,c/dc/d I I4 4d dc c图：图：图：图： 对于文法的转移函数图对于文法的转移函数图对于文法的转移函数图对于文法的转移函数图 文法的文法的LR(1)分析表分析表S.SS.CCC.cCC.d I0SC.CC.cCC.d I2SS. I1SCC. I5SCCCc.CC.cCC.d I3CcC. I6CcCd. I4dccd 文法的文法的文法的文法的LR(1)LR(1)分析表分析表分析表分析表文法的文法的文法的文法的LALR(1)LALR(1)分析表分析表分析表分析表7.1.4 LALR分析表的构造分析表的构
55、造 LR(k)LR(k)方法分析能力很强，但是也耗费大量存储空间。在方法分析能力很强，但是也耗费大量存储空间。在方法分析能力很强，但是也耗费大量存储空间。在方法分析能力很强，但是也耗费大量存储空间。在实际应用中，还须简化。观察实际应用中，还须简化。观察实际应用中，还须简化。观察实际应用中，还须简化。观察图图图图4.274.27可知可知可知可知: :1 1、从、从、从、从自动机状态等价自动机状态等价自动机状态等价自动机状态等价的角度来看，图中彩色相同的状态是等价的角度来看，图中彩色相同的状态是等价的角度来看，图中彩色相同的状态是等价的角度来看，图中彩色相同的状态是等价的。这些等价状态的特点是，它
56、们的的。这些等价状态的特点是，它们的的。这些等价状态的特点是，它们的的。这些等价状态的特点是，它们的LR(0)LR(0)有效项目集相同。由有效项目集相同。由有效项目集相同。由有效项目集相同。由于判断是否等价只须比较状态的输出弧，因而不难看出，于判断是否等价只须比较状态的输出弧，因而不难看出，于判断是否等价只须比较状态的输出弧，因而不难看出，于判断是否等价只须比较状态的输出弧，因而不难看出，LR(0)LR(0)有效项目集相同的状态必定等价有效项目集相同的状态必定等价有效项目集相同的状态必定等价有效项目集相同的状态必定等价。2 2、对于初始状态、对于初始状态、对于初始状态、对于初始状态I I0 0
57、，其中的其中的其中的其中的有效项目有效项目有效项目有效项目均可从项目均可从项目均可从项目均可从项目SS.S, #.S, #推导出来；对于非初始状态推导出来；对于非初始状态推导出来；对于非初始状态推导出来；对于非初始状态I I2 2, I, I3 3, I, I6 6，则其中则其中则其中则其中“ “点在最左端点在最左端点在最左端点在最左端” ”的的的的项目均可由项目均可由项目均可由项目均可由“ “点不在最左端点不在最左端点不在最左端点不在最左端” ”的项目推导出来。观察的项目推导出来。观察的项目推导出来。观察的项目推导出来。观察图图图图也可以也可以也可以也可以得到相同结果。因此在实际存储状态时，
58、可以只存储得到相同结果。因此在实际存储状态时，可以只存储得到相同结果。因此在实际存储状态时，可以只存储得到相同结果。因此在实际存储状态时，可以只存储“ “点不在点不在点不在点不在最左端最左端最左端最左端” ”的项目。的项目。的项目。的项目。为了叙述方便，引入为了叙述方便，引入为了叙述方便，引入为了叙述方便，引入“ “同心项同心项同心项同心项” ”和项目集的和项目集的和项目集的和项目集的“ “核核核核” ”的概念：的概念：的概念：的概念：定义定义定义定义 ( (同心项同心项同心项同心项) )：如果两个如果两个如果两个如果两个LR(1)LR(1)项目集去掉搜索符之后是相项目集去掉搜索符之后是相项目
59、集去掉搜索符之后是相项目集去掉搜索符之后是相同的，则称这两个项目集具有相同的心。同的，则称这两个项目集具有相同的心。同的，则称这两个项目集具有相同的心。同的，则称这两个项目集具有相同的心。 定义定义定义定义 ( (核核核核) )： 对于初始状态对于初始状态对于初始状态对于初始状态I I0 0，有效项目有效项目有效项目有效项目SS.S, #.S, #称为称为称为称为I I0 0的的的的核；而对于非初始状态，则其中核；而对于非初始状态，则其中核；而对于非初始状态，则其中核；而对于非初始状态，则其中 “ “点不在最左端点不在最左端点不在最左端点不在最左端” ”的有效项目的有效项目的有效项目的有效项目
60、称为它的核。称为它的核。称为它的核。称为它的核。LALRLALR分析法的基本思想：分析法的基本思想：分析法的基本思想：分析法的基本思想：在在在在LR(1)LR(1)项目集规范族中，合并项目集规范族中，合并项目集规范族中，合并项目集规范族中，合并同心项以减少状态的数目；在存储同心项以减少状态的数目；在存储同心项以减少状态的数目；在存储同心项以减少状态的数目；在存储LR(1)LR(1)有效项目集时，仅存储有效项目集时，仅存储有效项目集时，仅存储有效项目集时，仅存储其中的核。其中的核。其中的核。其中的核。 注意，由于同心项的合并，使项目的搜索符与活前缀的对注意，由于同心项的合并，使项目的搜索符与活前
61、缀的对注意，由于同心项的合并，使项目的搜索符与活前缀的对注意，由于同心项的合并，使项目的搜索符与活前缀的对应关系不唯一，降低了分析器的识别能力，参见以下两例。应关系不唯一，降低了分析器的识别能力，参见以下两例。应关系不唯一，降低了分析器的识别能力，参见以下两例。应关系不唯一，降低了分析器的识别能力，参见以下两例。C Cc.C, c/d/#c.C, c/d/#C C.cC.cC, c/d/#, c/d/#C C.d, c/d/#.d, c/d/# I I3636I I0 0CcCc+ + | c | c+ +C CcC.,c/dcC.,c/d/#/# I I8989C C 活前缀活前缀活前缀活前
62、缀CcCc+ +与搜索符与搜索符与搜索符与搜索符# #对应，对应，对应，对应， 而活前缀而活前缀而活前缀而活前缀c c+ +与搜索符与搜索符与搜索符与搜索符c c和和和和d d对应。对应。对应。对应。当合并后的自动机识别出活前缀当合并后的自动机识别出活前缀当合并后的自动机识别出活前缀当合并后的自动机识别出活前缀CcCCcC时，若当前的输时，若当前的输时，若当前的输时，若当前的输入符号是入符号是入符号是入符号是c c或或或或d d，LR(1)LR(1)分析器马上就能发现出错，而分析器马上就能发现出错，而分析器马上就能发现出错，而分析器马上就能发现出错，而LALRLALR分析器此时则不行，必须先归
63、约，得到活前缀分析器此时则不行，必须先归约，得到活前缀分析器此时则不行，必须先归约，得到活前缀分析器此时则不行，必须先归约，得到活前缀CCCC后才能发现出错。后才能发现出错。后才能发现出错。后才能发现出错。例：例：例：例：在在在在图图图图中，中，中，中，I I3 3和和和和I I6 6，I I8 8和和和和I I9 9合并后得到如下部分状态图合并后得到如下部分状态图合并后得到如下部分状态图合并后得到如下部分状态图问题问题问题问题: : LALR LALR分析器识别活前缀的能力是否比分析器识别活前缀的能力是否比分析器识别活前缀的能力是否比分析器识别活前缀的能力是否比LR(1)LR(1)的差？的差
64、？的差？的差？答：一样。既然都是识别文法活前缀的自动机，它们答：一样。既然都是识别文法活前缀的自动机，它们答：一样。既然都是识别文法活前缀的自动机，它们答：一样。既然都是识别文法活前缀的自动机，它们就是等价的。就是等价的。就是等价的。就是等价的。例：例：例：例：考虑文法考虑文法考虑文法考虑文法GG S SS S S SaAdaAd | | bBdbBd | | aBeaBe | | bAebAe A Ac c B Bc c构造构造构造构造GG的的的的LR(1)LR(1)项目集规范族如下项目集规范族如下项目集规范族如下项目集规范族如下I I0 0: : S S.S #.S # S S.aAd.a
65、Ad # # S S.bBd.bBd # # S S.aBe.aBe # # S S.bAe.bAe # #I I1 1:(I:(I0 0 S) S) S SS. #S. #I I2 2:(I:(I0 0 a) a) S Sa.Ad #a.Ad # S Sa.Be #a.Be # A A.c d.c d B B.c e.c eI I3 3:(I:(I0 0 b) b) S Sb.Bdb.Bd # # S Sb.Aeb.Ae # # A A.c e.c e B B.c d.c dI I4 4:(I:(I2 2 A) A) S SaA.daA.d # #I I5 5:(I:(I2 2 B) B)
66、S SaB.eaB.e # #I I6 6:(I:(I2 2 c) c) A Ac. dc. d B Bc. ec. eI I7 7:(I:(I3 3 B) B) S SbB.dbB.d # #I I8 8:(I:(I3 3 A) A) S SbA.ebA.e # #I I9 9:(I:(I3 3 c) c) A Ac. ec. e B Bc. dc. dI I1010:(I:(I4 4 d) d) S SaAdaAd. #. #I I1111:(I:(I4 4 e) e) S SaBeaBe. #. #I I1212:(I:(I7 7 d) d) S SbBdbBd. #. #I I1313
67、:(I:(I8 8 e) e) S SbAebAe. #. #I I6969: : A Ac. d/ec. d/e B Bc. d/ec. d/e合并同心项合并同心项合并同心项合并同心项若将同心项若将同心项若将同心项若将同心项I I6 6和和和和I I9 9合并，则得到项目集合并，则得到项目集合并，则得到项目集合并，则得到项目集 I I6969: : A Ac. d/ec. d/e B Bc. d/ec. d/e该项目集含该项目集含该项目集含该项目集含“ “归约归约归约归约- -归约归约归约归约” ”冲突。冲突。冲突。冲突。因此，文法因此，文法因此，文法因此，文法GG是是是是LR(1)LR(1
68、)文法，但不是文法，但不是文法，但不是文法，但不是LALRLALR文法。文法。文法。文法。一、一、LALR(1)分析表的原理性构造方法分析表的原理性构造方法 构造构造构造构造LR(1)LR(1)项目集族项目集族项目集族项目集族, , 如果它不存在冲突如果它不存在冲突如果它不存在冲突如果它不存在冲突, , 就把就把就把就把同心集合并在一起。若同心集合并在一起。若同心集合并在一起。若同心集合并在一起。若合并后合并后合并后合并后不存在归约不存在归约不存在归约不存在归约- -归约冲突归约冲突归约冲突归约冲突，则按这个集族构造文法则按这个集族构造文法则按这个集族构造文法则按这个集族构造文法LALR(1)
69、LALR(1)分析表。分析表。分析表。分析表。算法：算法：算法：算法： LALRLALR分析表的构造分析表的构造分析表的构造分析表的构造输入：拓广文法输入：拓广文法输入：拓广文法输入：拓广文法GG输出：对于输出：对于输出：对于输出：对于GG的的的的LALR(1)LALR(1)分析表分析表分析表分析表 方法：方法：方法：方法：1. 1. 构造文法的构造文法的构造文法的构造文法的LR(1)LR(1)项目集族项目集族项目集族项目集族C=IC=I0 0, I, I1 1, , I, , In n 2. 2.合并合并合并合并C C中的同心集，得到中的同心集，得到中的同心集，得到中的同心集，得到C=JC=
70、J0 0, J, J1 1, , , , J Jmm 3. 3. 从从从从CC出发构造出发构造出发构造出发构造actionaction表表表表: : (a) (a) 若若若若AA . a . a ,b ,b J Ji i且且且且 go (go (J Ji i ,a)=,a)= J Jj j 置置置置actioni,a = shift jactioni,a = shift j (b) (b) 若若若若AA. ,a . ,a J Ji i, ,置置置置actioni,a = r Aactioni,a = r A , A , A S S (c) (c) 若若若若SSS., # S., # J Ji
71、i, ,置置置置actioni, #= acceptactioni, #= accept 4. 4. 若若若若go(Igo(Ik k, A) = , A) = J Jj j, A, A V VN N , , 则则则则 gotok,Agotok,A = j = j 5. 5. 分析表其余位置为分析表其余位置为分析表其余位置为分析表其余位置为errorerror二、二、LALR分析表的有效构造方法分析表的有效构造方法 前算法在构造前算法在构造前算法在构造前算法在构造LALRLALR分析表时，耗费的存储空间与分析表时，耗费的存储空间与分析表时，耗费的存储空间与分析表时，耗费的存储空间与LR(1)LR
72、(1)算算算算法完全相同，代价还是太大。可以从两个方面改进：法完全相同，代价还是太大。可以从两个方面改进：法完全相同，代价还是太大。可以从两个方面改进：法完全相同，代价还是太大。可以从两个方面改进：1 1、存储有效项目集时，只存储它们的核，每当需要完、存储有效项目集时，只存储它们的核，每当需要完、存储有效项目集时，只存储它们的核，每当需要完、存储有效项目集时，只存储它们的核，每当需要完整的有效项目集时，再根据核来计算。整的有效项目集时，再根据核来计算。整的有效项目集时，再根据核来计算。整的有效项目集时，再根据核来计算。2 2、直接生成、直接生成、直接生成、直接生成LALRLALR项目集规范族的
73、核，这是有效构造项目集规范族的核，这是有效构造项目集规范族的核，这是有效构造项目集规范族的核，这是有效构造方法的关键。方法的关键。方法的关键。方法的关键。 注意，注意，注意，注意，LALRLALR项目的搜索符一般是与该项目相关的非终结符项目的搜索符一般是与该项目相关的非终结符项目的搜索符一般是与该项目相关的非终结符项目的搜索符一般是与该项目相关的非终结符号的号的号的号的FollowFollow集的子集，这正是集的子集，这正是集的子集，这正是集的子集，这正是LALRLALR分析法比分析法比分析法比分析法比SLRSLR分析法强的原分析法强的原分析法强的原分析法强的原因。因。因。因。直接生成直接生成
74、直接生成直接生成LALRLALR项目集规范族的项目集规范族的项目集规范族的项目集规范族的核核的方法如下：的方法如下：的方法如下：的方法如下：(1)(1)构造构造构造构造LR(0)LR(0)项目集规范族的核及其自动机。项目集规范族的核及其自动机。项目集规范族的核及其自动机。项目集规范族的核及其自动机。(2)(2)为为为为LR(0)LR(0)项目集规范簇中的每个核项目配上适当的搜索符。项目集规范簇中的每个核项目配上适当的搜索符。项目集规范簇中的每个核项目配上适当的搜索符。项目集规范簇中的每个核项目配上适当的搜索符。核项目的搜索符无非有两种产生途径：核项目的搜索符无非有两种产生途径：核项目的搜索符无
75、非有两种产生途径：核项目的搜索符无非有两种产生途径：若搜索符从其父核传递下来，则称这样的搜索符为若搜索符从其父核传递下来，则称这样的搜索符为若搜索符从其父核传递下来，则称这样的搜索符为若搜索符从其父核传递下来，则称这样的搜索符为“ “传播的传播的传播的传播的” ”；否则，称搜索符为；否则，称搜索符为；否则，称搜索符为；否则，称搜索符为“ “自生的自生的自生的自生的” ”。下面算法确定核项目的搜索符是下面算法确定核项目的搜索符是下面算法确定核项目的搜索符是下面算法确定核项目的搜索符是自生的自生的自生的自生的或者是或者是或者是或者是传播的传播的传播的传播的：for for 有效项目集有效项目集有效
76、项目集有效项目集I I的核的核的核的核KK中的每一项目中的每一项目中的每一项目中的每一项目B B. . do begin do begin J = closure( J = closure(B B. . , #);, #); for J for J中的每一个项目中的每一个项目中的每一个项目中的每一个项目AA.X.X , a do, a do 如果如果如果如果a#a#，则有效项目集则有效项目集则有效项目集则有效项目集go(I, X)go(I, X)中的核项目中的核项目中的核项目中的核项目AAX.X. , , aa中的搜索符是自生的，否则就是传播的。中的搜索符是自生的，否则就是传播的。中的搜索符是
77、自生的，否则就是传播的。中的搜索符是自生的，否则就是传播的。练习：已知文法：练习：已知文法：请构造请构造LALR分析表。分析表。构造构造构造构造文法文法文法文法的的的的LALR(1)LALR(1)项目集的核。项目集的核。项目集的核。项目集的核。LR(0)LR(0)项目集的核：项目集的核：项目集的核：项目集的核：I I0 0: S: S.S .S I I1 1: S: SS. S. I I2 2: : S SL.=R L.=R I I3 3: : S SR. R. I I4 4: : L L*.R *.R I I5 5: : L Lid. id. I I6 6: : S SL=.R L=.R I
78、 I7 7: : L L*R. *R. I I8 8: : R RL. L. I I9 9: : S SL=R. L=R. 计算计算计算计算closure(closure(S S.S ,#.S ,#) S S.S #.S # S S.L=R #.L=R # S S.R #.R # L L.*R # /.*R # / = = L L.id # / .id # / = = R R.L #.L #GS: (0) SGS: (0) SS S (1) S (1) S L=R L=R (2) S (2) S R R(3) L (3) L *R *R(4) L (4) L id id(5) R (5) R L L表表表表4.15 4.15 搜索符的传播搜索符的传播搜索符的传播搜索符的传播表表表表4.16 4.16 搜索符的计算搜索符的计算搜索符的计算搜索符的计算Thanks.
