编译第7章.ppt

1、第7章 语法制导翻译和中间代码生成,7.1 属性文法 7.2 语法制导翻译 7.3 中间代码的形式 7.4 一些语句的翻译,语义处理,编译程序的语义处理功能： 1、审查每个语法结构的静态语义，即验证语法结构合理的程序是否真正有意义。称静态语义审查。 2、如果静态语义正确，要执行真正的翻译，即要么生成一种中间代码形式，要么生成实际的目标代码。称解释执行动态语义、生成代码。,静态语义分析通常包括, 类型检查。验证程序中执行的每个操作是否遵守语言的类型系统的过程.编译程序必须报告不符合类型系统的信息。 控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语

2、句的最小while、for或switch语句。如果不存在包括它的这样的语句，则就报错。 一致性检查。在很多场合要求对象只能被定义一次。例如Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。 相关名字检查。有时，同一名字必须出现两次或多次。例如，Ada 语言程序中，循环或程序块可以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。 名字的作用域分析,语义处理方法,对应每一个产生式编制一个语义子程序，当一个产生式获得匹配时，调用相应的语义子程序实现语义检查与翻译。 在产生式的右部的适当位置，

3、插入相应的语义动作，按照分析的进程，执行遇到的语义动作。 语义可以看成是相应文法符号的属性,虽然形式语义学(如指称语义学、公理语义学、操作语义学等)的研究已取得了许多重大的进展，但目前在实际应用中比较流行的语义描述和语义处理的方法主要还是属性文法和语法制导翻译方法.,7.1 属性(Attribute)文法(1),属性文法是Knuth在1968年提出的. 所谓属性，其涉及的概念比较广泛，常用以描述事物或人的特征、性质，品质等等。比如，谈到一个物体，可以用“颜色”描述它，谈起某人，可以使用“有幽默感”来形容他。对编译程序使用的语法树的结点，可以用“类型”、“值”或“存储位置”来描述它。 它是在上下

4、文无关文法的基础上，为每个文法符号(终结符或非终结符)配备若干相关的“值”（称为属性）。,属性(Attribute)文法(2),1、属性文法定义,属性文法(attribute grammar)是一个三元组:A=(G,V,F),其中 G:是一个上下文无关文法 V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等 .属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。 F:关于属性的属性断言或一组属性的计算规则(称为语义规则) . 断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终

5、结符相联的属性. 编译程序的静态语义审查工作就是验证关于所编译的程序的断言是否全部为真。,属性文法举例,有文法G为：ET1 + T2|T1 or T2Tnum|true|false（因为T在同一个产生式里出现了两次，使用上角标将它们区分开。）对输入串3+4的语法树如图7.1（A）,属性文法记号中常使用Nt的形式表示与非终结符N相联的属性t。比如可把对上面表达式的类型检查的属性文法写成图7.2的形式。,图7.2类型检查的属性文法 ET1+T2 T1.tintANDT2.tintET1orT2 T1.tboolAND T2.tboolTnumT.tintTtrueT.tboolTfalseT.tb

6、ool,与每个非终结符T相联的有属性t，t要么是int，要么是bool。 与非终结符E的产生式相联的断言指明：两个T的属性必须相同。,2、属性分类（1）,设 AX1X2Xn 为一个产生式 A.s=f(c1,c2,ck) c1,c2,ck是X1，X2，Xn的属性 A.s是从其子结点的属性值计算出来的 这种属性叫做综合(Synthesized)属性 适应：归约分析,例: 简单算术表达式求值的语义描述,文法描述 L E E E1 + T | T T T1 * F | F F ( E ) | digit ？如何描述翻译过程,每个非终结符都有一个整数值的称作val的属性。,属性文法（语法制导定义）,与L

7、 E相连的语义规则是一个过程，打印E的值，理解为L的属性是虚的或空的。 E,T,F的属性val都为综合属性。 lexval 是单词 digit 的属性。,属性分类（2）,设AX1X2Xn为一个产生式 B.in=f(c1,c2,ck) B为Xi， c1,c2,ck是A, X1，X2，Xi-1的属性 这种属性叫做继承(Inherited)属性,例：说明语句,说明语句的文法 D T L T int T real L L1,id L id,将类型信息作为类型描述 T 的综合属性 type 和变量表 L 的继承属性 in。,语法制导定义(属性文法),D T L L.in := T.type T int

8、T.type := integer T real T.type := real L L1,id L1.in := L.in addtype( id.entry, L.in ) L id addtype( id.entry, L.in ),entry 单词 id 的属性 addtype 在符号表中为变量填加标识符的类型信息,属性的计算,综合属性 自底向上按照语义规则来计算各结点的综合属性值 继承属性 根据依赖关系决定计算顺序 依赖图的任意一个拓扑排序（Topological Sort),例：3*5+4 的分析树与属性计算,例:real id1,id2,id3 的分析树和属性计算,在语法分析的过程

9、中，随着分析的步步进展，根据每个产生式所对应的语义子程序边分析边翻译的方法。 注：1)语法制导翻译时会根据文法产生式右部符号串的含义，进行翻译，翻译的结果是生成相应中间代码。 2)语法制导翻译的依据是语义子程序。 3)每个产生式均配置一个语义子程序，当语法分析进行归约和推导时，就调用相应语义子程序，完成一部分翻译任务。 4)语法分析完成，翻译工作也告结束。,7.2 语法制导翻译,何谓中间代码： 源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。,为什麽要此阶段 逻辑结构清楚； 利于不同目标机上实现同一种语言； 利于进行与机器无关的优化； 这些内部形式也能用于解释；,7.

10、3 中间代码的形式,常用的中间代码(语言),三地址代码（四元式） 语法(结构)树（三元式） 后缀式逆波兰表示 特点 形式简单、语义明确、便于翻译 独立于目标语言,形式： Operand1 Operand2 Operator,1、后缀表示式(逆波兰表达式),最简单的一种中间代码形式。 是波兰逻辑学家卢卡西维奇发明的。 优点：易于计算机处理表达式。,语句相应的逆波兰表示形式：,表达式求值的算法,常用的算法是使用一个栈，自左至右扫描算术表达式（后缀表示），每扫描到运算对象，就把它推进栈；扫描到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施该运算，并将运算结果代替这两个运算对象而进栈；若是一

11、目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈，最后的结果留在栈顶。,逆波兰: A B C D - * + E C D -N / +,例 : A + B * ( C - D ) + E / ( C - D ) N,形式：(Operator,Operand1,Operand2) 注： 1)这里三元式本身作为存放结果的单元 2)为了在其它三元式中利用当前三元式的结果，需要对三元式进行编号。 3)三元式的编号就作为相应三元式的结果值。,2、三元式,例 : A + B * ( C - D ) + E / ( C - D ) N,3、树形表示,形式：,简单变量或常数的树是其自身。如果e1和

12、e2的树分别为T1和T2，那么e1+e2,e1*e2,e1-e2的树分别为：,例 : A + B * ( C - D ) + E / ( C - D ) N,+,+,*,-,-,/,A,B,C,D,C D,E,N,形式： (Operator,Operand1,Operand2,Result) 注：1) 通过语法制导翻译所生成的四元式中， Operand1,Operand2,Result 可能是用户自定义的变量，也可能是编译时引进的变量。 2)四元式中变量采用符号表入口的地址，而不用变量的地址，因为语义分析不仅需要变量的地址，还需要从符号表查到的变量的属性、类型和地址等。 3)四元式的优点是容易

13、转换为目标代码和容易进行优化。,4、四元式,例 : A + B * ( C - D ) + E / ( C - D ) N,常用的三地址语句对应的四元式,X=y op z = (op,y,z,x) X=-y =(uminus,y,_,x) X=y =(=,y,_,x) Par x1 =(par,x1,_,_) /过程调用语句 Goto L =(j,_,_,L) If x rop y goto L =(jrop,x,y,L),四元式形式:,相关语义属性： : id表示的单词名字。 E.place：存放E值的变量名在符号表的登录项或一整数码（临时变量时）。 相关函数： lookup(

14、) 检查 是否出现在符号表中，如在返回指向该登录项的指针，否则返回nil; 相关过程： emit(op ，arg1，arg2，result) 表示产生一个四元式并填入四元式表中; Newtemp：生成一个新的临时变量的整数码，变量名可设为T1、T2、,(op ,arg1,arg2,result) 或 result := arg1 op arg2,7.4、简单赋值语句的翻译,产生式和语义描述：,(,1,) S,id : = E,P,:=lookup,(,),;,if P,nil then emit( =,E.place,_,P),else error()

15、 ,翻译赋值语句到四元式的语义描述,包括对先定义后使用的检查,(2) EE1+E2 E.place:= newtemp; emit(+, E1.place , E2.place ,E.place); (3) EE1*E2 E.place:= newtemp; emit(*, E1.place , E2.place ,E.place); （4）E - E1 E.place:=newtemp; emit(uminus , E1.place ,_,E.place); (5) E( E1) E.place:=newtemp; E.place:= E1.place (6) Eid E.place:=ne

16、wtemp; P:=lookup(); if Pnil then E.place:=P else error();,每个表达式中可能出现各种不同类型的变量或常数，此时应该进行类型转换的语义处理。 为此增加： E.type:E的类型信息 itr:将整型转换成实型 *i， *r分别表示int和real类型的乘法运算； 对第3条产生式的语义描述为：,(3) EE1*E2 E.place:= newtemp; if E1 . type=int AND E2. type=int then begin emit(E.place“:=” E1.place“*i”E2.place); E.typ

17、e=int end,else if E1 . type=real AND E2. type=real then begin emit(E.place“:=”E1.place“*r”E2.place); E.type=real end else if E1 . type=int / AND E2. type=real then begin t:=newtemp; emit(t “:=” “ itr” E1.place ); emit(E.place“:=”t“*r”E2.place); E.type=real end Else begin t:=newtemp; emit(t“:=” “ itr

18、” E2.place ); emit(E.place“:=”E1.place “*r” t); E.type=real end ,7.5 布尔表达式的翻译,在程序设计语言中，布尔表达式有两个基本作用： 计算逻辑值； 用作控制流语句如 if-then、if-then-else和 while-do等之中的条件表达式。 布尔表达式是用布尔运算符号（and、 or、not )作用到布尔变量或关系表达式上而组成的。 关系表达式形式如：E1 relop E2, 其中E1和E2是算术表达式， relop为关系运算符 （ =, , =, ）。,在本节中我们考虑由下列文法产生的布尔表达式： EE or E |

19、E and E | not E | (E) | id relop id |true|false 说明： 我们使用relop的属性relop.op来确定relop所指的六中关系运算中的哪一个。 按惯例，我们假定or和and 是左结合的， 并且规定or 的优先级最低，其次是and, not的优先级最高。,一、布尔表达式的翻译方法,考虑用1表示真，0表示假来实现布尔表达式的翻译。一个形如 ab的关系表达式可等价的写成: if ab then 1 else 0 ,并将它翻译成如下三地址语句序列： 100： if ab goto 103 101 T:=0 102 goto 104 103 T:= 1 104,EE1 or E2Eplace=newtemp；emit（Eplace=E1placeorE2place）EE1 and E2Eplace =newtemp；emit（Eplace=E1place andE2place） Enot E1Eplace =newtemp：；emit（Eplace=notE1place）E（E1）Eplace=E1placeEid1 relop id2Eplace=newtemp；emit（ifid1place relop id