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

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

1. 编译程序工作过程中，各个阶段的工作都要涉及到 ( )。

• A. 词法分析
• B. 语法分析
• C. 表格管理与出错处理
• D. 语义分析

2. 关于编译和解释，以下说法正确的是 ( )。

• A. 编译是指把高级语言程序翻译成为中间代码的过程
• B. 任何编译程序都必须包含代码优化阶段
• C. 编译程序产生目标代码，而解释程序不产生目标代码
• D. 解释程序不对源语言进行翻译

3. 文法 $G$ 产生的 ( ) 的全体称为该文法描述的语言。

• A. 句型
• B. 句子
• C. 非终结符
• D. 终结符

4. 若文法 $G$ 定义的语言是无限集，则该文法必然是 ( )。

• A. 递归的
• B. 上下文有关的
• C. 二义性的
• D. 无二义性的

5. 词法分析器输出的单词符号通常不包括 ( )。

• A. 关键字
• B. 标识符
• C. 表达式
• D. 常数

6. 正规式 $M_1$ 和 $M_2$ 等价是指 ( )。

• A. $M_1$ 和 $M_2$ 的状态数相等
• B. $M_1$ 和 $M_2$ 的有向弧条数相等
• C. $M_1$ 和 $M_2$ 所表示的语言集相等
• D. $M_1$ 和 $M_2$ 的状态数与有向弧条数相等

7. 在高级语言编译程序常用的语法分析方法中，采用自上而下分析方法时，必须 ( )。

• A. 消除左递归
• B. 消除右递归
• C. 消除回溯
• D. 提取公共右因子

8. 下列哪种文法一定不是 LL(1) 文法 ( )。

• A. 递归文法
• B. 右递归文法
• C. 含有公共左因子的文法
• D. 3 型文法

9. 如果文法是无二义的，那么规范归约是指 ( )。

• A. 最左推导的逆过程
• B. 最右推导的逆过程
• C. 规范推导
• D. 最左归约的逆过程

10. LR 分析器的核心部分是一张分析表，该表由 ( ) 组成。

• A. ACTION 表
• B. GOTO 表
• C. 预测分析表
• D. ACTION 表和 GOTO 表

---

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

1. 编译程序工作过程中，贯穿于编译程序始终的两个独立且重要的工作是__________和__________。

2. 按照乔姆斯基 (Chomsky) 对文法的分类，2 型文法也称为__________文法，3 型文法也称为__________文法。

3. 自上而下语法分析的两个典型分析程序是__________和__________。

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

5. 确定有限自动机 (DFA) 与非确定有限自动机 (NFA) 的主要区别在于：DFA 的初态是__________的，且状态转移函数是__________函数。

---

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

1. （词法分析） 为正规表达式 $(a \mid b)^*abb$ 构造相应的非确定有限自动机 (NFA)，并利用子集构造法将其确定化为确定有限自动机 (DFA)。

2. （自顶向下分析） 已知文法 $G(S)$： $S \to S*aT \mid aT \mid *aT$ $T \to +aT \mid +a$ (1) 消除该文法的左递归，并提取公共左因子。 (2) 计算改写后文法中各个非终结符的 FIRST 集和 FOLLOW 集。

3. （短语与句柄） 已知文法 $G[S]$： $S \to SdT \mid T$ $T \to T<G \mid G$ $G \to (S) \mid a$ 请给出句型 $(SdG)<a$ 的所有短语、简单（直接）短语、最左素短语和句柄。

---

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

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

2. （LL(1) 语法分析） 已知文法 $G(S)$： $S \to aBc \mid bAB$ $A \to aAb \mid b$ $B \to b \mid \varepsilon$ (1) 计算该文法各非终结符的 FIRST 集和 FOLLOW 集。 (2) 构造该文法的 LL(1) 预测分析表，并判定其是否为 LL(1) 文法。

3. （LR(0) 语法分析） 已知文法 $G(S)$： $S \to aS \mid bS \mid a$ (1) 增加增广文法产生式 $S' \to S$ 后，构造其 LR(0) 项目集规范族及识别活前缀的 DFA。 (2) 判断该文法是否为 LR(0) 文法，并说明理由。如果不是 LR(0) 文法，请指出具体存在什么冲突。

4. （SLR(1) 语法分析） 已知增广文法 $G(A)$： $A' \to A$ $A \to aAd \mid aAb \mid \varepsilon$ (1) 构造该文法的 LR(0) 项目集规范族。 (2) 证明该文法不是 LR(0) 文法而是 SLR(1) 文法，并构造其 SLR(1) 分析表。