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

属性文法和语法的制导翻译 习题#

---

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

1. 关于 S-属性文法，以下说法错误的是 ( B )。

• A. S-属性文法中的文法符号仅包含综合属性
• B. S-属性文法中的每个文法符号都必须至少包含一个综合属性
• C. S-属性文法能够在自下而上语法分析过程中完成语义处理
• D. S-属性文法的翻译过程需要借助于栈来完成

【解析】 S-属性文法要求文法中只使用综合属性（不使用继承属性），但并不要求每个文法符号都必须拥有至少一个综合属性。某些文法符号可以没有任何属性。因此 B 说法错误。

2. 关于属性文法，以下说法错误的是 ( C )。

• A. 终结符号只有综合属性
• B. 非终结符号既可以有综合属性，也可以有继承属性
• C. 某个属性可以既是综合属性，又是继承属性
• D. S-属性文法是 L-属性文法的一种特殊情况

【解析】 一个属性要么是综合属性，要么是继承属性，不能同时是两者。综合属性的值由子节点计算，继承属性的值由父节点或兄弟节点传递，两种计算方向是互斥的。因此 C 说法错误。

3. 下面的属性文法中适合一遍自上而下计算的是 ( B )。

• A. S - 属性文法
• B. L - 属性文法
• C. 任何属性文法
• D. 只含继承属性的属性文法

【解析】 L-属性文法（L-Attributed Grammar）的特点是每个属性要么是综合属性，要么是继承属性但只依赖于其左边兄弟节点或父节点的属性。这种特性使得 L-属性文法适合在一遍自上而下（如递归下降）的语法分析过程中完成属性计算。S-属性文法适合自下而上计算。

4. 终结符仅有 ______ 属性。( B )

• A. 传递
• B. 综合
• C. 抽象
• D. 继承

【解析】 终结符只有综合属性，其值通常由词法分析器提供（如标识符的名字、常数的值等）。终结符没有继承属性，因为终结符是叶节点，不需要从父节点向下传递信息。

5. 程序设计语言的语义通常不包括 ( C )。

• A. 静态语义
• B. 动态语义
• C. 语法语义
• D. 语用语义

【解析】 程序设计语言的语义分类通常包括静态语义（编译时可检查的语义，如类型检查）、动态语义（运行时的行为含义）和语用语义（语言使用的上下文含义）。“语法语义”不是标准的语义分类术语，语法和语义是编译过程中两个不同层次的概念。

6. 语义分析阶段的主要输出是 ( C )。

• A. 单词符号
• B. 语法树
• C. 带语义信息的语法树
• D. 目标代码

【解析】 词法分析输出单词符号，语法分析输出语法树，语义分析在语法树的基础上附加语义信息（如类型、作用域等），输出带语义信息的语法树（注释语法树）。目标代码是代码生成阶段的输出。

7. 文法制导翻译的主要目的是 ( B )。

• A. 检查程序的语法
• B. 利用语法规则将源程序翻译成中间代码或目标代码
• C. 优化程序的执行
• D. 解析源程序查找语法错误

【解析】 文法制导翻译（Syntax-Directed Translation）的核心思想是将语义规则与语法规则结合，在语法分析的同时或之后，利用语法规则指导将源程序翻译为中间代码或目标代码。检查语法是语法分析的任务，代码优化是优化阶段的任务。

8. 在文法制导翻译中，属性表示 ( A )。

• A. 与语法树节点相关联的一段信息
• B. 源程序中的语法错误
• C. 一种解析技术
• D. 一种代码优化技术

【解析】 在文法制导翻译中，属性（Attribute）是附加在语法树节点上的信息，用于描述该节点对应的语法成分的语义特征，如变量的类型、表达式的值等。

9. 文法制导翻译的关键组成部分是 ( A )。

• A. 属性文法
• B. 语法分析器
• C. 语义分析器
• D. 代码生成器

【解析】 属性文法（Attribute Grammar）是文法制导翻译的理论基础和关键组成部分，它将语义规则与文法产生式关联起来，定义了属性的计算方法。语法分析器、语义分析器和代码生成器是编译器的组成部分，但不是文法制导翻译特有的核心概念。

10. 语义规则在文法制导翻译中的作用是 ( A )。

• A. 定义属性如何在语法树中计算 and 传播
• B. 检查程序的语法
• C. 优化程序代码
• D. 生成目标代码

【解析】 语义规则描述了各个属性之间的依赖关系和计算方法，定义了属性值如何在语法树中从一个节点传播到另一个节点（综合属性自下而上，继承属性自上而下或从左到右）。

11. 下列关于综合属性的说法正确的是 ( A )。

• A. 其值由其子节点的值计算得到
• B. 其值由其父节点的值计算得到
• C. 其值从父节点传递到子节点
• D. 用于语义检查

【解析】 综合属性（Synthesized Attribute）的值由该节点的子节点（产生式右部符号）的属性值计算得到，信息流向是自下而上的。B 和 C 描述的是继承属性的特征，D 过于笼统。

12. 有文法 $G$ 及其语法制导翻译如下所示（其中 $*$ 和 $+$ 分别是常规意义下的算术乘法和加法运算）：( C )

$$\begin{aligned} T &\to T_1 \wedge T_2 && \{ T.\text{val} = T_1.\text{val} \times T_2.\text{val} \} \\ T &\to T_1 \# n && \{ T.\text{val} = T_1.\text{val} + n.\text{val} \} \\ T &\to n && \{ T.\text{val} = n.\text{val} \} \end{aligned}$$

若分析句子 1 ∧ 2 ∧ 3 # 4，其属性计算的算术表达式应为：

• A. 1 + (2 * 3) + 4
• B. 1 * (2 + 3) + 4
• C. 1 * (2 * (3 + 4))
• D. 1 * (2 + 3 * 4)

【解析】 文法 $T \to T_1 \wedge T_2$ 和 $T \to T_1 \# n$ 都是左递归产生式。对于输入 1 ∧ 2 ∧ 3 # 4，需要分析语法树的结构。由于 $\wedge$ 的右侧是 $T_2$（非终结符），它可以继续展开；而 $\#$ 的右侧是 $n$（终结符）。在自底向上分析中，首先 3 # 4 归约为 $T$（值为 $3+4$），然后 2 ∧ T 归约为 $T$（值为 $2 \times (3+4)$），最后 1 ∧ T$ 归约为 $T$（值为 $1 \times (2 \times (3+4))$）。因此结果为 1 * (2 * (3 + 4))`。

13. 文法制导翻译中，翻译方案是指 ( A )。

• A. 一组用于将源程序翻译的产生式规则和相关语义动作
• B. 一组语法检查规则
• C. 一组代码优化规则
• D. 一组目标代码生成规则

【解析】 翻译方案（Translation Scheme）是文法制导翻译的具体实现形式，它将语义动作嵌入到产生式中，形成一组产生式规则和相关的语义动作，用于在语法分析过程中完成翻译工作。

14. 关于文法制导翻译，下列说法正确的是 ( A )。

• A. 它将语法分析和语义分析结合起来
• B. 它仅用于语法错误检测
• C. 它只专注于代码优化
• D. 它仅用于中间代码生成

【解析】 文法制导翻译的核心思想就是在语法分析的过程中嵌入语义动作，将语法分析和语义分析/翻译结合起来同步进行。它不仅仅用于语法错误检测或中间代码生成，而是一种综合性的翻译框架。

15. 下列关于继承属性的描述，正确的是 ( B )。

• A. 继承属性的值由该节点的子节点属性计算得到
• B. 继承属性的值从父节点或兄弟节点传递而来
• C. 综合属性和继承属性不能同时出现在同一个文法符号中
• D. 继承属性仅用于表示常量或变量的取值

【解析】 继承属性（Inherited Attribute）的值由该节点的父节点或左兄弟节点的属性值计算得到，信息流向是自上而下或从左到右。A 描述的是综合属性的特征，C 不正确（同一个非终结符可以同时有综合和继承属性），D 过于局限。

16. 在语法制导翻译中，属性文法的 “属性” 不可以表示 ( D )。

• A. 变量的类型
• B. 表达式的值
• C. 语法树的深度
• D. 源程序的行号

【解析】 属性文法中的属性用于表示与文法符号语义相关的信息。变量类型、表达式的值、语法树的深度都是与文法结构直接相关的语义信息，可以通过语义规则计算。而源程序的行号是源代码的物理位置信息，与文法的语义结构无关，不属于属性文法中属性的表示范围。

17. 翻译方法与属性文法的主要区别在于 ( B )。

• A. 翻译方法只处理综合属性，属性文法处理所有属性
• B. 翻译方法将语义动作嵌入到产生式右部，属性文法将语义规则独立列出
• C. 翻译方法用于代码生成，属性文法用于语义检查
• D. 翻译方法是属性文法的一种简化形式，不含继承属性

【解析】 翻译方案（Translation Scheme）与属性文法的主要区别在于语义动作的组织方式：翻译方案将语义动作直接嵌入到产生式右部的特定位置，明确指定执行顺序；而属性文法将语义规则作为产生式的附属，独立列出，不指定具体执行顺序。

18. 文法制导翻译中，对语法树进行属性计算的常用方法是 ( B )。

• A. 先序遍历
• B. 后序遍历（适用于综合属性）
• C. 层次遍历
• D. 随机遍历

【解析】 综合属性的值由子节点计算得到，因此需要先计算子节点的属性值，再计算父节点的属性值，这恰好对应后序遍历（先访问子节点，再访问父节点）的顺序。后序遍历是计算综合属性最自然、最常用的方法。

19. 设有文法片段及语义规则如下：( B )

$$\begin{aligned} S &\to aAb && \{ S.\text{len} = A.\text{len} + 2 \} \\ A &\to bA'c && \{ A.\text{len} = A'.\text{len} + 2 \} \\ A &\to \varepsilon && \{ A.\text{len} = 0 \} \end{aligned}$$

则句子 a bbcc b（其中 bbcc 表示两个 b 和两个 c）对应的 $S.\text{len}$ 值为 ( )。

• A. 4
• B. 6
• C. 8
• D. 10

【解析】 对句子 a bbcc b 进行推导：

• $S \to aAb$，其中 $A$ 对应 bbcc
• $A \to bA'c$，$A'$ 对应 bc
• $A' \to bA''c$，$A''$ 对应 $\varepsilon$
• $A''.\text{len} = 0$（由 $A \to \varepsilon$）
• $A'.\text{len} = A''.\text{len} + 2 = 0 + 2 = 2$
• $A.\text{len} = A'.\text{len} + 2 = 2 + 2 = 4$
• $S.\text{len} = A.\text{len} + 2 = 4 + 2 = 6$

20. 下列不属于文法制导翻译应用场景的是 ( D )。

• A. 计算表达式的值
• B. 检查变量是否声明
• C. 生成中间代码（如三地址码）
• D. 对源程序进行词法分析

【解析】 词法分析是编译的第一个阶段，它将源程序的字符流分解为单词符号（Token），这个过程使用正则表达式和有限自动机，与文法制导翻译无关。文法制导翻译用于语法分析之后的语义处理，包括计算表达式值、检查变量声明、生成中间代码等。

21. 语义分析的主要目的是 ( B )。

• A. 识别源程序的语法结构是否符合文法规则
• B. 检查源程序的语义正确性，并收集类型信息等用于后续翻译
• C. 将源程序转换为中间代码
• D. 优化目标代码的执行效率

【解析】 语义分析的核心任务是检查源程序的语义正确性（如类型检查、作用域检查等），并收集必要的类型信息和其他语义信息，为后续的中间代码生成和代码优化提供基础。A 是语法分析的任务，C 是中间代码生成的任务，D 是代码优化的任务。

22. 下列哪项不属于语义分析的常见任务 ( C )。

• A. 变量未声明就使用的检查
• B. 表达式中不同类型数据的运算合法性检查
• C. 识别源程序中的关键字和标识符
• D. 函数调用时实参与形参的个数和类型匹配检查

【解析】 识别关键字和标识符是词法分析阶段的任务，词法分析器通过模式匹配将源程序字符流分解为 Token。而变量声明检查、类型检查和函数参数匹配检查都是语义分析的典型任务。

23. 在语义分析中，“类型检查”的核心是 ( B )。

• A. 检查变量名是否符合命名规范
• B. 确保运算或函数调用中参与的操作数类型符合语法规则
• C. 确保变量在使用前已被赋值
• D. 检查表达式的括号是否匹配

【解析】 类型检查的核心是验证程序中各种运算和函数调用中操作数（或参数）的类型是否兼容、是否符合语言的类型规则。例如，检查整数和字符串是否能相加，函数实参类型是否与形参类型匹配等。A 是命名规范检查，C 是数据流分析的内容，D 是语法分析的任务。

24. 语义分析阶段收集的信息通常存储在 ( B ) 中，供后续代码生成等阶段使用。

• A. 语法树
• B. 符号表
• C. 中间代码
• D. 目标代码

【解析】 符号表（Symbol Table）是编译器中用于存储标识符相关信息（如变量名、类型、作用域、存储地址等）的重要数据结构。语义分析阶段收集的类型信息、作用域信息等都存储在符号表中，供后续的中间代码生成和代码优化阶段使用。

25. 下列关于语义分析与语法分析的关系，说法正确的是 ( B )。

• A. 语义分析必须在语法分析之前进行
• B. 语义分析依赖语法分析的结果（如语法树）
• C. 语法分析和语义分析是完全独立的过程
• D. 语义分析仅关注源程序的结构，不关注意义

【解析】 语义分析以语法分析产生的语法树为基础进行工作，它依赖语法分析的结果来确定程序的结构，然后在此基础上进行语义检查和信息收集。语义分析不能先于语法分析进行，两者也不是完全独立的过程。

26. 下列哪种错误最可能在语义分析阶段被发现 ( C )。

• A. 括号不匹配（如 (a + b）
• B. 关键字拼写错误（如 whle 代替 while）
• C. 整数与指针进行加法运算
• D. 语句末尾缺少分号

【解析】 括号不匹配和缺少分号是语法错误，在语法分析阶段发现；关键字拼写错误在词法分析阶段发现（会被识别为标识符而非关键字）。整数与指针进行加法运算是类型不匹配的语义错误，需要在语义分析阶段通过类型检查发现。

27. 对于表达式 x + 5，若 x 是字符串类型，语义分析阶段会 ( B )。

• A. 认为语法错误，因为 + 不能连接字符串和整数
• B. 认为语义错误，因为类型不匹配
• C. 自动将整数转换为字符串后允许运算
• D. 忽略类型问题，留待代码生成阶段处理

【解析】 x + 5 在语法上是合法的表达式（符合 表达式 + 表达式 的语法规则），但在语义上，字符串类型与整数类型之间的加法运算在大多数强类型语言中是不允许的，这是一个类型不匹配的语义错误，由语义分析阶段的类型检查机制发现。

28. 编译过程中，不属于中间代码生成阶段的任务是 ( B )。

• A. 生成三地址码
• B. 进行类型转换
• C. 生成四元式
• D. 生成抽象语法树

【解析】 三地址码、四元式和抽象语法树都是中间代码的表示形式，属于中间代码生成阶段的任务。而类型转换（类型检查和隐式类型转换的决策）属于语义分析阶段的工作，不属于中间代码生成阶段的任务。

29. 对于属性文法中的综合属性，下列说法正确的是 ( C )。

• A. 只能由父节点传递给子节点
• B. 可用于表示变量的类型（需从声明处传递到使用处）
• C. 其值由子节点的属性计算得到
• D. 必须通过继承属性才能计算

【解析】 综合属性的定义特征就是其值由子节点（产生式右部符号）的属性计算得到，信息自下而上流动。A 描述的是继承属性，B 中变量类型的传递通常使用继承属性，D 说法错误，综合属性不依赖继承属性。

30. 下列属于语义分析阶段完成的工作是 ( B )。

• A. 消除文法的左递归
• B. 记录变量的类型和作用域
• C. 将 a + b 转换为 add(a, b)
• D. 优化循环结构

【解析】 记录变量的类型和作用域信息（填入符号表）是语义分析阶段的核心工作之一。A 是文法变换，属于语法分析的预处理；C 是中间代码生成或目标代码生成的工作；D 是代码优化阶段的工作。

31. 关于终结符的属性，下列说法正确的是 ( B )

• A. 终结符可以有继承属性，且需通过父节点传递
• B. 终结符的综合属性值通常由词法分析器提供（如标识符的名字、常数的值）
• C. 终结符的属性必须由语义规则显式定义
• D. 终结符不能有任何属性

【解析】 终结符只有综合属性，没有继承属性。终结符的综合属性值通常由词法分析器在识别 Token 时确定并提供，例如标识符的名字（id.name）、常数的值（num.val）等。这些值不需要通过语义规则计算，而是直接从词法分析阶段获取。

32. 属性文法中的 “语义规则” 主要用于 ( B )

• A. 定义语法结构的合法性（如语法规则）
• B. 计算属性值，描述语法成分的语义含义（如类型检查、值计算）
• C. 确定语法分析的优先级和结合性
• D. 生成目标代码

【解析】 语义规则是属性文法的核心组成部分，它们附加在产生式上，用于定义属性值的计算方法。通过语义规则，可以描述各语法成分的语义含义，实现类型检查、表达式求值、代码生成等功能。A 是语法规则的作用，C 是语法分析技术的内容，D 是代码生成阶段的任务。

---

二、 主观题（本题共 2 小题，每小题 10 分，共 20 分）#

1. 产生式 $A \to BC$ 有以下语义规则：

C.d := B.c + 1
A.b := A.a + B.c

属性 $a, b, c, d$ 是综合属性还是继承属性？

【参考答案】

对于产生式 $A \to BC$，左部为 $A$，右部为 $B$ 和 $C$。

分析每个属性：

• 属性 $a$（继承属性）：$A.a$ 出现在语义规则 $A.b := A.a + B.c$ 的右侧。$A$ 是产生式左部符号，$A.a$ 的值被使用但未在此产生式中定义，说明其值来自于 $A$ 的父节点或兄弟节点（即从外部传入），因此 $a$ 是 $A$ 的继承属性。

• 属性 $b$（综合属性）：$A.b$ 出现在语义规则 $A.b := A.a + B.c$ 的左侧，被赋值定义。$A$ 是产生式左部符号，左部符号的属性在该产生式中被定义，说明其值由产生式右部的属性计算得到，因此 $b$ 是 $A$ 的综合属性。

• 属性 $c$（综合属性）：$B.c$ 出现在两条语义规则的右侧，被使用但未在此产生式中定义。$B$ 是产生式右部符号，$B.c$ 的值必须由 $B$ 自身的产生式计算得到（自底向上传递），因此 $c$ 是 $B$ 的综合属性。

• 属性 $d$（继承属性）：$C.d$ 出现在语义规则 $C.d := B.c + 1$ 的左侧，被赋值定义。$C$ 是产生式右部符号，右部符号的属性在该产生式中被定义，说明其值由父节点或兄弟节点传递而来，因此 $d$ 是 $C$ 的继承属性。

总结：$a$ 是继承属性，$b$ 是综合属性，$c$ 是综合属性，$d$ 是继承属性。

2. 以下属性文法中的属性 $\text{val}$ 是综合属性还是继承属性？

$$\begin{array}{ll} \text{产生式} & \text{语义规则} \\ \hline L \to En & \text{print}(E.\text{val}) \\ E \to E_1 + T & E.\text{val} := E_1.\text{val} + T.\text{val} \\ E \to T & E.\text{val} := T.\text{val} \\ T \to T_1 * F & T.\text{val} := T_1.\text{val} \times F.\text{val} \\ T \to F & T.\text{val} := F.\text{val} \\ F \to (E) & F.\text{val} := E.\text{val} \\ F \to \text{digit} & F.\text{val} := \text{digit}.\text{lexval} \end{array}$$

【参考答案】

属性 $\text{val}$ 是综合属性。

分析如下：在每一条产生式的语义规则中，$\text{val}$ 属性总是在产生式左部符号上被定义（赋值），其值由产生式右部符号的属性计算得到：

• $E \to E_1 + T$：$E.\text{val}$ 由子节点 $E_1.\text{val}$ 和 $T.\text{val}$ 计算得到
• $E \to T$：$E.\text{val}$ 由子节点 $T.\text{val}$ 直接赋值
• $T \to T_1 * F$：$T.\text{val}$ 由子节点 $T_1.\text{val}$ 和 $F.\text{val}$ 计算得到
• $T \to F$：$T.\text{val}$ 由子节点 $F.\text{val}$ 直接赋值
• $F \to (E)$：$F.\text{val}$ 由子节点 $E.\text{val}$ 直接赋值
• $F \to \text{digit}$：$F.\text{val}$ 由终结符 $\text{digit}$ 的词法值 $\text{lexval}$ 赋值

所有情况中，$\text{val}$ 属性的值都是自底向上（从子节点到父节点）计算的，符合综合属性的定义。该属性文法是一个典型的 S-属性文法，所有属性均为综合属性，可在自底向上的语法分析过程中通过后序遍历完成计算。