9. 10. 11. 12. 13. 14. 15.
第四章 语法分析—自上而下分析
一.填空题
1. 语法分析器的工作本质上就是按____________________，识别输入符号串是否为一个句 子。这里所说的输入串是指由____________________ 组成的有限序列。
2. 自顶向下分析会遇到的主要问题是____________________和__________________。
3. 自上而下地为输入串建立一棵语法树，就是为输入串寻找一个______________。
4. 在扩充的巴科斯范式中，用______________表示符号或串α的出现可有可无。
5. 对于一个文法，当给出一串符号时，怎么能知道它是不是该文法的一个句子呢？这就要 判断，
看是否能___________________________________________。
6. 文法exp → exp addop term | term 消除左递归的结果为__________________________ _______。
7. 写出E→T | E+T的EBNF范式为__________________________。
8. 扩展的巴克斯范式描述语法的好处是，直观易懂，便于表示_________________________ _____。
解答: 1. 2. 3. 4. 5. 6. 7. 8.
二.判断题
1. LL(k)文法都不是二义性的。（ ）
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 | ε?