学堂在线测试 —— 编译原理

语法分析----自下而上分析习题

一、单项选择题（本题共 16 小题，每小题 1 分，共 16 分）

1. 在规范归约中，用来表示可归约串的是 ( A )。

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

【解析】 规范归约（最左归约）中，每一步归约的对象是句柄，即句型中最左的直接短语。素短语是算符优先分析中使用的概念，短语不一定是当前步骤可归约的最小单位，直接短语可能有多个但只归约最左的那个。

2. 下面哪些有可能是可归约串？( B )

A. 连续出现的单词序列
B. 短语
C. 字符串

【解析】 可归约串是指能通过某个产生式归约的子串。短语是从语法分析树的某个非终结符结点推导出来的子串，因此短语有可能是可归约串（句柄是最左直接短语，也是短语的一种）。一般的字符串或连续单词序列不一定满足文法规则。

3. 一个 ______ 指明了在分析过程中的某时刻所能看到的产生式多大一部分。( C )

A. 活前缀
B. 前缀
C. 项目
D. 项目集

【解析】 项目（Item） 是在产生式右部某处加一个圆点”·“，用来指示分析器当前已识别了产生式的多大一部分。例如 $A \to \alpha \cdot \beta$ 表示已看到 $\alpha$ 部分，还期望看到 $\beta$ 。项目集是项目的集合，活前缀是栈中可出现的符号串前缀。

4. 规范归约是指 ( B )。

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

【解析】 规范归约 = 最左归约 = 最右推导的逆过程。最右推导又称规范推导，其逆过程自然就是规范归约。每一步归约最左的句柄，对应的正是最右推导中最后被替换的那个非终结符。

5. 自下而上语法分析法的原理是 ( B )。

A. “移进 - 推导法”
B. “移进 - 归约法”
C. “最左推导法”
D. “推导 - 归约法”

【解析】 自下而上分析的基本方法是移进-归约法（Shift-Reduce）：将输入符号逐个移进栈中，当栈顶形成某个产生式右部时就归约为左部非终结符，反复进行直到归约为开始符号。

6. LR 分析法中，基于 LR(0) 项目集规范族的分析表有 ( C )。

A. LR(0) 和 LR(1)
B. LR(0) 和 LALR(1)
C. SLR(1) 和 LR(0)
D. SLR(1) 和 LALR(1)

【解析】 基于 LR(0) 项目集规范族（即不带搜索符的项目集）构造的分析表有两种：LR(0) 分析表和 SLR(1) 分析表。SLR(1) 在 LR(0) 项目集的基础上利用 FOLLOW 集来解决冲突。而 LR(1) 和 LALR(1) 则需要基于 LR(1) 项目集规范族（带搜索符的项目集）来构造。

7. 下面对 LR 文法描述语言的能力的包含关系中正确的是 ( C )。

A. $\text{LR}(1) \subset \text{LR}(0)$
B. $\text{LALR}(1) \subset \text{SLR}(1)$
C. $\text{LR}(0) \subset \text{SLR}(1)$
D. $\text{LR}(1) \subset \text{LALR}(1)$

【解析】 LR 文法的描述能力从弱到强为： $\text{LR}(0) \subset \text{SLR}(1) \subset \text{LALR}(1) \subset \text{LR}(1)$ 。因此 C 正确。A 和 D 方向反了，B 也反了（应为 $\text{SLR}(1) \subset \text{LALR}(1)$ ）。

8. 两个 LR(1) 项目集如果除去下列哪一项后是相同的，则称这两个 LR(1) 项目集同心：( C )。

A. 项目
B. 活前缀
C. 搜索符
D. 前缀

【解析】 LR(1) 项目形如 $[A \to \alpha \cdot \beta, a]$ ，其中 $a$ 是搜索符（lookahead）。两个 LR(1) 项目集同心是指它们的核心项目（即去掉搜索符后的 LR(0) 项目部分）完全相同，只是搜索符可能不同。LALR(1) 分析就是将同心的 LR(1) 项目集合并。

9. 下列哪个冲突在同心集合并中不会新产生 ( C )。

A. 二义
B. 移进/移进
C. 移进/归约
D. 归约/归约

【解析】 同心集合并（构造 LALR 分析表）时，合并操作只改变归约项目的搜索符集合（取并集），不会改变移进动作。因此：

移进/归约冲突不会因合并而新产生（移进动作不变，如果合并前没有冲突，合并后也不会有）；

归约/归约冲突可能因为搜索符合并后出现交集而新产生。

10. 下列关于 LR 分析表的说法，正确的是 ( A )。

A. LR 分析表由 ACTION 表和 GOTO 表组成
B. ACTION 表用于确定非终结符的转移
C. GOTO 表用于确定终结符的动作
D. LR(0) 分析表的能力强于 LR(1)

【解析】 LR 分析表由两部分组成：ACTION 表（根据当前状态和输入终结符决定移进/归约/接受/报错动作）和 GOTO 表（根据当前状态和非终结符确定转移到的下一状态）。B 和 C 描述反了，D 也不对（LR(1) 的能力强于 LR(0)）。

11. 文法中的 “句柄” 是指 ( A )。

A. 句型中最左的直接短语
B. 句型中最右的直接短语
C. 产生式右部的第一个符号
D. 文法的开始符号

【解析】 句柄（Handle） 的定义是句型中最左的直接短语。在规范归约（最左归约）中，每次归约的对象就是句柄。

12. LR 分析器的核心组成部分是 ( B )。

A. 预测分析表
B. 移进 - 归约表（分析表）
C. 递归函数集合
D. 产生式的优先关系表

【解析】 LR 分析器的核心是 LR 分析表（即移进-归约表），包含 ACTION 表和 GOTO 表，用来驱动移进-归约过程。预测分析表是 LL 分析器的核心，递归函数集合是递归下降分析的组成部分，优先关系表是算符优先分析的核心。

13. 下列关于 LR(0) 文法的说法，错误的是 ( C )。

A. LR(0) 文法是无二义性的
B. 所有 LR(0) 文法都是 SLR(1) 文法
C. LR(0) 文法的识别能力强于 LR(1) 文法
D. LR(0) 分析器的分析效率高于回溯法分析器

【解析】 C 是错误的。LR 文法的能力关系为 $\text{LR}(0) \subset \text{SLR}(1) \subset \text{LALR}(1) \subset \text{LR}(1)$ ，因此 LR(0) 的识别能力弱于 LR(1)，而非强于。A 正确（所有 LR 文法都是无二义性的），B 正确（LR(0) 是 SLR(1) 的真子集），D 正确（LR 分析器是确定性的，效率高于回溯法）。

14. LR(0) 分析中， $GOTO(I, X)$ 表示 ( B )。

A. 从项目集 $I$ 出发，输入符号 $X$ 后的归约动作
B. 从项目集 $I$ 出发，经过符号 $X$ （终结符或非终结符）转换后到达的项目集
C. 仅当 $X$ 是终结符时，从 $I$ 出发的移进动作
D. 项目集 $I$ 中所有包含 $X$ 的项目集合

【解析】 $GOTO(I, X)$ 的定义是：对于项目集 $I$ 中所有形如 $A \to \alpha \cdot X \beta$ 的项目，将圆点移过符号 $X$ 得到 $A \to \alpha X \cdot \beta$ ，再求其闭包，所得的项目集就是 $GOTO(I, X)$ 。 $X$ 可以是终结符也可以是非终结符。

15. 在自底向上的语法分析中，“归约” 是指 ( B )。

A. 从开始符号推导出当前句型
B. 将输入串中的一部分替换为某个产生式的左部符号
C. 检查输入串是否符合文法的终止条件
D. 消除文法中的左递归

【解析】 归约（Reduce）是推导的逆操作：当栈顶的符号串匹配某产生式 $A \to \alpha$ 的右部 $\alpha$ 时，将 $\alpha$ 替换为产生式的左部符号 $A$ 。A 描述的是推导而非归约，C 和 D 与归约概念无关。

16. 若项目集 $I_k$ 含有 $A \to \alpha \cdot$ ，则在状态 $k$ 时，仅当面临的输入符号 $a \in \text{FOLLOW}(A)$ 时，才采取 $A \to \alpha \cdot$ 动作的一定是 ( D )。

A. LALR 文法
B. LR(0) 文法
C. LR(1) 文法
D. SLR(1) 文法

【解析】 这是 SLR(1) 分析法的核心特征。SLR(1) 在遇到归约项目 $A \to \alpha \cdot$ 时，查看 $\text{FOLLOW}(A)$ 来决定是否归约。LR(0) 不看任何向前看符号，遇到归约项目就直接归约；LR(1) 和 LALR(1) 使用的是项目中附带的搜索符（lookahead），搜索符是 $\text{FOLLOW}(A)$ 的子集，比 FOLLOW 集更精确。因此”一定是”使用 $\text{FOLLOW}(A)$ 的是 SLR(1)。

二、多项选择题（本题共 2 小题，每小题 2 分，共 4 分。多选、少选、错选均不得分）

1. 若项目集 $I_k$ 含有 $A \to \alpha \cdot$ ，则在状态 $k$ 时，仅当面临 of 输入符号 $a \in \text{FOLLOW}(A)$ 时，才采取 $A \to \alpha \cdot$ 动作的是 ( A, D )。

A. LALR 文法
B. LR(0) 文法
C. LR(1) 文法
D. SLR(1) 文法

【解析】

SLR(1)：直接使用 $\text{FOLLOW}(A)$ 决定是否归约，完全符合题意。

LALR(1)：使用搜索符（lookahead set）决定归约，搜索符是 $\text{FOLLOW}(A)$ 的子集，因此也满足”仅当 $a \in \text{FOLLOW}(A)$ 时才归约”的条件（搜索符 $\subseteq$ FOLLOW 集）。

LR(0)：不看向前看符号，遇到归约项目对所有输入符号都归约，不满足”仅当”的条件。

LR(1)：使用精确的搜索符，搜索符也是 $\text{FOLLOW}(A)$ 的子集，但 LR(1) 的搜索符不一定等于 FOLLOW 集，题目强调的是以 FOLLOW 集为判断依据的方法，LR(1) 的判据更精确，不以 FOLLOW 集为直接依据。

注意本题与单选第 16 题的区别：单选问”一定是”，答案唯一为 SLR(1)；多选问”是”，LALR 和 SLR(1) 都满足条件。

2. LR(0) 分析表的 “动作表” (ACTION) 中，若状态 $i$ 面对输入符号 $a$ 时， $GOTO(i, a) = j$ ，则 $ACTION[i, a]$ 应为 ( B )。

A. 归约 (r)
B. 移进 (sj)
C. 接受 (acc)
D. 报错

【解析】 当 $GOTO(i, a) = j$ （其中 $a$ 是终结符）时，说明在状态 $i$ 下可以读入终结符 $a$ 并转移到状态 $j$ ，这正是移进（Shift） 操作。因此 $ACTION[i, a] = sj$ （shift to state $j$ ）。归约操作针对的是归约项目 $A \to \alpha \cdot$ ，与 $GOTO(i, a) = j$ 的转移动作不同。

三、主观题（本题共 1 小题，每小题 10 分，共 10 分）

1. 已知文法 $G$ ：

\begin{aligned} T &\to t \mid \varepsilon \mid (F) \\ F &\to T + F \mid T \end{aligned}

给出句型 $((t)+T)$ 的短语、直接短语。

【参考答案】
一、构造语法分析树
对句型 $((t)+T)$ 进行最右推导：
$T \Rightarrow (F) \Rightarrow (T+F) \Rightarrow (T+T) \Rightarrow ((F)+T) \Rightarrow ((T)+T) \Rightarrow ((t)+T)$
对应的语法分析树如下：
T
└── ( F )
    └── T + F
        │       └── T  ← [未展开的 T，即句型中的 T]
        └── T
            └── ( F )
                └── T
                    └── t
其中最右边的 $T$ 是句型中未被展开的非终结符（叶结点）。
二、确定短语
短语是语法树中每棵子树的叶结点从左到右排列所得的符号串（即从某个非终结符可以推导出的子串）：

子树根结点推导过程短语
$T$ （根） $T \Rightarrow^* ((t)+T)$ $((t)+T)$
$F$ （根的子结点） $F \Rightarrow^* (t)+T$ $(t)+T$
$T$ （ $+$ 左边） $T \Rightarrow^* (t)$ $(t)$
$F$ （内层括号内） $F \Rightarrow^* t$ $t$
$T$ （最内层） $T \Rightarrow t$ $t$
$F$ （ $+$ 右边） $F \Rightarrow T$ $T$
$T$ （最右叶结点） $T \Rightarrow^* T$ （自身） $T$
去重后，短语为： $((t)+T)$ 、 $(t)+T$ 、 $(t)$ 、 $t$ 、 $T$
三、确定直接短语
直接短语是仅经过一步推导（对应语法树中高度为 2 的子树，即父结点直接产生叶结点）得到的短语：

产生式直接短语
$T \to t$ $t$
$F \to T$ $T$
因此，直接短语为： $t$ 、 $T$
四、确定句柄
句柄是最左的直接短语。在句型 $((t)+T)$ 中，两个直接短语为 $t$ （位置靠左）和 $T$ （位置靠右），因此句柄为 $t$ 。

音乐

音乐

学堂在线测试 —— 编译原理

学堂在线测试 —— 编译原理

语法分析----自下而上分析习题

一、单项选择题（本题共 16 小题，每小题 1 分，共 16 分）

二、多项选择题（本题共 2 小题，每小题 2 分，共 4 分。多选、少选、错选均不得分）

三、主观题（本题共 1 小题，每小题 10 分，共 10 分）

音乐

课程

学堂在线测试 —— 编译原理

学堂在线测试 —— 编译原理#

语法分析----自下而上分析 习题#

一、 单项选择题（本题共 16 小题，每小题 1 分，共 16 分）#

二、 多项选择题（本题共 2 小题，每小题 2 分，共 4 分。多选、少选、错选均不得分）#

三、 主观题（本题共 1 小题，每小题 10 分，共 10 分）#

学堂在线测试 —— 编译原理

语法分析----自下而上分析习题

一、单项选择题（本题共 16 小题，每小题 1 分，共 16 分）

二、多项选择题（本题共 2 小题，每小题 2 分，共 4 分。多选、少选、错选均不得分）

三、主观题（本题共 1 小题，每小题 10 分，共 10 分）