第8章语法制导与中间代码生成

1、8.1 8.1 属性文法属性文法 语法分析后的源程序=语义处理 静态语义是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为类型规则和作用域/可见性规则两大类 动态语义 程序单位描述的计算编译程序的语义处理工作 1 静态语义审查，即验证语法结构合法的程序是否有意义 2 生成中间代码静态语义审查 （1）类型检查。根据类型相容性要求，验证程序中执行的每个操作是否遵守语言的类型系统的过程，编译程序必须报告不符合类型系统的信息。 （2）控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语句的最小while

2、、for或switch语句。如果不存在包括它的这样的语句，则就报错。 （3）一致性检查。在很多场合要求对象只能被定义一次。例如Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。 （4）上下文相关性检查。比如，变量名字必须先声明后引用； （5）名字的作用域分析。各变量的作用域可能是不一样的，要通过分析明确各变量的作用域。解释执行动态语义 （计算）生成代码（中间代码或目标代码）例：有文法GE: E T1+T2 | T1 or T2 T num|true|false对输入串 2+6 语法树如图：ET+T26ET1.t=T2.t

3、T+26TT2.t=intT1.t=int类型检查的属性文法：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属性文法，语法制导翻译属性文法，语法制导翻译属性文法A(attribute grammar)是一个三元组:A=(G,V,F),其中 G:是一个上下文无关文法, V:有穷的属性集,每个属性与文法的一终结符或非终结符相连, F:关于属性的属性断言或谓词集.每个断言与一个产生式相联.而此断言只引用该产生式左端或右端的终结符

4、或非终结符相联的属性例如：定义表达式的文法如下： EE+E E(E)En 给出定义表达式值的属性文法。 我们为文法符号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、 属性文法属性文法:允许为每个终结符和非终结符配备一允许为每个终结符和非终结符配备一些属性的文法些属性的文法.它既能描述程序设计语言的语法它既能描述程序设计语言的语法,又为其语义描述提供了手段又为其语义描述提供了手段. 属性文法由属性文法由D.E.Knuth于于1968年引进年引进.后来才后来才被用于编译程序的设计。被用于编译程序的设计。 属性有不同的类型属性有不同的类型,可以象变量一样地被赋值。可以象变量一样地被赋值。赋值规则附加于语法规则之上。赋值与语法同时赋值规则附加于语法规则之上。赋值与语法同时进行进行,赋值过程就是语义处理过程。在推导语法树赋值过程就是语义处理过程。在推导语法树的时候

6、，诸属性的值被计算并通过赋值规则层层的时候，诸属性的值被计算并通过赋值规则层层传递。有的从语法规则左边向右边传传递。有的从语法规则左边向右边传,有的从右边有的从右边向左边传。语法推导树最后完成时向左边传。语法推导树最后完成时,就得到开始符就得到开始符号的属性值。也就是整个程序的语义号的属性值。也就是整个程序的语义.属性分为两种:继承属性和综合属性. inherited and synthesized(derived)attribute 继承属性的计算规则由顶向下, 综合属性的计算规则由底向上.例如定义表达式值的属性文法， E.val是一个综合属性的例子： EE1+E2 E.val := E1.

7、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=1 例8.1 一个简单台式计算器的定义 综合属性val语 义 规 则 L EE E1+TE TT T1 * FT FF (E)F digitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T

8、.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=digit.lexval产 生 式3*5+6的带注释的分析树的带注释的分析树只使用综合属性.LE.val=21E.val=15T.val=6T.val=15F.val=6T.val=3F.val=3F.val=5digit.lexval=6digit.lexval=5digit.lexval=3+*3*5+6的带注释的分析树的带注释的分析树继承属性继承属性一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。例8.2 添加标识符类型的语义描述： 继承属性继承属性type产生式语

9、 义 规 则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) DL.type= realL.type= realL.type= realT.type=realrealid2id1id3.继承属性（续）继承属性（续）Real id1,id2,id3的带注释的语法树的带注释的语法树, 8.2 语法制导概论 属性文法：描述语义规则。一个属性文法包含一个上下文无关文法和一系列语义规则

10、，这些语义规则附在文法的每一个产生式上。 语法制导翻译：在语法分析的同时，执行语义子程序： 1 检查静态语义 2 翻译(生成)中间(目标)代码 基于属性文法的处理过程即语法制导翻译是这样的： 对符号串进行语法分析，构造语法树，然后根据需要构造属性依赖图，遍历语法树并在语法树的各结点按语义规则进行计算。 8.2.1 计算语义规则 属性依赖图是一个有向图，用于描述分析树中的属性和属性间的互相依赖关系。 对于编译程序来讲，在单遍扫描中完成语义翻译工作非常重要。 8.2.2 S-属性文法和自下而上翻译 一般的属性文法的翻译器很难建立，然而L-属性文法的翻译器很容易建立。 L-属性文法的一个特例叫S-属

11、性文法。S-属性文法是只含有综合属性的属性文法。8.2.3 L-属性文法在自下而上分析中实现 L-属性文法允许一次遍历就计算出所以的属性值。8.3 8.3 中间代码的形式中间代码的形式 编译程序的总任务是把源语言的程序代码(源代码)翻译成目标语言的程序代码(目标代码)。 有些编译程序直接把源代码翻译目标代码，而有些编译程序首先把源代码翻译成一种中间语言的程序代码(中间代码),再生成目标代码。翻译方法可分为语法制导非语法制导中间代码的特点： 中间代码与机器无关，编译程序易于移植。 中间代码级进行优化较为容易。常见的中间代码形式有逆波兰式，三元式，四元式，树等。 在产生语法制导翻译程序时，完全根据

12、文法的产生式来生成的，有时为了达到语法制导的目的，不得不对现有产生式做一些修改，这也是语法制导方法的特点。 语法制导方法是一种形式化方法。它严格依赖于产生式结构。中间代码中间代码概述概述何谓中间代码何谓中间代码( Intermediate code) (Intermediate representation) (Intermediate language)是源程序的一种内部表示复杂性介于源语言和目标机语言之间中间代码的作用：使编译程序的逻辑结构更加简单明确利于进行与目标机无关的优化利于在不同目标机上实现同一种语言中间代码的形式： 逆波兰式、四元式、三元式、间接三元式、树中间代码的层次中间代码的

13、层次中间代码按照其与高级语言和机器语言的接近程度，可以分成以下三个层次：高级：最接近高级语言，保留了大部分源语言的结构。中级：介于二者之间，与源语言和机器语言都有一定差异。低级：最接近机器语言，能够反映目标机的系统结构，因而经常依赖于目标机。不同层次的中间代码举例不同层次的中间代码举例源语言源语言（高级语言）（高级语言）中间代码中间代码（高级）（高级）中间代码中间代码（中级）（中级）中间代码中间代码（低级）（低级）float a1020;aij+2;t1 = ai, j+2t1 = j + 2t2 = i * 20t3 = t1 + t2t4 = 4 * t3t5 = addr at6 = t

14、5 + t4t7 = *t6r1 = fp - 4r2 = r1 + 2r3 = fp - 8r4 = r3 * 20r5 = r4 + r2r6 = 4 * r5 r7 = fp 216f1 = r7 + r68.3.1 8.3.1 逆波兰式逆波兰式 运算符跟在所有运算对象的后面的表示法写出的式子称为后缀法或逆波兰法。例子： 中缀表示：a+b 后缀表示：ab+ 前缀表示：+ab 若用POS(E)表示中缀式E的逆波兰式则当E=E1T时有：POS(E)=POS(E1)|POS(T)|其中“|”表示串的“捻接”。POS(F)=POS(E) F=(E) POS(F)=i F=i POS(T)=POS

15、(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 POS(E)=POS(T) E=T 逆波兰式 中缀式 例：POS(A+B*C)= POS(A)|POS(B*C)|+ = ABC*+POS(A*B+c)= POS(A*B)|POS(C)|+ = AB*C+ 处理原则：F 运算对象出现的顺序与原来的相同F 运算符按实际运算顺序出现。F 运算符紧跟在运算对象的后

16、面出现，并且没有括号。逆波兰式的优点：转换为逆波兰式的语言中间形式后，容易实现中间代码的翻译或目标指令。 逆波兰式的生成： 运算对象向左移动 运算符与栈顶比较优先数 括号处理：左括号进栈，起间隔作用；右括号与左括号匹配抵消。 .波兰表达式表达式运算符栈运算对象运算符.进栈.退栈a*(b+c/d)#.#例子：a*(b+c/d)abcd/+*的推导*(b+c/d)#.#a(b+c/d)#.*#ab+c/d)#.(*#a+c/d)#.(*#abc/d)#.+(*#ab/d)#.+(*#abcd)#./+(*#abc)#./+(*#abcd)#.+(*#abcd/)#.(*#abcd/+#.*#abc

17、d/+#.#abcd/+*.abcd/+*动画演示8.3.2 8.3.2 表达式的三元式和树表达式的三元式和树一、三元式 三元式的一般形式：i:(,OPR1,OPR2) i是三元式编号，不同三元式不能有相同编号。 是运算符部分。 OPR1和OPR2是运算对象部分。例子： 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例子：tri(A*B+C) =tri(A*B)|tri(c)|2:(+,C) =1：(*， A，B) A*B 2：(+，C) A*B+C tri(A*B+

18、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+15:(, X, 0) X06:(, B) X0B7:(, D) (X0B)D8:(,)二、树 二目运算对应二叉树，多目运算对应多叉树。三元式可以用二叉树表示。例： (a+b*(c-d)-e/f的树。 (-，c， d ) c-d (*，b，(1) b*(c-d) (+，a，(2) a+b*(c-d) (/，e， f ) e/f (-,(3),(4

19、) 该题的树结构如下：cd-+/*-abef1234 该树的根后序为：abcd-*+ef/-,为该式的逆波兰式。58.3.3 8.3.3 四元式四元式 四元式的一般形式是： (,OPR1,OPR2，RESULT)* 其中是运算符。* OPR1和OPR2是第一，二分量，* RESULT是运算结果变量名。例： 求a:=b*c+b*d 的四元式1)(*，b，c，T1) b*c2)(*，b, d，T2)b*d3)(+，T1，T2，T3)b*c+b*d 4)(:=，T3，-，a)下面是表达式四元式的形式定义。 FOUR(T) RES(E)=RES(T)1E=T四元式中缀式FOUR(E1) 2E=E1+T

20、 FOUR(T)(+,RES(E1),RES(T),TEMP)RES(E)=TEMP(临时变量)空RES(F)=ID 7F=I 类似于2 6T=T1/F 类似于2 5.T=T1*F FOUR(F) RES(T)=RES(F) 4T=F 类似于2 3E=E1-T FOUR(E)RES(F)=RES(E) 8F=(E) 例：设有表达式A*(B+C*(A-B)则有 (-，A，B，T1)A-B (*，C，T1,T2)C*(A-B) (+，B，T2,T3)B+C*(A-B) (*，A，T3,T4) 引进一过程GENQT： GENQT():BEGIN RESULT:=NEWTEMP； QTJ:=(,SEM

21、S-2,SEMS-1,RESULT); SEMS-2:=RESULT； J:=J+1； S:=S-1 END 语法制导翻译算法如下： 空 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 语义子程序 产生式 例例 ； A + B * ( C - D ) + E / ( C - D ) N 逆逆波波兰兰 A B C D - * + E C D N / + 四四元元式式 (1) ( - C D T1 ) (2) ( * B T1 T2) (

22、3) ( + A T2 T3) (4) ( - C D T4) (5) ( T4 N T5) (6) ( / E T5 T6) (7) ( + T3 T6 T7)8.4 8.4 类型检查与类型转换类型检查与类型转换例：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为整形变量,其它为实型变量，则产生的四元式如下： 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)

23、j+17(tran，T6， T7)8(r/， T5， T7， T8)a*(i+1)/(j+1)9(r+， T2， T8， T9) 8.5 8.5 语句的中间代码及其语法制导生成语句的中间代码及其语法制导生成循环语句只考虑While型循环语句。所要考虑的语句文法如下：Gs：Si:=E | if E then S | if E then S else S | while E do S | begin B end | goto l | l:S BS | B; S 下面是语句四元式的形式定义:four(E) (then, res(E),) four(S1) (ifend,，) Sif E then S

24、1 four(E)(=:,res(E), ,i) Si:=E 四元式 源代码 (while,) Four(E) (do res(E),) four(S1) Swhile E do S1 four(E) (then,res(E),，) four(S1) (else, ) four(S2) (ifend,，) Sif E then S1 else S2 four(S) BS (label,，l) four(S1)Sl:S1four(B1) Four(S) BB1;S (goto,l) Sgoto l four(B) Sbegin B end whend(,) 例：设有语句 if X=Y+1 the

25、n X:=X*Y else while X0 do begin X:=X-1;Y:=Y+2 end则其四元式如下： 1.(+, Y, 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, , ) 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:

26、=Y+2 14.(whend, , , ) 15.(ifend, , , ) 语法制导用的新文法可设计如下：Gs：SAssig E | Ifthen S | Ifelse S | Whido S | begin B end | goto l | Label S Assigi:= Ifthenif E then Ifelse Ifthen S elseWhido While E doWhile whileLabel l:BS| B; S8.68.6 复合变量的中间代码复合变量的中间代码及其语法制导生成及其语法制导生成在Pascal中，变量形式定义是： Vid | VE | V.id称后两种为复合

27、变量。其中V又可以是任意变量，因此复合变量的形式可能是很复杂的。首先考虑下标变量VE情形。 ClASS POINT atp:LtpulLOW UP CTP ClEN 其中tp是成分类型的TYPEL地址，L是成分类型的长度。若用typ(V)和addr(V)表示变量V的类型(TYPEL地址)和V的始地址,则有： addr(VE)=addr(V)+(E-l)*L 其中 l=AINFLTYPELtp.TPOINT.LOW L=AINFLTYPELtp.TPOINT.CLEN 下面考虑域选择变量V.id情形。 设tpy(V)=tp,且TYPELtp.TCLASS=d.这是tp指向一个记录类型的内部表示：

28、 ClASS POINT dtp:RINFL 若用V.id中的id去查RINFL部分可得到id关于该记录的区距off。若用off (tp,id)表示id 关于tp记录的区距，则有：addr(V.id)=addr(V)+off(typ(V),id)例：设有PASCAL说明：TYPE at=ARRAY1.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

29、+(i-1)*5下面考虑VE和V.id情形的四元式。变量目标的任务是计算变量的地址，于是其四元式可描述如下：vfour(V): addr(V)=T其中vfour表示变量的四元式。变量的目标代码不一定要彻底计算出变量的地址并将它存于临时变量中。如果没有方便的目标代码,则计算X:=VE的过程大致是： 1) Addr(V)=T12) Value(E)T23) T1+ T2T3 4) T3X 但如果有方便的目标代码，则计算过程可以是： 1) Addr(V)T1 2) Value(E)T2 3) T2T1T3VE的四元式结构可设计如下： vfour(VE)：vfour(V) efour(E) (,ere

30、s(E),l,T1) (*,T1,L,T2) (,vres(V),T2,T)F eres(E)是表示E的结果变量。F vres(V)是表示V变量的地址所在的变量F l和L分别为数组的下界和成分类型长度。 用efour(E)形式表示现在表达式的四元式，eres(E)也类似。其中的vres(v)和efour(E)分别为SEMs-2和SEMs-1,而l和L则可按下法求出：tp:=SYMBLSEMS-2.TYPE l:=AINFLTYPELtp.LOW L:=AINFLTYPELtp.CLEN 域选择变量V.id的四元式可设计如下： vfour(V.id) : vfour(V)(., vres(V),

31、off,T) 例：假定有前例的说明，则有： 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)例：设有说明部分VAR x,i,j:integer; B:boolean a:ARRAY1.10OF1.5OF integer; b:ARRAY1.5 OF i

32、nteger则下列语句 aij:=bbi ai:=b 的四元式部分如下：I.1.(, i, l, T1) 2.(*, T1,5, T2) 3.(, a, T2,T3) ai 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) bbi13.(=:, T12, T6)aij:=bbi II. 1.(,i, 1, T1) 2.(*

33、, T1,5, T2) 3.(,a, T2,T3) ai 4.(=:,b, ,T3) ai:=b8.7 8.7 过程语句的中间代码及其语法制导生成过程语句的中间代码及其语法制导生成过程语句调用的四元式结构：g(E1,E2,En) efour(E1) efour(E2) .efour(En) (act,eres(E1), 1,OFF(X1)(act,eres(E2), 2,OFF(X2)(act,eres(En), n,OFF(Xn)(call,EADDR(g),) 当Xi为赋值形参时，i部分为1，当Xi为引用型形参时， i部分为0 。 如果是函数调用，那么最后一条为: (call,EADDR(

34、g),，NEWT) 在上述四元式中，Xi(i=1,2,.,n)为g的形参名。OFF(Xi)表示形参Xi的off值。例：设有如下说明部分 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)的四元式 1.(, i, 1, T1) 2.(*. T1, 1, T2) 3.(, a, T2, T3) ai 4.(act, T3, 0, 4) 5.(call,g, , T4) g(ai) 6.(*, T4, 3, T5) g(ai)*3 7.(+, y, 2.5,T6)