语义分析及翻译

属性文法与语法制导翻译

这两章主要介绍语义分析及翻译问题，都是编译过程的阶段。

语义分析是对经语法分析器处理过后的在结构上正确的源程序进行上下文有关性质的审查，是编译程序最实质的过程。语义描述和语义处理最常用的方法是属性文法与语法制导翻译方法，也是本章主要介绍内容。

属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）。属性是代表与文法符号相关的信息，和变量一样，可以进行计算和传递，分综合属性（自下而上）和继承属性（自上而下）。特别的，仅仅使用综合属性的属性文法叫S—属性文法。属性的计算规则称为语义规则，形式为b:=f(c1,c2,…,ck)。

基于属性文法的处理方法是对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。即按“输入串→语法树→依赖图→语义规则计算次序→计算结果”步骤计算，这种方法即为语法制导翻译法。将语法树中对翻译不必要的信息去掉，而获得更有效的源程序中间表示，就形成了抽象语法树。其中依赖图是指描述在一颗语法树中的结点的继承属性和综合属性之间的相互依赖关系的有向图。在一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规则引入一个虚综合属性b，把每一个语义规则都写成b:= f(c1,c2, …ck) 形式。依赖图为每一个属性设置一个结点，如果属性b依赖属性c，则从属性c的结点有一条有向边连到属性b的结点（被依赖的属性向依赖的属性画弧）。若属性文法不存在属性之间的循环依赖（若p、c1、c2存在如下关系p:=f1(c1)、c1:=f2(c2)、c2=f3(p)则称）关系，则称该文法为良定义的。下面讨论属性的计算次序，一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2, …mk,使得边必须是从序列中前面的结点指向后面的结点，即若mi→mj，序列中mi必须出现在mj之前。在拓扑排序中，在一个结点上，语义规则b:=f（c1,c2,…ck)中的属性c1,c2…ck在计算b以前都是可用的。下面介绍几种计算属性的方法：（1）树遍历：可以通过遍历已经建立好的语法树来计算属性，深度优先或宽度优先。（2）一遍扫描：在语法分析的同时计算属性值，无需构造实际语法树。因为一遍扫描的处理方法与语法分析器的相互作用，所以它与采用的语法分析方法和属性的计算次序密切相关。S-属性文法的翻译器通常可借助于LR分析器实现，将LR分析器增加一个域来保存综合属性值。还有一种文法允许我们通过一次遍历就计算出所有属性值，叫L-属性文法,它的定义是如果每个产生式A →X1X2 … Xn 的每条语义规则计算的属性是A的综合属性；或者是Xj 的继承属性（1≤j≤n）, 但它仅依赖：该产生式中Xj左边符号X1, X2, …, Xj-1的属性；A的继承属性，则这种文法是L-属性文法。可以在自上而下语法分析的同时实现L属性文法的计算。

翻译模式也是一种适合语法制导翻译的描述形式，给出了使用语义规则进行计算的次序，可以表现某些实现细节。其中属性与文法符号相对应，语义规则或语义动作用花括号｛｝括起来，可被插入到产生式右部的任何合适的位置上。可以根据语法制导的定义设计翻译模式，两种情况区别处理：只需要综合属性时，为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾；既有综合属性又有继承属性时，产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。一个动作不能引用这个动作右边符号的综合属性。产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的未尾。

翻译模式可以构造自顶向下翻译。对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取左公因子，在改写基本文法时考虑属性值的计算。

语义分析和中间代码产生

介绍几种常用的中间语言形式：后缀式，三地址代码（三元式、四元式、间接三元式），DAG图。后缀式表示法也叫逆波兰表示法，操作数在前，运算符在后。中间代码生成程序的任务是把经过语法分析和语义分析而获得的源程序中间表示翻译为中间代码表示。图表示法：抽象语法树、DAG。DAG与抽象语法树基本上一样，但在一个DAG中代表公共子表达式的结点具有多个父结点，即取消重复子树。三地址代码一般形式为x：＝y op z，分为赋值语句（一目、二目运算）、无条件转移语句（goto）、条件转移语句、复制语句、过程调用、索引赋值、地址和指针赋值。具体实现形式为四元式（op, arg1, arg2, result）、三元式（op, arg1, arg2）、间接三元式（间接码表+三元式表）。在生成中间代码翻译说明语句时，可为局部于该过程的名字分配存储空间，一个过程中的所有说明语句作为一个类集来处理，在符号表中建立相应的表项。

下面具体介绍各种形式三地址码的翻译。在翻译赋值语句的时候要考虑如何在符号表中查找名字（指向符号表中相应该名字表项的指针）以及如何存取数组和记录的元素。对于简单赋值语句(不考虑数组元素、记录、函数的引用等情况)，过程lookup(id.name)检查是否在符号表中存在相应此名字的表项。对于数组地址分配（复杂赋值语句），其数组地址为常量部分加变量部分。在翻译布尔表达式（用布尔运算符号(and,or,not)作用到布尔变量或关系表达式上而组成）的时候要注意有很多短路操作（若变量a=false，无论b为何值，整体都为false），表示一个布尔表达式的值时可用数值表示（用1表示真，0表示假来实现布尔表达式的翻译）真和假，从而对布尔表达式的求值可以象对算术表达式的求值那样一步一步地来计算或根据布尔表达式的特点，采用了某种优化措施。控制流语句中的布尔表达式对于出现在条件语句 if E then s1 else s2中的布尔表达式E，其作用就是控制对S1和S2的选择，上述的第二种方法适于处理它，把作为条件的布尔表达式设计成两个出口：E.true 和 E.false，对于IF语句，E.true 指向S1，E.false指向S2，对于while语句E.true 指向循环的开始，E.false指向while 的下一语句。翻译有多种方法：如用基本思想：假定E 形如a＜b,则将生成三地址或四元式形式的E的代码；用优化代码结构翻译；用语法制导定义目标代码结构翻译；用四元式表示中间代码：用四元式实现三地址码,表示真假出口；使用回填翻译布尔表达式；使用一遍扫描的布尔表达式的翻译模式。对于形如S→if E then S1| if E then S1 else S2 | while E do S1的控制流语句可以用语法制导定义、回填翻译。过程调用的翻译包括一个调用序列，即进入和离开每一个过程所采取的动作序列，可用语法制导定义实现。