编译原理【第四+七章】

考试题

1、简述语法制导翻译的基本思想

将语法分析和语义分析结合起来，通过语法规则驱动语义动作执行，用于将源程序翻译成目标代码或中间代码。

通过使用属性和语义动作，编译器可以在语法分析的同时生成目标代码或中间代码，实现高效的翻译过程。

在这里插入图片描述

语法制导翻译（Syntax-Directed Translation, SDT）是一种在编译器中将语法分析和语义分析结合起来的方法，用于将源程序翻译成目标代码或中间代码。SDT的基本思想是通过语法规则驱动语义动作，从而完成翻译过程。

基本思想

语法制导翻译的基本思想是将语义动作（Semantic Actions）与语法规则（Grammar Rules）关联起来。在进行语法分析的同时，按照语法规则的推导顺序执行相应的语义动作，实现翻译功能。

主要组件

语法制导翻译通常由以下几个组件组成：

上下文无关文法（Context-Free Grammar, CFG）：
- 描述源语言的语法结构，通常表示为四元组 ( G = (V, \Sigma, R, S) )。
  - ( V )：非终结符集合
  - ( \Sigma )：终结符集合
  - ( R )：产生式规则集合
  - ( S )：开始符号
语义动作（Semantic Actions）：
- 关联到文法产生式的动作，用于计算属性值、生成代码或执行其他与翻译相关的操作。
属性（Attributes）：
- 与语法分析树中的节点相关联，用于存储与该节点相关的语义信息。属性分为两类：
  - 综合属性（Synthesized Attributes）：从子节点传递到父节点。
  - 继承属性（Inherited Attributes）：从父节点或兄弟节点传递到子节点。

属性文法（Attribute Grammar）

属性文法是上下文无关文法的一种扩展，其中每个产生式都与一组语义动作相关联。每个语法符号都可以有零个或多个属性。属性文法根据属性的计算方向分为两种主要类型：

S-属性文法（S-Attributed Grammar）：
- 只使用综合属性，适合自底向上的语法分析（如LR分析）。
L-属性文法（L-Attributed Grammar）：
- 允许综合属性和某些限制的继承属性，适合自顶向下的语法分析（如LL分析）。

语法制导定义（Syntax-Directed Definition）

语法制导定义（SDD）是在上下文无关文法的基础上，通过添加语义动作来描述语法制导翻译过程。语义动作通常使用花括号 {} 表示，并嵌入到文法规则中。

例子

考虑一个简单的算术表达式文法和对应的语法制导定义：

文法规则

E -> E1 + T { E.val = E1.val + T.val; }
E -> T     { E.val = T.val; }
T -> T1 * F { T.val = T1.val * F.val; }
T -> F     { T.val = F.val; }
F -> ( E ) { F.val = E.val; }
F -> num   { F.val = num.val; }

属性和语义动作

E, T, F 的属性 val 表示表达式的值。
num 的属性 val 存储数值。

过程

语法分析：
- 根据输入字符串，构建语法分析树（或语法分析栈）。
语义动作执行：
- 在语法分析的同时，按照文法规则执行相应的语义动作，计算属性值。

示例

对于输入 3 + 4 * 5，构建的语法分析树及其属性值如下：

       E.val = 23
      /     \
  E1.val=3  T.val=20
   |         |
  T.val=3   T1.val=4
   |         |
 F.val=3    F.val=5
   |         |
  num.val=3  num.val=4