SDTS（Syntax-Directed Translation Schema）是一种将源程序翻译为目标代码或执行特定操作的形式化方法。作为SDD的补充，SDTS通过将程序片段嵌入上下文无关文法，使程序员能够直观理解语义规则的执行时机与顺序。通常，所有SDD均可通过简单规则转换为SDTS实现。  

        嵌入产生式中的程序片段称为语义动作（Semantic Action），约定使用大括号（{}）包裹，可置于产生式体的任意位置。需注意的是，语法分析程序遇到语义动作时会立即执行，其位置直接影响翻译结果，因此文法设计中必须仔细斟酌每个语义动作的位置。例如：  

1. 产生式S -> S1 '-' F {System.out.println("-")}：当符号F匹配成功后，立即执行括号内的打印动作。  
2. 产生式S ->{System.out.println("-")} S1 '-' F：S对应的方法开始执行时，即在方法入口处执行打印动作。  

        可见，语义动作的位置差异会导致最终结果不同。

        在为SDTS构建语法分析树的时候，可以将语义动作视为一个终结符号，并应为其构建一个对应的子节点。仍然以产生式“S -> S1 '-' F {System.out.println("-")}”为例，其对应的语法分析树如图 7.21-a所示。采用自顶向下语法分析算法的话，需要对文法进行转换以消除左递归。针对产生式S，转换后的文法会引入一个名为R的非终结符，其产生式为“R -> '-' F {System.out.println("-")} R1”，对应的语法分析树如图 7.21-b所示。可以看到，由于我们将语义动作视为一个终结符号，即使文法格式产生了变化，它所在的位置仍然保持在F之后。值得注意的是，这一原则（将语义动作视为终结符号）仅适用于某些无副作用语义动作的场景，比如案例中的打印动作。而对于复杂的计算、修改符号表、生成中间代码、属性值传递等这类可产生副作用的动作，这一原则可能是不适用的。

图 7.21 将语义动作视为语法分析树中的节点

        接下来，让我们看一下如何通过SDTS来描述减法表达式所对应的翻译方案，文法如SDTS 7-1所示：

SDTS 7-1

S -> S1 '-' F {addToOutputCache('-')}
S -> F
F -> 'integer' {addToOutputCache(integer.lexeme)}

        语义动作addToOutputCache()用于将终结符的属性值加入到输出对象列表之中。由于文法存在左递归，不能直接使用自顶向下的分析方式，因此需要对其进行转换，转换后的结果如STDS 7-2所示：

STDS 7-2

S -> F R
R -> '-' F {addToOutputCache('-')} R1 | ε
F -> 'integer' {addToOutputCache(integer.lexeme)}

        可以看到，由于语义动作不涉及到属性值的计算，因为被当成了终结符号处理。针对上述文法，代码7-28展示了递归下降语法分析器的实现方式：

代码7-28

class SubtractionParser {
    List<String> outputCache= new ArrayList<>();

    //S -> F R
    void s() {
        lookahead = next();
        f();
        r();
    }

    //R -> '-' F {addToOutputCache('-')} R1 | ε
    void r() {
        if (this.lookahead.type == TokenType.MINUS) {
            matchAndMove(TokenType.MINUS);
            f();
            this.addToOutputCache("-");
            r();
        }
    }

    //F -> 'integer' {addToOutputCache(integer.lexeme)}
    void f() {
        Token current = this.lookahead;
        matchAndMove(TokenType.DIGIT);
        this.addToOutputCache(current.lexeme);
    }

    void addToOutputCache(String symbol) {
        this.outputCache.add(symbol);
    }
}

        通过对比可知，代码7-28的实现逻辑与STDS 7-2的描述完全一致。关于语义动作的实现，由于笔者采用Java语言开发语法分析器，因此语义动作自然由Java代码片段构成。通常情况下，使用与语法分析器相同的编程语言实现语义动作最为便捷高效，但这并非强制要求。开发者可根据实际需求选择不同类型的语言（如JavaScript、Python等），某些场景下可能更具优势。当然，这种选择会增加接口复杂度与调试难度，需结合具体情况权衡利弊，选取最优方案。

        回到代码7-28中。由于我们将语义动作视为了终结符，对文法进行转换后，它的位置仍然保持不变。当对表达式“5-2-1”进行语法分析的时候，程序最终的输出结果为：[5, 2, -, 1, -]，是示例表达式“5-2-1”的后缀形式，又称作逆波兰式（Reverse Polish Notation，RPN）。上述案例只是对表达式中的元素进行了打印，如果想要执行计算的话，了解数据结构的读者一定会发出会心的一笑。很多计算器和编译器内部都采用了RPN的方法来计算四则运算表达式的值，即便表达式中包含有括号这种复杂的情况。有关这一方面的知识，您可以找一些专门的资料进行了解，笔者不在此进行过多地说明。

        通过前文可知：SDD分为S属性的和L属性的两类，其中S属性的SDD需要使用自底向上的语法分析方式。这种情况下，应当将语义动作放到产生式的最后面，我们称这样的分析方式为后缀翻译方案，如SDTS 7-1。后缀翻译方案适合自底向上的语法分析方式，不过这并非本书的重点，因此我们不作过多的说明。

        实践当中，在不考虑使用语法分析器生成器的前提之下，自顶向下语法分析方式使用得最为广泛。更进一步，不包含回溯且向前看字符数量为1的递归下降语法分析算法使用频率最高。这就意味着L属性的SDD将会比较常见，那么如何将L属性的SDD转换成SDTS呢？读者可参考如下两项规则：

1. 将非终结符A的继承属性的动作插入到A的左侧。
2. 将产生式头的综合属性的动作放置到产生式的最右侧。

        以SDD 7-3为例，按上述规则所得到的翻译方案如SDTS 7-3所示：

SDTS 7-3

p1) S -> F { R.inh = F.val } R { S.val = R.syn }
p2) R -> '-' F { R1.inh = R.inh - F.val } R1 { R.syn = R1.syn }
p3) R -> ε { R.syn = R.inh }
p4) F -> integer { F.val = integer.lexeme }

        读者可将SDD 7-3和SDTS 7-3进行一下对比。它们指向的其实是同一个文法，但后者明显更具指导性。以第一条产生式p1为例，调用R符号所对应的方法r()之前，需要首先执行语义动作{R.inh = F.val}。按照规则，这一动作的含义是将f()方法的返回值做为参数传入到r()方法中。同样还是p1产生式，r()方法执行完毕后还需要执行另外一个语义动作{S.val = R.syn}。按照规则，该动作的含义是将r()方法的返回值作为s()方法的返回值。通过对比可发现，语法分析器代码的实现逻辑与SDTS 7-3的描述完全一致，这也是为什么笔者会说SDTS是SDD的补充。

        关于何时使用SDD与SDTS，很难给出普适性结论。根据实践经验，多数场景下SDD已能满足日常需求，因其通过属性依赖关系定义语义规则，适合描述静态翻译逻辑。然而，这并不意味着无需掌握SDTS：当使用语法分析器生成器时，常需编写语义动作，此时SDTS将语义规则与文法产生式直接绑定的特性更为实用；对于复杂语义需求，尤其是语义动作包含过程性逻辑时，SDTS通过明确动作执行顺序所提供的指导性更为显著。因此，建议读者在实践中优先通过SDD定义语义规则，再根据具体需求判断是否需要借助SDTS进一步细化执行逻辑。

上一章  下一章