编译原理习题解答.pptVIP

补充题： S→bAb A→(B|a B→Aa) LR(0)项目集规范族为： I0: I1=go(I0,S): S’→.S S→.A A→.Ab A→.bBa S’→S. I2=go(I0,A): S→A. A→A.b I3=go(I0,b): A→b.Ba B→ .aAc B→ .a B→ .aAb I4=go(I2,b): A→Ab. I5=go(I3,B): I6=go(I3,a): A→bB.a B→ a.Ac B→ a. B→ a.Ab A→.Ab A→.bBa I7=go(I5,a): A→bBa. I8=go(I6,A): go(I6,b) = I3 B→ aA.c B→ aA.b A→A.b I9=go(I8,c): B→ aAc. I10=go(I8,b): B→ aAb. A→Ab. r4 r4 r4 r4 9 R2 r6 R2 r6 R2 r6 R2 r6 10 s9 s10 8 r3 r3 r3 r3 7 8 s3 6 s7 5 r2 r2 r2 r2 4 5 s6 3 s4 2 acc 1 2 1 s3 0 B A S # c b a Goto Action 状态 LR(0)分析表(有冲突) * * 1.从下列文法中消除左递归，提取左公因子 S→Aa|Ab|c A→Ad|Se|f 先消除直接的左递归 A→SeA’|fA’ A’→dA’| ε 再消除间接左递归： S→SeA’a|SeA’b|fA’a|fA’b|c S→fA’aS’|fA’bS’|cS’ S’ →eA’aS’|eA’bS’| ε S→fA’aS’|fA’bS’|cS’ S’ →eA’aS’|eA’bS’| ε A’→dA’| ε 提取左公因子： S→fA’B|cS’ B→aS’|bS’ S’→eA’C| ε C→aS’|bS’ A’ →dA’| ε P81 1. S→a|^|(T) T→T,S|S 消除左递归： S→a|^|(T) T→ST’ T’→，ST’|ε Procedure T Begin S;T’ End Procedure S If sym=‘(‘ then Begin Advance;T If sym=‘)’ then advance Else error End Else if sym=‘^’ then advance Else if sym=‘a’ then advance Else error Procedure T’ If sym=‘,’ then Begin Advance; S;T’ End (2)判断是否为LL(1) First(T’)={‘,’，ε} First(T) = First(S) ={a， ^,( } Follow(S)={#，’,’，）} Follow(T)={）} Follow(T’)={）} T’有两个候选， 但first(T’)∩follow(T’)=φ 文法是LL(1)的 构造预测分析表： T’→,ST’ T’→ε T’ T→ST’ T→ST’ T→ST’ T S→(T) S→ ^ S→a S # , ) ( ^ a 2. E→TE’ E’→+E| ε T→FT’ T’→T|ε F→PF’ F’→*F’| ε P→(E)|a|b|^ ? ? ? ? ? ? ? ? a ? ? ? ? ? ? ? ? b ? ? ? ε ? ? ? ? ? ? ? ? P→(E)|a|b|^ ? ? ? ? ? ? F’→*F’| ε ? ? ? ? ? ? ? F→PF’ ? ? ? ? ? T’→T| ε ? ? ? ? ? T→FT’ ? ? ? E’→+E|ε ? ? ? ? E→TE’ # ^ ) ( * + FIRST(E)={(,^,a,b}; FIRST(E’)={+, ε}; FIRST(T)={(,^,a,b}; FIRST(T’)={(,^,a,b, ε}; FIRST(F)={(,^,a,b}; FIRST(F’)={*,ε}; FIRST(P)={(,^,a,b}; FOLLOW(E)={),#}; FOLLOW(E’)={),#}; FOLLOW(T)={+,),#}; FOLLOW(T’)={+,),#}; FOLLOW(F)={+,(, ),^,a,b,#}; FOLLOW(F’)={+,(, ),^,a,b,#}; FOLLOW(P)={+,*,(, ) , ^,a,b,#}; 因为： E’→+E| ε FIRST(+E)?FOLLOW(E’)={+}?{ ) ,#}=Φ; T’→T| ε FIRST(T)?FOLLOW(T’)={(,^,a,b}?{+,),#}=Φ;