64LR(1)和LALR(1)分析 规范LR分析
6.4 LR(1)和LALR(1)分析 规范LR分析
例1文法G0)s→s(1)S→aAd(2)S→bAc (3)S→aec(4)S→bed(5)A→e I1:S→S.I,:S→a.Ad S→,aAd S→a.ec S→,bAc A→ S→.aec S bed 3:S→b.AcI4 SA b. ed S→aA.d S→ae.c A 8 S→bA.c S→be.dS→aAd. A l:S→aec. 10:S→bAc.I1:S→bed
例1文法G 0）S`→S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e I0: S`→．S I1: S`→S． I2: S→a．Ad S→．aAd S→a．ec S→．bAc A→．e S→．aec S→．bed I3: S→b．Ac I4: I5 : S→b．ed S→aA．d S→ae．c A→．e A→e ． I6 : I7 : I8: S→bA．c S→be．d S→aAd． A→e． I9 : S→aec． I10: S→bAc． I11: S→bed．
ACTION GOTO a c d #S A S3 S7 345678 S8 r5s9 I5 r5 r5 571 S10 r r7 r rSII r7 r r 4r4 [4 4
ACTION GOTO a c e b d # S A 0 S2 S3 1 1 acc 2 S5 4 3 S7 6 4 S8 5 r5 r5S9 r5 r5 r5 r5 6 S10 7 r7 r7 r7 r7 r7 S11 r7 8 r1 r1 r1 r1 r1 r1 9 r3 r3 r3 r3 r3 r3 10 r2 r2 r2 r2 r2 r2 11 r4 r4 r4 r4 r4 r4
(0)S→S(1)S→aAd(2)S→bAc (3)S→aec(4)S→bed(5)A→e 非LR(0),非SLR(1) L5 S→ae.c 7 S→be.d A→e A→e SRSR aAdR- >aed S’==>S三=>bAc==>bec S=> R R aec RedR ae是活前缀 be是活前缀 aAc不是规范句型, bAd不是规范句型 不作无效归约?信息一在特定的规范推导中,哪些输入符号 能跟在句柄之后 GIS: 若SaAω=>aBr是αβ的前缀,则 R 称r是G的一个活前缀.哪个项目在什么条件下对某个活前缀有效
( 0）S’→S (1) S→aAd (2) S→bAc (3) S→aec (4) S→bed (5) A→e 非 LR(0),非SLR(1) I5: S →ae．c I7: S →be．d A →e． A →e． S’==>S==>aAd==>aed S’==>S==>bAc==>bec S’==>S==>aec S’==>S==>bed ae是活前缀 be是活前缀 aAc不是规范句型, bAd不是规范句型 不作无效归约 ？信息－ 在特定的规范推导中，哪些输入符号 能跟在句柄之后 G[S]: 若S => αAω =>αβω r是αβ的前缀，则 称r是G的一个活前缀. 哪个项目在什么条件下对某个活前缀有效 R R R R R R R R R R R R * * * * *
例2GS: (0)S→S(1)S→L=R (2)S→R (3)L→*R(4)L→id (5)R→L IO:S→> I4:L→>*R SS LE R R>·L R L→>·R R→>·L L->id d I5:L→>jd →>·R I6:S→>L=·R I1:S→>S RLL >·R I2:S→>L·=R R→>L I7:L→>*R I8:R→>L I3:S→>R· I 9 S->L=R
例2 G[S]: (0) S`→S (1) S→L=R (2) S→R (3) L→ *R (4) L→id (5) R→L I0: S' –> •S S –> •L = R S –> •R R –> •L L –> •id L –> •*R I1: S' –> S• I2: S –> L• = R R –> L• I3: S –> R• I4: L –> *•R R –> •L L –> •*R L –> •id I5: L –> id• I6: S –> L =•R R –> •L L –> •*R L –> •id I7: L –> *R• I8: R –> L• I9: S –> L=R•
I2:S->L·=R R→>L 考虑分析表达式id=id时,在工作到I2处已经 把第一个id归约到L了,看到下一个输入= 要作决策,第一个项目要设置Acon[2=]为 S6,即把赋值的其它部分找到.但=也是属于 Follow(R)的第二个项目要用R>L归约出 现 shift-reduce冲突 若将栈顶的符号序列归约到R会有问题!因 为不可能有规范句型以R=…开头(有以*R =…开头的规范句型)
I2: S –> L• = R R –> L• 考虑分析表达式 id = id时，在工作到 I2 处已经 把第一个 id 归约到 L了, 看到下一个输入 = 要作决策，第一个项目要设置Action[2,=] 为 S6, 即把赋值的其它部分找到. 但 =也是属于 Follow(R) 的. 第二个项目要用 R–>L归约.出 现 shift-reduce 冲突. 若将栈顶的符号序列归约到 R,会有问题！因 为不可能有规范句型以R = …开头 (有以 *R = ... 开头的规范句型)
SLR(1)的局限 follow集包含了在任何句型中跟在R后的符号但没 有严格地指出在一个特定的推导里哪些符号跟在 R后所以需要扩充状态以包含更多的信息: follow 集的哪些部分才是进到该状态最恰当的归约依据. 处在状态2时,试图构建句子有两条路: 1S→L=R或 2.S→R→L 如下一符号是三,那就不能用第二个选择,必须用 第一个即移进只有下一个符号是#时才能归约尽 管=属于Fo|oW(R),那是因为一个R可以出现 在别的上下文中,在现在这个特定的情况,它不 合适,因为在用S→R→L推导句子时,=不能跟 在R后
SLR（1）的局限 follow 集包含了在任何句型中跟在 R 后的符号但没 有严格地指出在一个特定的推导里哪些符号跟在 R后.所以需要扩充状态以包含更多的信息：follow 集的哪些部分 才是进到该状态最恰当的归约依据. 处在状态 2时，试图构建句子有两条路： 1.S L = R 或 2.S R L. 如下一符号是 =, 那就不能用第二个选择，必须用 第一个,即移进. 只有下一个符号是#时才能归约. 尽 管 = 属于 Follow(R) ，那是因为一个 R 可以出现 在别的上下文中，在现在这个特定的情况，它不 合适,因为在用S R L推导句子时, = 不能跟 在R后
讨论例2后有以下结果: 不是LR(0)文法 S→L.=RR→L.中存在移进/ 归约冲突 ☆SLR能否解决I中的冲突 FOLLOW(R)={#,}与{交不为空不 是SLR(1)文法 如早有信息告知:若用R→L归约则 形成R=而R=不是活前缀
. 讨论例2后有以下结果： ❖ 不是LR(0)文法 ∵ I2 S→L．=R R→L.中存在移进/ 归约冲突 ❖ SLR能否解决I2中的冲突 ∴FOLLOW（R）={#,=}与{=}交不为空 不 是SLR（1）文法 ❖ 如早有信息告知： 若用 R→L 归约 则 形成R=… 而 R=不是活前缀
SLR(1)的局限 在sLR分析中若项目集I含有项目A→β ,那么在相应的状态下只要当前输入符号a∈ fOllow(A)集就确 定采用A→进行归约但在某些情况下当状态k呈现于栈顶 时栈内的串?所构成的活前缀未必允许把β归约为A因为 可能没有一个规范句型含有前缀Aa即在这种情况下,用A →阝归约未必有效 所以需要扩充状态以包含更多的信息: follow集的哪些部分 才是进到该状态最恰当的归约依据 重新定义项目 LR(1)方法 若A→>aBβ∈I 则B (B→y是一产生式) 把 FIRST(B)中的符号作为用B→γ归约的搜索符,向前搜索符
SLR（1）的局限 在SLR 分析中,若项目集Ik含有项目 A →. ,那么在相应的状态下,只要当前输入符号afollow(A) 集,就确 定采用A →进行归约.但在某些情况下,当状态k呈现于栈顶 时,栈内的串所构成的活前缀未必允许把归约为A,.因为 可能没有一个规范句型含有前缀Aa.即在这种情况下,用A →归约未必有效. .所以需要扩充状态以包含更多的信息：follow 集的哪些部分 才是进到该状态最恰当的归约依据. 重新定义项目. LR（1）方法 若 A → .B I 则 B → . I （ B → 是一产生式） 把FIRST（ ）中的符号作为用B → 归约的搜索符，向前搜索符
LR(1)项目(配置)的一般形式 IA→>0.β,a a称作该项目(配置)的向前搜索符( lookahead) 向前搜索符( lookahead)只对圆点在最后的项月起 作用 A->αβ 意味着处在栈中是aβ的相应状态,但只有当下一个 输入符是a时才能进行归约.a是一个终结符,或是 输入结束标记# 有多个向前搜索符,比如ab,c时,可写作A→>u, a/b/c
LR（1）项目( 配置）的一般形式 – [ A → . ， a ] a 称作该项目( 配置） 的向前搜索符（ lookahead ） 向前搜索符（ lookahead ）只对圆点在最后的项目起 作用 A –> •, a .意味着处在栈中是 的相应状态，但只有当下一个 输入符是a时才能进行归约. a 是一个终结符，或是 输入结束标记# 有多个向前搜索符，比如a,b,c时，可写作 A –> u•, a/b/c