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

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

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

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

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

5、rm termterm*factor | factor factor(exp)| number exp(或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.tree term(1)term(2)*factor term(

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

7、它属性，换句话说不依赖上层和同层其它结点的属性） S属性文法的属性值可以通过对树进行简单后序遍历来计算,void PostEval(treenode T) for each child C of T do PostEval(C); compute all synthesized attributes of T;,并不是所有的属性都是综合的。所有的非综合属性称为继承(inherited)属性,例8.4 对例8.1中的文法进行修改，数可以是八进制或十进制的 based-numnum basechar basecharo | d numnum digit | digit digit0 | 1 | 2

8、 | 3 | 4 | 5 | 6 | 7 | 8 | 9 此时，num和digit均需要一个新的属性base用来计算属性val,文法规则语义规则 based-numnum basecharbased-num.val=num.val num.base=basechar.base basecharobasechar.base=8 basechardbasechar.base=10 num(1)num(2) digitnum(1).val= if digit.val=error or num(2).val=error then error else num(2).val*num(1).base+di

9、git.val num(2).base=num(1).base digit.base=num(1).base numdigit num.val=digit.val digit.base=num.base digit0digit.val=0 digit7digit.val=7 digit8digit.val=if digit.base=8 then error else 8 digit9digit.val=if digit.base=8 then error else 9,345o的语法树,与综合属性不同，子孙继承属性计算的顺序是重要的，因为在子孙的属性中继承属性可能有依赖关系。 此文法有两个属

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

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

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

13、更加清晰、简练、不易出错的的语义分析子程序，同时子程序也更加易懂,例8.5 再次考虑变量声明的简单文法： decltype var-list typeint | float var-listid, var-list | id 可将这个文法改写为： declvar-list id var-listvar-list id, | type typeint | float,8.2 属性文法和语法制导翻译,语义分析包括构造符号表、记录声明中建立的名字的含义、在表达式和语句中进行类型检查等。 类型检查应验证一种结构的类型是否匹配其上下文的要求。 如何把源程序改造成某种形式的中间语言程序？ 在语法分析中，有

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

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

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

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

18、符号表中,几个语义变量和语义过程： D.dtype FILL(p, A)：把性质A填进p所指符号表入口的有关栏中。 ENTRY(i)：查询和取得i所代表的标识符在符号表中的入口 各产生式语义动作,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).dtype 3var-listtypevar-list.dtype=type.dtype 4typeinttype.dt

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

20、(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 expnumber exp.val = number.val,state,val,Z,Z.z,Y,Y.y,X,X.x,top,在LR分析中，表达式3*4+5的语法和语义动作： 分析栈 输入语法动作值栈 语义动作 1 # 3*4+5# 移进# 2 #n *4+5# 规约En #3 E.val=n.val 3 #E *4+5# 移进#3 4

21、 #E* 4+5# 移进#3* 5 #E*n +5# 规约En#3*4 E.val=n.val 6 #E*E +5# 规约EE*E #3*4 E(1).val=E(2).val+E(3).val 7 #E +5# 移进#12 8 #E+ 5# 移进#12+ 9 #E+n # 规约En#12+5 E.val=n.val 10 #E+E # 规约EE+E#12+5 E(1).val=E(2).val+E(3).val 11 #E#17,8.3 中间代码的形式,复杂性程度介于源程序语言和机器语言之间的语言。 引入目的：为了使编译程序结构在逻辑上更为简单明确, 便于编译系统的建立和编译系统的移植，特别

22、是为了使目标代码的优化比较容易实现并独立于机器进行。 中间代码生成是通过遍历由于法分析器建立的语法树实现的。遍历语法树的操作可以和建立语法树的操作同时进行，也可以在语法树建立之后再遍历一次语法树，前一种叫语法制导翻译。 常见形式：逆波兰记号、树结构表示、三元式、四元式等,逆波兰式,逆波兰式是波兰逻辑学家卢卡西维奇发明的一种表示表达式的方法，用于说明算术表达式：不使用括号，运算量在前，算符在后，故也称为后缀式,2逆波兰式的特点 无括号，形式简洁清楚； 运算符的顺序与运算的次序完全相同,三元式和树结构表示,表达式A * B + C * D的三元式序列为： （1）（*，A，B） （2）（*，C，D）

23、 （3）（+，（1），（2） 可用树形结构直观地表示三元式及其序列，形成抽象的树型数据结构形式的中间代码,树型表示的语法制导翻译算法为,产生式语义动作 (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, RIGHT)：建立二叉树，回送的值是一个指示器，指向新树根。 UNARY (OP, CHILD )：与NODE类似

24、，只有一个枝。 LEAF(i)：建立以i.LEXVAL指示的叶结点并回送此结点的地址,四元式表示法,四元式是四元组： (OP, ARG1, ARG2, RESULT) 也称作三地址码。在实现时，OP代表算符对应的整数码。ARG1、ARG2和RESULT或是指向有关符号表的某一位置的指示器或是代表临时变量的整数码,A= -B*(C + D)可翻译成四元式序列： （1）BT1临时变量T1 （2）+CDT2临时变量T2 （3）*T1T2T3临时变量T3 （4）:=T3A赋值运算,更直观的形式：RESULT:=ARG1 OP ARG2,抽象语法树,在语法树中去掉那些对翻译不必要的信息，从而获得更有效的

25、源程序中间表示。这种经变换后的语法树称之为抽象语法树。 在抽象语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点 如产生式Sif B then S1 else S2抽象语法树表示,8.4 简单表达式及赋值语句的语法制导翻译,一、只含整型变量的简单赋值句的文法： Ai:=E EE+E | E*E | -E | (E) | i 语义变量和语义过程： NEWTEMP：每次调用时，回送一个代表新临时变量名的整数码，临时变量名产生顺序可想象为T1,T2,。 E.PLACE：表示存放E值的变量名在符号表的入口或整数码 。 GEN(OP, ARG1, ARG2, RESULT)：将四元式填进

26、表中。 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).PLACE , E.PLACE) (4) E-E(1) E.PLACE:=NEWTEMP; GEN ( , E(1).PLACE , , E.PLACE) (5)

27、 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 需增加四元式：(itr , A , T)，并在运算符上指出相应的类型。 如X=Y + I * J(X、Y为实型，I、J为整型)的四元式序列为： (*i , I , J , T1) (itr , T1, T2) (+r , Y , T2 , T3) (= , T3 , X,二、控制语句中的布尔表达式的翻译,布尔表达式在程序设

28、计语言中有两个基本功用，一是作为控制语句的条件式；二是作为逻辑运算，获得逻辑值。 后者的翻译较为简单，下面只考虑作为控制语句中的条件式 在高级程序设计语言中，布尔表达式一般的处理方式是采用某种优化措施简化计算过程。 考虑下述文法的布尔表达式： EEE | EE | E | (E) | i | i rop i 我们可以用条件句来解释布尔计算： AB解释为 if A then true else B AB解释为 if A then B else false A解释为 if A then false else true,为按此方式翻译布尔式，引入如下三种形式的四元式： (1) (jnz ,A1 ,

29、, p)，若A1为真，则转向第p个四元式。 (2) (j, A1 ,A2 , p)，若A1A2为真，则转向第p个四元式。 (3) (j , , , p)，无条件转向第p个四元式,这样，ab等价于if ab then 1 else 0，可翻译为： (1) if ab goto (4) (2) t:=0 (3) goto (5) (4) t:=1 (5) 其中用临时变量t存放布尔表达式ab的值,if A10 goto p,if A1 A2 goto p,goto p,对ab WHILE 四元式p的第四区段的内容不为0 DO p:=四元式p的第四区段的内容; 把p2填进四元式p的第四区段; RETU

30、RN p1;,void BACKPATCH (p, t) q=p; WHILE q0 DO q:=四元式q的第四区段的内容; 把t填进四元式p的第四区段; p=q,若不改写文法，则子程序不一定出现在产生式的最后，而须在适当的地方插入子程序。此时，LR分析器会替你进行改写,语义子程序如下： Ei E.TC=NXQ; E.FC=NXQ+1; GEN (jnz, ENTRY(i), 0); GEN (j , 0) (2) Ei(1) rop i(2) E.TC :=NXQ; E.FC := NXQ + 1; GEN (jrop, ENTRY(i(1), ENTRY(i(2) , 0); GEN (j

31、 , 0) (3) E(E(1) E.TC:=E(1).TC; E.FC:= E(1).FC (4) EE(1) E.TC:=E(1).FC; E.FC:= E(1).TC (5) EAE(1) BACKPATCH(E(1).TC, NXQ); EA.FC:=E(1).FC (6) EEAE(2) E.TC:=E(2).TC; E.FC:= MERG (EA.FC, E(2).FC) (7) EOE(1) BACKPATCH(E(1).FC,NXQ); EO.TC:=E(1).TC (8) EEOE(2) E.FC:=E(2).FC; E.TC:= MERG (EO.TC, E(2).TC),

32、例：考虑表达式ab or cd and ef 一棵作了注释的分析树,8.5 控制语句的翻译,一、考虑下列文法： Sif E then S1 | if E then S1 else S2 | while E do S1 | begin L end | A L L; S | S,A是赋值句,E,S1,S2,E.true E.false,t,f,部分四元式不完整，需记住其位置,E中的a rop b： E.true (j rop , a, b, ?) E.false (j, -, -, ,例 if ab or cd and ef then S1 else S2,1) if ab goto 0 (2)

33、goto (3) (3) if cd goto (5) (4) goto 0 (5) if ef goto 1 (6) goto 4 (7) S1的四元式 (p) goto ? (p+1) S2的四元式 (q,回填位置,实际是一条链,true,false,分别叫真假链,若有语句： while (x0) do if (xy) then x:= x-y else y:=y-x,翻译结果为： 100 (j , x, 0, 102） 101 (j , 110) 102 (j , x , y , 104) 103 (j , 107) 104 (+ , x , y , T) 105 (:= , T , x) 106 (j , 100) 107 (- , y , x , T) 108 (:= , T , y) 109 (j , 100) 110,二进制纯小数文法,S-.LL-LB | BB-0 | 1试加语义子程序，将输入的小数点为前导的二进制串翻译为相应的值并输出。例若输入为.101，则输出为0.625