编译-第09章-语法制导翻译技术

Fyw0o Nothing •

2025-11-22

Compiler

Compiler Theory

编译-第9章-语法制导翻译技术

9.0 本章导言

词法分析、语法分析：解决单词和语言成分的识别及词法和语法结构的检查。语法结构可形式化地用一组产生式来描述。给定一组产生式，我们应该能够将其分析器构造出来。

本章要介绍的是语义分析和代码生成技术。

9.1 翻译文法和语法制导翻译

基本概念

有上下文无关文法G[E]：

E→E+T
E→T
T→T*F
T→F
F→(E)
F→i

此文法是一个中缀算术表达式文法。

翻译任务：中缀表达式→逆波兰表示

a+bc → abc+

翻译文法的构造

假如我们的翻译任务是要将中缀表达式简单变换为波兰后缀表示，只需在上述文法中插入相应的动作符号：

E→E+T@+
E→T
T→TF@
T→F
F→(E)
F→i@i

其中：@+，@*，@i为动作符号。@为动作符号标记，其后为字符串。

动作符号=动作符号标记+字符串

语义动作

在该具体例示中，其对应语义子程序的功能是要输出打印动作符号标记后面的字符串：

产生式1：E→E+T@+ 的语义是分析E、+和T输出+
产生式6：F→i@i 分析i输出i

基本定义

输入文法：未插入动作符号时的文法。由输入文法可以通过推导产生输入序列。

翻译文法：插入动作符号的文法。由翻译文法可以通过推导产生活动序列。

示例分析

活动序列：由翻译文法推导出的符号串，由终结符和动作符号组成。

从活动序列中：

抽去动作符号则得输入序列(i+i)*i
抽去输入序列，则得动作序列

执行动作序列，则完成翻译任务：

1	@i@i@+@i@* => ii+i* 刚好是逆波兰表示

形式化定义

**定义9.1** 翻译文法是上下文无关文法，终结符号集由输入符号和动作符号组成。由翻译文法所产生的终结符号串称为活动序列。

以上例题中的翻译文法为：

![image](/images/编译-第9章-语法制导翻译技术/1763810711253_nf4qi4_image.png)

**符号串翻译文法**：一种特殊的翻译文法：**动作符号对应的语义子程序功能是直接输出动作符号标记后面的字符串**。

**语法制导翻译**：按翻译文法进行的翻译。给定一个输入符号串，根据翻译文法获得翻译该符号串的动作序列，并执行该序列所规定的动作过程。

### 语法制导翻译的实现方法

- 在文法的适当位置插入语义动作符号。当按文法分析到动作符号时就调用相应的语义子程序，完成翻译任务。
- 翻译文法所定义的翻译是由输入序列和动作序列组成的对偶集。因此，给定一个翻译文法，就给定了一个对偶集。（怎么理解对偶？？？**对偶**就是**有序对**（Ordered Pair）的概念，在语法制导翻译中，对偶集合=（被翻译的符号串，动作序列））

## 9.2 属性翻译文法

在翻译文法的基础上，我们可以进一步定义属性文法。翻译文法中的符号，包括**终结符、非终结符和动作符号**均可带有属性，这样能更好地描述和实现编译过程。

属性可以分为两种：

- 综合属性
- 继承属性

### 9.2.1 综合属性

基本操作数带有属性的表达式文法G[E]：

1. E→E+T
2. E→T
3. T→T*F
4. T→F
5. F→(E)
6. F→i↑c

其中 ↑c是综合属性符号，↑为综合属性标记，c为属性变量或者属性值。

此文法能够产生如下的输入序列：(i↑3+i↑9)*i↑2

### 属性求值规则

为了形式地表示上述表达式的属性求值过程，我们可以改写上述文法：

| 产生式 | 求值规则 |
| --- | --- |
| 1. E↑p₄→ E↑q₅+ T↑r₂ | p₄ := q₅ + r₂ |
| 2. E↑p₃→T↑q₄ | p₃ := q₄ |
| 3. T↑p₂→T↑q₃*F↑r₁ | p₂ := q₃ * r₁ |
| 4. T↑p₂→F↑q₂ | p₂ := q₂ |
| 5. F↑p₁→(E↑q₁) | p₁ := q₁ |
| 6. F↑p₁→i↑q₁ | p₁ := q₁ |

说明：

- p, q, r为属性变量名
- 属性变量名**局限于每个产生式**，可使用不同的名字
- 求值规则：综合属性是自右向左，自底向上

### 9.2.2 继承属性

考虑到下列文法：G[<说明>]

1. <说明>→ Type id<变量表>
2. <变量表>→，id<变量表>
3. <变量表>→ε

其中：

- Type：类型名，值为integer,real,boolean等，词法分析程序返回的类型的类别码
- id：变量（值：标识符本身）

对于上述文法的说明语句：integer A, B1

该文法的翻译任务：将声明的变量填入符号表（语义）

完成该工作的动作符号：@set_table

### 属性翻译文法设计

@set_table的插入位置表示填表动作的时机。

翻译文法：

1. <说明>→Type id@set_table<变量表>
2. <变量表>→,id@set_table<变量表>
3. <变量表>→ε

填表时需要的信息：类型、名字、以及位置（可以用全程变量的指针）如何得到？

终结符（输入符号）的类型和名字在词法分析时得到，可设两个综合属性：

- Type↑t：t中是类型值
- id↑n：n是变量名

填表动作符号也可带有属性：@set_table↓t₁,n₁

可从其前面的符号得到，称为继承属性，继承前面符号的值。

<变量表>↓t₂：↓t₂同上

属性翻译文法：

1. <说明>→Type↑t id↑n @set_table↓t₁,n₁ <变量表>↓t₂
    
    1
t2,t1:=t;n1:=n

    
2. <变量表>↓t₂→, id↑n @set_table↓t₁,n₁ <变量表>↓t₃
    
    1
t3,t1:=t2;n1:=n

    
3. <变量表>↓t₁→ε

### 示例分析

int A,BC ⇒ Type↑int id↑A, id↑BC

**继承属性求值规则：自左向右，自顶向下，具体规则看下方**

[https://www.notion.so/28ef96e6b2b7807aababd61e10e8afcf?source=copy_link#28ef96e6b2b780d0bb1feb0f10513a94](https://www.notion.so/28ef96e6b2b7807aababd61e10e8afcf?pvs=21)

### 9.2.3 属性翻译文法的自顶向下翻译

### （一）L-属性翻译文法（L-ATG）

其输入文法要求是LL(1)文法，可用自顶向下分析方法构造分析器

LL(1)文法要求：

- 无左递归
- A::=α|β，FIRST(α)∩FIRST(β)=Φ
- 若β=>ε，则FIRST(α)∩FOLLOW(A)=Φ

特点：某个符号的继承属性只依赖于该符号左边的信息！

**定义9.2** L-属性翻译文法是带有下列说明的翻译文法：

1. 文法中的终结符，非终结符及动作符号都带有属性，且每个属性都有一个值域
2. 非终结符及动作符号的属性可分为继承属性和综合属性
3. 开始符号的继承属性具有指定的初始值
4. 输入符号（终结符号）的每个综合属性具有指定的初始值（通过词法分析拿到的），**没有继承属性**
- 终结符只有综合属性（它们由词法分析器提供）。
- 非终结符和动作符号既可以有综合属性也可有继承属性。
- 文法开始符号的所有继承属性作为属性计算前的初始值。

### 属性求值规则

继承属性体现自顶向下，自左向右的求值特性：

1. 产生式左部非终结符号的继承属性值，取前面产生式右部该符号已有的继承属性值
2. 产生式右部符号（非终结符、动作符号）的继承属性值，用该产生式左部符号的继承属性或出现在该符号左部的符号的属性值进行计算

综合属性体现自底向上，自右向左的求值特性：

1. 产生式右部非终结符号的综合属性值，取其下部产生式左部同名非终结符号的综合属性值
2. 产生式左部非终结符号的综合属性值，用该产生式左部符号的继承属性或某些右部符号的（任意）属性进行计算
3. 动作符号的综合属性用该符号的继承属性或某些右部符号的（任意）属性进行计算

### （二）简单赋值形式的L-属性翻译文法（SL-ATG）

一般情况下：x:=f(y,z)，x的属性值是y和z的属性值的函数

SL-ATG：x:=某符号的属性值或常量

例：x,y,z:=17称为复写规则

**定义9.4** 一个L-ATG被定义为简单赋值形式的（SL-ATG），当且仅当满足如下条件：

1. 产生式右部符号的继承属性是一个常量，它等于左部符号的继承属性值，或等于出现在所给符号左部某个符号的综合属性值
2. 产生式左部非终结符号的综合属性是一个常量，它等于其自身的继承属性值或等于右部某个符号的综合属性值

目的：一个简单赋值形式的L-ATG除动作符号外，其余符号的属性求值规则右部是属性或是常量（一简单化）。

### L-ATG ⇒ SL-ATG转换

给定一个L-ATG，如何找一个等价的简单赋值形式的L-ATG？

考虑产生式：

1
⟨A>→a↑R⟨B>↑S⟨C>↓II:=f(R,S)


显然：继承属性求值规则不是简单赋值形式的，因为它需要对f求值。

转换步骤：

1. 设动作符号"@f"表示函数f求值，该动作符号有两个继承属性和一个综合属性
2. 修改产生式：
    - 插入"@f"到右部的适当位置
    - 引进新的复写规则（将R,S赋给I₁和I₂，f值赋给S₁）
    - 删去原有包含f的规则

1
<A>→a↑R<B>↑s@f↓I1,I2↑s1<C>↓I,


1
I1:=R,I2:=S,S1:=f(I1,I2),I:=S1


该文法是简单赋值形式的L-ATG。

## 9.3 自顶向下语法制导翻译

先介绍翻译文法的自顶向下翻译，然后介绍属性翻译文法的自顶向下翻译。

### 9.3.1 翻译文法的自顶向下翻译（递归下降翻译器）

按翻译要求，在文法中插入语法动作符号，在分析过程中调用相应的语义处理程序，完成翻译任务。

NEXTSYM：词法分析程序。每调用一次，单词类别码→CLASS，该符号指针指向下一个单词。

### 9.3.2 属性翻译文法的自顶向下翻译的实现（递归下降翻译器）

我们把处理翻译文法的递归下降翻译器进行适当扩展，便可得到处理属性（翻译）文法的递归下降翻译器。

### 方法

对于每个非终结符号都编写一个翻译子程序（过程）。根据该非终结符号具有的属性数目，设置相应的参数。

1
U↓x,↑y⟶..


- 继承属性：声明为赋值形参
- 综合属性：声明为变量形参

过程调用语句的实参：

- 继承属性：继承属性值（传实参值）
- 综合属性：属性变量名（传地址，返回时有值）

### 关于属性名的约定

1. 具有相同值的属性取相同的属性名（这样可省去不少属性求值规则）
2. 产生式左部的同名非终结符使用相同的属性名（递归下降分析法规定每个非终结符只编写一个子程序！）

具有简单赋值形式的属性变量名取相同的属性名，可删去属性求值规则。

### 示例分析

通过一个例子详细介绍如何构造属性文法的递归下降翻译器（该文法应是具有L-属性的符号串翻译文法）。

例：有如下属性翻译文法G[<S>]

1. `<S>↓R1⟶a↑T1<A>↑Q1@x↓T2,R2<S>↓Q2`
    
    1
R2:=R1,T2:=T1,Q2:=Q1

    
2. `<S>↓R1⟶b@Z↓R2R2:=R1`
3. `<A>↑P⟶c↑U1@y↓U2<A>↑Q<S>↓Z@v↓Pb`
    
    1
U2:=U1,P:=Q+U1,Z:=U1−3

    
4. `<A>↑P\longrightarrow@wP:=8`

开始符号的继承属性R=7。

简化后的属性翻译文法G[<S>]：

1. `<S>↓R⟶a↑T<A>↑Q@X↓T,R<S>↓Q`
2. `<S>↓R⟶b@Z↓R`
3. `<A>↑P⟶c↑U@y↓U<A>↑Q<S>↓Z@v↓Pb`
    
    1
P:=Q+U,Z:=U−3

    
4. `<A>↑P\longrightarrow@wP:=8`

### 递归下降翻译器实现

全局变量的过程声明：

- CLASS：存放单词类别码
- TOKEN：存放单词值
- NEXTSYM：词法分析程序。每调用一次，单词类别码→CLASS，单词值→TOKEN，该符号指针指向下一个单词

主程序：

1
2
3
4
NEXTSYM; /* CLASS=第一个输入符号的类型; TOKEN=第一个输入符号的值; */
PROCS(7);
if CLASS≠右界符 then ERROR;
ACCEPT;


过程实现细节（略）

### 另一个示例：中缀表达式翻译成四元式

例：构造将算术表达式翻译成四元组的属性翻译文法，并写出递归下降分析程序。

翻译的输入：算术表达式a+b

翻译的输出：四元组ADD,Pa,Pb,Pr

（Pa,Pb,Pr为变量a,b和结果单元的地址，由编译分配）

表达式：(a+b)*c

数据区：

输入：(id↑1+id↑2)∗id↑4

输出：

ADD,1,2,3

MULT,3,4,5

### （1）翻译文法设计

- E→E+T@ADD
- E→T
- T→T*F@MULT
- T→F
- F→(E)
- F→id

其中：

- @ADD为输出ADD四元式的动作符号
- @MULT为输出MULT四元式的动作符号

### （2）属性翻译文法的设计

在翻译文法的基础上可设计其属性翻译文法：

- 输入符号（操作数）有一综合属性，它是该符号在数据区的地址
- 每个非终结符有一个综合属性，该属性是由它产生的代表该子表达式在数据区中的地址（中间结果）
- 动作符号有三个继承属性，它们分别是左右操作数和运算结果在数据区的地址

属性翻译文法：

1. `E↑x→E↑q+T↑r@ADD↓y,z,p`
    
    1
x,p:=NEW,y:=q,z:=r

    
2. `E↑x→T↑px:=p`
3. `T↑x→T↑q∗F↑r@MULT↓y,z,p`
    
    1
x,p:=NEW,y:=q,z:=r

    
4. `T↑x→F↑px:=p`
5. `F↑x→(E↑p)x:=p`
6. `F↑x→id↑px:=p`

说明：id的综合属性p是数据区地址。NEW为系统过程，返回的数据区地址。

语义动作程序：

1
@ADD↓y,z,p⇒fprintf(objfile,"ADD%d%d%d\n",y,z,p)


### （3）编写递归下降翻译程序（自己编写）