编译原理试题集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)若输入串为“(a,)”,请给出语法分析过程。

12. 给定文法 G=({ i,d,“(“,“)“ },{E,A},E,P) 其中 P: 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的句柄是_________________。