编译原理试题集78677

(a) 求每个非终结符的FIRST和Follow集。 (b) 构造这个文法的LL(1)分析表 (c) 说明这个文法不是LL(1)的; (d) 尽可能少地修改此文法,使其成为能产生相同语言的LL(1)文法.

4. 已知文法如下： E→T | E+T T→F | T*F F→i | (E) 构造预测分析表，并给出对输入串i*i+i的分析过程。

5. 文法G1： S→a|^|(T) T→T,S|S (1) 证明文法G是LL(1)文法。 (2) 构造LL(1)分析表。 (3) 写出句子（a,a）#的分析过程。

6. 设文法G(S)： S→(L)|aS|a L→L,S|S (1)消除左递归和回溯； (2)计算每个非终结符的FIRST和FOLLOW； (3)构造预测分析表。 (4)已知输入串(aa,a)a，该输入串是否文法的句子？给出分析过程。

7. 对于文法 bexpr → bexpr or bterm | bterm bterm → bterm and bfactor | bfactor bfactor→ not bfactor | (bexpr) | true | false 构造一个预测分析器。

8. 已知G[R]的产生式如下: R → R“ | “T | T T → TF | F F → F* | C C → (R) | a | b 构造它的LL(1)分析表，并写出对输入串的分析过程。

9. 已知文法如下： S→S*T | S/T | T T→T+F | T-F | F

F →(S) | i | i e i

构造预测分析表，并给出对输入串的分析过程。

10. 已知文法： S→Ac|c A→Bb|b B→Sa|a 构造预测分析表，给出对输入串的分析过程。

11. 已知文法G：

S → ( L | a

L → S , L | )

（1）构造文法 G 的预测分析表。 （2）若输入串为“（ａ，）”，请给出语法分析过程。

12. 给定文法 Ｇ＝({ i，d，“(“，“)“ }，{Ｅ，Ａ}，Ｅ，Ｐ) 其中 Ｐ： E →iA E →EA A → i A →d A → (E) (1)消除左递归； (2)计算改写后文法中各非终结符的 FIRST 集和 FOLLOW 集； (3)构造改写后文法的预测分析表；该文法是 LL(1) 文法吗?。

13. 已知文法： A→aABe|a B→Bb|d ⅰ.消除左递归，若有左因子则提取之； ⅱ.对（1）中得到的文法求First集合和Follow集合 ⅲ.对（1）中得到的文法构造一个预测分析表； ⅳ.给出对句子aadb上的分析动作

14. 已知文法： S→Aa|b

A→SB B→ab

(1) 改写文法以消除左递归，若有左因子则提取之；

(2)计算改写后文法中各非终结符的 FIRST 集和 FOLLOW 集； (3)构造改写后文法的预测分析表；该文法是 LL(1) 文法吗?。

15. 文法： S→MH|a H→LSo|ε K→dML|ε L→eHf M→K|bLM (1)消除左递归； (2)计算改写后文法中各非终结符的 FIRST 集和 FOLLOW 集； (3)构造改写后文法的预测分析表；该文法是 LL(1) 文法吗?。

16. 对下面文法 Expr→-Expr Expr→ (Expr)|Var ExprTail ExprTail→-Expr | ε? Var→id VarTail VarTail→ (Expr) | ε? (1) 构造LL（1）分析表。 (2) 给出对句子id--id((id))的分析过程。

17. 把下面文法改写为LL（1）的： Declist→Declist; Decl | Decl Decl→idList:Type IdList→Idlist, id | id Type→ScalarType | array (ScalarTypeList) of Type ScalarType→id | Bound..Bound Bound→Sign IntLiteral | id Sign→+ | - | e ScalarTypeList→ScalarTypeList, ScalarType | ScalarType

解答: 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.

第五章 语法分析—自下而上分析

一.填空题

1. 规范归约的关键问题是_______________________。

2. LR(k)分析法中，L的含义是____________________，

R的含义是_______________________，

k的含义是_______________________。

3. 移进一归约分析对符号串的使用有四类操作：移进、__________、_________和出错处理 。 4. 设文法G（E为其开始符号）产生式如下：

E→E+T|T T→T*F|F F→（E）|i

则句型E+T*F+i的句柄是_________________。