《编译原理》期末考试试卷#

一、 单项选择题（本题共 10 小题，每小题 2 分，共 20 分）#

1. 编译程序绝大多数时间花在 ( ) 上。

• A. 出错处理
• B. 词法分析
• C. 目标代码生成
• D. 表格管理

2. 解释程序和编译程序的区别在于 ( )。

• A. 是否生成中间代码
• B. 加工的对象不同
• C. 使用的实现技术不同
• D. 是否生成目标代码

3. 乔姆斯基(Chomsky)把文法分为四种类型，即 0 型、1 型、2 型、3 型，其中 3 型文法是 ( )。

• A. 非限制文法
• B. 正则文法
• C. 上下文有关文法
• D. 上下文无关文法

4. 如果文法 $G$ 是无二义的，则它的任何句子 $\alpha$ ( )。

• A. 最左推导和最右推导对应的语法树必定相同
• B. 最左推导和最右推导对应的语法树可能不同
• C. 最左推导和最右推导必定相同
• D. 可能存在两个不同的最左推导，但它们对应的语法树相同

5. 词法分析器的输出结果是 ( )。

• A. 单词自身值
• B. 单词在符号表中的位置
• C. 单词的种别编码
• D. 单词的种别编码和自身值

6. 非确定有限自动机 (NFA) 与确定有限自动机 (DFA) 的主要区别在于 ( )。

• A. NFA 不能识别正则语言，DFA 可以
• B. NFA 的状态转换可能不确定（同一状态和输入有多个下一状态）
• C. NFA 没有接受状态，DFA 有
• D. NFA 只能处理短输入串，DFA 可处理任意长度

7. 在高级语言编译程序常用的语法分析方法中，预测分析方法属于 ( )。

• A. 自左至右分析法
• B. 自上而下分析法
• C. 自下而上分析法
• D. 自右至左分析法

8. 在规范归约中，用 ( ) 来刻画可归约串。

• A. 直接短语
• B. 句柄
• C. 最左素短语
• D. 素短语

9. 在 LR 分析法中，分析栈中存放的状态是识别规范句型 ( ) 的 DFA 状态。

• A. 句柄
• B. 前缀
• C. 活前缀
• D. LR(0) 项目

10. LR(1) 文法都是 ( )。

• A. 无二义性且无左递归
• B. 可能有二义性但无左递归
• C. 无二义性但可能是左递归
• D. 可以既有二义性又有左递归

---

二、 填空题（本题共 5 小题，每小题 2 分，共 10 分）#

1. 编译过程通常可分为 5 个阶段：、、语义分析与中间代码产生、代码优化和目标代码生成。

2. 词法分析基于__________文法进行，语法分析基于__________文法进行。

3. 语法分析最常用的两类方法是__________和__________分析法。

4. 规范归约中的可归约串是指__________，算符优先分析中的可归约串是指__________。

5. 一个上下文无关文法 $G$ 包括四个部分：、、开始符号和一组产生式。

---

三、 求解题（本题共 3 小题，每小题 10 分，共 30 分）#

1. （词法分析） 构造一个最小的确定有限自动机 (DFA) $M$，使其接受字母表 $\Sigma=\{0, 1\}$ 上所有满足下述条件的串：每个 1 都有 0 直接跟在右边。并构造和 $M$ 等价的正规式。

2. （自顶向下分析） 已知文法 $G(S)$： $S \to (L) \mid aS \mid a$ $L \to L,S \mid S$ (1) 消除该文法的左递归和回溯。 (5分) (2) 计算该文法消除左递归后每个非终结符的 FIRST 集和 FOLLOW 集。 (5分)

3. （自底向上分析） 已知文法 $G[E]$： $E \to E+T \mid T$ $T \to T*F \mid F$ $F \to (E) \mid i$ 请写出句型 $(E+F)*i$ 的所有短语、简单（直接）短语、句柄和最左素短语。

---

四、 综合题（本题共 4 小题，每小题 10 分，共 40 分）#

1. （文法二义性证明） 已知文法 $G(S)$： $S \to aSbS \mid bSaS \mid \varepsilon$ 试证明 $G(S)$ 是二义文法。并给出句子 $abab$ 的两种不同的最左推导过程。

2. （LL(1)语法分析） 判断下面文法是否为 LL(1) 文法，若是，请构造相应的 LL(1) 预测分析表。 $S \to aD$ $D \to STe \mid \varepsilon$ $T \to bH \mid H$ $H \to d \mid \varepsilon$

3. （LR(0)语法分析） 对下面的文法 $G$： $S' \to E$ $E \to aA$ $A \to cA \mid d$ (1) 列出该文法的 LR(0) 项目，并构造它的 LR(0) 项目集规范族及识别活前缀的 DFA。 (2) 判定该文法是否是 LR(0) 文法，若是，构造它的 LR(0) 分析表。

4. （SLR(1)语法分析） 某语言的文法 $G$ 为： $E \to aTd \mid \varepsilon$ $T \to Eb \mid a$ 证明 $G$ 不是 LR(0) 文法而是 SLR(1) 文法，并请给出该文法的 SLR(1) 分析表。