资源描述
LALR(1)项目集构造的另一种算法,核: 圆点不在最左端的项目，但初态项目SS,# 除外。 用核代替闭包，将缩小项目集所需的存储空间。 若BC,#属于LR(1)项目集I的核K，且有C A, A X是一个产生式 ，则GO(I,X)核中A X , a中的搜索符a为以下两种情况: 若 aFRIST()，则 a 是自生的。 若 , 则 a = b，则称 I 的核K中的BC将自己的搜索符传播给GO(I,X)核中的A X 。,*,R,*,R,搜索符的传播判定算法 Procedure Sponsor(I,X) /* I是一个LR(0)集,X是一个文法符号 */ For I的核中的每个项目B Do Begin J:=Closure(B , ) ; /* 采用 LR(1)项目集求闭包算法 */ if A X , a J但a不等于 then GO(I,X)核中的A X , a 的搜索符a 是自生的; if A X , J then GO(I,X)核中的A X , a 的搜索符a 是从K中的B 传播过来的 End,#,#,#,LALR(1)项目集构造算法,构造G的所有LR(0)项目集的核 使用算法Sponsor，对于每个LR(0)集I的核K和每个文法符号X，确定出GO(I,X)核中的每个项目所有自生的搜索符，并确定GO(I,X)中哪些项目将接受到从K中传播过来的搜索符。 传播每个核的自生搜索符，直到无法再传播为止。 使用一个栈Stack ,元素为(I, A , a ) 使用数组OnI, A , a=true表示已在栈中。 使用Insert过程将三元式推进Stack 中。,LALR(1)项目集构造核算法-造核算法,Begin For 任何I, A 和 a Do OnI, A , a=false Stack:= 空 Insert(I0, SS,#) For 每个I, A 和 a ，a是I中的A 一个自生搜索符 Do Insert(I, A , a) While Stack 非空 Do Begin 移去Stack栈顶的 (I,B,a ) For 每个文法符号X Do For GO(I,X)中的每个满足下述条件的 A ： I中的B把自己的搜索符a传播给GO(I,X)中的A Do Insert(Go(I,X), A , a),End of while End of Algorithm Procedure Insert(I, A , a) ; if not OnI, A , a then Begin 把三元式(I, A , a) 推进Stack; OnI, A , a := True; 把 a 加到I中的项目A 的搜索符集中 End of Insert,LALR(1)项目集构造核算法-造核算法,例5.14：有如下文法GS: (0) S S (1) S L=R (2) S R (3) L *R (4) L i (5) R L 构造文法的LALR项目集,LR(0)项目集,能够产生搜索符的项目 SS 和 S L=R 分别拥有搜索符 # 和 = 将 (I0, SS,#) 推进 Stack 按Sponsor算法重构 I0 则 = 是非核项目L *R和L i的搜索符， 从而=是I4 的核L * R和I5 的核 L i 的一个自生搜索符。 将 (I4, L * R, =) 推进 Stack 将 (I5, L i , =) 推进 Stack 其中I5是归约项目，不会再传播,弹出栈顶 (I4, L * R, =) 按Sponsor算法将搜索符=传播到 I7 的核L * R I8 的核RL I5 的核L i I4 自身 但I5 、 I7 和 I8都是归约项目，不会再传播 弹出栈顶 (I0, SS,#) 按Sponsor算法将搜索符#传播到 I2 的核SL=R I3 的核SR I2 的核R L I4 的核L * R I5 的核L i I1 的核SS 进栈后，考虑可以继续传播的项目 （I4 ，L * R ，#） （I2 ，SL=R，#）,弹出栈顶 （I2 ，SL=R，#） 引起 （I6 ， SL= R ，#）进栈 弹出栈顶 （I6 ， SL= R ，#） 按Sponsor算法将搜索符#传播到 （I9 ， SL= R ，#）（I8 ， RL ，#） （I5 ， L i ，#）（I4 ， L * R，#） 但均为归约项目，不会再传播或已在栈中 弹出栈顶 （I4 ，L * R ，#） 按Sponsor算法将搜索符#传播到 （I7 ， L * R ，#），不会再传播 栈空算法结束,得到LALR(1)集核为: I0: SS,# I4: L * R,=/# I1 : SS ,# I5: L i , =/# I2 : SL=R ,# I6: SL= R , =/# R L ,# I7: L * R , =/# I3 : SR ,# I8: RL , =/# I9 : SL= R ,#,
展开阅读全文