在本节中，我们给出一种形式叫做语法导向的定义，用来指定对编程语言构造的翻译。一个语法导向的定义一种构造的翻译，用它语法成员的属性来定义。在后面的各章，语法导向的定义用来指定许多翻译，发生在一个编译器的前端。
我们也将介绍一种更加过程型的记法，叫做translation scheme，用来指定翻译。本章，我们使用translation scheme把中缀表达式翻译为后缀记法。更加的细节和它们的实现在第5章。
Postfix Notation
一个表达式E的postfix notation 后缀记法可以归纳定义如下：
- 如果E是一个变量或常量，那么E的后缀记法就是E自己
- 如果E是一个具有E1 op E2 形式的表达式，op是任何二元操作符，那么E的后缀记法是E1' E2' op，其中E1'和E2'分别是E1和E2的后缀记法
- 如果E是一个具有(E1)形式的表达式，那么E1的后缀记法就是E的后缀记法
后缀记法中不需要括号，因为操作符的位置和arity(参数的数目）只允许一种后缀表达式编码方式。例如(9-5)+2的后缀记法是95-2+而9-(5+2)的后缀记法是952+-。
Syntax-Directed Definitions
一个syntax-directed definition 使用一个上下文无关文法来指定输入的语法结构。对每一个文法符号，它关联一系列属性，以及对于每一个产生式，都有一套语义规则semantic rules来计算出现在该产生式中的符号的属性值。文法和语义规则集合组成语法导向定义。
一次翻译就是一次输入输出映射。每一个输入x的输出用下列方式指定。
首先，构造x的一棵解析树。假设解析树中一个节点n用文法符号X作为标签。我们写成X.a来表示该节点上X属性a的值。在n上X.a值的计算是通过在节点n使用的X-产生式相关的属性a的语义规则得到的。一棵解析树，每一个节点都显示属性值，我们称之为annotated parse tree.
Synthesized Attributes
如果一个节点的某一属性值是由该节点的子节点的属性值决定的，我们称之为synthesized合成的。合成属性具有一个很好的特性，就是它们能够通过一次自底向上的解析树遍历计算得到。本章只使用合成属性；“继承”属性在chap 5介绍。
Example 2.6 翻译一个由数字组成并由加减号分隔的表达式的后缀表达式的一个语法导向的定义如Fig. 2.5 所示。和每个非终结符相关是一个字符值属性t，它代表在一棵解析树中该非终结符生成的表达式的后缀记法。
| PRODUCTION | SEMANTIC RULE | |
|---|---|---|
| expr → expr1 + term | expr.t := expr1.t || term.t || '+' | |
| expr → expr1 - term | expr.t := expr1.t || term.t || '-' | |
| expr → term | expr.t = term.t | |
| term → 0 | term.t := '0' | |
| term → 1 | term.t := '1' | |
| .... | ... | |
| term → 9 | term.t = '9' |
Fig 2.5 syntax-directed definition for infix to postfix translation
一个数字的后缀表达式是它自己，例如，和产生式term→ 9相关的语义规则定义term.t 是9，无论何时这个产生式用在一个解析树中的节点。当产生式expr → term被应用的时候，term.t的值变成expr.t的值。
产生式expr → expr1 + term 派生一个表达式包含一个加号操作符(expr1中的下标区分右边和左边两个不同的expr实例).加法操作符左边的操作数由expr1和右边的操作数term给出。和这个产生式相关连的语义规则：
expr.t := expr1.t || term.t || '+'
连接epr1.t和term.t的后缀形式，再加上加号，这样定义了属性expr.t的值。语义规则中的||操作符代表字符串连接。
Fig 2.6包含了一个annoted解释树对应Fig 2.2的树。
Example 2.7 假设一个机器人可能被指令从它的当前位置向东、南、西、北移动一步。这样的一系列指令可以用下面的文法产生：
seq → seq instr | begin
instr → east | morth | west | south
输入序列
begin west south east east east north north
发生的机器人位置改变如Fig 2.7
在图中，一个位置是通过一对(x,y)标记的，其中x和y 代表从开始位置往东和北的步数
让我们构造一个语法导向的定义把指令序列翻译为一个机器人的位置。我们应该使用两个属性seq.x和seq.y，跟踪由非终结符seq生成的指令序列得到的结果位置。最初seq生成begin,seq.x和seq.y都是0，如所示在begin west south解析树最左边的内部节点。
位置的改变是由于从instr派生的单个指令找成的，我们给它们instr.dx和instr.dy属性。例如，如果instr派生west，那么instr.dx = -1，instr.dy = 0。假设一个序列是由一个序列seq加上一个新的指令instr组成的。那么robot的新位置是由下列规则给出的：
seq.x = seq1.x + instr.dx
seq.y = seq1.y + instr.dy
把指令序列翻译成机器人位置的语法导向的定义如Fig 2.9所示。
Depth-First Traversals
一个语法导向的定义并不对一棵解析树上属性的计算强加任何顺序；任何计算的顺序，只要它在计算a的属性前，计算好所有a依赖的属性，那么都是允许的。通常，在遍历解析树的时候，我们有时侯在某一个节点首次到达的时候必须计算某些属性，其它的则在它所有的子被访问以后，或者在访问节点的子节点之间的某个点。合适的计算顺序以后讨论。
本章的翻译都可以用固定的顺序、根据语义规则计算解析树的属性。一个树的遍历traversal从根节点开始，以某些顺序访问树中的每个节点。语义规则将通过Fig 2.10 定义的深度优先算法进行计算。
procedure visit(n:node)
begin
for each child m of n. from left to right do
visit(m);
evaluate semantic rules at node n
end
Fig 2.10 树的深度优先遍历
Fig2.11 演示这一过程，从root开始，按照从左到右的次序递归访问每一个节点的子
给定节点的语义规则在所有它的后代节点被访问才进行计算。之所以叫做深度优先是因为它尽可能首先访问一个节点的未被访问的子节点，因此它尝试访问可能的离根节点最远的节点。
Translation Schemes
本章剩下部分，我们使用一个过程型的规格定义一种翻译。一个translation scheme是一个上下文无关文法，其中叫做semantic action的程序片断嵌入到产生式的右边。一个translation scheme 就象一个语法导向定义，除了语义规则的计算顺序是显式展现出来的。
动作执行的点通过{}号表示，并且写在产生式右边的中间，例如：
rest → + term {print('+')} rest1
一个translation scheme 为每一个语句x生成输出，由底下的文法通过执行动作生成的，次序是它们在x解析树中的深度优先遍历顺序。例如，考虑一个解析树节点标为rest代表这个产生式。那么动作{print('+')}将在term子树被遍历但在rest1子树被访问前执行。
在为一个translation scheme画出一棵解析树时，我们把动作作为一个额外的子节点，通过一条虚线和它产生式的节点相连。例如，上述产生式的解析树部分和动作显示在Fig 2.12。一个语义动作节点没有子节点，所以访问到该节点的时候动作将被执行。
Emitting a Translation
本章中，translations schemes的语义动作将把一个翻译的输出写到一个文件中，每次一个字符或字符串。例如，我们把9-5+2翻译为95-2+,其中每个字符被打印一次，不使用任何存储用于子表达式的翻译。当输出用这种方式增量创建时，字符被打印的次序非常重要。
注意，到现在为止提到的语法导向的定义有下列重要的属性：代表每个生成式左边的非终结符的翻译的字符串是把所有右边非终结符翻译连接起来的结果，按照产生式中的相同顺序，在中间加入附加的字符串（可能没有）。具有这个属性的语法导向定义有一个术语叫做simple。例如，考虑下面的第一个产生式和语义规则，取自Fig2.5的语法导向定义：
PRODUCTION SEMANTIC RULE
expr → expr1 + term expr.t := expr.t || term.t || '+' (2.6)
这里expr.t的翻译是把expr1的翻译和term的翻译连接起来，跟上符号＋.注意产生式的右边expr1出现在term的前面。
在term.t和rest1.t中间出现附加的字符串：
PRODUCTION SEMANTIC RULE
rest → + term rest1 rest.t := term.t || '+' || rest1.t (2.7)
但是，再次，非终结符term在右边出现在rest1的前面。
简单的语法导向定义可以用translation scheme来实现，其中action打印附加的字符串，以他们在定义中出现的顺序。下面产生式中的动作分别打印(2.6)和(2.7)中的附加字符串：
expr → expr1 + term {print('+')}
rest → + term {print('+')} rest1
Example 2.8. Figure 2.5包含一个简单的定义，把表达式翻译成后缀形式。Fig. 2.13 给出一个从该定义派生的translation scheme，以及一棵有动作的解析树9-5+2 在2.14:
expr → expr + term {print('+')}
expr → expr -term {print('-')}
expr → term
term → 0 {print('0')}
term → 1 {print('1')}
...
term → 9 {print('9')}
Fig. 2.13 Actions translating expressions into postfix notation.
注意虽然Fig 2.6 和2.14代表相同的输入输出映射，但是两种情况下翻译用不同的方式构造出来。
Fig 2.6把输出附加到解析树的根，而Fig 2.14增量的打印输出。
Fig 2.14的根代表Fig 2,13的第一个产生式。在一个深度优先遍历中，我们首先执行左边操作符expr子树的所有动作，当我们遍历根的最左子树。我们接着访问叶子+，没有动作。我们接着执行右边的操作数term的子树，最后，语义动作{print('+')}这个额外节点被执行。
因为term的产生式右边只有一个数字，该数字被打印。对产生式expr → term而言不需要任何输出，前两个产生式也只有操作符需要被打印。在执行解析树的深度优先遍历时，Fig. 2.14的动作打印95-2+.
作为一个通用规则，绝大多数解析方法以一种“贪婪”的方式处理它们的输入，从左到右，也就是说，它们尽可能多地构造一棵解析树的部分，在阅读下一个输入token前。在一个简单translation scheme(从一个简单语法导向定义派生而来)中，动作也是按照从左到右的次序完成的。因此，为了实现一个简单的translation scheme，我们可以在解析的同时执行语义动作，根本没有必要去构造解析树。
没有评论:
发表评论