BUAACT-Chap09-语法制导翻译技术

第九章 语法制导翻译技术

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

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

1. E -> E + T    4. T -> F
2. E -> T        5. F -> '(' E ')'
3. T -> T * F    6. F -> i

翻译的任务是：中缀表达式翻译为逆波兰表达式，只需在上述文法中插入相应的动作符号。

1. E := E + T @+   4. T := F
2. E := T          5. F := '(' E ')'
3. T := T * F @*   6. F := i @i

@为动作符号标记，其后为字符串，功能为输出后面的字符串。

输入文法和翻译文法的概念：

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

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

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

以上例题中的翻译文法为： \[\begin{aligned}G_T =& (V_n, V_t, P, E)\\V_n =& \{E, T, F\}\\V_t =& \{i, +, *, (, ), @+, @*, @i\}\\P =& \{E\to E + T @+, \\&E\to T, \\&T\to T * F@*, \\&T\to F, \\&F\to (E), \\&F\to i @ i\} \end{aligned}\]

符号串翻译文法：输入文法中的动作符号对应的语义子程序是输出动作符号标记@后的字符串的文法。

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

9.2 属性翻译文法

在翻译文法的基础上，进一步定义属性文法。

翻译文法中的符号，包括终结符、非终结符和动作符号均可带有属性，这样能更好地描述和实现编译过程。

属性可分为两种：综合属性、继承属性。

9.2.1 综合属性

基本操作数带有属性的表达式文法 G[E]： \[\begin{aligned}&1. E\to E + T\\&2. E\to T\\&3. T\to T * F\\&4. T \to F\\&5. F \to (E)\\&6. F\to i_{\uparrow c}\end{aligned}\] 其中 \(\uparrow c\) 是综合属性符号，\(\uparrow\) 是综合属性标记，\(c\) 是属性变量或属性值。

此文法能够产生输入序列：\((i_{\uparrow_3} + i_{\uparrow 9})*i_{\uparrow 2}\)。

根据给定的文法，可写出该输入序列的语法树：

语法树

综合属性的求值规律是自底向上，自右向左的。

9.2.2 继承属性

符号表填充文法

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

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

翻译文法：

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

填表动作符号也可以带有属性：

填表动作符号的属性

属性翻译文法：

属性翻译文法

一个例子

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

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

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

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

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

• 文法中的终结符，非终结符及动作符号都带有属性，且每个属性都有一个值域；
• 非终结符及动作符号的属性可分为继承属性和综合属性；
• 开始符号的继承属性具有指定的初始值；
• 输入符号（终结符号）的每个综合属性具有指定的初始值；
• 属性值的求值规则如下：
  • 继承属性——体现自顶向下，自左向右的求值特性：
    • 产生式左部非终结符号的继承属性值，取前面产生式右部该符号已有的继承属性值；
    • 产生式右部符号的继承属性值，用该产生式左部符号的继承属性或出现在该符号左部的符号的属性值进行计算；
  • 综合属性——体现自底向上，自右向左的求值特性：
    • 产生式右部非终结符号的综合属性值，取其下部产生式左部同名非终结符号的综合属性值；
    • 产生式左部非终结符号的综合属性值，用该产生式左部符号的继承属性或某些右部符号的（任意）属性进行计算；
    • 动作符号的综合属性用该符号的继承属性或某些右部符号的（任意）属性进行计算。

1. 终结符只有综合属性（它们由词法分析器提供）；
2. 非终结符和动作符号既可以有综合属性也可有继承属性；
3. 文法开始符号的所有继承属性作为属性计算前的初始值。

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

• 一般情况：x := f(y, z)，x的属性值是y和z属性值的函数
• SL-ATG中：x := 某符号的属性值或常量

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

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

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

将L-ATG 转化为 SL-ATG 方法是，插入动作符号，例如：

L-ATG文法

第一步：设动作符号@f表示函数 f 求值，该动作符号有两个继承属性和一个综合属性：


第二步，修改产生式：

1. 插入@f到右部的适当位置；
2. 引进新的复写规则（将 R、S 赋给 I₁ 和 I₂，f 值赋给 S₁）；
3. 删去原有包含 f 的规则。

改写后的文法

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

9.3.1 翻译文法的自顶向下翻译——递归下降翻译器

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

其实就是在原本的递归下降分析里面加一些动作，还是比较简单的。

9.3.2 属性文法自顶向下翻译的实现——递归下降翻译

仍将递归下降法进行一定扩展，做法是编写子程序的时候传入属性作为参数：

• 继承属性：传入属性的值（赋值形参）
• 综合属性：传入属性的地址（变量形参）

对于规则 \(U_{\downarrow x, \uparrow y}\)，编写子程序：

Procedure U(x, y);
// x: 赋值形参(值)
// y: 变量形参(地址)

具体实现过程暂时小摸一下~