语法制导翻译和中间代码生成.ppt

1、第8章 语法制导翻译和中间代码生成,8.1概述 一、语义处理的任务：,编译中的语义处理是指两个功能： 第一 静态语义分析或静态审查。,静态语义分析通常包括： 类型检查。 控制流检查。控制流语句必须使控制转移到合法 的地方。 一致性检查。 相关名字检查。有时，同一名字必须出现两次或 多次。例如，Ada 语言程序中，循环或程序块可 以有一个名字，出现在这些结构的开头和结尾， 编译程序必须检查这两个地方用 的名字是相同的。 名字的作用域分析,第二 动态语义处理：如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。,二、属

2、性文法： 1、属性： 所谓属性，其涉及的概念比较广泛，常用以描述事物或人的特征、性质，品质等等。比如，谈到一个 物体，可以用“颜色”描述它，谈起某人，可以使用“有幽默感“来形容他。对编译程序使用的语法树的结点，可以用类型、值或存储位置来描述它。,2、属性文法(也称属性翻译文法) 它是在上下文无关文法的基础上，为每个文法符号(终结符或非终结符)配备若干相关的值（称为属性）。这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。,属性与变量一样，可以进行计算和传递。 属性加工的过程即是语义处理的过程。,对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。,假如语法分

3、析方法是自下而上的。在用某一产生式进行归约的同时就执行相应的语义动作，在分析出一个句子时，这个句子的值也就同时产生了,一个属性文法是一个三元组： A（G，V，F）， G: 是一个上下文无关文法 V: 有穷的属性集,每个属性与文法的一终结符 或非终 结符相连。 F: 关于属性的属性断言或谓词集.每个断言与一个 产生式相 联。一个断言就是一个语义规则， 描 述各属性的关系。,用法： 针对语义：为每个符号设置一个属性，终结符号用单词属性。 为每个产生式设置语义规则描述各属性的关系。,3、属性文法的定义：,例如：定义表达式的文法如下： EE+E E(E)En 给出定义表达式值的属性文法。,我们为文法符

4、号E引进属性符号val,用E.val表示E的值，属性计算规则以赋值语句的形式给出，附在每个产生式后，并用大括号括起来。为了明确E的不同出现位置，用上角标区别。终结符n的值是词法分析程序提供的，这里用n.lex表示。下面给出属性文法： EE1+E2 E.val := E1.val +E2.val E(E1) E.val := E1.val En E.val := n.lex 属性文法的主要思想有两点： 首先对于每个文法符号引进相关的属性符号； 其次对于每个产生式写出属性值计算的规则。,属性分为两种:继承属性和综合属性. 综合属性：在语法树中，一个结点的综合属性由该结点 的子结点的属性值确定。它的

5、计算规则由底 向上. 继承属性:在语法树中，一个结点的继承属性由该结点的 父结点/兄弟结点的属性确定。即它 的计算规 则由顶向下。,例如定义表达式值的属性文法， E.val是一个综合属性的例子： EE1+E2 E.val := E1.val +E2.val E(E1) E.val := E1.val En E.val := n.lex 考虑句子2（31）的求值顺序，将2（31）的语法树结点改为有附加属性的结点（这样的树称为带注释的语法树）： E.val=6 E.val=2 + E.val=4 n.lex=2 ( E.val=4 ) E.val=3 + E.val=1 n.lex=3 n.lex

6、=1,又例：一个简单台式计算器的定义 综合属性val,语 义 规 则,L E,E E1+T,E T,T T1 * F,T F,F (E),F digit,Print(E.val),E.val:=E1.val+T.val,E.val:=T.val,T.val:=T1.val F.val,T.val:=F.val,F.val:=E.val,F.val:=digit.lexval,产 生 式,3*5+4的带注释的分析树,只使用综合属性.,L,E.val=19,E.val=15,T.val=4,T.val=15,F.val=4,T.val=3,F.val=3,F.val=5,digit.lexval=

7、4,digit.lexval=5,digit.lexval=3,+,*,3*5+4的带注释的分析树,继承属性,一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。例，添加标识符类型的语义描述： 继承属性type,L1.in:=L.in,与L产生式相联的语义规则中有一个过程调用addtype，过程addtype的功能是把每个标识符的类型信息登录在符号表的相关项中。,句子 int id1,id2 的语法树，使用 表示属性的传递情况。,三、中间代码,是源程序的一种内部表示 复杂性介于源语言和目标机语言之间 中间代码的形式： 逆波兰式、四元式、三元式、间接三元式、 树,1 逆波兰记

8、号,逆波兰记号是最简单的一种中间代码表示形式。,这种表示法将运算对象写在前面，把运算符号写在后面，比如把a+b写成ab+，把a*b写成ab*，用这种表示法表示的表达式也称做后缀式。,后缀表示法表示表达式，其最大的优点是易于计算机处理表达式。常用的算法是使用一个栈，自左至右扫描算术表达式（后缀表示），每扫描到运算对象，就把它推进栈；扫描到运算符，若该运算符是二目的，则对栈顶部的两个运算对象实施该运算，并将运算结果代替这两个运算对象而进栈；若是一目运算符，则对栈顶元素执行该运算，并以运算结果代替该元素进栈，最后的结果留在栈顶。,例如 BCD*+（它的中缀表示为B+C*D，使用表示一目减）的计值过程

9、为：1. B进栈；2. 对栈顶元素施行一目减运算，并将结果代替栈顶，即B置于栈顶；3. C进栈； 4. D进栈；5. 栈顶两元素相乘，两元素退栈，相乘结果置栈顶；6. 栈顶两元素相加，两元素退栈，相加结果进栈，现在栈顶存放的是整个表达式的值。,逆波兰表示很容易扩充到表达式以外的范围。,只要遵守运算对象后直接紧跟它们的运算符的规 则即可。 比如把转语句GOTO L写为“L jump ， 运算对象L为语句标号，运算符jump表示转到 某个标号。再比如条件语句if E then S1 else S2 可表示为：ES1S2￥，把if then else看成三目运 算符，用￥来表示。,生成后缀式的属性文

10、法,注释： | 表示代码序列的连接,例:给出下列表达式的逆波兰式: (1) a*(-b+c) (2) a+b*(c+d/e),解 (1) abc+* (2) abcde/+*+,练习:P188 1,2 三元式和树形表示 另一类中间代码形式是三元式。把表达式及各种语句表示成一组三元式。每个三元式由三个部分组成，分别是：算符op，第一运算对象ARG1和第二运算对象ARG2。运算对象可能是源程序中的变量，也可能是某个三元式的结果，用三元式的编号表示。 例如a =b*c+b*d的表示为：（1）（*， b，c）（2）（*， b，d）（3）（+ （1）， （2）（4）（ （3）， a）,树形表示是三元式表

11、示的翻版。 例:a =b*c+b*d可表示成下面的树表示：,例 表达式 (A - 12) * B + 6 的语法结构树,将赋值语句变换为语法结构树,基本函数结点构造 Mknode(op,left,right) 建标记为op的算符结点,结点有两个域，分别为left和right. Mkleaf(id,entry) 建标记为id的叶结点，有一个entry域，它是指向符号表的入口。 Mkleaf(num,val)建标记为id的叶结点,有一个val域，是表示该数的值。,构造 a-4+c的语法树：,(1) p1:=mkleaf(id,entry a); (2) p2:=mkleaf(num, 4); (3

12、) p3:=mknode(-，p1,p2) (4) p4:=mkleaf(id, entry c) (5) p5:=mknode(+,p3,p4),语法制导定义(属性文法),E.p 是语法结构树指针,四元式和三元式的主要不同在于，四元式对中间结果的引用必须通过给定的名字，而三元式是通过产生中间结果的三元式编号。也就是说，四元式之间的联系是通过临时变量实现的。,有时，为了更直观，也把四元式的形式写成简单赋值形式或更易理解的形式。比如把上述四元式序列写成： （1）t1=b*c（2）t2=b*d（3）t3=t1+t2（4）a=t3 把（jump，L）写成goto L 把（jrop，B，C，L）写成i

13、f B rop C goto L,请将表达式-(a+b)*(c+d)-(a+b)分别表示成三元式、间接三元式和四元式序列。,三元式 (1) (+ a, b) (2) (+ c, d) (3) (* (1), (2) (4) (- (3), /)(5) (+ a, b)(6) (- (4), (5),间接三元式间接三元式序列 间接码表(1) (+ a, b) (1)(2) (+ c, d) (2) (3) (* (1), (2) (3) (4) (- (3), /) (4)(5) (- (4), (1) (1) (5),四元式(1) (+, a, b, t1)(2) (+, c, d, t2)(

14、3) (*, t1, t2, t3) (4) (-, t3, /, t4) (5) (+, a, b, t5)(6) (-, t4, t5, t6),实际上，在一个表达式中可能出现各种不同 类型的变量，而不象前面假定为同一类型。 因此，上例应改为P163 图8.10 的形式。,采用语法制导翻译思想，表达式E的值的描述如下： 产生式 语义动作 (0) SE print E.VAL(1) EE1+E2 E.VAL=E1.VAL+E2.VAL (2) EE1*E2 E.VAL=E1.VAL*E2.VAL (3) E(E1) E.VAL=E1.VAL(4) En E.VAL=n.LEXVAL 假如终结

15、符n可以是整数或实数，算符+和*的运算对象类型一致，语义处理增加类型匹配检查，请给出相应的语义描述。,(0) SE if error1 then print E.VAL EE1+E2 if E1.TYPE=int AND E2.TYPE=int thenbeginE.VAL:=E1.VAL + E2.VAL;E.YTPE:=int;end else if E1.TYPE=real AND E2.TYPE=real then begin E.VAL:=E1.VAL + E2.VAL;E.YTPE:=real; end else error=1 ,(2) EE1*E2 if E1.TYPE=int

16、 AND E2.TYPE=int then beginE.VAL:=E1.VAL * E2.VAL; E.YTPE:=int; end else if E1.TYPE=real AND E2.TYPE=real thenbeginE.VAL:=E1.VAL * E2.VAL; E.YTPE:=real;end else error=1,(3) E(E1) E.VAL:=E1.VAL; E.TYPE:=E1.TYPE (4) En E.VAL:=n.LEXVAL;E.TYPE:=n.LEXTYPE ,8.3 布尔表达式的翻译,程序设计语言中的布尔表达式有两个作用。 一是计算逻辑值 更多的情况是二

17、:用做改变控制流语句中的 条件表达式，如在if-then，if-then-else， 或是while-do语句中那样。,布尔表达式是由布尔算符and，or和not施于布尔变量或关系表达式而成。 即布尔表达式的形式为E1 rop E2，其中E1和E2都是算术表达式，rop是关系符，如，等等。,布尔表达式的翻译方法,通常，计算布尔表达式的值有两种办法: 第一种办法，如同计算算术表达式一样，步步 计算出各部分的真假值，最后计算出整个表 达式的值。,那么布尔表达式1 or（not 0 and 0）or 0的计算过程是： 1 or（not 0 and 0）or 01 or（1 and 0）or 01 o

18、r 0 or 01 or 01,用数值1表示true，用0表示false。,另一种计算方法是采取某种优化措施，只计算部分表达式. 例如要计算A or B，若计算出A的值为1，那么B的值就无需再计算了，因为不管B的值为何结果，A or B的值都为1。,控制语句中布尔表达式的翻译 现在讨论出现在 if then；if then else和while do等语句中的布尔表达式E的翻译。 这三种语句的语法为： Sif E then S1|if E then S1 else S2| while E do S1,控制语句的代码结构,(a) if E then S1,(b)|if E then S1 els

19、e S2,(c)while E do S1,翻译的基本思路：对于E为a rop b,形成代码为： If a rop b goto E.true goto E.false 对于E为 E1 or E2 的形式： 1、E1为真，则E为真，即E的真出口为E1的真 出口。 2、E1为假，计算E2，即E1的假出口应 为E2的第一个四元式标号，E2的真、假出 口与E的真、假出口一样。,我们使用Etrue和Efalse分别表示整个表达式ab or cd and ef的真、假出口，而Etrue和Efalse的值并不能在产生四元式的同时就知道。为了看清这一点，我们把该表达式放在条件语句中考虑，如语句 If ( a

20、b or cd and ef )then S1 else S2 的四元式序列见下页：,（p）goto（q） （p+1）（关于S2的四元式） （q）,If ( ab or cd and ef )then S1 else S2 的四元式序列为（1）ifabgoto（7） /*（7）是整个布尔表达式的真出口*/（2）goto（3）（3）ifcdgoto（5）（4）goto(p+1) /*（p+1）是整个布尔表达式的假出口*/（5）ifefgoto（7）（6）goto（p+1）（7） （关于S1的四元式） ,如：E1 or E2 E1有一个真出口，E2也有一个真 出口，将两个链合并为一条链。,（7）E

21、 true E.true:=nextstat; E.codebegin:= nextstat; emit(goto _) (8) E false E.false:=nextstat; E.codebegin:= nextstat; emit(goto _) ,以表达式 ab or cd and ef 为例，将分析产生语法树时的语义动作结果“真”“假”链情况注释在相应结点处，见P168 图8.14,控制语句的翻译,条件转移考虑if then，if then else和while do语句，在图8.12中已给出了它们的代码结构。这里我们使用下面文法GS定义这些语句：GS（1）Sif E then

22、S（2）|if E then S else S（3）|while E do S（4）|begin L end（5）|A（6）LL；S（7）|S其中各非终结符号的意义是：S-语句L-语句串A-赋值句E-布尔表达式,为了能及时回填有关四元式串的转移目标,对G(S)进行修改为G(S):,(1) SCS1 (8) Cif E then (2) STpS2 (9) TpCS else (3) SWdS3 (10) Wd W E do (4) S begin L end (11) Wwhile (5) S A (6) S Ls S1 (12) Ls L; (7) L S,(1) SCS1 S.Chain:

23、=merge( C.Chain, S1 .Chain),(8) Cif E then backpatch (E.true, nextstat) C.chain:=E.false,(2) STpS2 S.chain:= merge(Tp .Chain , S2 .Chain),(9) TpCS else q:=nextstat emit( goto _ ) backpatch(C.Chain, nextstat) Tp .Chain:=merge( S.chain, q) ,(11) Wwhile W.codebegin :=nextstat ,(10) Wd W E do backpatch(

24、E.true, nextstat) Wd .chain:=E.false Wd .codebegin:= W.codebegin ,SWdS3 backpatch(S3 .chain, Wd .codebegin) emit( goto Wd .codebegin S.chain:= Wd .chain,(4) S begin L end S.chain:= L.chain,(5) S A S.chain:= 0 /*空链*/,L S L.chain:=S.chain,(12) Ls L; backpatch( L.chain, nextstat),(6) L Ls S1 L.chain:=

25、S1 .chain ,按照上述文法产生式相应的语义动作，加上前述关于赋值句和布尔表达式的翻译法，语句while （AB） do if （CD） then X=Y+Z,将被翻译成如下的一串四元式：100if AB goto 102101goto107102ifCD goto 104103goto 100104T=Y+Z105X=T106goto 100107,while （AB） do if （CD） then X=Y+Z,for循环语句,for i=E1 step E2 until E3 do S1为了简单起见，假定E2总是正的。在这种假定下，上述循环句的意义等价于：i=E1；goto OVE

26、R；AGAIN： i=i+E2；OVER： if iE3 thenbegin S1； goto AGAIN end； 翻译见P173-P174,开关语句,开关语句（case语句或switch语句）,switch E ofcase V1：S1case V2：S2case Vn-1：Sn-1default：Snend,如果分叉不太多，case语句翻译成如下的一连串条件转移语句。t=E；L1：if tV1 goto L2； S1；goto next；L2：if tV2 goto L3；S2goto next；Ln-1：if tVn-1 goto Ln；Sn-1；goto next；Ln：Sn；nex

27、t：,另一种方法:P172 图8.15,goto语句,多数程序语言中的转移是通过标号和goto语句实现的。带标号语句的形式是LS；goto语句的形式是goto L。,当LS；语句被处理之后，标号L是定义了的。即在符号表中，将登记L的项的地址栏中登上语句S的第一个四元式的地址。,如果goto L是一个向上转移的语句，那么，当编译程序碰到这个语句时，L必是已定义了的。通过对L查找符号表获得它的定义地址p，编译程序可立即产生出相应于这个goto L的四元式如（j，p）。,如果goto L是一个向下转移的语句，也就是说，标号L尚未定义，那么，若L是第一次出现，则把它填进符号表中并标志上“未定义”。 由

28、于L尚未定义，对goto L只能产生一个不完全的四元式（goto），它的转移目标须待L定义时再回填进去。 在这种情况下，必须把所有那些以L为转移目标的四元式的地址全都记录下来，以便一旦L定义时就可对这些四元式进行回填。,我们将采用如图8.13所示的拉链办法，把所有以L为转移目标的四元式串在一起。链的首地址放在符号表中L的地址栏中,建链的方法是：若goto L中的标号L尚未在符号表中出现，则把L填入表中，置L的“定义否”标志为“未”，把nextstat填进L的地址栏中作为新链首，然后，产生四元式(p)（goto 0），其中0为链尾标志。若L已在符号表中出现（但“定义否”标志为“未”），则把它的地

29、址栏中的编号（记为p）取出，把nextstat填进该栏作新链首，然后，产生四元式(q)（goto p）。,一旦标号L定义时，我们将根据这条链回填那些待填转移目标的四元式。一般而言，假定用下面的产生式来定义标号语句,Slabel Slabeli：,1.若i所指的标识符（假定为L）不在符号表中，则把它填入，置类型为标号，定义否为已，地址为nextstat。2.若L已在符号表中但类型不为标号或定义否为已，则报告出错。3.若L已在符号表中，则把标志未改为已，然后，把地址栏中的链首（记为q）取出，同时把nextstat填在其中，最后，执行回填。,过程调用的四元式产生,过程调用的实质是把程序控制转移到子程

30、序,在转子之前,必须用某种办法把实参的信息传给调用的子程序。 传递实参信息方面有种种不同的方法,我们这里只讨论一种,即传实参地址的方式。 若实参是一个变量或数组，则直接传递地址。 若实参是表达式，如：A+B或2，则把它们的值计算出来，并存放在一个临时变量T中，然后传递T的地址。,传递实参地址的一个简单办法是：把实参地址逐一放在转指令的前面；,例：过程调用：Call S(A+B, Z)译为： 计算AB的值置于T中 /*T:=A+B */ Par T /*第一个实参的地址*/ Par Z /*第二个实参的地址*/ Call S /*转指令*/,为了处理在实参时记住每个实参的地址，以便最后把它们排在

31、Call指令之前，我们需要把这些地址存放起来，我们可用队列来存放。,例：一个描述过程调用语句的文法如下： (1) S call i () (2) 1 ,E (3) E,它的语法制导翻译见P178,例：写一个翻译过程调用语句的语义子程序。要求生 成的四元式序列在转指令之前的参数四元式par 按反序出现（与实在参数的顺序相反）。,过程调用语句的文法如下： (1) S call i () (2) 1 ,E (3) E,(1) E 建一个arglist.Stack栈， 它仅包含一项E.Place (2) 1 ,E 将E.Palce压入arglist.Stack栈， arglist.Stack:=arglist1.Stack (3) S call i () While arglist.Stacknull do begin 将arglist.Stack栈顶弹出生成 Gen(par,_,_,p) end; Gen(call,_,_,Entry(i) ,简单说明语句的翻译,程序设计语言中的说明语句旨在定义各种形式的有名实体，如常量、变量、数组、记录(结构)、过程、子程序等等，说明语句的种类也多，对象说明、变量说明、类型说明、过程说明等等。 编译程序把说明语句中定义的名字和性质登记在符号表中，用以检