2 翻译方案

翻译方案（SDT, syntax-directed translation scheme）和语法制导定义的区别在于，其语义动作（在此不叫语义规则）不是放在表里，而是插在各文法符号之前或之后的（放在花括号之中）。

通常情况下，SDT 是随着语法分析过程而实现的，不会真的构造一棵语法分析树。

主要有两类：

• 基本文法是 LR 的，SDD 是 S 属性的
• 基本文法是 LL 的，SDD 是 L 属性的

后缀翻译方案

基本文法是 LR 的，SDD 是 S 属性的，简单

每个动作都在产生式的最后，这些动作可以和语法分析器的归约步骤一起执行。

显式地看看栈操作：

产生式内部带有语义动作的 SDT

当一个动作左边的所有符号都被处理过后，该动作立刻执行。

如 $B→X\{a\}Y$

• 如果是 LR 分析，则当 X 出现在语法分析栈顶的时候立刻执行动作 $a$
• 如果是 LL 分析，则当在处理 Y 之前执行动作 $a$

任何 SDT 都可以按照如下方法实现：

从 SDT 中消除左递归

LL 分析不能处理左递归文法，在 SDT 中，还要考虑动作是怎么处理的。

• 在转换左递归文法的时候，将动作当成新的终结符号处理。

案例

1. $A→A_1Y\quad \{A.a=A_1.a+Y.y\}$
2. $A→X\quad \{A.a=X.x\}$

假设这里都是综合属性，则这个基础文法被改成

1. $A→XR$
2. $R→YR|\epsilon$

需要对 $R$ 引入继承属性 $R.i$ 来累计从 $A.a$ 一直到 $X.x$ 的结果。

上面没有显示 R.s，当 R 不再生成 Y 时，才开始计算 R.s（自底向上，沿着树向上拷贝）

SDT：

1. $A→X\quad\{R.i=X.x\}\quad R\quad\{A.a=R.s\}$
2. $R→Y\quad \{R_1.i=R.i+Y.y\}\quad R_1\quad \{R.s=R_1.s\}$
3. $R→\epsilon\quad\{R.s=R.i\}$

L 属性定义的 SDT

• S 属性定义的 SDD 转换成后缀 SDT，只要基础文法是 LR 的，后缀 SDT 就可以按照自底向上的方式进行语法分析和翻译
• 现在来考虑 S 属性的 SDD，假设基础文法是 LL 语法分析的，否则翻译过程无法和语法分析一起完成
• 只需要将动作附加到一棵语法分析树中，并对这棵树进行前序遍历时执行这些动作

把一个 L 属性 SDD 转换为一个 SDT 的规则：

（设 $A$ 是非终结符，具有继承属性）

1. 计算 $A.i$ 的动作插入到产生式右部紧靠在 $A$ 之前的位置（多个继承属性以拓扑排序定求值顺序）
2. 计算产生式头部的综合属性的动作放在产生式体最右端

翻译的代码实现

方法

1. 非终结符 A 对应的函数 A 的参数是 A 的继承属性
2. 函数 A 的返回值是 A 的综合属性集合
3. 在函数 A 中，使用 lookahead(), match() 等函数进行操作

举例

拓广文法：

• $S'→S$
• $S→(L)$
• $S→a$
• $L→L,S$
• $L→S$

语法制导定义：

给 $S,L$ 继承属性 $i$ 表示左侧字符数，综合属性 $s$ 表示文法符号推出的字符串中最后一个字符在句子中是第几个字符。

产生式	语法制导定义
$S'→S$	$S.i=0$
$S→(L)$	$L.i=S.i+1;\quad S.s=L.s+1$
$S→a$	$S.s=S.i+1\quad print(S.s)$
$L→L_1,S$	$L_1.i=L.i\quad S.i=L_1.s+1\quad L.s=S.s$
$L→S$	$L.s=S.s\quad S.i=L.i$

翻译方案：

• $S'→\{S.i=0;\}S$
• $S→(\{L.i=S.i+1;\}L)\{S.s=L.s+1;\}$
• $S→a\{S.s=S.i+1;print(S.s);\}$
• $L→\{L_1.i=L.i;\}L_1,\{S.i=L_1.s+1;\}S\{L.s=S.s;\}$
• $L→\{S.i=L.i;\}S\{L.s=S.s;\}$

消除左递归：

• $S'→S$
• $S→(L)$
• $S→a$
• $L→SL'$
• $L'→,SL'$
• $L'→\varepsilon$

消除左递归后的语法制导定义：

产生式	语法制导定义
$S'→S$	$S.i = 0$
$S→(L)$	$L.i = S.i +1\quad S.s = L.s + 1$
$S→a$	$S.s = S.i + 1\quad print(S.s)$
$L→SL'$	$S.i=L.i\quad L'.i = S.s\quad L.s = L'.s$
$L'→,SL'_1$	$L'_1.i=S.s\quad L'.s=L'_1.s\quad S.i=L'.i+1$
$L'→\varepsilon$	$L'.s=L'.i$

预测翻译器：

void S_prime() {
    S(0);
} 

int S(int S_i) {
    if (lookahead == 'a') {
        match('a');
        int S_s = S_i + 1;
        print(S_s);
        return S_s;
    }
    else if (lookahead == '(') {
        match('(');
        int L_s = L(S_i + 1);
        match(')');
        return L_s + 1;
    }
    else error(); 
}

int L(int L_i) {
    int S_i = L_i;
    int S_s = S(S_i);
    int L_prime_i = S_s;
    int L_prime_s = L_prime(L_prime_i);
    return L_prime_s;
}

int L_prime(int L_prime_i) {
    if (lookahead == ',') {
        match(',');
        int S_i = L_prime_i + 1;
        int S_s = S(S_i);
        int L_prime_1_i = S_s;
        int L_prime_1_s = L_prime(L_prime_1_i);
        return L_prime_1_s;
    }
    else {
        return L_prime_i;
    }
}

本文阅读量