U8 语法制导翻译技术

一、总述

为代码生成做“需求分析”：符号表、运行时存储、中间表示（前面三章内容）。

方法：

1. 翻译文法（TG）和语法制导翻译
2. 属性翻译文法（ATG）
3. 自顶向下的语法制导翻译
   翻译文法的自顶向下语法制导翻译。
   属性文法的自顶向下语法制导翻译。

二、翻译文法

1、概念

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

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

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

1. 从活动序列中，抽去动作符号，则得输入序列$(i+i)\ast i$
2. 从活动序列中，抽去输入序列，则得动作序列，执行动作序列，则完成翻译任务：

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

三、语法制导翻译

1、概念

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

2、带属性的翻译文法

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

3）综合属性

$\uparrow C$是综合属性符号，$\uparrow$为综合属性标记，$c$为属性变量或者属性值

求值规则：综合属性是自右向左，自底向上求值

p,q,r为属性变量名。
属性变量名局部于每个产生式，也可使用不同的名字。

4）继承属性

5）举例

3、 L-属性翻译文法（L-ATG）

1）概念

这是属性翻译文法中较简单的一种。其输入文法要求是LL(1)文法，可用自顶向下分析构造分析器。在分析过程中可进行属性求值。

2）求值规则

1. 继承属性
   产生式左部非终结符号的继承属性值，取前面产生式右部该符号已有的继承属性值。
   产生式右部符号的继承属性值，用该产生式左部符号的继承属性或出现在该符号左部的符号的属性值进行计算。
2. 综合属性
   产生式右部非终结符号的综合属性值，取其下部产生式左部同名非终结符号的综合属性值。
   产生式左部非终结符号的综合属性值，用该产生式左部符号的继承属性或某个右部符号的属性进行计算。
   动作符号的综合属性用该符号的继承属性或某个右部符号的属性进行计算。

4、简单赋值形式的L-ATG（SL-ATG）

1）概念

一个L-ATG被定义为简单赋值形式的(SL-ATG)，当且仅当满足如下条件:

1. 产生式右部符号的继承属性↓是一个常量，它等于左部符号的继承属性值或等于出现在所给符号左边符号的一个综合属性值。
2. 产生式左部非终结符号的综合属性是一个常量，它等于左部符号的继承属性值或等于右部符号的综合属性值。
   例子：
   
   改进方法：把求值函数变成一个动作@f。