第四章 文法与语法分析.doc

第四章 文法与语法分析4.8 形如A-Aa 的产生式称为左递归的，类似地称B-B 的产生式为右递归的。证明如果一个非终极符既有左又有右递归式，则文法一定有二义性。答案：设文法的非终极符A，有产生式AA|AA|字符串 符合文法的要求，但分析树有两种A A/ / A A| | 因此非终极符既有左递归式，又有右递归式，则一定有二义性。4.12. 下列那些文法是LL(1)文法？ 答案：LL(1)文法的条件：对于任意非终极符A,其任意两个产生式A-和A-都要满足下面条件：predict(A-)predict(A-)=;(a) 因为非终极符B 不可到达，所以最后两个产生式可以去掉。对具有相同左部的产生式A-a 和A-,它们的Predict 集的交集为空：predict(A-a)=a;Predict(A-)=b故a)所示文法是LL(1)文法。(b) 1)A,B 可导出空2)first(A)=a,b,first(B)=b,first(S)=a,bfollow(A)=b, follow(B)=b, follow(S)=#predict(S-Ab)=a,b,predict(A-a)=a,predict(A-B)=b,predict(A-)=bpredict(B-b)=b,predict(B-)=b因为predict(A-B)predict(A-)=b!=predict(B-b)predict(B-)=b!=所以不是LL(1)文法(c) 1)S,A,B 可导出空2)first(S)=a,b,first(A)=a,first(B)=b,follow(S) =#,follow(A) =a,b,#,follow(B) =a,b,#predict(S-ABBA)=a,b,#predict(A-a)=a,predict( A- )=a,b,# (*)predict(B-b)=b,predict(B-)=a,b,# (*)由(*)和(*)两行知，不是LL(1)文法.(d) 1)没有非终极符可导出空2)first(C)=c,d,first(B)=b,c,c,first(S)=a,b,c,dfollow(S)=e,#,follow(B)=e,#,follow(C)=c,e,#predict(S-aSe)=a,predict(S-B)=b,c,dpredict(B-bBe)=b,predict(B-C)=c,dpredict(C-cCc)=c,predict(C-d)=d因为满足LL(1)文法的条件，所以是LL(1)文法.4.13 对下列文法构造LL(1)分析表：E -EE -(E)E -Var EtailEtail -EEtail -Var -id VtailVtail -(E)Vtail -答案：First(E)=-, (, id Follow(E)=,)First(Etail)=-, Follow(Etail)=,)First(Var)= id Follow(Var)=-,)First(Vtail)= (, Follow(Vtail)-,)1 predict (E-E)= 2 predict (E(E)=(3 predict (EVar Etail)=id4 predict (Etail-E)= 5 predict (Etail)=,)6 predict (Varid Vtail)=id7 predict (Vtail(E)=(8 predict (Vtail)= ,)4.14 写出上述LL(1)分析器分析i-i(i)的过程，其中i 是标志符。4.15 对下列文法转换为LL(1)文法：DL -DL；DDL -DD -idL: TypeidL -ididL -idL, idType -StypeType -array (StypeL) of TypeSttype -idSTtype -Bound.BoundBound -Sign IntLiteralBound -idSign -+Sign -STypeL -STypeL, StypeSTypeL -Stype答案：First(DL)=idFirst(D)=idFirst(idL)=idFirst(Type)=id, array, +, -First(SType)=id, +, -First(Bound)= id, +, -First(Sign)=+, -First(SType L)= id, +, -1 DLDL; D2 DLD3 DidL:Type4 idLid5 idLidL,id6 TypeStype7 Typearray (STypeL) of Type8 Stypeid9 StypeBoundBound10 BoundSignIntLiteral11 Boundid12 Sign +13 Sign -14 STypeLSTypeL, Stype15 STypeLStype12的Predict 集相同45的Predict 集相同89 的Predict 集不为空1415 的Predict 集不为空改为下面的样子即为LL（1）文法12去掉45 去掉89 去掉1415 去掉添加： DLD DLtailDLtail ；DLtail|idLid idtailidt