语法制导翻译与中间代码生成

关于语法制导翻译与中间代码生成8.1属性和属性文法8.1.1属性文法属性(attribute)是编程语言结构的任意特性，是一个语法概念的特征描述。属性是想表示的任何东西，典型的属性有：变量的数据类型、表达式的值、存储器中变量的位置、程序的目标代码、数的有效位数等。属性文法(attributegrammar)：将属性关系等式附加在相应文法规则上的文法属性的表示：若a是文法符号X的一个属性，则记作X.a。a称为属性变量。属性关系等式与采用何种语法分析方式无关，但是属性的计算次序受分析方法所限定的分析树结点的建立次序的约束。第2页,共48页，2024年2月25日，星期天例8.1考虑下面简单的无符号数文法：number→numberdigit|digitdigit→0|1|2|3|4|5|6|7|8|9属性文法：

文法规则 语义规则number(1)→number(2)digit number(1).val=number(2).val*10+digit.valnumber→digit number.val=digit.valdigit→0 digit.val=0…

…digit→9 digit.val=9第3页,共48页，2024年2月25日，星期天属性计算依赖于分析树或语法树明确或不明确的遍历：第4页,共48页，2024年2月25日，星期天例8.2考虑下列类似C语言中变量声明的简单文法：decl→typevar-listtype→int|floatvar-list→id,var-list|id属性文法： 文法规则 语义规则decl→typevar-list var-list.dtype=type.dtypetype→int type.dtype=integertype→float type.dtype=realvar-list(1)→id,var-list(2) id.dtype=var-list(1).dtype var-list(2).dtype=var-list(1).dtypevar-list→id id.dtype=var-list.dtype第5页,共48页，2024年2月25日，星期天字符串floatx,y的语法树，显示属性文法指定的dtype属性：第6页,共48页，2024年2月25日，星期天辅助函数mkOpNode和mkNumNode：mkOpNode构成一个新的树结点；mkNumNode构成一个叶子结点。例8.3考虑下列简单的整数算术表达式文法：exp→exp+term|exp-term|termterm→term*factor|factorfactor→(exp)|numberexp(或term或factor)的基本属性是它的数字值，写作val。属性文法……简单整型算术表达式的抽象语法树的属性文法：文法规则 语义规则exp(1)→exp(2)+term exp(1).tree=mkOpNode(+,exp(2).tree,term.tree)exp(1)→exp(2)-term exp(1).tree=mkOpNode(-,exp(2).tree,term.tree)exp→term exp.tree=term.treeterm(1)→term(2)*factorterm(1).tree=mkOpNode(*,term(2).tree,factor.tree)term→factor term.tree=factor.treefactor→(exp) factor.tree=exp.treefactor→number factor.tree=mkNumNode(number.lexval)第7页,共48页，2024年2月25日，星期天8.1.2综合和继承属性

综合属性(synthesizedattribute)

：若产生式左部符号A的属性值是通过右部符号的属性值或A的其它属性值得来的S属性文法：所有的属性都是综合的—任一右部符号的属性计算与它所在的产生式无关（从语法树看，任一结点的属性仅依赖它的下层或它自己的其它属性，换句话说不依赖上层和同层其它结点的属性）S属性文法的属性值可以通过对树进行简单后序遍历来计算：voidPostEval(treenodeT){foreachchildCofTdoPostEval(C);computeallsynthesizedattributesofT;}第8页,共48页，2024年2月25日，星期天并不是所有的属性都是综合的。所有的非综合属性称为继承(inherited)属性。例8.4对例8.1中的文法进行修改，数可以是八进制或十进制的based-num→numbasecharbasechar→o|dnum→numdigit|digitdigit→0|1|2|3|4|5|6|7|8|9此时，num和digit均需要一个新的属性base用来计算属性val。第9页,共48页，2024年2月25日，星期天

文法规则 语义规则based-num→numbasechar based-num.val=num.val num.base=basechar.basebasechar→o basechar.base=8basechar→d basechar.base=10num(1)→num(2)digit num(1).val= ifdigit.val=errorornum(2).val=error thenerror elsenum(2).val*num(1).base+digit.valnum(2).base=num(1).basedigit.base=num(1).basenum→digit num.val=digit.valdigit.base=num.basedigit→0 digit.val=0…

…digit→7 digit.val=7digit→8 digit.val=ifdigit.base=8thenerrorelse8digit→9 digit.val=ifdigit.base=8thenerrorelse9第10页,共48页，2024年2月25日，星期天345o的语法树：第11页,共48页，2024年2月25日，星期天与综合属性不同，子孙继承属性计算的顺序是重要的，因为在子孙的属性中继承属性可能有依赖关系。此文法有两个属性，综合属性val、继承属性base；先计算base，再用后序遍历计算val。综上所述，属性文法是带有下列说明的翻译文法：1．每个终结符、非终结符都有一个与其相关的属性的有穷集。2．每一个非终结符号的属性可分为两类：继承的或综合的。3．在分析树中，一个结点的综合属性值是从其子结点和它本身的属性值计算出来的；而一个结点的继承属性值是由该结点兄第结点和父结点和它本身的属性值计算出来的。第12页,共48页，2024年2月25日，星期天属性计算方法树遍历的属性计算方法

若语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。有时可能需要进行多遍遍历。一遍扫描的处理方法在很多情况下，翻译可以在扫描分析过程中完成，不需要构造出明确的语法分析树。L属性翻译的语法制导翻译方案包含了所有可以在语法分析过程中完成的翻译方案。一遍扫描的处理方法与下面两个因素密切相关：

（1）所采用的语法分析方法（不同方法对属性计算的方便性不同）（2）属性的计算次序。

第13页,共48页，2024年2月25日，星期天8.1.3属性的变换属性计算主要在语义分析阶段进行，但语义分析的部分工作可以放到词法/语法分析阶段进行。如，当一个名字填入符号表时，就可以检查这个名字是否只定义了一次。如果语义分析可以推迟到所有的语法分析完成之后进行，那么实现语义分析的任务就相当容易，其本质上是对语法树的一序列的遍历过程，同时在遍历中每次遇到结点时进行计算，但也这就意味着编译程序必须是多遍的。另一方面，如果要求编译程序在一遍中完成所有的操作(包括代码生成)，那么语义分析的实现就会变成寻找计算语义信息的正确顺序和方法的特别的过程。第14页,共48页，2024年2月25日，星期天可能会有这样的情况，不改变语言合法的字符串而修改文法会使属性的计算更简单或更复杂。定理：(Knuth[1968])给定一个属性文法，通过适当地修改文法，而无须改变文法的语言，所有的继承属性可以改变成综合属性。虽然重写文法使之仅使用综合属性总是可能的，但通常是使用带继承属性的属性文法更自然些。属性等式与使用什么样的语法分析方法以及分析算法的具体实现无关。在下面的语法制导翻译中，我们将会看到属性文法的作用在于它能指导我们写出更加清晰、简练、不易出错的的语义分析子程序，同时子程序也更加易懂。第15页,共48页，2024年2月25日，星期天例8.5再次考虑变量声明的简单文法：decl→typevar-listtype→int|floatvar-list→id,var-list|id可将这个文法改写为：decl→var-listidvar-list→var-listid,|typetype→int|floatinta,b,c第16页,共48页，2024年2月25日，星期天8.2属性文法和语法制导翻译语义分析包括构造符号表、记录声明中建立的名字的含义、在表达式和语句中进行类型检查等。类型检查应验证一种结构的类型是否匹配其上下文的要求。如何把源程序改造成某种形式的中间语言程序？在语法分析中，有相当成熟的理论和算法：使用BNF中的上下文无关文法描述语言的语法结构，并用自顶向下或自底向上的分析算法实现语法分析。语义分析目前还没有给出一种公认的形式化描述系统，只能说有一些成功的系统和方法，其中比较接近形式化的一种方法是语法制导翻译法。第17页,共48页，2024年2月25日，星期天所谓语法制导翻译，直观上说就是为每个产生式配上一个翻译子程序（语义子程序），并且在语法分析的同时执行它。语义子程序的功能包括改变编译程序某些变量的值、查填各种符号表、诊察与报告源程序错误、产生中间代码等。语义子程序是给产生式赋予具体意义的手段，一方面规定了产生式产生的符号串的意义，另一方面又按照这种意义规定了生成代码应做的基本动作。例如，定义二进制算术表达式E的”值”的语义：

1.E

E(1)+E(2) {E.VAL:=E(1).VAL+E(2).VAL}2.E

0 {E.VAL:=0}3.E

1 {E.VAL:=1}对输入串1+1+0+1，一旦分析器认出它是一个句子时，它的值“11”也就被语义子程序计算出来了。第18页,共48页，2024年2月25日，星期天语法制导翻译既可以用来产生中间代码，也可以用来产生目标指令，甚至可用来对输入串进行解释执行。总之，按语法制导翻译的方法来实现语言的翻译，就是要根据语言的文法，按照各产生式的语义，分别编写出完成这些操作的语义子程序，并把它们插入到各产生式右部的适当位置上，从而形成翻译文法。这样，在语法分析过程中，就能在分析符号串的同时，执行由翻译文法所确定的、与该符号串相对应的动作序列，即按动作符号的顺序调用相应的子程序完成翻译任务。语义子程序的设计：以属性文法为基础，将属性等式转化为计算规则（属性等式本身指示了属性计算时的顺序约束）。第19页,共48页，2024年2月25日，星期天对产生式X0→X1

X2...Xn的属性等式Xi.aj=fij(X0.a1，…，X0.ak，X1.a1，…，X1.ak，…，Xn.a1，…，Xn.ak)等式右边出现的所有属性值必须已经存在。但在属性文法的说明中，这个要求可能被忽略，可以将等式写成任意顺序而不会影响正确性。实现属性文法的关键在于为属性的计算寻找一个顺序，以确保当每次进行计算时使用的所有属性值都是有效的。

文法规则 语义规则decl→var-listid id.dtype=var-list.dtypevar-list(1)→var-list(2)id,id.dtype=var-list(2).dtype var-list(1).dtype=var-list(2).dtypevar-list→type var-list.dtype=type.dtypetype→int type.dtype=integertype→float type.dtype=real仍以简单说明句的属性文法为例其语义动作就是在符号表中登记上这些名字的有关性质。按此属性文法，就可把所说明的性质及时告诉每个名字id。或者说每当读进一个标识符时，就可以把它的性质登记在符号表中。第20页,共48页，2024年2月25日，星期天几个语义变量和语义过程：D.dtypeFILL(p,A)：把性质A填进p所指符号表入口的有关栏中。ENTRY(i)：查询和取得i所代表的标识符在符号表中的入口各产生式语义动作：1．decl→var-listid {FILL(ENTRY(id),var-list.dtype);}2．var-list(1)→var-list(2)id, {FILL(ENTRY(id),var-list(2).dtype); var-list(1).dtype=var-list(2).dtype}3．var-list→type {var-list.dtype=type.dtype}4．type→int {type.dtype=integer}6．type→float {type.dtype=real}可见，语法制导翻译就是属性文法的一种实现方式。第21页,共48页，2024年2月25日，星期天S属性文法的语法制导翻译通常可借助于LR分析器实现，在对输入串进行语法分析的同时对属性进行计算。对LR分析程序，可以通过扩充分析栈，修改总控程序，使之适合于主要处理S属性文法。对综合属性，可设置一个值栈进行存储，值栈将和分析栈并行操作，每当在分析栈出现移进或规约时，就根据属性等式来计算新值。以简单算术表达式的二义性版本为例：exp→exp+exp|exp*exp|(exp)|number

文法规则 语义规则exp(1)→exp(2)+exp(3) {exp(1).val=exp(2).val+exp(3).val}exp(1)→exp(2)*exp(3){exp(1).val=exp(2).val*exp(3).val}exp(1)→(exp(2)) {exp(1).val=exp(2).val}exp→number {exp.val=number.val}第22页,共48页，2024年2月25日，星期天statevalZZ.zYY.y......XX.xtop第23页,共48页，2024年2月25日，星期天在LR分析中，表达式3*4+5的语法和语义动作：分析栈输入 语法动作 值栈 语义动作1# 3*4+5# 移进 #2#n*4+5# 规约E→n #3 E.val=n.val3#E *4+5# 移进 #34#E*4+5# 移进 #3*5#E*n+5# 规约E→n #3*4 E.val=n.val6#E*E+5# 规约E→E*E #3*4E(1).val=E(2).val+E(3).val

7#E+5# 移进 #128#E+5# 移进 #12+9#E+n# 规约E→n #12+5 E.val=n.val10#E+E# 规约E→E+E #12+5E(1).val=E(2).val+E(3).val

11#E# #17第24页,共48页，2024年2月25日，星期天8.3中间代码的形式复杂性程度介于源程序语言和机器语言之间的语言。引入目的：为了使编译程序结构在逻辑上更为简单明确,便于编译系统的建立和编译系统的移植，特别是为了使目标代码的优化比较容易实现并独立于机器进行。中间代码生成是通过遍历由于法分析器建立的语法树实现的。遍历语法树的操作可以和建立语法树的操作同时进行，也可以在语法树建立之后再遍历一次语法树，前一种叫语法制导翻译。常见形式：逆波兰记号、树结构表示、三元式、四元式等。第25页,共48页，2024年2月25日，星期天逆波兰式逆波兰式是波兰逻辑学家卢卡西维奇发明的一种表示表达式的方法，用于说明算术表达式：不使用括号，运算量在前，算符在后，故也称为后缀式。1．简单表达式的逆波兰表示

(a+b)*c中缀前缀*+abc后缀ab+c*2．逆波兰式的特点无括号，形式简洁清楚；运算符的顺序与运算的次序完全相同。第26页,共48页，2024年2月25日，星期天三元式和树结构表示表达式A*B+C*D的三元式序列为：（1）（*，A，B）（2）（*，C，D）（3）（+，（1），（2））

可用树形结构直观地表示三元式及其序列，形成抽象的树型数据结构形式的中间代码。第27页,共48页，2024年2月25日，星期天树型表示的语法制导翻译算法为：

产生式 语义动作(1)E

E(1)opE(2) {E.VAL=NODE(op,E(1).VAL,E(2).VAL)}(2)E

(E(1)) {E.VAL=E(1).VAL}(3)E

-E(1) {E.VAL=UNARY(@,E(1).VAL)}(4)E

i {E.VAL=LEAF(i)}E.VAL：指示器，指向树的一个结点。NODE(op,LEFT,RIGHT)：建立二叉树，回送的值是一个指示器，指向新树根。UNARY(OP,CHILD)：与NODE类似，只有一个枝。LEAF(i)：建立以i.LEXVAL指示的叶结点并回送此结点的地址。第28页,共48页，2024年2月25日，星期天四元式表示法

四元式是四元组：

(OP,ARG1,ARG2,RESULT)也称作三地址码。在实现时，OP代表算符对应的整数码。ARG1、ARG2和RESULT或是指向有关符号表的某一位置的指示器或是代表临时变量的整数码。A=-B*(C+D)可翻译成四元式序列：（1） @ B — T1 临时变量T1（2） + C D T2 临时变量T2（3） * T1 T2 T3 临时变量T3（4） := T3 — A 赋值运算更直观的形式：RESULT:=ARG1OPARG2第29页,共48页，2024年2月25日，星期天抽象语法树在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树。在抽象语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点如产生式S→ifBthenS1elseS2抽象语法树表示if-then-elseBS1S2第30页,共48页，2024年2月25日，星期天8.4简单表达式及赋值语句的语法制导翻译

一、只含整型变量的简单赋值句的文法：

A

i:=E E

E+E|E*E|-E|(E)|i语义变量和语义过程：NEWTEMP：每次调用时，回送一个代表新临时变量名的整数码，临时变量名产生顺序可想象为T1,T2,…。E.PLACE：表示存放E值的变量名在符号表的入口或整数码。GEN(OP,ARG1,ARG2,RESULT)：将四元式填进表中。ENTRY(i)：查找并取得与i相对应的标识符在符号表中的入口第31页,共48页，2024年2月25日，星期天

产生式 语义动作(1)A

i:=E {GEN(:=,E.PLACE,—,ENTRY(i))}(2)E

E(1)+E(2) {E.PLACE:=NEWTEMP; GEN(+,E(1).PLACE,E(2).PLACE,E.PLACE)}(3)E

E(1)*E(2) {E.PLACE:=NEWTEMP; GEN(*,E(1).PLACE,E(2).PLACE,E.PLACE)}(4)E

-E(1) {E.PLACE:=NEWTEMP; GEN(@,E(1).PLACE,—,E.PLACE)}(5)E

(E(1))

{E.PLACE:=E(1).PLACE}(6)E

i

{E.PLACE:=ENTRY(i)}第32页,共48页，2024年2月25日，星期天在进行不同类型量混合运算时，须为非终结符增加类型属性E.MODE。如在产生式E

E(1)opE(2)中，E.MODE的语义规则定义为：

{if(E(1).MODE==Int&&E(2).MODE==Int) E.MODE=Int elseE.MODE=r; }需增加四元式：(itr,A,—,T)，并在运算符上指出相应的类型。如X=Y+I*J(X、Y为实型，I、J为整型)的四元式序列为：(*i,I,J,T1)(itr,T1,—,T2)(+r,Y,T2,T3)(=,T3,—,X)第33页,共48页，2024年2月25日，星期天二、控制语句中的布尔表达式的翻译

布尔表达式在程序设计语言中有两个基本功用，一是作为控制语句的条件式；二是作为逻辑运算，获得逻辑值。后者的翻译较为简单，下面只考虑作为控制语句中的条件式在高级程序设计语言中，布尔表达式一般的处理方式是采用某种优化措施简化计算过程。考虑下述文法的布尔表达式：

E

E∧E|E∨E|┒E|(E)|i|iropi 我们可以用条件句来解释布尔计算：

A∨B解释为ifAthentrueelseBA∧B解释为ifAthenBelsefalse┒A解释为ifAthenfalseelsetrue1a=2,b=31||a=2&&b=31a=0,b=0a=b=0第34页,共48页，2024年2月25日，星期天为按此方式翻译布尔式，引入如下三种形式的四元式：

(1)(jnz,A1,—,p)，若A1为‘真’，则转向第p个四元式。

(2)(jθ,A1,A2,p)，若A1θA2为‘真’，则转向第p个四元式。

(3)(j,—,—,p)，无条件转向第p个四元式。这样，a<b等价于ifa<bthen1else0，可翻译为：

(1)ifa<bgoto(4)(2)t:=0(3)goto(5)(4)t:=1(5)…其中用临时变量t存放布尔表达式a<b的值。ifA1≠0gotopifA1θA2gotopgotop第35页,共48页，2024年2月25日，星期天对a<b&&c<d，得下列序列：(1)(j<,a,b,3)(2)(j,-,-,5)(3)(j<,c,d,7)(4)(j,-,-,5)(5)(:=,0,-,t1)(6)(j,-,-,8)(7)(:=,1,-,t1)(8)第36页,共48页，2024年2月25日，星期天作为条件控制的布尔式，比如ifEthenS1elseS2中的E，它的作用仅仅在于控制对S1和S2的选择，因此只涉及到E的两个出口而不需要保留E的值。如图8-7所示。第37页,共48页，2024年2月25日，星期天例如,ifA∨B<DthenS1elseS2可解释为：若A为‘真’，则执行S1，否则若B<D为‘真’，则执行S1，否则执行S2。其四元式序列为：(1)(jnz,A,—,5) A的“真”出口转移目标为5。(2)(j,—,—,3) A的“假”出口转移目标为3。(3)(j<,B,D,5) B<D的“真”出口转移目标为5。(4)(j,—,—,p+1) B<D的“假”出口转移目标为（p+1）。(5)(关于S1的四元式序列)(p)(j,—,—,q) 跳过S2的代码段。(p+1)(关于S2的四元式序列)(q)第38页,共48页，2024年2月25日，星期天这里需注意，一个布尔表达式的真假出口转移目标。如E

E(1)∨E(2)，若E(1)为真，则E为真，E(1)的真出口转移目标即E的真出口转移目标；若E(1)为假，需再看E(2)；若E(2)为真，则E为真，而E(2)为假，则E为假。即E(2)的真、假出口转移目标就是E的真、假出口转移目标。问题在于在自下而上的分析过程中，一个布尔式的真假出口转移目标往往不能在产生四元式时就能确定。例如，对于A∨B<D，当把A归约为E(E

i）时，产生四元式(jnz,A,—,p)，但当前并不能确定p的值，此时四元式是不完整的。因此，我们需要记录这些暂时还不完整的四元式的位置，一旦p被定义，就及时回填。而p被定义之处在后选式中的对应点正是文法变换时的分割点。第39页,共48页，2024年2月25日，星期天为了使用语法制导翻译在扫描到∧或∨时能及时回填一些业已明确的待填的转移目标，需要把文法改写成：

E

EAE|EOE|┒E|(E)|i|iropi EA

E∧EO

E∨

需定义两个语义属性E.TC和E.FC，分别记录表达式E所对应的需回填真、假出口转移目标的四元式所构成的链。例如，若E的四元式中需回填‘真’出口转移目标的有p、q和r三个四元式，则这三个四元式可以通过第四个字段链成一条‘真’链并用E.TC记录链首r。

(p)(……0) 0为链尾标志

…… (q)(……p) …… (r)(……q) E.TC第40页,共48页，2024年2月25日，星期天为了处理E.TC和E.FC，需定义新的语义变量和语义过程。NXQ：是指向下一个将要形成但尚未形成的四元式的指示器。每执行GEN一次，就自动增1MERG(p1,p2)：把p1和p2链合二为一的函数。BACKPATCH(p,t)：‘回填’链表p中每个四元式的第四区段为t。POINTERMERG(p1,p2)IF(p1==0)RETURNp2ELSE{p=p1;WHILE四元式p的第四区段的内容不为0DO p:=四元式p的第四区段的内容;

把p2填进四元式p的第四区段;RETURNp1;}第41页,共48页，2024年2月25日，星期天voidBACKPATCH(p,t){q=p;WHILEq≠0DO{q:=四元式q的第四区段的内容;

把t填进四元式p的第四区段; p=q}}若不改写文法，则子程序不一定出现在产生式的最后，而须在适当的地方插入子程序。此时，LR分析器会替你进行改写。第42页,共48页，2024年2月25日，星期天语义子程序如下：E

i{E.TC=NXQ;E.FC=NXQ+1;GEN(jnz,ENTRY(i),—,0);GEN(j,—,—,0)}(2)E

i(1)ropi(2){E.TC:=NXQ;E.FC:=NXQ+1;GEN(jrop,ENTRY(i(1)),ENTRY(i(2)),0);GEN(j,—,—,0)}(3)E

(E(1)){E.TC:=