编译原理 第八章语法制导翻译与中间代码生成

1、第八章第八章 语法制导翻译与中间代码生成语法制导翻译与中间代码生成u语言的结构可形式的用一组产生式(BNF)描述，这使得语言的词法分析器和语法分析器的自动生成成为可能。u本章：语义的形式化困难，语义处理复杂，难以形式化 语义处理主要包括静态语义（包括类型规则和作用域/可见性规则）检查和翻译成中间代码； 对属性和属性文法作一介绍；语法制导翻译：一种接近形式化的系统；典型的中间代码；语义子程序设计；各种基本语言成分的自下而上分析的语法制导翻译。8.1 属性和属性文法8.1.1属性文法属性(attribute)是编程语言结构的任意特性，是一个语法概念的特征描述。属性是想表示的任何东西，典型的属性有：

2、变量的数据类型、表达式的值、存储器中变量的位置、程序的目标代码、数的有效位数等。属性文法(attribute grammar)：将属性关系等式附加在相应文法规则上的文法属性的表示：若a是文法符号X的一个属性，则记作X.a。a称为属性变量。属性关系等式与采用何种语法分析方式无关，但是属性的计算次序受分析方法所限定的分析树结点的建立次序的约束。例8.1 考虑下面简单的无符号数文法： numbernumber digit | digitdigit0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9属性文法：文法规则语义规则number(1)number(2) digit num

3、ber(1).val=number(2).val*10 + digit.valnumberdigit number.val=digit.valdigit0 digit.val=0digit9 digit.val=9属性计算依赖于分析树或语法树明确或不明确的遍历：例8.2 考虑下列类似C语言中变量声明的简单文法：decltype var-listtypeint | floatvar-listid, var-list | id属性文法：文法规则语义规则decltype var-list var-list.dtype=type.dtypetypeint type.dtype=integertypef

4、loat type.dtype=realvar-list(1)id ,var-list(2) id.dtype=var-list(1).dtype var-list(2).dtype=var-list(1).dtypevar-listid id.dtype=var-list.dtype字符串float x,y的语法树，显示属性文法指定的dtype属性：辅助函数mkOpNode和mkNumNode：nmkOpNode构成一个新的树结点；nmkNumNode构成一个叶子结点。 例8.3 考虑下列简单的整数算术表达式文法：expexp+term | exp-term | termtermterm*f

5、actor | factorfactor(exp)| numberexp(或term或factor)的基本属性是它的数字值，写作val。属性文法简单整型算术表达式的抽象语法树的属性文法： 文法规则 语义规则exp(1)exp(2)+termexp(1).tree=mkOpNode(+,exp(2).tree,term.tree)exp(1)exp(2)-termexp(1).tree=mkOpNode(-,exp(2).tree,term.tree)exptermexp.tree=term.treeterm(1)term(2)*factor term(1).tree=mkOpNode(*,te

6、rm(2).tree,factor.tree)termfactorterm.tree=factor.treefactor(exp)factor.tree=exp.treefactornumberfactor.tree=mkNumNode(number.lexval)8.1.2 综合和继承属性综合和继承属性 n综合属性(synthesized attribute) ：若产生式左部符号A的属性值是通过右部符号的属性值或A的其它属性值得来的nS属性文法：所有的属性都是综合的任一右部符号的属性计算与它所在的产生式无关（从语法树看，任一结点的属性仅依赖它的下层或它自己的其它属性，换句话说不依赖上层和同层

7、其它结点的属性）nS属性文法的属性值可以通过对树进行简单后序遍历来计算：void PostEval(treenode T) for each child C of T do PostEval(C); compute all synthesized attributes of T;n并不是所有的属性都是综合的。所有的非综合属性称为继承(inherited)属性。例8.4 对例8.1中的文法进行修改，数可以是八进制或十进制的based-numnum basecharbasecharo | dnumnum digit | digitdigit0 | 1 | 2 | 3 | 4 | 5 | 6 | 7

8、 | 8 | 9此时，num和digit均需要一个新的属性base用来计算属性val。 文法规则语义规则based-numnum basecharbased-num.val=num.valnum.base=basechar.basebasecharobasechar.base=8basechardbasechar.base=10num(1)num(2) digitnum(1).val=if digit.val=error or num(2).val=error then errorelse num(2).val*num(1).base+digit.val num(2).base=num(1).

9、base digit.base=num(1).basenumdigit num.val=digit.val digit.base=num.basedigit0digit.val=0digit7digit.val=7digit8digit.val=if digit.base=8 then error else 8digit9digit.val=if digit.base=8 then error else 9345o的语法树：n与综合属性不同，子孙继承属性计算的顺序是重要的，因为在子孙的属性中继承属性可能有依赖关系。n此文法有两个属性，综合属性val、继承属性base；n先计算base，再用后序

10、遍历计算val。综上所述，属性文法是带有下列说明的翻译文法：1每个终结符、非终结符都有一个与其相关的属性的有穷集。2每一个非终结符号的属性可分为两类：继承的或综合的。3在分析树中，一个结点的综合属性值是从其子结点和它本身的属性值计算出来的；而一个结点的继承属性值是由该结点兄第结点和父结点和它本身的属性值计算出来的。属性计算方法n树遍历的属性计算方法若语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。有时可能需要进行多遍遍历。 n一遍扫描的处理方法 在很多情况下，翻译可以在扫描分析过程中完成，不需要构造出明确的语法分析树。L属性

11、翻译的语法制导翻译方案包含了所有可以在语法分析过程中完成的翻译方案。n一遍扫描的处理方法与下面两个因素密切相关： （1）所采用的语法分析方法（不同方法对属性计算的方便性不同） （2）属性的计算次序。 8.1.3 属性的变换属性的变换n属性计算主要在语义分析阶段进行，但语义分析的部分工作可以放到词法/语法分析阶段进行。如，当一个名字填入符号表时，就可以检查这个名字是否只定义了一次。n如果语义分析可以推迟到所有的语法分析完成之后进行，那么实现语义分析的任务就相当容易，其本质上是对语法树的一序列的遍历过程，同时在遍历中每次遇到结点时进行计算，但也这就意味着编译程序必须是多遍的。n另一方面，如果要求编

12、译程序在一遍中完成所有的操作(包括代码生成)，那么语义分析的实现就会变成寻找计算语义信息的正确顺序和方法的特别的过程。n可能会有这样的情况，不改变语言合法的字符串而修改文法会使属性的计算更简单或更复杂。n定理：(Knuth 1968)给定一个属性文法，通过适当地修改文法，而无须改变文法的语言，所有的继承属性可以改变成综合属性。n虽然重写文法使之仅使用综合属性总是可能的，但通常是使用带继承属性的属性文法更自然些。属性等式与使用什么样的语法分析方法以及分析算法的具体实现无关。在下面的语法制导翻译中，我们将会看到属性文法的作用在于它能指导我们写出更加清晰、简练、不易出错的的语义分析子程序，同时子程序

13、也更加易懂。例8.5 再次考虑变量声明的简单文法：decltype var-listtypeint | floatvar-listid, var-list | id可将这个文法改写为：declvar-list idvar-listvar-list id, | typetypeint | floatint a, b, c8.2 属性文法和语法制导翻译n语义分析包括构造符号表、记录声明中建立的名字的含义、在表达式和语句中进行类型检查等。 n类型检查应验证一种结构的类型是否匹配其上下文的要求。n如何把源程序改造成某种形式的中间语言程序？ 在语法分析中，有相当成熟的理论和算法：使用 BNF中的上下文无

14、关文法描述语言的语法结构，并用自顶向下或自底向上的分析算法实现语法分析。 n语义分析目前还没有给出一种公认的形式化描述系统，只能说有一些成功的系统和方法，其中比较接近形式化的一种方法是语法制导翻译法。 n所谓语法制导翻译，直观上说就是为每个产生式配上一个翻译子程序（语义子程序），并且在语法分析的同时执行它。n语义子程序的功能包括改变编译程序某些变量的值、查填各种符号表、诊察与报告源程序错误、产生中间代码等。n语义子程序是给产生式赋予具体意义的手段，一方面规定了产生式产生的符号串的意义，另一方面又按照这种意义规定了生成代码应做的基本动作。例如，定义二进制算术表达式E的”值”的语义： 1. EE(

15、1)+E(2)E.VAL:=E(1).VAL+E(2).VAL 2. E0E.VAL:=0 3. E1E.VAL:=1对输入串1+1+0+1，一旦分析器认出它是一个句子时，它的值“11”也就被语义子程序计算出来了。 n语法制导翻译既可以用来产生中间代码，也可以用来产生目标指令，甚至可用来对输入串进行解释执行。 n总之，按语法制导翻译的方法来实现语言的翻译，就是要根据语言的文法，按照各产生式的语义，分别编写出完成这些操作的语义子程序，并把它们插入到各产生式右部的适当位置上，从而形成翻译文法。这样，在语法分析过程中，就能在分析符号串的同时，执行由翻译文法所确定的、与该符号串相对应的动作序列，即按动

16、作符号的顺序调用相应的子程序完成翻译任务。n语义子程序的设计：以属性文法为基础，将属性等式转化为计算规则（属性等式本身指示了属性计算时的顺序约束）。对产生式 X0X1 X2 . . . Xn 的属性等式Xi.aj=fij(X0.a1，X0.ak，X1.a1，X1.ak，Xn.a1，Xn.ak)等式右边出现的所有属性值必须已经存在。但在属性文法的说明中，这个要求可能被忽略，可以将等式写成任意顺序而不会影响正确性。实现属性文法的关键在于为属性的计算寻找一个顺序，以确保当每次进行计算时使用的所有属性值都是有效的。文法规则 语义规则declvar-list id id.dtype=var-list.d

17、typevar-list(1)var-list(2) id, id.dtype=var-list(2).dtype var-list(1).dtype=var-list(2).dtypevar-listtype var-list.dtype=type.dtypetypeint type.dtype=integertypefloat type.dtype=real仍以简单说明句的属性文法为例其语义动作就是在符号表中登记上这些名字的有关性质。按此属性文法，就可把所说明的性质及时告诉每个名字id。或者说每当读进一个标识符时，就可以把它的性质登记在符号表中。 几个语义变量和语义过程：nD.dtypen

18、FILL(p, A)：把性质A填进p所指符号表入口的有关栏中。nENTRY(i)：查询和取得i所代表的标识符在符号表中的入口n各产生式语义动作：1declvar-list idFILL(ENTRY(id), var-list.dtype); 2var-list(1)var-list(2) id,FILL(ENTRY(id), var-list(2).dtype); var-list(1).dtype=var-list(2).dtype3var-listtypevar-list.dtype=type.dtype4typeinttype.dtype=integer6typefloattype.dt

19、ype=real可见，语法制导翻译就是属性文法的一种实现方式。 nS属性文法的语法制导翻译通常可借助于LR分析器实现，在对输入串进行语法分析的同时对属性进行计算。n对LR分析程序，可以通过扩充分析栈，修改总控程序，使之适合于主要处理S属性文法。 对综合属性，可设置一个值栈进行存储，值栈将和分析栈并行操作，每当在分析栈出现移进或规约时，就根据属性等式来计算新值。 以简单算术表达式的二义性版本为例：expexp+exp | exp*exp | (exp) | number文法规则语义规则exp(1)exp(2) + exp(3) exp(1).val = exp(2).val + exp(3).v

20、alexp(1)exp(2) * exp(3) exp(1).val = exp(2).val * exp(3).valexp(1)(exp(2) exp(1).val = exp(2).valexpnumber exp.val = number.valstatevalZZ.zYY.y.XX.xtop在LR分析中，表达式3*4+5的语法和语义动作： 分析栈 输入语法动作值栈 语义动作1 # 3*4+5# 移进#2 #n *4+5# 规约En #3 E.val=n.val3 #E *4+5# 移进#34 #E* 4+5# 移进#3*5 #E*n +5# 规约En#3*4 E.val=n.val6

21、 #E*E +5# 规约EE*E #3*4 E(1).val=E(2).val+E(3).val 7 #E +5# 移进#128 #E+ 5# 移进#12+9 #E+n # 规约En#12+5 E.val=n.val10 #E+E # 规约EE+E#12+5 E(1).val=E(2).val+E(3).val 11 #E#178.3 中间代码的形式n复杂性程度介于源程序语言和机器语言之间的语言。n引入目的：为了使编译程序结构在逻辑上更为简单明确, 便于编译系统的建立和编译系统的移植，特别是为了使目标代码的优化比较容易实现并独立于机器进行。 n中间代码生成是通过遍历由于法分析器建立的语法树实现

22、的。遍历语法树的操作可以和建立语法树的操作同时进行，也可以在语法树建立之后再遍历一次语法树，前一种叫语法制导翻译。n常见形式：逆波兰记号、树结构表示、三元式、四元式等。逆波兰式逆波兰式是波兰逻辑学家卢卡西维奇发明的一种表示表达式的方法，用于说明算术表达式：不使用括号，运算量在前，算符在后，故也称为后缀式。1简单表达式的逆波兰表示 (a+b)*c中缀 前缀 * + a b c后缀 a b + c *2逆波兰式的特点l无括号，形式简洁清楚；l运算符的顺序与运算的次序完全相同。三元式和树结构表示n表达式表达式A * B + C * D的三元式序列为：的三元式序列为：（1）（）（*，A，B）（2）（）

23、（*，C，D）（3）（）（+，（，（1），（），（2） n可用树形结构直观地表示三元式及其序列，形成抽象的树型数据结构形式的中间代码。 *(1)（1） + A B C D *(2) 图 6-5 表示 A*B+C*D 的树 n树型表示的语法制导翻译算法为：产生式语义动作(1) EE(1)op E(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) Ei E.VAL=LEAF(i)E.VAL：指示器，指向树的一个结点。NODE (op , LEFT, RIG

24、HT)：建立二叉树，回送的值是一个指示器，指向新树根。UNARY (OP, CHILD )：与NODE类似，只有一个枝。LEAF(i)：建立以i.LEXVAL指示的叶结点并回送此结点的地址。四元式表示法四元式表示法 n四元式是四元组： (OP, ARG1, ARG2, RESULT)n也称作三地址码。在实现时，OP代表算符对应的整数码。ARG1、ARG2和RESULT或是指向有关符号表的某一位置的指示器或是代表临时变量的整数码。A= -B*(C + D)可翻译成四元式序列：（1） BT1临时变量T1（2） +CDT2临时变量T2（3） *T1T2T3临时变量T3（4） :=T3A赋值运算更直观

25、的形式：RESULT:=ARG1 OP ARG2抽象语法树在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树。 在抽象语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点如产生式Sif B then S1 else S2抽象语法树表示 if-then-elseB S1 S28.4 简单表达式及赋值语句的语法制导翻译简单表达式及赋值语句的语法制导翻译 一、只含整型变量的简单赋值句的文法：Ai:=EEE+E | E*E | -E | (E) | i 语义变量和语义过程： NEWTEMP：每次调用时，回送一个代表新临时变量名的整数

26、码，临时变量名产生顺序可想象为T1,T2,。E.PLACE：表示存放E值的变量名在符号表的入口或整数码 。GEN(OP, ARG1, ARG2, RESULT)：将四元式填进表中。ENTRY(i)：查找并取得与i相对应的标识符在符号表中的 入口产生式语义动作(1) Ai:=E GEN(:= ,E.PLACE , , ENTRY(i)(2) EE(1)+E(2)E.PLACE:=NEWTEMP; GEN (+ , E(1).PLACE , E(2).PLACE , E.PLACE) (3) EE(1)*E(2)E.PLACE:=NEWTEMP; GEN (* , E(1).PLACE , E(2

27、).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) EiE.PLACE:=ENTRY(i)在进行不同类型量混合运算时，须为非终结符增加类型属性E.MODE。如在产生式EE(1) op E(2)中，E.MODE的语义规则定义为：if (E(1).MODE=Int&E(2) .MODE=Int) E.MODE=Int else E.MODE=r;需增加四元式：(itr , A , T)，并在运算符上指出相应的类型。如

28、X=Y + I * J(X、Y为实型，I、J为整型)的四元式序列为： (*i , I , J , T1) (itr , T1, T2) (+r , Y , T2 , T3) (= , T3 , X)二、控制语句中的布尔表达式的翻译二、控制语句中的布尔表达式的翻译 n布尔表达式在程序设计语言中有两个基本功用，一是作为控制语句的条件式；二是作为逻辑运算，获得逻辑值。n后者的翻译较为简单，下面只考虑作为控制语句中的条件式n在高级程序设计语言中，布尔表达式一般的处理方式是采用某种优化措施简化计算过程。n考虑下述文法的布尔表达式： EEE | EE | E | (E) | i | i rop i n我们

29、可以用条件句来解释布尔计算： AB解释为 if A then true else B AB解释为 if A then B else false A解释为 if A then false else true1 a=2, b=31|a=2&b=31 a=0, b=0a=b=0n为按此方式翻译布尔式，引入如下三种形式的四元式： (1) (jnz ,A1 , , p)，若A1为真，则转向第p个四元式。 (2) (j, A1 ,A2 , p)，若A1A2为真，则转向第p个四元式。 (3) (j , , , p)，无条件转向第p个四元式。这样，ab等价于if ab then 1 else 0，可翻

30、译为： (1) if ab goto (4) (2) t:=0 (3) goto (5) (4) t:=1 (5)其中用临时变量t存放布尔表达式ab的值。if A10 goto pif A1 A2 goto pgoto p对ab & cd，得下列序列：(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)作为条件控制的布尔式，比如if E then S1 else S2中的E，它的作用仅仅在于控制对S1和S2的选择，因此只涉及到E的两个出口而不需

31、要保留E的值。如图8-7所示。 E 的代码 S1的代码 S2的代码 图 8-7 条件语句的代码结构 例如, if ABD then S1 else S2 可解释为：若A为真，则执行S1，否则若BD为真，则执行S1，否则执行S2。其四元式序列为：(1) (jnz , A , 5) A的“真”出口转移目标为5。(2) (j , , , 3)A的“假”出口转移目标为3。(3) (j , B , D , 5) BD的“真”出口转移目标为5。(4) (j , , p+1) BD的“假”出口转移目标为（p+1）。(5) (关于S1的四元式序列)(p) (j , , , q)跳过S2的代码段。(p+1) (

32、关于S2的四元式序列)(q)n这里需注意，一个布尔表达式的真假出口转移目标。如EE(1)E(2)，若E(1)为真，则E为真，E(1)的真出口转移目标即E的真出口转移目标；若E(1)为假，需再看E(2)；若E(2)为真，则E为真，而E(2)为假，则E为假。即E(2)的真、假出口转移目标就是E的真、假出口转移目标。n问题在于在自下而上的分析过程中，一个布尔式的真假出口转移目标往往不能在产生四元式时就能确定。n例如，对于ABD，当把A归约为E(Ei）时，产生四元式(jnz ,A , , p)，但当前并不能确定p的值，此时四元式是不完整的。n因此，我们需要记录这些暂时还不完整的四元式的位置，一旦p被定

33、义，就及时回填。而p被定义之处在后选式中的对应点正是文法变换时的分割点。为了使用语法制导翻译在扫描到或时能及时回填一些业已明确的待填的转移目标，需要把文法改写成： EEAE | EOE |E| (E) | i | i rop i EAE EOE需定义两个语义属性E.TC和E.FC，分别记录表达式E所对应的需回填真、假出口转移目标的四元式所构成的链。 例如，若E的四元式中需回填真出口转移目标的有p、q和r三个四元式，则这三个四元式可以通过第四个字段链成一条真链并用E.TC记录链首r。(p) ( 0)0为链尾标志 (q) ( p) (r) ( q) E.TC为了处理E.TC和E.FC，需定义新的语

34、义变量和语义过程。NXQ：是指向下一个将要形成但尚未形成的四元式的指示器。每执行GEN一次，就自动增1MERG(p1, p2)：把p1和p2链合二为一的函数。BACKPATCH(p, t)：回填 链表p中每个四元式的第四区段为t。POINTER MERG(p1,p2) IF (p1=0) RETURN p2 ELSE p=p1; WHILE 四元式p的第四区段的内容不为0 DO p:=四元式p的第四区段的内容; 把p2填进四元式p的第四区段; RETURN p1; void BACKPATCH (p, t) q=p; WHILE q0 DO q:=四元式q的第四区段的内容;把t填进四元式p的第四区段;p=q 若不改写文法，则子程序不一定出现在产生式的最后，而须在适当的地方插入子程序。此时，LR分析器会替你进行改写。语义子程序如下：(1) Ei E.TC=NXQ; E.