第08章、语法制导翻译

1、表格管理程序错误处理程序第8章 语法制导翻译和中间代码生成28.1属性文法8.2语法制导翻译8.3常用中间代码 8.4 简单赋值语句的翻译第8章 语法制导翻译和中间代码生成3教学要求：u理解语法制导翻译的基本思想 u会写出语句的逆波兰表示、三元式、四元式和树形结构4编译中的语义处理是指两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义，也称为静态语义检查或静态审查。动态语义检查需要生成相应的目标代码，在运行时进行。第二，如果静态语义正确，语义处理的工作是要执行真正的翻译，即生成程序的一种中间表示形式（中间代码），或者直接生成实际的目标代码。语法分析后的源程序语义

2、处理中间代码5静态语义检查 （1）类型检查。根据类型相容性要求，验证程序中执行的每个操作是否遵守语言的类型系统的过程，编译程序必须报告不符合类型系统的信息。 （2）控制流检查。控制流语句必须使控制转移到合法的地方。如C语言中不允许goto转入case语句流；break语句需要寻找包含它的最小switch、while或for语句方可找到转向点，否则出错。 （3）上下文相关性检查。比如，变量名字必须先声明后引用。 （4）一致性检查。如在相同作用域中标识符只能说明一次、case语句的标号不能相同等。6 语义的形式化描述要远比语法的形式化困难得多。目前较为常见的是用属性文法作为描述程序语言语义的工具，

3、并采用语法制导翻译的方法完成对语法成分的翻译工作。7 在语法分析过程中，每当一个产生式获得匹配（自上而下分析）或用于归约（自下而上分析）时，就执行相应于该产生式的语义子程序进行语义处理，这个过程就是语法制导翻译。8属性文法是Knuth在1968年首先提出的。它是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）附加若干相关的“值”（称为属性）。这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列、符号表内容等。属性与变量一样，可以进行计算和传递。属性的加工过程即是语义处理的过程。对于文法的每个产生式附加一组属性的计算规则，称为语义规则。这样一来，属性文法实际上就是附加了一组属

4、性和语义规则的文法。9一、属性文法的形式属性文法(AG，Attribute Grammar)是一个三元组：A=(G,V, F)， 其中，G: 是一个上下文无关文法；V: 有穷的属性集，每个属性与一个文法符号相连；F：语义规则，每条与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。 文法符号X的属性t常用X.t来表示。10附加了一组属性和运算（语义）规则的文法 属性文法文法符号X的属性t常用X.t来表示 语义规则是根据产生式所蕴涵的语义操作建立起来的，并与语义分析的目标有关 不同的产生式对应不同的语义规则 不同的分析目标也对应不同的语义规则 1. 属性的表示2.语义规则的表

5、示语义信息语义之间的关系静态语义检查、符号表操作、代码生成及打印各种错误信息 11二、属性的分类- 继承的和综合的属性 综合属性：在语法树中，一个结点的综合属性由该结点的子结点的属性值确定。它的计算规则由底向上. 继承属性：在语法树中，一个结点的继承属性由该结点的父结点/兄弟结点的属性确定。即它 的计算规则由顶向下。简单地说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。12出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由参数提供。 (1) 非终结符既可以有综合属性，也可以有继承属性。

6、(2) 终结符只有综合属性,它们是由词法分析器提供的。 (3) 文法开始符号的所有继承属性，作为属性计算前的初始值是已知的。 书上错：文法开始符号没有继承属性（）。13 综合属性）可用作台式计算器的简单算术表达式求值的语义描述 非终结符E、T及F都有一个综合属性val，符号 i 有一个综合属性，它的值由词法分析器提供。与产生式LE对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规则定义了L的一个虚属性。某些非终结符加上标（也有的参考书加下标）是为了区分一个产生式中同一非终结符多次出现。语 义 规 则 L EE E1+TE TT T1 * FT FF (E)F iPri

7、nt(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=i.lexval产 生 式属性文法的主要思想有两点： 首先对于每个文法符号引进相关的属性符号； 其次对于每个产生式写出属性值计算的规则。14设表达式为35+4，则语义动作打印数值19LE19E15T4T15F4T3F3F 5i=4i5i3+*3*5+4 的带语义信息的分析树：表示综合属性（很直观） 一个结点的综合属性值是其子结点的某些属性来决定的15综合属性）表达式文法 ET+T| T or T Tn | b

8、 (只考虑整型和布尔型) 与每个非终结符T相连的属性type要么是int，要么是bool。与非终结符E的产生式相连的语义规则（断言）指明：两个T的属性必须相同。(注意：书上用Pascal语法描述) ET1 + T2 T1.type= =int & T2.type= =int;/断言 E.type = int E T1 or T2 T1.type= =bool & T2.type= =bool; /断言 E.type = bool T n T.type = int T b T.type = bool 16继承属性)说明语句中各种变量的类型信息的语义规则 T的属性type由关键字i

9、nt或float决定。属性type会沿着语法树传递到下面的结点使用。生 产 式语 义 规 则D TL T int T float L L1，idL idL.type=T.typeT.type=intT.type= float L1.type=L. type; id.type=L.type id.type=L.type17 int id1,id2,id3DL intLintL intTintintid2 intid1 intid3int，生 产 式语 义 规 则D TL T int T floatL L1，idL idL.type=T.type T.type=int T.type= float

10、L1.type=L. type; id.type=L.type id.type=L.type一个结点的继承属性值是由其父结点或兄弟结点的某些属性决定的18 一个翻译是符号串对的一个集合。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。 各个编译阶段定义一个翻译： 词法分析：（字符串，单词串） 语法分析：（单词串，语法树） 代码生成：（语法树，中间代码） （语法树，汇编语言） （语法树，机器代码） 语法制导翻译：将语义规则与语法规则相结合，在语法分析的过程中通过执行语义动作，计算语义属性值，从而完成预定的翻译工作。 19 定义：语法制导翻译（SDT） 为文法的每个产生式配上一个语义子程序

11、，在语法分析的过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的方法，称为。 20 综合属性）可用作台式计算器的简单算术表达式求值的语义描述语 义 规 则 L EE E1+TE TT T1 * FT FF (E)F iPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=i.lexval产 生 式21设表达式为35+4，则语义动作打印数值19LE19E15T4T15F4T3F3F 5i=4i5i3+*3*5+

12、4 的带语义信息的分析树：表示综合属性（很直观） 一个结点的综合属性值是其子结点的某些属性来决定的22 直观地说，一个语法制导翻译的基础是一个文法，其中翻译成分依附在每一产生式上。例4： 有文法 GS：SS0|S1|0|1 请按照语法制导翻译的方法，给出每个产生式相应的语义规则(或者说配上语义动作子程序)，它输出由S生成的二进制的数值。例如，对于输入101，输出5 。 23 解：拓展文法，加入新开始符号S和产生式SS。用 S.val 表示二进制值。语义规则如下： 产生式 语义规则 (0) SS (1) SS1 0 (2) SS1 1 (3) S 0 (4) S 1 print(S.val)S.

13、val= 2*S1.valS.val= 2*S1.val+1S.val= 0S.val= 124 何谓中间代码 (Intermediate code) (Intermediate representation) (Intermediate language) 源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。为什么要此阶段 逻辑结构清楚；利于不同目标机上实现同一种语言；利于进行与机器无关的优化；这些内部形式也能用于解释。中间代码的几种形式 逆波兰式，三元式和树，四元式， 25例 : A + B * ( C - D ) + E / ( C - D ) N逆波兰 : A B

14、 C D - * + E C D N / + 中缀表达式逆波兰表示算法： 设一个操作符栈，当读到操作数时，就立即输出该操作数，当扫描到操作符时，与栈顶操作符比较优先级，若栈顶操作符优先级高于栈外，则输出该栈顶操作符，反之，则栈外操作符入栈。对于赋值语句，则需规定赋值符号的优先级低于其他操作符。1. 逆波兰式（后缀式）26后缀表示法表示表达式，其最大的优点是易于计算机处理表达式。常用的算法是使用一个栈，自左至右扫描算术表达式（后缀表示），每扫描到运算对象，就把它推进栈；扫描到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施该运算，并将运算结果代替这两个运算对象而进栈；若是一目运算符，则对

15、栈顶元素执行该运算，并以运算结果代替该元素进栈，最后的结果留在栈顶。27分别给出下列表达式的后缀表示1. -a+b*(-c+d)2. X:=-(a+b)/(c-d)-(a+b*c)3. a=c b=d4. ab+c ada+bea-bc-d+*+Xab+-cd-/abc*+-:=ac= bd=abc+ ad ab+e 28生成后缀式的属性文法产产生生式式 语语义义规规则则 Sid:=E EE1+E2 EE1*E2 E -E1 E (E1) E id E num Print( | E.code | “:=”) E.code := E1.code | E2.code | ”+” E.

16、code := E1.code | E2.code | ”*” E.code := E1.code | “-“ E.code := E1.code E.code := E.code := num.val； 属属性性 code 表表示示生生成成的的代代码码 注释： | 表示代码序列的连接292. 三元式和树 三元式的一般形式：i:(,OPR1,OPR2) i是三元式编号，不同三元式不能有相同编号。 是运算符部分。 OPR1和OPR2是运算对象部分。30 三元式三元式: (1) ( - , C, D ) (2) ( *, B, (1) ) (3) ( +, A, (2) ) (4)

17、 ( - , C, D ) (5) ( , (4) , N ) (6) ( / , E, (5) ) (7) ( +, (3) , (6) ) 例 : A + B * ( C - D ) + E / ( C - D ) N31树形表示是三元式表示的翻版。例 : a + b * c二目运算对应二叉树，多目运算对应多叉树。32将赋值语句变换为语法结构树n基本函数结点构造uMknode(op,left,right) 建标记为op的算符结点,结点有两个域，分别为left和right.uMkleaf(id,entry) 建标记为id的叶结点，有一个entry域，它是指向符号表的入口。uMkleaf(nu

18、m,val)建标记为id的叶结点,有一个val域，是表示该数的值。33构造构造 a-4+c的语法树：的语法树： id指向c的入口id指向a 的入口num 4(1) p1:=mkleaf(id,entry a);(2) p2:=mkleaf(num, 4);(3) p3:=mknode(-，p1,p2)(4) p4:=mkleaf(id, entry c)(5) p5:=mknode(+,p3,p4)34语法制导定义(属性文法)产产生生式式 语语义义规规则则 Sid:=E EE1+E2 EE1*E2 E -E1 E (E1) E id E num S.p:= mknode(:=, mkleaf(

19、id, id.entry), E.p) E.p:= mknode(+, E1.p, E2.p) E.p:= mknode(*, E1.p, E2.p) E.p:= mknode(-, 0, E1.p) E.p:= E1.p E.p:= mkleaf(id, id.entry) E.p:=mkleaf(num,num.val) E.p 是语法结构树指针354. 四元式四元式的一般形式是： (,OPR1,OPR2，RESULT)* 其中是运算符。* OPR1和OPR2是第一，二分量，* RESULT是运算结果变量名。36例 : A + B * ( C - D ) + E / ( C - D ) N

20、37有时，为了更直观，也把四元式的形式写成简单赋值形式或更易理解的形式。比如把上述四元式序列写成： （1）T1 =C-D （2）T2 =B*T1 （3）T3 =A+T2 （4）38请将表达式-(a+b)*(c+d)-(a+b)分别表示成三元式和四元式序列。三元式 (1) (+, a, b) (2) (-, (1), /) (3)(+,c, d) (4) (*, (2), (3) (5) (+, a, b)(6) (-, (4), (5) 四元式(1) (+, a, b, t1)(2) (-, t1, /, t2)(3) (+, c, d, t3) (4) (*, t2, t3, t4) (5)

21、 (+, a, b, t5)(6) (-, t4, t5, t6) 398.4 简单赋值语句的翻译四元式形式： t:=arg1 op arg2语义属性： , E.place函数： lookup();过程： emit(t:=arg1 op arg2);(生成一条指令) newtemp;(分配一个工作单元)40产生式和语义描述：(1) S id:=E P:=lookup(); if Pnil then emit(P:= E.place) else error (2) E E1+E2 E.place:=newtemp; emit(E.place := E1.

22、place + E2.place) (3) E E1*E2 E.place:=newtemp; emit(E.place := E1.place * E2.place) (4) E - E1 E.place:=newtemp; emit(E.place := uminusE1.place (5) E (E1) E.place:=E1.place (6) E id P:=lookup(); if P nil then E.place:=P else error 41示例输入串为 X：=Y+I*JX,Y为实型，I，J为整型四元式四元式（* *i i, I,J,T, I,J,T1 1）(itr, T(itr, T1 1,_,T,_,T2 2) )(+(+r r,Y,T,Y,T2 2,T,T3 3 ) )(:=,T(:=,T3 3,_,X ),_,X )42采用语法制导翻译思想，表达式E的“值”的描述如