【从零开始学习计算机科学】编译原理（五）语法制导翻译

语法制导翻译

语法表述的是语言的形式，或者说是语言的样子和结构。而程序设计语言中另一方面，是附着在语言结构上的语义；语义揭示了程序本身的涵义、施加于语言结构上的限制、要执行的动作。

语法制导翻译就是如何在语法上绑定语义。语法制导翻译是目前最常用的语义分析技术，具体包括两种标记方法：语法制导定义(Syntax-directed definitions)SDD和语法制导的翻译方案(Syntax-directed translation scheme)SDT。

语法制导定义SDD

语法制导翻译的基本思想是在上下文无关文法的基础上，将语言结构的语义以属性的形式赋予代表此结构的文法符号。其属性的计算以语义规则的形式赋予由文法符号组成的产生式。属性可以代表任何对象：字符串、数字、内存单元或其它对象。

例如，对于文法:

E $\to$ $E_1$+T

E $\to$ T

T $\to$ F

F $\to$ digit

假设F.val、T.val、E.val分别为文法符号F、T、E的属性值。digit.lexval为文法符号digit的属性：当digit为常数时，digit.lexval为在常数表中的入口，当digit为标识符时，digit.lexval为在符号表中的入口

语义规则用来计算与产生式中出现的文法符号相关联的属性的值。在一个语法制导定义中，语法规则中的任一条产生式$A\to \alpha$，都有与之相关联的一套语义规则。比如：

E $\to$ $E_1$+T , E.val := $E_1$.val + T.val

E $\to$ T , E.val := T.val

T $\to$ F , T.val := F.val

F $\to$ digit , F.val := digit.lexval

为每一个产生式配上语义规则并且在适当的时候执行。即，当归约或推导到某个产生式时，除了按照产生式进行相应的代换之外(语法分析)，还要按照所对应的语义规则执行操作，如计算表达式、查填符号表、产生中间代码。

语法树结点N上的非终结符号A的属性可分为两种：

综合属性：只能通过N的子节点或N本身的属性值（一个节点可有多个属性）来定义。语法规则中等号的左边必然为产生式头部。

继承属性：只能通过N的父节点、N本身和N的兄弟结点上的属性值来定义。

在语法分析树中为每个文法符号上加上它们的属性，则称为带注释的语法分析树，简称注释语法分析树。

SDD的求值顺序

对于同时具有继承属性和综合属性的SDD，不能保证有一个顺序来对所有节点上的属性进行求值。例如产生式 A → B A \to B