语法制导翻译——语法制导翻译方案

语法制导的翻译方案

语法制导的翻译方案（Syntax-directed translation scheme, SDT），简称翻译方案，是用来实现语法制导定义的常见方法，其通过在产生式中嵌入程序片段（称为语义动作）来进行翻译。任何一个SDT都可以通过先生成含有程序片段（把程序片段作为树的叶子节点）的语法分析树，然后前序遍历并执行遍历到的程序来实现。当然，我们一般并不显式地构造语法分析树，因此我们着重关注两类可以在翻译过程中直接执行的SDT，这些SDT和SDD密切相关：

基本文法（即不包括任何SDD或SDT的文法）可以用LR技术分析，且SDD是S-属性的；
基本文法可以用LL技术分析，且SDD是L-属性的。

我们将介绍在这两种情况下如何把SDD转化成SDT，并在语法分析中直接执行，通常是在语义动作左侧的符号匹配后立刻执行。我们可以用一种简单的方法判断SDT是否可以在某种语法分析中执行：为每一个语义动作生成一个特殊的非终结符号$M$，其产生式只有$M \to \epsilon$，然后用这个终结符号替换语义动作。如果新的文法可以用原来的语法分析技术识别，那么这个SDT就可以在这种语法分析中实现。

后缀翻译方案

我们将研究一种特殊的翻译方案：后缀翻译方案。这种翻译方案的特点是所有语义动作都在产生式体最右侧。

一个S-属性的SDD在使用LR技术分析时就会生成这种翻译方案，此时所有语义动作都会在发生规约时执行。为了在LR分析时实现这种翻译方案，我们必须在语法符号栈（状态栈）中引入更多的信息来储存属性。对于简单的属性，我们可以直接把它放到栈中，但对于更复杂的属性，可能不得不用指针代替具体的值。

在进行LR分析时，栈中的元素一定是已经被语法分析器处理过的，因此它们的属性值都是已知的，我们可以直接用相对栈顶的位置来得到每个符号的属性值。下面的例子说明了如何利用额外的栈计算每个文法符号的属性值。 $\begin{aligned} L &\to E \mathbf{n} &\{ \text{print(stack[top-1].val); top = top-1} \} \\ E &\to E_1 + T &\{ \text{stack[top-2].val = stack[top-2].val+stack[top].val; top=top-2} \} \\ E &\to T &\{ \} \\ T &\to T_1 * F &\{ \text{stack[top-2].val = stack[top-2].val*stack[top].val; top=top-2} \} \\ T &\to F &\{ \} \\ F &\to (E) &\{ stack[top-2].val = stack[top-1].val; top=top-2 \} \\ F &\to \mathbf{digit} &\{ \} \\ \end{aligned}$ 正如上文所述，值得注意的是有几个产生式附加的语义动作为空，这是因为它们的产生式头的属性直接继承了式体的属性。

内部带有语义动作的翻译方案

虽然后缀翻译方案很容易在LR分析中实现，我们还是需要关心那些产生式中带有语义动作的翻译方案。根据定义，在语义动作右侧的文法符号被识别到（如果是终结符，就是识别到本身，如果是非终结符，就是识别到可以由它推导出的终结符号串）后，立刻执行。假设产生式为$B \to X { a } Y$，其中${a}$为语义动作。如果语法分析是自顶向下的，那么我们在试图展开$Y$之前（如果是非终结符）或是识别到$Y$之前（如果是终结符）执行语义动作；而如果语法分析是自底向上的，那么我们在$X$出现在栈顶时执行语义动作。

需要注意，尽管所有SDT都可以通过先忽略语义动作并构造语法分析树，然后在语法分析树中插入语义动作，最后前序遍历并执行来实现，我们更关心那些可以一边翻译一边执行而不用生成语法分析树的SDT。可惜的是，并非所有SDT都可以这样执行。考虑下面这个SDT： $\begin{aligned} L &\to E \mathbf{n} & \\ E &\to \text{\{print('+')\}} E_1 + T \\ E &\to T \\ T &\to \text{\{print('*')\}} T_1 * F \\ T &\to F \\ F &\to (E) \\ F &\to \mathbf{digit} \text{\{print(digit.val)\}} \end{aligned}$ 这个SDT就不能在自顶向下或自底向上语法分析中执行，因为语法分析器在还没有确定使用哪个产生式之前就被要求打印运算符号。如果我们用上面介绍过的判定规则把所有语义动作都用产生空串的非终结符替代，那么对一个LR分析器，它就会在处理单个数字的输入时陷入移入/规约冲突。

消除左递归

如果我们要使用LL语法分析方法进行语法分析，那么就需要消除这个文法中的左递归。然而，消除左递归会导致原文法的结构被破坏，进而影响SDT的执行顺序。

如果我们只关心SDT中动作执行的顺序，而不要求动作求出正确的值，比如要求按顺序打印某些字符，那么这种转换还是相当简单的。我们只需要把语义动作当作一个终结符号即可。

考虑下面这个左递归文法： $\begin{aligned} E \quad &\to \quad E_1 + T \; \text{\{ print('+') \}} \\ E \quad &\to \quad T \end{aligned}$ 回忆一下，对立即左递归$A \to A \alpha \vert \beta$，我们创建一个新的非终结符号$R \to \alpha R \vert \epsilon$，并把其产生式替换为$A \to \beta R$。对上述文法，我们把语义动作视为非终结符号，然后直接用这个算法进行替换，即可得到： $\begin{aligned} E \quad & \to \quad T R \\ R \quad & \to \quad + T \; \text{ \{ print('+') \} } \; R \\ R \quad & \to \quad \epsilon \\ \end{aligned}$

然而，如果SDT中执行的动作不仅需要以正确的顺序执行，还要求出正确的属性值，那么我们就不得不仔细考虑如何修改这些语义动作的顺序。对S属性的SDD，我们总是可以通过将计算属性值的动作放在新产生式的适当的位置来构造出SDT。

我们只考虑单个递归产生式，单个非递归产生式，单个属性的情况。考虑以下SDT： $\begin{aligned} A \quad &\to \quad A_1 + Y \; \text{\{ A.a = g(A_1.a, Y.y) \}} \\ A \quad &\to \quad X \; \text{\{ A.a = f(X.x) \}} \end{aligned}$

我们知道，所谓左递归的消除，就是把语法树的左子树转换成右子树，因此，为了保证信息在不同子树之间的流通，我们需要引入继承属性。除此之外，左子树的信息必须被传递到右子树的底部，然后通过一个综合属性返还给根节点。对于消除左递归后的文法，其在使用产生式$ R \to \epsilon $时标志了递归的终止，因此我们在此节点的语义动作上把继承属性传递给综合属性，然后返还给根节点。这个继承属性需要收集所有左子树的信息以便进行计算。应用这些思想，我们可以设计出这个消除了左递归的文法： $\begin{aligned} A \quad &\to \quad X \; \text{\{ R.i = f(X.x) \}} \; R \; \text{\{ A.a = R.s \}} \\ R \quad &\to \quad Y \; \text{\{ R_1.i = g(R.i, Y.y)\}} \; R_1 \; \text{\{ R.s = R_1.s \}} \\ R \quad &\to \quad \epsilon \; \text{\{ R.s = R.i \}} \end{aligned}$ 正如我们描述的那样，在运用$A \to X R$这一产生式时，我们把$X$的属性传递到$R$上。然后，在运用$R \to Y R$这一产生式时，把$Y$和$R$的属性和收集到$R_1$上。最后，在运用$R \to \epsilon$这一产生式时，把继承属性传给综合属性，并逐步回传给$A$。

为L属性SDD构造翻译方案

在本节中，我们将介绍如何为L-属性的SDD构造翻译方案，但先不介绍如何实现它。始终记得，对任何翻译方案，我们都可以先构造语法分析树，再执行语义动作。在后面的章节中，我们将仔细介绍如何不经过语法分析树而在语法分析时直接执行语义动作。

为L属性的SDD构造翻译方案相当简单，只需要对产生式体的继承属性和产生式头的综合属性分别处理即可：

将决定产生式头的综合属性的语义动作放在产生式右侧；
将决定式体的文法符号的继承属性的语义动作放在紧邻这个文法符号的左侧，注意小心继承属性的依赖关系。

我们以生成while语句的产生式$S \to \mathbf{while} S_1$为例介绍如何构造翻译方案。首先，我们明确其SDD：

L1 = new_label();
L2 = new_label();
S1.next = L1;
C.false = S.next;
C.true = L2;
S.code = "label " + L1 + " " + C.code + " label " + L2 + " " + S1.code;

简单介绍一下这些属性：

new_label()生成一个新的标号；
继承属性S.next是在$S$之后执行的代码的开始处的标号，根据继承属性的定义，其计算规则不仅由这个产生式给出。
继承属性C.true和C.false分别表示条件为真或假时跳转到的标号。
综合属性C.code是表达式的中间代码，我们也要求其含有跳转至C.true和C.false的指令。
综合属性S.code表示生成的中间代码。特别地，我们要求对所有结点，其生成的代码执行完后应跳转至S.next。我们注意到C.code中已经含有这一条指令，因此不再对S额外生成它了。

按照上面的规则，其翻译方案如下： $\begin{aligned} S \to &\mathbf{while} ( &\{ \text{L1 = new_label(); L2 = new_label(); C.false = S.next; C.true = L2;} \} \\ &C) &\{ \text{S1.next = L1;} \} \\ &S_1 &\{ \text{S.code = ...} \} \end{aligned}$ L1和L2不是属性，因此其原则上可以放在任何位置。考虑到依赖关系等，我们决定把它们放在第一个语义动作之前。理论上说我们当然可以把它们放在最左边，但是这会给语法分析造成诸多不利，因此我们选择尽可能地拖延以方便语法分析器在执行语义动作前获取更多的信息。

实现L属性的SDD

我们知道，通过构造语法分析树并用属性依赖的拓扑序遍历，可以实现任意（无环）的SDD。为了实现L属性的SDD，我们可以构造翻译方案，因为对翻译方案，我们甚至不需要以拓扑序遍历，只要以先序遍历并在遍历时执行语义动作即可实现。但是我们还是更加关心不需要构造语法分析树即可进行翻译的方法。

在这一节中，我们将介绍三种边分析边计算的方法：

与递归下降分析器结合，要么利用SDD通过函数计算结点的属性，要么通过SDT直接生成中间代码；
与LL分析器结合，实现一个SDT；
与LR分析器结合，实现一个SDT。

在文章开头，我们说我们特别关心“基本文法可以用LL技术分析，且SDD是L-属性的”。这或许会让人迷惑，因为可以用LL技术分析（即文法是LL(1)的）通常代表使用自顶向下的分析器；然而，我们将看到，如果文法是LL的，即使使用自底向上的分析器也可以正确执行。

递归下降的分析

本节中我们将介绍两个在递归下降分析中实现SDD的方法。

基于函数返回值的方法

我们此前介绍了基于递归下降的分析方法。这种分析法有一个特征，即所有非终结符号都有一个对应的函数。我们只需要修改这个函数使其支持属性值的计算即可。

我们要求，新的函数必须返回该非终结符号的综合属性，并以其继承属性作为参数。这个函数原来包括几步：

决定用哪一个产生式来展开这个非终结符号，如果需要回溯，则枚举可能的产生式；
需要读入一个非终结符号时，检查输入中是否有这个符号，如果没有，则报错或进行回溯；
需要读入一个终结符号时，调用对应终结符号的函数。

现在，我们只需要在其中加入属性值的计算即可。我们用局部变量保存所有需要的属性值，用来计算产生式体非终结符号的继承属性或产生式头（即自己）的综合属性。在调用终结符号的函数时，我们需要将其所有继承属性作为参数带入函数之中。如果这个文法是L属性的，那么此时其所有继承属性一定都已经完成计算了，因此不会发生错误。

下面这个代码就是用来处理上文中所提的while语句的。

std::string S(label next)
{
    std::string Scode, Ccode;
    label L1, L2;

    if(lexer.next_token() == WHILE)
    {
        lexer.consume_token();
        if(lexer.next_token() != LEFT_PAREN)
            throw UnexpectedToken();
        lexer.consume_token();

        L1 = new_label(), L2 = new_label();
        Ccode = C(next, L2);

        if(lexer.next_token() != RIGHT_PAREN)
            throw UnexpectedToken();
        lexer.consume_token();

        Scode = S(L1);
        return "label " + L1 + " " + Ccode + " label " + L2 + " " + Scode;
    }
    else 
        ;/* ...... */
}

边扫描边生成的方法

在上一个例子中，我们直接使用字符串作为返回值，这会导致大量的复制或移动，从而使程序效率低下。尽管我们可以用指向字符串的指针代替字符串而降低时间花费，这又会导致一些新的问题。接下来，我们将介绍直接一边扫描一边生成结果的方法，其原理实际上和上文所述的基于返回值的方法相差无几。

如果要一边扫描一边生成结果，那么SDT需要满足以下要求：

存在一个主属性，这个属性必须是综合属性，出于方便起见，我们规定其类型为字符串。
对其的求值满足以下要求：
1. 主属性是通过将各种要素依次连接起来得到的；
2. 连接时，各个非终结符号的属性值在运算中出现的顺序和其在产生式体中出现的顺序相同。

如果主属性满足以上要求，那么对于根节点，其值就可以增量地构造出来。这个主属性的要求几乎是为中间代码量身定制的。继续上文的例子，我们仅需稍稍修改一下函数即可：

void S(label next)
{
    label L1, L2;

    if(lexer.next_token() == WHILE)
    {
        lexer.consume_token();
        if(lexer.next_token() != LEFT_PAREN)
            throw UnexpectedToken();
        lexer.consume_token();

        L1 = new_label(), L2 = new_label();
        std::cout << "label " << L1 << " " ;
        C(next, L2);

        if(lexer.next_token() != RIGHT_PAREN)
            throw UnexpectedToken();
        lexer.consume_token();

        std::cout << "label " << L2 << " " ;
        Scode = S(L1);
    }
    else 
        ;/* ...... */
}

我们现在要求每个函数都直接把它的中间代码打印出来，这样就可以直接输出所有中间代码了。

LL语法分析

我们为LL语法分析栈中引入两个新的元素，用来实现SDT：

动作记录：当这个记录位于栈顶时，执行一些语义动作，然后直接弹出它；
综合记录：保存文法符号的综合属性。

然后我们用以下规定来管理这文法符号的属性：

非终结符号的继承属性直接放在其栈记录中，对这些属性求值的动作保存在其上方（靠近栈顶）的动作记录中；
非终结符号的综合属性放在其下方（靠近栈底）的综合记录中。

实际上，综合记录几乎不可能单独出现，而总是伴随着一些动作，因为我们需要把计算出的综合属性保存到栈的更低的位置，否则就浪费了。综合记录下面往往紧挨着一个动作记录，这个动作记录负责从产生式体的属性产生产生式头的综合属性，因此我们可以把综合记录看作特殊的动作记录，这样当综合记录位于栈顶时，也执行附加的语义动作，然后直接弹出栈。除此之外，综合记录还可能需要保存计算其父节点的综合属性所需的其他文法符号的属性，因为当综合记录位于栈顶时，其依赖的文法符号很可能已经弹出栈了; 相对地，动作属性也可能需要保存一些属性值或者局部变量以用于自己的动作。

我们考虑在LL语法分析时用产生式$A \to B C$进行展开，此时栈顶为$A$，它被弹出栈，然后依次压入$C$和$B$，现在$B$位于栈顶。因为SDD是L属性的，此时$A$的所有继承属性都已经计算出来了，而其综合属性放在综合记录中，在$C$的下方。然而，我们假设$C$的某个继承属性依赖于$A$的继承属性，如果直接把$A$的记录弹出栈，这些属性就丢失了。为了解决这个问题，我们不得不在$A$被弹出栈时，把自己的继承属性复制到用来计算$C$的继承属性的动作记录里面。幸运的是，在决定用哪个产生式展开后，栈上记录的相对位置都确定了，因此这样的复制不会发生问题。

总结一下，当我们使用某个产生式展开时，会进行下面的操作：

构造新的栈中的元素，按照从栈顶（产生式体左边）到栈底（产生式体右边）的顺序：
- 为所有语义动作构造动作属性，并把它放在和翻译方案匹配的位置；
- 如果文法符号有综合属性，那么构造综合记录并把它放到文法符号下面；
- 如果其有继承属性，则放在栈中和文法符号相同的位置。
- 有些时候可以简化一些动作，以避免多余的复制；出于简洁，还可以把继承记录和紧邻的动作记录合并。
把产生式头的继承属性复制到需要的地方，然后把它弹出栈，把新构造的栈压入栈中。
检查现在的栈顶：
- 如果是文法符号，那么进行正常的语法分析；
- 如果是动作记录，那么执行动作并把它弹出栈；
- 如果是综合记录，那么执行动作（如果有）并把它弹出栈。
- 如果出栈的记录（无论是文法符号还是各种记录）中含有的属性被后面的符号依赖，那么复制这个属性。

我们考虑下面这个SDT： $\begin{aligned} S \to &\mathbf{while} ( &\{ \text{L1 = new_label(); L2 = new_label(); C.false = S.next; C.true = L2;} \} \\ &C) &\{ \text{S1.next = L1;} \} \\ &S_1 &\{ \text{S.code = ...} \} \end{aligned}$ 当使用这个产生式展开时，栈中应该是这样的：S SYN.S ... $，其中SYN.S表示S的综合记录。然后我们为这个产生式构造栈，首先插入动作记录：

while ( ACT1 C ) ACT2 S1 ACT3

然后插入综合记录：

while ( ACT1 C SYN.C ) ACT2 S1 SYN.S1 ACT3

现在我们考虑一下各种动作记录中应该填什么。第一个动作，对应语义动作$\text{L1 = new_label(); L2 = new_label(); C.false = S.next; C.true = L2;}$。这个动作依赖$S.next$，因此我们需要在S出栈时把它复制到这个记录来，假设此时其位于Snext中。除此之外，我们还注意到有些计算需要在此处构造的两个标签L1和L2，因此我们也要复制它们。那么动作可写为：

L1 = new_label();
L2 = new_label();
stack[top-1].true = L2;
stack[top-1].false = Snext;
stack[top-4].l1 = L1;
stack[top-7].l1 = L1;
stack[top-7].l2 = L2;

然后考虑第二个动作，对应语义动作$\text{S1.next = L1;}$：

stack[top-1].next = l1;

再考虑最后一个动作，此时我们需要计算SYN.S中的中间代码，此时这个综合记录必然位于动作记录下方，即top-1的位置。此属性依赖于SYN.S1和SYN.C中的综合属性code，还依赖于两个标签L1和L2，我们假设它们都被复制到这个动作记录里了。

stack[top-1].code = "label " + l1 + " " + Ccode + " label " + l2 + " " + S1code;

对SYN.C，我们也需要进行复制，因此其也有动作：

stack[top-5].Ccode = code;

对SYN.S1同理。然后我们把S弹出栈，并把其继承属性复制到ACT1.Snext中。

上面这个方案足以实现这个SDT了，但是其中还包括了许多多余的复制等。比如我们可以直接把S.next复制到C.false中，而不用经过ACT1；如果我们把ACT3和SYN.S1合并，那么S1.code也不需要再复制一遍。

LR语法分析

虽然我们说通常用LR语法分析处理S-属性的SDD、用LL语法分析处理L-属性的SDD，我们还是要提出一种方法，用来在自底向上语法分析中处理L属性的SDD。虽然分析方法是自底向上的，我们仍然要求基础文法是LL的。

我们用以下几步用LR语法分析技术实现L-属性的SDD：

首先用上文所述的方法构造SDT，即把继承属性对应的语义动作放在文法符号右侧，综合属性放在左侧；
对每个语义动作，用一个独特的、仅能产生空串的非终结符号替代它，比如$A \to \alpha { a } \beta$就被替换成$A \to \alpha M \beta$，其中$M \to \epsilon$。
对每个由语义动作$a$产生的产生式$M \to \epsilon$，为它关联一个新的语义动作，使其在利用这个产生式规约时执行这个动作：
1. 首先把$A$或$\alpha$中所有需要的继承属性像$M$的继承属性一样复制到$M$上；
2. 按照语义动作中的操作计算所有属性，把它们都当作$M$的综合属性。

我们要求，所有文法符号的继承属性恰好位于其下方（更靠近栈底）的文法符号上，而其综合属性和文法符号在栈中的同一位置，这一约定恰好和LL语法分析相反，但对LR语法分析不存在单独的“继承记录”。

比如，对翻译方案$A \to \{B.i = f(A.i)\} B C$，我们把这个产生式替换为$A \to M B C$。然后，为$M$附加语义动作：$M \to \{ M.i = A.i;\; M.s = f(M.i) \}$。 $M$只生成空串，因此只有语义动作。我们必须先复制$A.i$再使用它，否则$M.s$就不满足综合属性的定义了。原则上，我们没有办法直接得到$A.i$的值，但我们可以通过安排分析栈来使得进行规约时所有$A$的继承属性都恰好位于原来$A$所在位置下方。

我们继续考虑SDT： $\begin{aligned} S \to &\mathbf{while} ( &\{ \text{L1 = new_label(); L2 = new_label(); C.false = S.next; C.true = L2;} \} \\ &C) &\{ \text{S1.next = L1;} \} \\ &S_1 &\{ \text{S.code = ...} \} \end{aligned}$ 它可以转化成： $S \to \mathbf{while} ( M C ) N S_1 \quad M \to \epsilon \quad N \to \epsilon$ 我们没有转化最末尾的那个语义动作，因为它可以和这个产生式本身关联，从而在规约时执行。首先，我们（归纳地）假设S的继承属性next位于其正下方某个未知的文法符号上：

$   ?       S
    S.next

当我们决定用产生式$M \to \epsilon$规约时，栈中的内容如下：

$   ?       while   (   M
    S.next              C.true, C.false, L1, L2

然后我们用这个产生式关联的语义动作计算这些值：

L1 = new_label();
L2 = new_label();
C.true = L2;
C.false = stack[top-3].next

因为栈中的相对位置总是能根据产生式确定，我们可以直接用下标访问这个属性。然后继续进行语法分析，直到栈顶为$C$：

$   ?       while   (   M                   C
    S.next              C.true, C.false     C.code
                        L1, L2

不难发现，C的继承属性恰好位于其下方的文法符号M上，这满足我们的归纳假设。最后我们需要规约为S时，栈为：

$   ?   while   (   M   C   )   N   S1

此时我们执行代码：

tempCode = ...
top = top - 6;
stack[top].code = tempCode;

然后栈变为$ ? S 注意我们先计算属性的值，再把它们弹出栈。

需要注意的是，实际上在LR语法分析中，在栈中储存的是状态而非文法符号，但相应的思路是相同的。

Twitter Facebook LinkedIn