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•