编译原理作业集 第四章 自上而下语法分析
第四章 语法分析—自上而下分析
本章要点
1. 语法分析器的功能；
2. 自上而下分析方法，LL(1)文法 3. 递归下降分析程序构造；
4. 预测分析表的构造及预测分析过程； 5. LL(1)分析中的错误处理。
本章目标
理解和掌握语法分析器的功能、自上而下分析所面临的问题、LL（1）分析法、递归下降分析的构造过程、预测分析程序等内容。
本章重点
1．语法分析器的功能，自上而下的基本概念
2．LL（1）文法的条件及其判别，计算first集和follow集 3．递归下降分析方法、预测分析表的构造及其预测过程。
本章难点
1. 非终结符的First集合，产生式候选的First集合，非终结符的follow集合的求解； 2. 左递归消除；
3. 递归下降分析程序的编写；
作业题
一、单项选择题：
1. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于 分析法。
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:24 AM
- 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表示成扩展的巴克斯范式以后，画出它的语法图应该是 。
T F F * 图a T T F * F 图b F * F 图c T F * F 图d
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. b；2. c；3. d；4. c；5. d；6. 图a；
二、填空题：
1. 语法分析器的工作本质上就是按____________________，识别输入符号串是否为一个句
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:24 AM
- 2 -
编译原理作业集 第四章 自上而下语法分析
子。这里所说的输入串是指由____________________组成的有限序列。
2. 自顶向下分析会遇到的主要问题是____________________和__________________。 3. 自上而下地为输入串建立一棵语法树，就是为输入串寻找一个______________。 4. 在扩充的巴科斯范式中，用______________表示符号或串α的出现可有可无。
5. 对于一个文法，当给出一串符号时，怎么能知道它是不是该文法的一个句子呢？这就要判断，看是否能 。
6. 文法exp → exp addop term | term 消除左递归的结果为 。 7. 写出E→T | E+T的EBNF范式为 。 8. 扩展的巴克斯范式描述语法的好处是，直观易懂，便于表示 。
二．答案：1. 文法的产生式，单词符号（文法的终结符）2. 左递归，回溯；3.最左推导；4. 方括号（或[?]）；5. 从文法的开始符号出发推导出这个输入串。（或：能否建立一棵与输入串相匹配的语法分析树。）6. exp → term exp′；exp′→ addop term exp′| ?；7. E→T{+T}；8. 左递归消去和左因子提取。
三、判断题：
1. LL(k)文法都不是二义性的。（ ）
2. 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。 ( ) 3. 一个文法是含有左递归的，如果存在非终结符P，使得P?*?P。（ ） 4. 提取公共左因子的副产品是引进了大量的非终结符和ε产生式。 ( )
5. 把一个文法改造成任何非终结符的所有后选终结首符集两两不相交的办法是消除左递归。( ) 6. 若X∈VT，则FIRST(X)={ X }。 ( )
7. 一个文法的预测分析表含有多重定义入口，说明该文法是LL(1)的。（ ） 8. 自上而下分析及自下而上分析中的“下”是指被分析的源程序串。（ ） 三．答案：1. ?；2. ?；3. ×；4. ?；5. ×；6. ?；7. ×；8. ?；
四、名词解释：
1. 左递归；
2. 递归下降分析器； 3. LL(1)文法； 4. 预测分析表 5. 自上而下分析
四．答案：
1.一个文法如果存在非终结符P，P=>+P?，则称该文法是左递归的。
2. 当一个文法满足LL(1)条件时，可以为它构造一个不带回溯的的自上而下分析程序，该程序是由一组递归过程组成的，每个过程对应文法的一个非终结符。这样的分析程序称为递归
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:24 AM
- 3 -