第4章语法分析(4)

1、1第四章第四章 语法分析语法分析(4)4.7 LR(1)、LALR24.6.5 可行前缀（可行前缀（viable prefix）q 对于一个文法G，构造一个LR（0）自动机，它能识别所有可能出现在分析栈中的文法符号串，栈中的文法符号串一定是某个右句型的前缀。q 不是右句型的所有前缀都会出现在栈中。xSrm*id*)(id*EFErmrm例如：前缀(E)*不会出现在栈中。3q 可以出现在移进归约分析器栈中的右句型的前缀称为可行前缀。q 定义：一个可行前缀是一个右句型的前缀，并且不含右句柄一个可行前缀是一个右句型的前缀，并且不含右句柄之后的任何符号之后的任何符号。例如：对于右句型(E)*id,(

2、(、(E、(E)是可行前缀， (E)*不是可行前缀q 可行前缀后加上终结符可以得到右句型。q 只有输入串中已分析过的那部分能归约成可行前缀，就没有语法错误。q 事实上，LR（0）自动机是一个识别可行前缀的识别可行前缀的DFADFA。产生式： F (E) | id4识别识别G的所有可行前缀的的所有可行前缀的NFAqNFA的状态是一个LR(0)项目。q从每个形如B X的状态出发画一条标记为X的弧到状态BX ，q从每个形如B A的状态出发画一条标记为的弧到所有形如A 的状态。q这个NFA通过子集构造法得到的DFA和前面构造的LR(0)自动机是相同的。5例：例：p153 描述文法的可行前缀描述文法的可

3、行前缀S SS SS+| SS* | a文法的项目有：1. S S 2. S S3. S SS+4. S SS+ 5. S SS +6. S SS+ 7. S SS*8. S SS*9. S SS*10. S SS*11 S a12. S a6startS123 7 S4S511 S8S12 识别可行前缀的识别可行前缀的NFA +69*10 aS SS SS+| SS* | a一个项目对应NFA的一个状态 1. S S 2. S S3. S SS+4. S SS+ 5. S SS +6. S SS+ 7. S SS*8. S SS*9. S SS*10. S SS*11 S a12. S a7

4、S.SS.SS+S.SS*S.a I0startSa识别可行前缀的识别可行前缀的DFASS .SS. S+SS. S*S.SS+S.SS*S.a I1Sa . I2SSS . +SSS . * SS. S+SS. S*S.SS+S.SS*S.a I3SaSSS +. I4SaSSS *. I5+*8有效项目有效项目q 如果存在一个最右推导S Aw 12w， 则称项项A A 1 1 2 2 对可行前缀有效的对可行前缀有效的。q 若项目A1 B2 对可行前缀1 是有效的，且 B 是产生式，则项目项目 B B 对可行前缀对可行前缀1 1 也是有效的也是有效的。据假设，存在一个最右推导S *Aw 1B

5、2w设2w * xw， 则对任何B 有最右推导S *Aw 1 B 2w 1 Bxw 1 xw所以 B . 对可行前缀 1 也是有效的。*两个条件：两个条件： 1是可行前缀，是可行前缀， 1 1是是1 的后缀的后缀9q一个项目可能对好几个可行前缀都是有效的。qE E+T对 和和( (这两个可行前缀都有效 E+T ，E E (，1都为空) ( E+T)， E E (E) ( =“(”，1为空)qDFA读入 和和( (后到达不同的状态，那么项目E E+T就出现在不同的项目集中S Aw 1 B 2w 1 Bxw 1 xw*10有效项目集和项目集规范族有效项目集和项目集规范族q 文法G的某个可行前缀的所

6、有有效项目组成的集合，称为可行前缀的LR(0)有效项目集。例如：I0，I1，I2都是有效项目集。q 文法G的所有有效项目集组成的集合，称为G的LR(0)项目集规范族。例如：I0，I1，I211I0I1I6I9E+T*to I7Fto I3(to I4idto I5I2I7I10T*F(to I4idto I5I3FI4I8I11(E)+to I6Tto I2Fto I3I5idid(图4.36 识别可行前缀的 DFA124.6.4 构造SLR分析表q 算法算法 4.32 构造SLR分析表输入：一个拓广文法G输出：G 的SLR分析表的函数action和goto方法：1. 构造G 的LR(0)项目

7、集规范族C = I0, I2, , In。2. 对于状态Ii的分析动作如下： (a) 若A . aB Ii且 goto (Ii ,a)= Ij actioni, a = “shift j” (b) 若A . Ii, 对于所有a FOLLOW(A) actioni, a = “reduce A” , A S (c) 若SS. Ii, actioni, $= “accept”3. 若goto(Ii, A) = Ij, AVN , 则 gotoi,A = j4. 分析表其余位置为error13例例4.34 每个每个SLR(1)文法都不是二义的，但是，文法都不是二义的，但是，有许多非二义的文法不是有许

8、多非二义的文法不是SLR(1)。 q 例如，下面的产生式文法S L=RS RL *RL idR L14拓广文法拓广文法G 的的LR(0)项目集规范族为：项目集规范族为：I0:S SS L=RS RL *RL idR LI3:SR I4:L* RR L L *RL idI5:Lid I6:SL= RR LL *RL idI7:L*R I8:RL I9:SL=R I1:SS I2:SL =RRL 15idS SS L=RS RL *RL idR LL id S L =RR L S S I0I1I2I3S R I4L * RR LL idL * RI5SL*idRS L= RR LL *RL idI

9、6=RS L=R R L LLI7idI3*L *R RI8I916第一个项目使得 action2, = 为shift 第二个项目使得 action2, = 为reduce，因为 = Follow(R)。S L = R * R = R但是，不存在以R=开始的右句型，只有* R = 开始的右句型。SLR(1)文法的描述能力有限文法的描述能力有限S SS L=RS RL *RL idR LS L =RR L I0I2L174.7 构造规范的构造规范的LR分析表分析表q 例 I2有两个项目SL =R和RL q 当下一个输入为=时用RL 归约，但是文法没有以R=开始的右句型，只有以*R=开始的右句型，

10、可见，仅仅知道可行前缀L，不应当进行归约。q 扩充项目的定义！产生式文法S L=RS RL *RL idR L18action goto 状 态 id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 图图4.31 表达式文法的表达式文法的LR(0)分析表分析表r2r2r4r4r6r6r1r1r3r3r5r

11、5LR(0)和和SLR的区别：减少了一些不该规约的动作的区别：减少了一些不该规约的动作I2: E T. ，T T.*F19FOLLOW(E)=$, +,)文法文法4.34的的SLR分析表分析表action goto 状 态 id + * ( ) $ E T F 0 1 2 3 4 5 6 7 8 9 10 11 s5 s4 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 r6 r6 r6 r6 s5 s4 s5 s4 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5 1 2 3 8 2 3 9 3 10 I2: E T. ，T T.

12、*F20LR(1)项目q 重新定义项目，让它带上搜索符(向前看符号)，成为如下形式q LR(1)项目项目: 由由LR(0)项目项目和一个和一个lookahead符号符号组成组成 A. , a q 对于项目 A, a ，搜索符a表示只有当下一个输入符号是a时，才能进行归约。 这样的a的集合一定是FOLLOW(A)的一个子集，可能是真子集。SLR中，中，A. 可以看成可以看成 A. , Follow(A)21qLR(1)项目A, a对可行前缀有效，如果存在着推导S *rm Aw rm w，其中： = ，且1. a是w的第一个符号，或者w为且a是$。22例4.37考虑文法：S BBB aB | ba

13、aaBabaaBabaBabBabBaBBBSrmrmrmrmrmrm从最右推导S *rm aaBab rm aaaBab看出：Ba B, a对可行前缀 = aaa是有效的；从最右推导S *rm BaB rm BaaB看出：Ba B, $对可行前缀 = Baa是有效的。这个文法生成的语言是什么？a*ba*bB=aB=aaB=aaaB=aaabLR(1)项目A, a对可行前缀有效，如果存在着推导S *rm Aw rm w，其中： = ，且1.a是w的第一个符号，或者w为且a是$。23构造有效的LR(1)项目集q 考虑对可行前缀有效的项目A B, a，必定存在最右推导S *rm Aax rm Ba

14、x，其中 = 。q 假设ax能推出by，那么， B , b对有效，b是从 能推出的第一个终结符，或当 可空时，b就是a。bFIRST(ax)= FIRST(a) 。LR(1)项目A, a对可行前缀有效，如果存在着推导S *rm Aw rm w，其中： = ，且1.a是w的第一个符号，或者w为且a是$。证明：S *rm Aax rm Bax rm Bby rm by 24算法4.38 LR(1)项目集的构造输入：拓广文法G。输出： LR(1)项目集规范族，是对G 的一个或多个可行前缀有效的项目集。方法：如图4-40所示。25function closure(I) repeat for ( I中的

15、每个项目 A B, a ) for ( G中的每个产生式 B ) for ( FIRST(a)中的每个终结符号b ) 将 B. , b加入到集合 I中中 until 不能在I中加入更多的项 return IFig4.40 LR(1) 项目集的构造项目集的构造 for G 26function goto(I, X)Begin J= ； for (I中的每个项目 A X, a )将项目 A X , a 加入到集合J中 return closure(J)end27procedure items(G )begin C = closure(S S, $); repeat for ( C中的每个项目集 I

16、 )for( 每个文法符号X ) if( goto(I, X) 非空且不在C中 ) 将goto(I, X) 加入到C中； until 不再有新的项集加入到 C 中end28计算S.S,$的闭包I0：S.S, $ S.CC, $ First( $)=$ C.cC, c/d First(C$)=c,d C.d, c/d for ( FIRST( a)中的每个终结符号中的每个终结符号b ) 将将 B. , b加入到集合加入到集合 I中中构造文法S S S C CC c C | d的LR(1) 分析表。C.cC, c/d是C.cC , c 和 C.cC , d的缩写项目 A B, a 搜索符29SC.

17、C,$C.cC,$C.d,$ I2CS .S,$S.CC,$C.cC,c/dC.d,c/d I0S S.,$ I1SCc.C, c/dC.cC, c/dC.d, c/d I3cCd.,c/d I4dSCC.,$ I5CCc.C,$C.cC,$C.d,$ I6CcC.,$ I9CcCd.,$ I7dcCcC.,c/d I8Ccdd新增很多状态。30算法算法4.40 规范规范LR(1)语法分析表的构造语法分析表的构造输入：拓广文法G。输出：文法G的规范LR语法分析表函数action和goto。方法：1. 构造G 的LR(1)项目集规范族C=I0, I1, , In。2. 从Ii构造分析器的状态i，

18、状态i的action函数确定如下： 若A a, b在Ii中，且goto(Ii, a) = Ij，则置actioni, a为“shift j”； 若A , a在Ii中，且A S，则置actioni, a为“reduce j”，j是产生式A 的序号；若SS, $在Ii中，则置actioni, $为“accept”。31算法算法4.40 规范规范LR(1)语法分析表的构造语法分析表的构造3. 状态i的goto函数确定如下：若goto(Ii, A) = Ij，则gotoi, A = j4. 用上面规则未能定义的所有条目都置为error。5. 语法分析器的初始状态是包含SS, $的项目集对应的状态。32

19、图图4-42 LR(1)分析表分析表33q 每个SLR(1)文法都是LR(1)文法。q 有的文法是LR(1)但不是SLR(1)的。q LR(1)语法分析器的状态数目比SLR(1)分析器的状态数目多。S L = RS R L * RL id R L I0 : S S， $S L = R, $S R, $L * * R, =/$L id, =/$ R L, $I2 : S L = R, $R L , $L 构造文法的构造文法的LR(1)分析表分析表不存在移进不存在移进归约冲突归约冲突S L = R, Follow(S)R L , Follow(R) 在SLR中，Follow(R)=,$35I0S

20、S， $S L = R, $S R, $L * R, =/$L id, =/$ R L, $I6S L = R, $R L, $L * R, $L id, $=I7L *R , =/$R I8R L , =/$L * S I1 SS., $ I2S L = R, $R L , $L I3S R , $R I4L * R, =/$R L, =/$L * R, =/$L id, =/$* I5L id , =/$id id I9S L= R, $R L I10R L , $I12L id , $id I11L * R, $R L, $L * R, $L id, $* * I13L *R , $R

21、id L 36BabSS S, $ I1S BB, $B aB, $B b, $ I2BB aB, b/aB aB, b/aB b, b/a I3Bb, b/a I4baaS BB, $ I5B aB, $B aB, $B b, $ I6B aB, $ I9B b, $ I7B aB, b/a I8BaBbb例例4.37文法的文法的LR(1)项目集转移图项目集转移图S S, $ I0S BB, $B aB, b/aB b, b/a引入引入LALR(1)37BabSS S, $ I1S BB, $B aB, $B b, $ I2BB aB, b/aB aB, b/aB b, b/a I3Bb,

22、b/a I4baaS BB, $ I5B aB, $B aB, $B b, $ I6B aB, $ I9B b, $ I7B aB, b/a I8BaBbb合并同心项合并同心项S S, $ I0S BB, $B aB, b/aB b, b/a38abbSS S, $ I1S BB, $B aB, $B b, $ I2BB aB, b/a/$B aB, b/a/$B b, b/a/$ I3Bb, b/a/$ I4baaS BB, $ I5B aB, b/a/$ I8BB合并同心项合并同心项S S, $ I0S BB, $B aB, b/aB b, b/a394.7.4 构造构造LALR语法分析表

23、语法分析表q LR(k)方法分析能力很强，但是耗费大量存储空间。在实际应用中，还须简化。q 观察图4.41可知:从自动机状态等价的角度来看，图中彩色相同的状态是等价的。这些等价状态的特点是，它们的LR(0)有效项目集相同。由于判断是否等价只须比较状态的输出弧，因而LR(0)有效项目集相同的状态必定等价。40q 对于初始状态I0，其中的有效项目均可从项目S.S, $推导出来；q 对于非初始状态I2, I3, I6，则其中“点在最左端点在最左端”的项目均可由“点不在最左端点不在最左端”的项目推导出来。因此在实际存储状态时，可以只存储“点不在最左端点不在最左端”的项目。41引入引入“同心项同心项”和

24、和 “核核”的概念：的概念：q 同心项同心项：如果两个LR(1)项目集去掉搜索符之后是相同的，则称这两个项目集具有相同的核心(core)。q 内核项目内核项目： 对于初始状态I0 ，有效项目S.S, $称为I0的内核项目；而对于非初始状态，则其中 “点不在最左端”的有效项目称为它的内核项目(kernel)。42LALR分析法的基本思想q 在LR(1)项目集规范族中，合并同心项以减少状态的数目。q 在存储LR(1)有效项目集时，仅存储其中的内核。q 注意，由于同心项的合并，使项目的搜索符与可行前缀的对应关系不唯一，降低了分析器的识别能力，参见以下两例。43Cc.C, c/d/$C.cC, c/d

25、/$C.d, c/d/$ I36I0Cc+ | c+CcC.,c/d/$ I89C可行前缀Cc+与搜索符$对应，而可行前缀c+与搜索符c和d对应。当合并后的自动机识别出可行前缀CcC时，若当前的输入符号是c或d，LR(1)分析器马上就能发现出错，而LALR分析器此时则不行，必须先归约，得到可行前缀CC后才能发现出错。图图4.41合并合并I3和和I6，I8和和I9得到的部分状态图得到的部分状态图44SC.C,$C.cC,$C.d,$ I2CS .S,$S.CC,$C.cC,c/dC.d,c/d I0S S.,$ I1SCc.C, c/dC.cC, c/dC.d, c/d I3cCd.,c/d I

26、4dSCC.,$ I5CCc.C,$C.cC,$C.d,$ I6CcC.,$ I9CcCd.,$ I7dcCcC.,c/d I8Ccdd新增很多状态。LR（1）45LALR(1)S .S,$S.CC,$C.cC, c/dC.d, c/d I0S S., $ I1SSC.C, $C.cC, $C.d, $ I2CCc.C, c/d/$C.cC, c/d/$C.d, c/d/$ I36c Cd., c/d/$ I47dSCC., $ I5CcCcC.,c/d/$ I89Ccdd46合并同心项目集可能会引起冲突合并同心项目集可能会引起冲突q 同心集的合并不会引起新的移进归约冲突 假设合并之后有两个项

27、目A, a和 Ba, b（存在移进归约冲突），那么，在合并之前一定有某个集合同时有A, a 和Ba, c（合并之前已经存在移进归约冲突）q 同心集的合并有可能产生新的归约归约冲突47考虑文法考虑文法S SS aAd | bBd | aBe | bAeA cB c该文法的语言为acd, bcd, ace, bce，是LR(1)文法。例例4.4248S.S , $S .aAd , $S .bBd , $S .aBe , $S .bAe , $ S S. , $S a.Ad , $S a.Be , $A .c , dB .c , eaSS b.Bd , $S b.Ae , $A .c , eB .c

28、 , d bA S aA.d , $BS aB.e , $cA c. , dB c. , eA c. , eB c. , dcI1I0I2I3I4I5I6S bB.d , $I7BS bA.e, $I8AI9 S aAd. , $I10deI11SaBe., $eI13SbAe., $eI12S bBd., $49S.S , $S .aAd , $S .bBd , $S .aBe , $S .bAe , $ S S. , $S a.Ad , $S a.Be , $A .c , dB .c , eaSS b.Bd , $S b.Ae , $A .c , eB .c , d bA S aA.d ,

29、 $BS aB.e , $ccI1I0I2I3I4I5S bB.d , $I7BS bA.e, $I8A S aAd. , $I10deI11SaBe., $eI13SbAe., $eI12S bBd., $合并同心项合并同心项I69A c. , d/eB c. , d/e50构造构造G的的LR(1)项目集规范族项目集规范族I0: S.S , $ S .aAd , $ S .bBd , $ S .aBe , $ S .bAe , $I1:(I0, S) S S. , $I2:(I0, a) S a.Ad , $ S a.Be , $ A .c , d B .c , eI3:(I0 , b) S

30、 b.Bd , $ S b.Ae , $ A .c , e B .c , d I4:(I2 , A) S aA.d , $I5:(I2 , B) S aB.e , $I6:(I2 , c) A c. , d B c. , eI7:(I3 , B) S bB.d , $I8:(I3 , A) S bA.e , $ I9:(I3 , c) A c. , e B c. , dI10:(I4 , d) S aAd. , $I11:(I4 , e) S aBe. , $I12:(I7 , d) S bBd. , $I13:(I8 , e) S bAe. , $51合并同心项合并同心项I0: S.S ,

31、$ S .aAd , $ S .bBd , $ S .aBe , $ S .bAe , $I1:(I0, S) S S. , $I2:(I0, a) S a.Ad , $ S a.Be , $ A .c , d B .c , eI3:(I0 , b) S b.Bd , $ S b.Ae , $ A .c , e B .c , d I4:(I2 , A) S aA.d , $I5:(I2 , B) S aB.e , $I6:(I2 , c) (I3 , c) A c. , d/e B c. , e/dI7:(I3 , B) S bB.d , $I8:(I3 , A) S bA.e , $ I10

32、:(I4 , d) S aAd. , $I11:(I4 , e) S aBe. , $I12:(I7 , d) S bBd. , $I13:(I8 , e) S bAe. , $52合并同心项合并同心项q 若将同心项I6和I9合并，则得到项目集 I69: Ac. d/e Bc. d/eq 该项目集含“归约-归约”冲突。q 因此，文法G是LR(1)文法，但不是LALR文法。53构造构造LALR分析表的两种算法分析表的两种算法q 从LR(1)到LALR简单、耗空间、耗时间q 直接构造LALR复杂54LALR(1)分析表的原理性构造方法分析表的原理性构造方法q 构造LR(1)项目集族，如果它不存在冲

33、突, 就把同心集合并在一起。若合并后不存在归约-归约冲突，则按这个项目集族构造文法LALR(1)分析表。q 如果分析表中没有动作冲突，则文法是LALR(1)文法。55算法算法4.43 LALR分析表的构造分析表的构造输入：拓广文法G输出：G的LALR(1)分析表方法：1. 构造文法的LR(1)项目集族C=I0, I1, , In；2.合并C中的同心集，得到C=J0, J1, , Jm；3. 从C出发，按LR(1)构造action算法（算法4.40）构造action表；4. 构造goto表：若goto(Ik, X) = Jj，则 gotok,X = j；5. 分析表其余位置为error。56算法

34、算法4.40 规范规范LR(1)语法分析表的构造语法分析表的构造输入：拓广文法G。输出：文法G的规范LR语法分析表函数action和goto。方法：1. 构造G 的LR(1)项目集规范族C=I0, I1, , In。2. 从Ii构造分析器的状态i，状态i的action函数确定如下： 若A a, b在Ii中，且goto(Ii, a) = Ij，则置actioni, a为“shift j”； 若A , a在Ii中，且A S，则置actioni, a为“reduce j”，j是产生式A 的序号；若SS, $在Ii中，则置actioni, $为“accept”。57图图4-42 LR(1)分析表分析表

35、58例例4.44 文法文法(4. 16)的的LALR(1)分析表分析表合并同心项：I36: C cC, c/d/$ C cC, c/d/$ C d, c/d/$I47: C d, c/d/$I89: C cC, c/d/$89598960LR(1)和和LALR(1)分析上的差别分析上的差别q 输入：ccd$q LR: 0 c 3 c 3 d 4 报错q LALR: 0 c 36 c 36 d 47 0 c 36 c 36 C 89 0 c 36 C 89 0 C 2 推迟报错文法文法S SS CCC cCC d语言：c*dc*d61几种几种LR方法比较方法比较q 不同点主要在归约动作的选择：L

36、R(0) 分析考虑所有终结符SLR(1) 分析考虑FOLLOW 集LR(1) 分析考虑 LR(1)项目中的搜索符LALR分析考虑的是LR(1)项目合并之后的搜索符q 注意，LALR项目的搜索符一般是与该项目相关的非终结符号的Follow集的子集，这正是LALR分析法比SLR分析法强的原因62q 一个可行前缀可能有多个有效项目。可能存在动作冲突q 一个可行前缀的有效项目集就是从这个DFA的初态出发，沿着标记为的路径到达的那个项目集（状态） 。63串E + T *是可行前缀，读完它后，DFA处于状态I7I7: TT *F, F ( E ), F id E E E E E E E+T E+T E+T

37、 E+T * F E+T * F E+T * F E+T * id E+T * (E ) E+T* id E+T * F * id例例4.35644.7.5 LALR分析表的有效构造方法分析表的有效构造方法q 算法4.43在构造LALR分析表时，耗费的存储空间与LR(1)算法完全相同，代价还是太大。65q 可以从两个方面改进：存储有效项目集时，只存储它们的核心项目，每当需要完整的有效项目集时，再根据核心项目来计算。根据LR(0)项直接生成LALR(1)项目集规范族的核心项目，这是有效构造方法的关键。只需要利用项目集的核心项目就能计算其动作。66利用项目集的核就能计算其动作利用项目集的核就能计算

38、其动作q 思想：利用项目集的内核项目构造action表q 归约动作A 且且 ，则该归约项目必在内核项目中；用A 归约，此时归约项目A 不在内核项目中，当且仅当存在内核项目B C , b且C*A ，输入a为FIRST( b)，才能用A 归约。可以事先计算出所有符合C*A 的非终结符A。67利用项目集的核就能计算其动作利用项目集的核就能计算其动作q 移进动作若存在内核项目B a , b，显然动作是将a移进；若存在内核项目B C , b，且C*ax，且推导的最后一步不是用产生式，则可以将a移进。可以事先计算出所有符合C*ax的终结符a。68利用项目集的核计算利用项目集的核计算goto转换转换q 利用

39、项目集的内核项目构造goto转换若 B X , b是I中内核项目，显然B X , b在goto(I, X)的内核项目中。若 B C , b是I中内核项目，且有C*A ，那么， A X , a在goto(I, X)的内核项目中，其中a是FIRST(b)。可以事先计算出所有符合C*A 的非终结符。69例例4.45 构造文法构造文法LR(0)项目集的内核项目集的内核I0: S .S I1: S S. I2: S L.=R R L. I3: S R. I4: L *.R I5: L id. I6: S L=.R I7: L *R. I8: R L. I9: S L=R. 70S S I0RS R I3

40、SL =RR L LI2SS SI1L * R*I4Lid idI5=S L= RI6RL * R I7RL LI8*idRS L= R I9L*id71“自生的自生的”和和“传播的传播的”搜索符搜索符q 下面考虑如何为核项目配上搜索符。q 为LR(0)核项目B 添加搜索符b：存在包含内核项A , a项目集I ，有goto(I, X) = J。计算GOTO(CLOSURE(A , a), X)得到的结果中包含B , b，则则搜索符b为“自生的自生的” (spontaneously)。A C , aIB X , b JXqC * B， bFirst(a)72SA C B aaaBaCAaSrmrmrmrm* 73“自生的自生的”和和“传播的传播的”搜索符搜索符q 下面考虑如何为核项目配上搜索符。q 为LR(0)核项目B 添加搜索符b：存在包含内核项A , a项目集I ，有goto(I, X) = J。计算GOTO(CLOSURE(A , a), X)得到的结果中包含B , b，则则