编译原理练习小题

第二题登堂入室 对下列文法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 FIRSTT A FOLLOWTz 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]是LL1文法。 第三题华山论剑 对于下列文法G[S], SaABbcd | AASd | BSAh | eC | C-Sf|Cg| DaBD | ⑴写出每个非终结符和候选式的FIRST集，每个非终结符的FOLLOW集； ⑵判断文法G[E]是否LL⑴文法。 答案略。 第四题决战LL1文法之巅 对于下列文法G[S], S 一T | aS | a T T,S | S 1 文法G[S]是否LL1文法简述判断依据； 2 如果G[S]不是LL1文法，请将其改造成LL 1文法； 3 对于改造后的文法，为其构造预测分析表，并给出对输入串a,aa的LL1分析过程。 解⑴不是LL⑴文法。 因为对于产生式s -⑴ aS a ,FIRSTaS nFIRSTa{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 分析失败