2. 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。 ( )
3. 一个文法是含有左递归的，如果存在非终结符P，使得P?*α。（ ）
4. 提取公共左因子的副产品是引进了大量的非终结符和ε产生式。 ( )
5. 把一个文法改造成任何非终结符的所有后选终结首符集两两不相交的办法是消除左递归 。( )
6. 若X∈VT，则FIRST(X)={ X }。 ( )
7. 一个文法的预测分析表含有多重定义入口，说明该文法是LL(1)的。（ ）
8. 自上而下分析及自下而上分析中的“下”是指被分析的源程序串。（ ）
解答: 1. 2. 3. 4. 5. 6. 7. 8.
三.单项选择题
1. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于____ 分析法。 a. 自左至右 b. 自顶向下 c. 自底向上 d. 自右向左
2. 上下文无关文法可以用____来描述。 a. 正则表达式 b. 正规文法 c. 扩展的BNF d. 翻译模式
3. 自上而下分析面临的四个问题中，不包括____ a. 需消除左递归；b. 存在回朔；c. 虚假匹配；d. 寻找可归约串
4. 语法分析器接收以________为单位的输入，并产生有关信息供以后各阶段使用。 a. 表达式；b. 产生式； c. 单词；d. 语句；
5. 自上而下分析的主旨是，对任何单词符号串，试图用一切可能的办法，从文法开始符号 （根结点）出发，________。 a. 为输入串寻找最右推导； b. 为输入串寻找最左直接子树； c. 为输入串建立最右直接子树；d. 为输入串寻找最左推导；
6. 把规则T→F | T*F表示成扩展的巴克斯范式以后，画出它的语法图应该是____。
7. 下列文法中，_______是LL(1)文法。 a. S→aSb|ab b. S→ab|Sab c. S→aS|b d. S→aS|a
8. 设有文法G： S→Ap|Bq A→a|cA B→b|dB 则，First(Ap)={_______________} a. a,c b. b,d c. p, q d. A, p
解答: 1. 2. 3. 4. 5. 6. 7. 8.
四.名词解释 1. 左递归；
2. 递归下降分析器；
3. LL(1)文法； 解答: 1. 2. 3.
五.简答题
1. 词法分析和语法分析都是对字符串进行识别的，二者有何区别？
2. 试说明没有一个左递归文法是LL(1)的。
3. 试说明没有一个LL(1)文法是二义性的。 解答: 1. 2. 3.
六.应用题
1. 已知文法G[S]： S → (L) | a L → L,S | S ⅰ.消除左递归，若有左因子则提取之； ⅱ.对ⅰ中得到的文法求First集合和Follow集合 ⅲ.对ⅰ中得到的文法构造一个预测分析表； ⅳ.给出对句子(a,(a,a))上的分析动作
2. 考查文法G(s): S→( T ) | a + S | a T→T, S | S ⅰ.消除文法的左递归，提取公共左因子 ⅱ. 改造后的文法是LL(1)的吗？为什么？ ⅲ. 如果是LL(1)文法，对每个非终结符，写出不带回朔的递归子程序。
3. 已知文法G[S]： S → uBDz B → Br | w D → EF E → y | ε? F → x | ε?
(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
