语法制导翻译与中间代码生成实用教案

1、会计学1语法制导语法制导(zhdo)翻译与中间代码生成翻译与中间代码生成第一页，共87页。8.1 8.1 属性属性(shxng)(shxng)文文法法 语法分析后的源程序=语义处理(chl) 静态语义是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为(fn wi)类型规则和作用域/可见性规则两大类 动态语义 程序单位描述的计算编译程序的语义处理工作 1 静态语义审查，即验证语法结构合法的程序是否有意义 2 生成中间代码第1页/共87页第二页，共87页。静态语义审查 （1）类型检查。根据类型相容性要求，验证程序中执行的每个操作是否遵守语言的类

2、型系统的过程(guchng)，编译程序必须报告不符合类型系统的信息。 （2）控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语句的最小while、for或switch语句。如果不存在包括它的这样的语句，则就报错。第2页/共87页第三页，共87页。 （3）一致性检查。在很多场合要求对象只能被定义一次。例如Pascal语言规定(gudng)同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。 （4）上下文相关性检查。比如，变量名字必须先声明后引用； （5）名字的作用域分析解释执行动态语义 （计算）生

3、成代码（中间代码或目标代码）第3页/共87页第四页，共87页。例：有文法GE: E T1+T2 | T1 or T2 T num|true|false对输入(shr)串 2+6 语法树如图：ET+T26ET1.t=T2.tT+26TT2.t=intT1.t=int第4页/共87页第五页，共87页。类型检查的属性(shxng)文法：E T1+T2 T1.t=int AND T2.t=intE T1 or T2 T1.t=bool AND T2.t=boolT num T.t:=intT true T.t:=boolT false T.t:=bool第5页/共87页第六页，共87页。第6页/共87

4、页第七页，共87页。第7页/共87页第八页，共87页。第8页/共87页第九页，共87页。第9页/共87页第十页，共87页。语 义 规 则 L EE E1+TE TT T1 * FT FF (E)F digitPrint(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:=digit.lexval产 生 式第10页/共87页第十一页，共87页。LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5dig

5、it.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的带注释(zhsh)的分析树的分析树第11页/共87页第十二页，共87页。产生(chnshng)式语 义 规 则D TL T int T real L L1,idL idL.type:=T.typeT.type=integerT.type:=real L1.type:=L.type addtype(id.entry,L.type) addtype(id.entry,L.type)第12页/共87页第十三页，共87页。DL.type= realL.type= realL.type= realT.t

6、ype=realrealid2id1id3.继承属性继承属性(shxng)（续）（续）Real id1,id2,id3的带注释的语法树的带注释的语法树,第13页/共87页第十四页，共87页。 8.2 语法制导(zhdo)概论 属性文法：描述语义规则。一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每一个产生式上。 语法制导翻译：在语法分析的同时，执行语义子程序： 1 检查静态语义 2 翻译(生成)中间(目标(mbio)代码第14页/共87页第十五页，共87页。 基于属性文法的处理过程即语法制导翻译是这样的： 对符号串进行语法分析，构造语法树，然后根据(gnj)需要构造

7、属性依赖图，遍历语法树并在语法树的各结点按语义规则进行计算。 8.2.1 计算语义规则 属性依赖图是一个有向图，用于描述分析树中的属性和属性间的互相依赖关系。 对于编译程序来讲，在单遍扫描中完成语义翻译(fny)工作非常重要。第15页/共87页第十六页，共87页。 8.2.2 S-属性文法和自下而上翻译(fny) 一般的属性文法的翻译(fny)器很难建立，然而L-属性文法的翻译(fny)器很容易建立。 L-属性(shxng)文法的一个特例叫S-属性(shxng)文法。S-属性(shxng)文法是只含有综合属性(shxng)的属性(shxng)文法。8.2.3 L-属性文法在自下而上(z xi

8、r shn)分析中实现 L-属性文法允许一次遍历就计算出所以的属性值。第16页/共87页第十七页，共87页。8.3 8.3 中间代码的形式中间代码的形式(xngsh)(xngsh) 编译程序的总任务是把源语言的程序代码(源代码)翻译成目标(mbio)语言的程序代码(目标(mbio)代码)。 有些编译程序直接把源代码翻译目标代码，而有些编译程序首先把源代码翻译成一种(y zhn)中间语言的程序代码(中间代码),再生成目标代码。第17页/共87页第十八页，共87页。翻译方法(fngf)可分为语法(yf)制导非语法(yf)制导中间代码的特点： 中间代码与机器无关，编译程序易于移植。 中间代码级进行优

9、化较为容易。常见的中间代码形式有逆波兰式，三元式，四元式，树等。 第18页/共87页第十九页，共87页。 在产生语法制导翻译程序时，完全根据文法的产生式来生成的，有时为了达到语法制导的目的，不得不对现有产生式做一些修改，这也是语法制导方法(fngf)的特点。 语法制导(zhdo)方法是一种形式化方法。它严格依赖于产生式结构。第19页/共87页第二十页，共87页。第20页/共87页第二十一页，共87页。第21页/共87页第二十二页，共87页。源语言源语言（高级语言）（高级语言）中间代码中间代码（高级）（高级）中间代码中间代码（中级）（中级）中间代码中间代码（低级）（低级）float a1020;

10、aij+2;t1 = ai, j+2t1 = j + 2t2 = i * 20t3 = t1 + t2t4 = 4 * t3t5 = addr at6 = t5 + t4t7 = *t6r1 = fp - 4r2 = r1 + 2r3 = fp - 8r4 = r3 * 20r5 = r4 + r2r6 = 4 * r5 r7 = fp 216f1 = r7 + r6第22页/共87页第二十三页，共87页。8.3.1 8.3.1 逆波兰逆波兰(b (b ln)ln)式式 运算符跟在所有运算对象的后面(hu mian)的表示法写出的式子称为后缀法或逆波兰法。例子(l zi)： 中缀表示：a+b

11、后缀表示：ab+ 前缀表示：+ab 若用post(E)表示中缀式E的逆波兰式则当E=E1T时有：第23页/共87页第二十四页，共87页。POS(E)=POS(E1)|POS(T)|其中(qzhng)“|”表示串的“捻接”。POS(F)=POS(E) F=(E) POS(F)=I F=I POS(T)=POS(T(1)|POS(F)|/ T=T(1)/F POS(T)=POS(T(1)|POS(F)|* T=T(1)*F POS(T)=POS(F) T=F POS(E) =POS(E(1)|POS(T)|- E=E(1)-T POS(E)=POS(E(1)|POS(T)|+ E=E(1)+T P

12、OS(E)=POS(T) E=T 逆波兰式 中缀式 第24页/共87页第二十五页，共87页。例子(l zi)：pos(A+B*C)=pos(A)|pos(B*C)|+=ABC*+pos(A*B+c)=pos(A*B)|pos(C)|+=AB*C+ 处理原则： 运算对象出现的顺序与原来的相同 运算符按实际运算顺序出现。 运算符紧跟(jn n)在运算对象的后面出现，并且没有括号。第25页/共87页第二十六页，共87页。逆波兰式的优点：转换为逆波兰式的语言(yyn)中间形式后，容易实现中间代码的翻译或目标指令。 逆波兰式的生成： 运算对象向左移动 运算符与栈顶比较优先数 括号(kuho)处理：左括号

13、(kuho)进栈，起间隔作用；右括号(kuho)与左括号(kuho)匹配抵消。 第26页/共87页第二十七页，共87页。.波兰(b ln)表达式表达式运算符栈运算(yn sun)对象运算符.进栈.退栈第27页/共87页第二十八页，共87页。a*(b+c/d)#.#例子(l zi)：a*(b+c/d)abcd/+*的推导第28页/共87页第二十九页，共87页。*(b+c/d)#.#a第29页/共87页第三十页，共87页。(b+c/d)#.*#a第30页/共87页第三十一页，共87页。b+c/d)#.(*#a第31页/共87页第三十二页，共87页。+c/d)#.(*#ab第32页/共87页第三十三

14、页，共87页。c/d)#.+(*#ab第33页/共87页第三十四页，共87页。/d)#.+(*#abc第34页/共87页第三十五页，共87页。d)#./+(*#abc第35页/共87页第三十六页，共87页。)#./+(*#abcd第36页/共87页第三十七页，共87页。)#.+(*#abcd/第37页/共87页第三十八页，共87页。)#.(*#abcd/+第38页/共87页第三十九页，共87页。#.*#abcd/+第39页/共87页第四十页，共87页。#.#abcd/+*第40页/共87页第四十一页，共87页。.abcd/+*第41页/共87页第四十二页，共87页。动画演示(ynsh)第42页

15、/共87页第四十三页，共87页。8.3.2 8.3.2 表达式的三元表达式的三元(sn (sn yun)yun)式和树式和树一、三元式 三元式的一般形式：i:(,OPR1,OPR2) i是三元式编号，不同(b tn)三元式不能有相同编号。 是运算符部分。 OPR1和OPR2是运算对象部分。第43页/共87页第四十四页，共87页。例子(l zi)： a:=b*c+b*d的相应三元组(*, b, c) b*c(*, b, d) b*d(+, (1),(2) b*c+b*d(:=,(3), a) a:=b*c+b*d例子(l zi)：tri(A*B+C) =tri(A*B)|TRI(c)|2:(+,

16、C) =1：(*， A，B) A*B 2：(+，C) A*B+C 第44页/共87页第四十五页，共87页。tri(A*B+C/D)= 1：(*， A， B) A*B 2：(/， C， D) C/D 3：(+，) A*B+C/Dtri(ABXY+1(X0B)D)=1:(+, Y, 1) Y+1 2:(,X,) XY+1 3:(,B,) BXY+1 4:(,A,) ABXY+1第45页/共87页第四十六页，共87页。5:(, X, 0) X06:(, B) X0B7:(, D) (X0B)D8:(,)二、树 二目运算对应二叉树，多目运算对应多叉树。三元(sn yun)式可以用二叉树表示。第46页/

17、共87页第四十七页，共87页。例： (a+b*(c-d)-e/f的树。1)(-，c， d ) c-d2)(*，b，(1) b*(c-d)3)(+，a，(2) a+b*(c-d)4)(/，e， f ) e/f5)(-,(3),(4) 该题的树结构如下(rxi)：第47页/共87页第四十八页，共87页。cd-+/*-abef1234 该树的根后序(hu x)为：abcd-*+ef/-,为该式的逆波兰式。5第48页/共87页第四十九页，共87页。8.3.3 8.3.3 四元四元(s yun)(s yun)式式 四元(s yun)式的一般形式是： (,OPR1,OPR2，RESULT) 其中是运算符。

18、 OPR1和OPR2是第一，二分量， RESULT是运算结果变量名。例： 求a:=b*c+b*d 的四元(s yun)式第49页/共87页第五十页，共87页。1)(*，b，c，T1) b*c2)(*，b, d，T2)b*d3)(+，T1，T2，T3)b*c+b*d 4)(:=，T3，-，a)下面是表达式四元式的形式(xngsh)定义。 FOUR(T) RES(E)=RES(T)1E=T四元式中缀式FOUR(E1) 2E=E1+T 第50页/共87页第五十一页，共87页。FOUR(T)(+,RES(E1),RES(T),TEMP)RES(E)=TEMP(临时变量)空RES(F)=ID 7F=I

19、类似于2 6T=T1/F 类似于2 5.T=T1*F FOUR(F) RES(T)=RES(F) 4T=F 类似于2 3E=E1-T 第51页/共87页第五十二页，共87页。FOUR(E)RES(F)=RES(E) 8F=(E) 例：设有表达式A*(B+C*(A-B)则有 1.(-，A，B，T1)A-B2.(*，C，T1,T2)C*(A-B)3.(+，B，T2,T3)B+C*(A-B)4.(*，A，T3,T4) 第52页/共87页第五十三页，共87页。 引进一过程GENQT： GENQT():BEGIN RESULT:=NEWTEMP； QTJ:=(,SEMS-2,SEMS-1,RESULT)

20、; SEMS-2:=RESULT； J:=J+1； S:=S-1 END 语法(yf)制导翻译算法如下：第53页/共87页第五十四页，共87页。 空 F-(E) SEMs:=EADDR(id);s:=s+1 F-I GENQT(/) T-T/F GENQT(*) T-T*F 空 T-F GENQT(-) E-E-T GENQT(+) E-E+T 空 E-T 语义子程序 产生式 第54页/共87页第五十五页，共87页。例例 ； A + B * ( C - D ) + E / ( C - D ) N 逆波兰逆波兰 A B C D - * + E C D N / + 四元式四元式 (1) ( - C

21、 D T1 ) (2) ( * B T1 T2) (3) ( + A T2 T3) (4) ( - C D T4) (5) ( T4 N T5) (6) ( / E T5 T6) (7) ( + T3 T6 T7)第55页/共87页第五十六页，共87页。8.4 8.4 类型类型(lixng)(lixng)检查与类检查与类型型(lixng)(lixng)转换转换例：a+b 3+5=8 3.2+5=3.2+5.0=8.2 3+T=?例：设有一表达式X*2+a*(i+1)/(j+1)其中i和j为整形(zhng xng)变量,其它为实型变量，则产生的四元式如下： 第56页/共87页第五十七页，共87页

22、。1(tran，2， T1)2(r*， x，T1， T2) x*23(i+， i， 1， T3) i+14(tran，T3，T4)5(r*， a， T4，T5) a*(i+1)6(i+， j， 1， T6) j+17(tran，T6， T7)8(r/， T5， T7， T8)a*(i+1)/(j+1)9(r+， T2， T8， T9) 第57页/共87页第五十八页，共87页。8.5 8.5 语句的中间代码及其语法语句的中间代码及其语法(yf)(yf)制导制导生成生成循环语句只考虑(kol)While型循环语句。所要考虑(kol)的语句文法如下：Gs：Si:=E | if E then S |

23、if E then S else S | while E do S | begin B end | goto l | l:S BS | B; S第58页/共87页第五十九页，共87页。 下面(xi mian)是语句四元式的形式定义:four(E) (then, res(E),) four(S1) (ifend,，) Sif E then S1 four(E)(=:,res(E), ,i) Si:=E 四元式 源代码 第59页/共87页第六十页，共87页。(while,) Four(E) (do res(E),) four(S1) Swhile E do S1 four(E) (then,res

24、(E),，) four(S1) (else, ) four(S2) (ifend,，) Sif E then S1 else S2 第60页/共87页第六十一页，共87页。four(S) BS (label,，l) four(S1)Sl:S1four(B1) Four(S) BB1;S (goto,l) Sgoto l four(B) Sbegin B end whend(,) 第61页/共87页第六十二页，共87页。例：设有语句(yj) if X=Y+1 then X:=X*Y else while X0 do begin X:=X-1;Y:=Y+2 end则其四元式如下： 1.(+, Y,

25、 1, T1) Y+1 2.(=, X, T1, T2) X=Y+1 3.(then,T2, ，)4.(*, X, Y, T3) X*Y5.(=:, T3, , X ) X:=X*Y6.(else, , ) 第62页/共87页第六十三页，共87页。 7.(while, , ) 8.(, X , 0, T4) X0 9.(do, T4, , )10.(-, X, 1, T5) X-111.(=:, T5, , X) X:=X-112.(+, Y, 2, T6) Y+2 13.(=:, T6, , Y) Y:=Y+2 14.(whend, , , ) 15.(ifend, , , ) 第63页/共

26、87页第六十四页，共87页。语法制导用的新文法可设计(shj)如下：Gs：SAssig E | Ifthen S | Ifelse S | Whido S | begin B end | goto l | Label S Assigi:= Ifthenif E then 第64页/共87页第六十五页，共87页。Ifelse Ifthen S elseWhido While E doWhile whileLabel l:BS| B; S第65页/共87页第六十六页，共87页。8.6 8.6 复合变量的中间代码复合变量的中间代码及其语法制导及其语法制导(zhdo)(zhdo)生成生成在Pascal

27、中，变量形式定义是： Vid | VE | V.id称后两种为复合变量。其中V又可以是任意变量，因此复合变量的形式可能(knng)是很复杂的。首先考虑下标变量VE情形。 ClASS POINT atp:LtpulLOW UP CTP ClEN第66页/共87页第六十七页，共87页。 其中tp是成分类型的TYPEL地址(dzh)，L是成分类型的长度。若用typ(V)和addr(V)表示变量V的类型(TYPEL地址(dzh)和V的始地址(dzh),则有： addr(VE)=addr(V)+(E-l)*L 其中 l=AINFLTYPELtp.TPOINT.LOW L=AINFLTYPELtp.TPO

28、INT.CLEN 下面(xi mian)考虑域选择变量V.id情形。第67页/共87页第六十八页，共87页。 设tpy(V)=tp,且TYPELtp.TCLASS=d.这是tp指向(zh xin)一个记录类型的内部表示： ClASS POINT dtp:RINFL 若用V.id中的id去查RINFL部分可得到id关于(guny)该记录的区距off。若用off (tp,id)表示id 关于(guny)tp记录的区距，则有：addr(V.id)=addr(V)+off(typ(V),id)第68页/共87页第六十九页，共87页。例：设有PASCAL说明(shumng)：TYPE at=ARRAY1

29、.10OF1.5OF integer; rt=RECORD d:real; a:at; b:at END;VAR c,g:at;r,u:rt; 则有：addr(ci)=c+(i-1)*5 addr(cij)=c+(i-1)*5+(j-1)*1 addr(u.a)=u+1 addr(u.ai)=u+1+(i-1)*5第69页/共87页第七十页，共87页。下面考虑VE和V.id情形的四元式。变量目标的任务是计算变量的地址，于是其四元式可描述如下：vfour(V): addr(V)=T其中vfour表示(biosh)变量的四元式。变量的目标代码不一定要彻底计算出变量的地址并将它存于临时变量中。如果没

30、有方便的目标代码,则计算X:=VE的过程大致是： 第70页/共87页第七十一页，共87页。1) Addr(V)=T12) Value(E)T23) T1+ T2T3 4) T3X 但如果(rgu)有方便的目标代码，则计算过程可以是： 1) Addr(V)T1 2) Value(E)T2 3) T2T1T3第71页/共87页第七十二页，共87页。VE的四元(s yun)式结构可设计如下： vfour(VE)：vfour(V) efour(E) (,eres(E),l,T1) (*,T1,L,T2) (,vres(V),T2,T)F eres(E)是表示E的结果变量。F vres(V)是表示V变量

31、的地址所在(suzi)的变量F l和L分别为数组的下界和成分类型长度。 第72页/共87页第七十三页，共87页。用efour(E)形式表示现在表达式的四元式，eres(E)也类似(li s)。其中的vres(v)和efour(E)分别为SEMs-2和SEMs-1,而l和L则可按下法求出：tp:=SYMBLSEMS-2.TYPE l:=AINFLTYPELtp.LOW L:=AINFLTYPELtp.CLEN 域选择(xunz)变量V.id的四元式可设计如下： vfour(V.id) : vfour(V)(., vres(V),off,T) 第73页/共87页第七十四页，共87页。例：假定(ji

32、dng)有前例的说明，则有： vfour(ci) : 1.(, i, 1, T1) 2.(*, T1,5, T2) 3.(, c, T2,T3)vfour(cij): 1. vfour(ci) 4.(, j, 1,T4) 5.(*, T4,1,T5) 6.(, T3,T5,T6)vfour(u.ai): 1.(., u,off,T1) 2.(,i, 1, T2) 3.(*, T2,5, T3) 4.(,T1, T3,T4)第74页/共87页第七十五页，共87页。例：设有说明部分(b fen)VAR x,i,j:integer; B:boolean a:ARRAY1.10OF1.5OF inte

33、ger; b:ARRAY1.5 OF integer则下列语句 aij:=bbi ai:=b 的四元式部分(b fen)如下：I.1.(, i, l, T1) 2.(*, T1,5, T2) 3.(, a, T2,T3) ai第75页/共87页第七十六页，共87页。 4.(, j, 1, T4) 5.(*, T4, 1, T5)可省 6.(, T3, T5, T6) aij 7.(, i, 1, T7) 8.(*, T7, 1, T8)可省 9.(, b, T8, T9) bi10.(, T9, 1, T10)11.(*, T10,1, T11)可省12.(, b, T11, T12) bbi

34、13.(=:, T12, T6)aij:=bbi 第76页/共87页第七十七页，共87页。II. 1.(,i, 1, T1) 2.(*, T1,5, T2) 3.(,a, T2,T3) ai 4.(=:,b, ,T3) ai:=b第77页/共87页第七十八页，共87页。8.7 8.7 过程语句的中间代码及其语法制导过程语句的中间代码及其语法制导(zhdo)(zhdo)生成生成过程(guchng)语句调用的四元式结构：g(E1,E2,En) efour(E1) efour(E2) .efour(En) (act,eres(E1), 1,OFF(X1)(act,eres(E2), 2,OFF(X2

35、)(act,eres(En), n,OFF(Xn)(call,EADDR(g),)第78页/共87页第七十九页，共87页。 当Xi为赋值形参时，i部分为1，当Xi为引用型形参时， i部分为0 。 如果(rgu)是函数调用，那么最后一条为: (call,EADDR(g),，NEWT) 在上述四元式中，Xi(i=1,2,.,n)为g的形参名。OFF(Xi)表示形参Xi的off值。第79页/共87页第八十页，共87页。例：设有如下说明(shumng)部分 TYPE arr=ARRAY1.10 OF integer; VAR x,y:real; i:integer; a:arr; FUNCTION f(VAR.Y1:real; Y2:integer;Y3:real):real;BEGINEND;FUNCTION g(VAR Z:integer):integer;BEGINEND 则有：f(x,g(ai)*3,y+2.5) 第80页/共87页第八十一页，共87页。 1.(, i, 1, T1) 2.(*. T1, 1, T2) 3.(, a, T2, T3) ai 4.(act, T3, 0, 4