搜索
第七章语法制导翻译和中间代码生成编译程序的任务是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等同，也就是说，尽管它们的语法结构完全不同，但它们所表达的结果应完全相同。通常，在词法分析程序和语法分析程序对源程序的语法结构进行分析之后，要么由语法分析程序直接调用相应的语义子程序进行语义处理，要么首先生成语法树或该结构的某种表示，再进行语义处理。编译中的语义处理是指两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。第二，如果静态语义正确，语义处理则要执行真正的翻译，即，要么生成程序的一种中间表示形式（中间代码），要么生成实际的目标代码。为什么有的编译程序直接生成目标代码，有的编译程序采用中间代码，所谓中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。一般，快速编译程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。但是为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作使得代码优化比较容易实现。本章重点：属性文法、语法制导翻译方法的基本思想、几种典型的中间代码形式、一些语法成分的翻译工作。第一节属性文法现在很多编译程序采用语法制导翻译方法。这仍不是一种形式系统，但它是比较接近形式化的。这种方法使用属性文法为工具来说明程序设计语言的语义。一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上，在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。首先简单介绍属性文法。属性，常用以描述事物或人的特征、性质、品质等等。比如，谈到一个物体，可以用“颜色”描述它，谈起某人，可以使用“有幽默感”来形容他。对编译程序使用的语法树的结点，可以用“类型”、“值”或“存储位置”来描述它。形式上讲，一个属性文法是一个三元组，A=（G，V，F），一个上下文无关文法G；一个属性的有穷集V和关于属性的断言或谓词的有穷集F。每个属性与文法的某个非终结符或终结符相联。每个断言与文法的某产生式相联。如果对G中的某一输入串而言（句子），A中的所有断言对该输入串的语法树结点的属性全为真，则该串也是A语言中的句子。编译程序的静态语义审查工作就是验证关于所编译的程序的断言是否全部为真。比如，有文法G为：E→T1+T2|T1orT2T→num|true|false因为T在同一个产生式里出现了两次，使用上角标将它们区分开。对输入串3+4的语法树如图7-1-1（a）属性文法记号中常使用N.t的形式表示与非终结符N相联的属性t。比如可把完成对上面表达式的类型检查的属性文法写成图7-1-2的形式。与每个非终结符T相联的有属性t，t要么是int，要么是bool。与非终结符E的产生式相联的断言指明：两个T的属性必须相同。图7-1-1(b)是图7-1-1(a)语法树结点带有语义信息的表示。{T1.t=int}ET+T43(a){T2.t=int}E{T1.t=T2.t}T+T43(b)图7-1-1静态语义审查E→T1+T2{T1.t=intANDT2.t=int}T→true{T.t：=bool}E→T1orT2{T1.t=boolANDT2.t=bool}T→false{T.t：=bool}T→num{T.t：=int}图7-1-2类型检查的属性文法属性文法最早出自克努特笔下。他把属性分成两类：继承属性和综合属性，我们不对属性文法进行理论上的研究而仅仅将它做为工具描述语义分析。在编译的许多实际应用中，属性和断言以多种形式出现，也就是说，与每个文法符号相联的可以是各种属性、断言、以及语义规则，或者某种程序设计语言的程序段等等。下面再给出一些例子。例1：简单算术表达式求值的语义描述。产生式语义规则（0）L→Eprint(E.val)（1）E→E1+TE.val：=E1.val+T.val（2）E→TE.val：=T.val（3）T→T1*FT.val：=T1.val×F.val（4）T→FT.val：=F.val（5）F→(E)F.val：=E.val（6）F→digitF.val：=digit.lexval在该描述中，每个非终结符都有一个属性：一个整数值的称作val的属性。按照语义规则对每个产生式来说，它的左部E，T，F的属性值的计算来自它右部的非终结符，这种属性称作综合属性。单词digit仅有综合属性，它的值是由词法分析程序提供的。和产生式L→E相联的语义规则是一个过程，打印由E产生的表达式的值。我们可以理解为L的属性是空的或是虚的。第二节语法制导翻译概论在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。假定我们现在要分析的语法成分是简单算术表达式，所完成的语义的处理不是将它翻译成中间代码或目标代码，而是计算表达式的值。采用的描述系统是上节的例1。假如语法分析方法是自下而上的。在用某一产生式进行归约的同时就执行相应的语义动作，在分析出一个句子时，这个句子的“值”也就同时产生了，例如输入串是2+3*5，其语法树如图7-2-1(a)，在第一步归约用到了产生式（6），执行的语义动作是置F.val的值为单词digit值，我们把语法树中每个结点的语义值括在该结点处。那么第一步归约并完成语义动作后的情形在图7-2-1(b)中指出。继续进行分析，第七次归约后的情形在图7-2-1(c)中指出归约至E时，它的值17也计算出来了。语法制导翻译的具体实现途径不困难。假定有一个LR语法分析器，现在把它的分析栈扩充，使得每个文法符号都跟有语义值，即把栈的结构看成图7-2-2所示那样。Smy.ValYSm-1x.ValX┆┆┆S0—#EE1+T32(a)TT1*FFFL5图7-2-1语法制导方法计算表达式EE1+T3(b)TT1*FF(2)FL5EE1+T(c)L(2)(15)状态栈语义值符号栈图7-2-2扩充的分析栈状态ACTION（动作）GOTO（转换）d+*()#ETF0s5s41231s6Acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5图7-2-3LR分析表同时把LR分析器的能力扩大，使它不仅执行语法分析任务，且能在用某个产生式进行归约的同时调用相应的语义子程序，完成在例1的属性文法中描述的语义动作。每步工作后的语义值保存在扩充的分析栈里“语义值”栏中。采用的LR分析表见图7-2-3，其中使用d代替digit。分析和计值2+3*5的过程列在图7-2-4中。按照上述实现办法，若把语义子程序改为产生某种中间代码的动作，那么则可在语法分析的制导下，随着分析的进展逐步生成中间代码。步骤归约动作状态栈语义栈（值栈）符号栈留余输入串1）0—#2+3*5#2）05——#2+3*5#3）r603—2#F+3*5#4）r402—2#T+3*5#5）r201—2#E+3*5#6）016—2—#E+3*5#7）0165—2——#E+3*5#8）r60163—2—3#E+F*5#9）r40169—2—3#E+T*5#10）01697—2—3—#E+T*5#11）016975—2—3——#E+T*5#12）r601697(10)—2—3—5#E+T*F#13）r30169—2—(15)#E+T#14）r101-（17）#E#15）接受图7-2-42+3*5的分析和计值过程第三节中间代码的形式编译程序所使用的中间代码有多种形式。常见的有逆波兰记号、三元式、四元式和树形表示。下面分别介绍。一、逆波兰记号逆波兰记号是最简单的一种中间代码表示形式，早在编译程序出现之前，它就用于表示算术表达式，是波兰逻辑学家卢卡西维奇发明的。这种表示法将运算对象写在前面，把运算符号写在后面，比如把a+b写成ab+，把a*b写成ab*，用这种表示法表示的表达式也称做后缀式。图7-3-1给出了程序设计语言中的简单表达式和赋值语句相应的逆波兰表示形式：程序设计语言中的表示逆波兰表示a+bab+：=a+**bcbd*T1T2e1*e2+T1T2e1+e2——T1—e1a+b*cabc*+(a+b)*cab+c*a：=b*c+b*dabc*bd*+：=图7-3-1逆波兰表示后缀表示法表示表达式，其最大的优点是最易于计算机处理表达式。利用一个栈，自左至右扫描算术表达式（后缀表示）。每碰到运算对象，就把它推进栈；碰到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施运算，并将运算结果代替这两个运算对象而进栈。若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈。最后的结果留在栈顶。例如B@CD*+（它的中缀表示为—B+C*D，使用@表示一目减）的计值过程为：1、B进栈；2、对栈顶元素施行一目减运算，并将结果代替栈顶，即—B置于栈顶；3、C进栈；4、D进栈；5、栈顶两元素相乘，两元素退栈，相乘结果置栈顶；6、栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存放的是整个表达式的值。由于后缀式表示上的简洁和计值的方便，特别适用于解释执行的程序设计语言的中间表示，也方便具有堆栈体系的计算机的目标代码生成。逆波兰表示很容易扩充到表达式以外的范围。二、三元式和树形表示另一类中间代码形式是三元式。把表达式及各种语句表示成一组三元式。每个三元式三个组成部分是：算符op，第一运算对象ARG1，和第二运算对象ARG2。例如：a：=b*c+b*d的表示为：（1）（*b，c）（2）（*b，c）（3）（+（1），（2））（4）（：=（3），a）与后缀式不同，三元式中含有对中间计算结果的显式引用，比如三元式（1）表示的是b*c的结果。三元式（3）中的（1）和（2）分别表示第一个三元式和第二个三元式的结果。对于一目算符op，只需选用一个运算对象，不防规定只用ARG1。至于多目算符，可用若干个相继的三元式表示。树形表示是三元式表示翻版。上述三元式可表示成下面的树表示：表达式的树形表示很容易实现：简单变量或常数的树就是该变量或常数自身，如果表达式e1和e2的树分别为T1和T2，那么e1+e2，e1*e2，—e1的树分别为：二目运算对应二叉子树，多目运算对应多叉子树，不过，为了便于安排存储空间，一棵多叉子树可以通过引进新结而表示成一棵二叉子树。三、四元式四元式是一种比较普遍采用的中间代码形式。四元式的四个组成成分是：算符op，第一和第二运算对象ARG1和ARG2及运算结果RESULT。运算对象和运算结果有时指用户自己定义的变量，有时指编译程序引进的临时变量。例如a:=b*c+b*d的四元式表示如下：（1）（*,b,c,t1）（2）（*,b,d,t2）（3）（*,t1,t2,t3）（4）（:=,t3,—,a）四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。四元式表示很类似于三地址指令，有时把这类中间表示称为“三地址代码”因为这种表示可看作一种虚拟三地址机的通用汇编码，即这种虚拟机的每条“指令”包含操作符和三个地址，两个是为运算对象的，一个是为结果的。这种表示对于代码优化的目标代码生成都较有利。为了更直观，把四元式的形式写成简单赋值形式。比如把上述四元式序列写成：（1）t1：=b*c（2）t2：=b*d（3）t3：=t1+t2（4）a：=t3把（jump，—，—，L）写成gotoL把（jrop，B，C，L）写成ifBropCgotoL为了叙述的方便，两种形式我们将同时使用。第四节简单赋值语句的翻译在第三节的四元式中，使用变量名字本身表示运算对象ARG1和ARG2，用ti表示RESULT。在实际实现中，它们或者是一个指针，指向符号表的某一登录项，或者是一个临时变量的整数码。在对赋值语句翻译为四元式的描述中，我们将表明怎样查找这样的