编译原理练习小题
第二题:登堂入室 对下列文法G[E], E -4 TE E T +E | £ T -4 FT T T T I £ P T (E)|a|bA ⑴ 写出每个非终结符和候选式的FIRST集,每个非终结符的FOLLOW集; (2)判断文法G[E]是否LL⑴文法。 答: 产生式 E T TE FIRST FOLLOW {),#} E T + E ->E T T FT {+} {£} {(, a,b} {),#} T T T T E F -4 PF {(, a,b} {£} {(,a,b} {+,),# F,T * F {*} {£} {(. a, b , + ,) ,#) {(} {a} {b} P - (E) -4 a T bA 因为对于产生式:E T + E I £ FIRST (+ E) Cl FOLLOW (E7 )=0 对于产生式:T T T I £ FIRST(T) A FOLLOW(Tz )=0 对于产生式:F T *F |£ FIRST (* Ff ) A FOLLOW (Fz )=0 对于产生式:P T (E)|a|bA FIRST (( E )) A FIRST (a) A FIRST (b A )=0 所以,文法G[E]是LL(1)文法。 第三题:华山论剑 对于下列文法G[S], S—^aABbcd | £ A—ASd | £ B—SAh | eC | £ C->Sf|Cg|£ D—>aBD | £ ⑴写出每个非终结符和候选式的FIRST集,每个非终结符的FOLLOW集; ⑵判断文法G[E]是否LL⑴文法。 答案:略。 第四题:决战LL(1)文法之巅 对于下列文法G[S], S 一(T) | a+S | a T — T,S | S (1) 文法G[S]是否LL(1)文法?简述判断依据; (2) 如果G[S]不是LL(1)文法,请将其改造成LL (1)文法; (3) 对于改造后的文法,为其构造预测分析表,并给出对输入串(a,a+a)的LL(1)分析过程。 解:⑴不是LL⑴文法。 因为对于产生式:s -⑴ a+S a ,FIRST(a+S) nFIRST(a)={a}乂0 对于产生式:T 一 T , S | S ,会产生直接左递归 (2)改造后如下: S _ (T) | a S, S, -* +S | e T — ST T, -,S T 1 e ⑶略: 友情赞助以弥补第四题答案缺失: 对于下列文法G[A]构造预测分析表,并给出对输入串aade#的分析过程 A — aC B 一 dB B — bB | e C -* AB| e 解:⑴ 每一个非终结符号的FIRST集和FOLLOW集 产生式 FIRST FOLLOW A — aC {a} {#, d} B — dB {d} {#, d} B,一 bB, B 一 £ {b, £} {#,d} C -* AB C — e {a, £} {#, d} 相应的LL (1)分析表 a b d A A -* aC B B — dB B B — bB B,一 e B — e C C -* AB C 一 e C 一 e 对输入串aade#进行预测分析的过程表 步骤 分析栈 余留输入串 所用产生式 1 #A aade# A — aC 2 #Ca aade# 匹配 3 #C ade# C -* AB 4 #BA ade# A -* aC 5 #BCa ade# 匹配 6 4BC de# C 一 e 7 #B de# B — dB 8 #B d de# 匹配 9 #B e# 分析失败