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

1、第8章 语法制导翻译和中间代码生成,编译程序的任务是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等同。 编译中的语义处理指以下两个功能： 审查每个语法结构的静态语义 如果静态语义正确则将源程序翻译成中间代码或生成实际的目标代码,第8章 语法制导翻译和中间代码生成,8.1 属性文法 8.2 语法制导翻译概论 8.3 中间代码的形式 8.4 简单赋值语句的翻译 8.5 布尔表达式的翻译 8.6 控制结构的翻译 8.7 说明语句的翻译 8.8 数组的翻译,8.1 属性文法,目前很多编译程序采用属性文法和语法制导翻译方法对语义处理工作进行比较规范的描述。 属性：用于描述事物或人的特征、性质和

2、品质等。 一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生式上。 所谓语法制导翻译是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作。,8.1 属性文法,属性文法(attribute grammar)是一个三元组： A=(G,V,F)，其中 G：一个上下文无关文法。 V：一个属性的有穷集，每个属性与文法的一个终结符或非终结符相连，这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。 F：关于属性的断言或一组属性的计算规则(称为语义规则)。断言或语义规则

3、与一个产生式相联，引用该产生式左端或右端的终结符或非终结符相联的属性。,8.1 属性文法,例，文法G： E T1+T2 E T1 or T2 T num T true T false,类型检查的属性文法 E T1+T2 T1.t=int AND T2.t=int E T1 or T2 T1.t=bool AND T2.t=bool T num T.t=int T true T.t=bool T false T.t=bool 与每个非终结符T相联的有属性t，t要么是int，要么是bool。与非终结符E的产生式的断言指明：两个T的属性必须相同。,E E T1.t=int AND T2.t=int

4、T + T T1.t=int T + T T2.t=int 3 4 3 4,8.1 属性文法,属性通常分为两类：综合属性和继承属性。 属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条规则的形式为b:=f(c1,c2ck) f是一个函数，b和c1,c2ck是该产生式文法符号的属性. 并且 （1）如果b是A的一个属性,c1,c2ck是产生式右部文法符号的属性或A的其他属性,则称b是A的综合属性。 （2）如果b是产生式右部某个文法符号X的一个属性,并且c1,c2ck是A或产生式右边任何文法符号的属性,则称b是文法符号X 的继承属性。 在两种情况下，我们都说属性b依赖于属性c1,c2c

5、k,8.1 属性文法,非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性。 终结符只有综合属性，它们由词法程序提供。 出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。 Eg. 如非终结符A,B和C， 其中A有一个继承属性a和一个综合属性b, B有综合属性c, C有继承属性d 在产生式ABC的语义规则中可计算 A.b:=f(A.a,B.c,C.d) Eg. A.b:=A.a+B.c C.d:=f(A.a,A.b,B.c) Eg. C.d:=B.c 而属性A.a和 B.c是在其他

6、地方计算的。,8.1 属性文法,语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码（中间）生成等等。通常把这样的语义规则写成过程调用或过程段。,8.1 属性文法,属性文法和综合属性的示例 简单算术表达式文法及其求值的语义描述 产生式 语义规则 L E Print(E.val) E E1+T E.val:=E1.val+T.val E T E.val:=T.val T T1*F T.val:=T1.val F.val T F T.val:=F.val F (E) F.val:=E.val F digit F.val:=digit.lexval E.Val，T.val，F.val

7、是综合属性。 digit.lexval是综合属性，其值由词法分析程序提供。,8.1 属性文法,属性文法和继承属性的示例 描述说明语句文法及其语句中各种变量的类型信息的语义规则。 产生式 语义规则 D TL L.in:=T.type T int 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) 过程addtype的功能是把每个标识符的类型信息登录到符号表的相关项中。,Real id1, id2, id3 每个L结点都带有继承属性的语法

8、树,8.2 语法制导翻译概论,一个一般的属性文法的翻译器是很难建立的，然而有一大类属性文法的翻译器是很容易建立的，那就是L-属性文法。首先介绍L-属性文法的一个特例S-属性文法。 S-属性文法和自下而上的翻译 S-属性文法是只含综合属性的属性文法。 综合属性可以在分析输入符号串的同时自下而上的来计算。S属性文法的翻译器通常可借助于LR分析器实现。将原来的分析栈扩充一个语义栈，用于存放符号的综合属性，使得每个文法符号都有一个语义值。每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。,8.2 语法制导翻译概论,S-属性文法和自下而上的翻译示例 简单算术表达式文法及其求值的语

9、义描述 产生式 语义规则 L E Print(E.val) E E1+T E.val:=E1.val + T.val T T1* F T.val:=T1.val F.val T F T.val:=F.val F (E) F.val:=E.val F digit F.val:=digit.lexval E.Val，T.val，F.val是综合属性 digit.lexval是综合属性，其值由词法分析程序提供。,8.2 语法制导翻译概论,串*的最左规约和计值过程,L Print(E.val) E.val E.val + T.val T.val T.val * F.val F.val F.val 5

10、2 3,分析时参照书 P142 表7.8表达式文法的改进的SLR(1)分析表,8.2 语法制导翻译概论,一个属性文法称为L属性文法，如果对于每个产生式AX1X2Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj（1jn）的一个继承属性且这个继承属性仅依赖于： （1）产生式中Xj左边符号X1，X2，Xj-1的属性； （2）A的继承属性。 S属性文法一定是L属性文法，因为(1)、(2)限制只用于继承属性。 L属性文法允许一次遍历就计算出所有属性的值,8.2 语法制导翻译概论,L-属性文法的示例： 描述说明语句文法及其语句中各种变量的类型信息的语义规则 产生式 语义规则 D TL1 L1.i

11、n:=T.type T int T.type:=integer T real T.type:=real L2 L3,id L3.in:=L2.in addtype(id.entry,L.in) L id addtype(id.entry,L.in) L1.in，L3.in是继承属性。T.type为综合属性。,8.2 语法制导翻译概论,L属性文法在自上而下分析中的实现 例： 将中缀表达式翻译成后缀表达式的属性文法： 设有文法GE： EE addop T print(addop.Lexeme) | T Tnum print(num.val) addop表示+或-,串2+3-5的语法树(根据文法G)

12、 E T R 22 + T+ R 33 - T- R 55 在对串的语法分析过程中同时执行语义动作。虚线连接的语义结点表示执行的语义动作。 输出串为：23+5-,这种自上而下的语法分析过程（最左推导）,从概念上说可以看成是深度优先建立语法树的过程，因此，我们可以在语法分析的同时执行L属性文法的语义动作。,将G改写为G以满足LL(1)文法的条件 ETR Raddop T print(addop.lexeme) R1 | Tnum print(num.val),8.2 语法制导翻译概论,L属性文法在自下而上分析中的实现 例： 将中缀表达式翻译成后缀表达式的属性文法： 设有文法GE： EE addo

13、p T print(addop.Lexeme) | T Tnum print(num.val) addop表示+或-,串2+3-5的语法树 E E - T - E + T + 5 5 T 3 3 2 2 在对串的语法分析过程中同时执行语义动作。虚线连接的语义结点表示执行的语义动作。 输出串为：23+5-,自下而上的语法分析过程（最左规约），我们可以在语法分析的同时实现L属性文法的计算。,8.2 语法制导翻译概论,通过改变基础文法用综合属性代替继承属性,例：文法GD D L : T T int | char L L , id | id,重构文法为： D id L D.type:=L.type;

14、addtype(id.entry,D.type) L , id L1 L.type:= L1.type; addtype(id.entry,L.type) L : T L.type:= T.type Tint T.type:=int Tchar T.type:=char ,串id,id:int的 语法树 D id L , id L : T int,串id,id:int的语法树 D L ： T L , id int id,8.3 中间代码的形式,中间代码： 源程序的一种内部表示，不依赖目标机的结构，易于机械生成。 使用中间代码可以逻辑结构清楚；利于不同目标机上实现同一种语言； 中间代码的几种形式

15、 逆波兰 三元式 树 四元式,8.3 中间代码的形式,四元式的组成 Op，Arg1，Arg2，Result Eg.,a:=b*c+b*d的四元式为 (*，b，c，t1) (*，b，d，t2) (+，t1，t2，t3) (:=, t3，-，a),t1 := b*c t2 := b*d t3 := t1+t2 a: = t3,四元式(jump，-，-，L) 或写为 goto L 四元式(jrop，B，C，L) 或写为 if B rop C goto L,或写为：,8.4 简单赋值语句的翻译,语义动作中的几个记号： E.place 语义变量，表示存放非终结符E值的变量名在符号表的登记项。 looku

16、p() 语义函数，审查是否出现在符号表中，若找到则返回一指向该登记项的指针，否则返回nil。 newtemp 语义过程，表示生成一临时变量，依次标记为t1, t2, 。 emit 语义过程，表示输出四元式到输出文件。,8.4 简单赋值语句的翻译,赋值语句的文法和语义动作描述：,语义动作 P:=lookup () ; if Pnil then emit(:=,E.place, _ , id.place) else err E.place:= newtemp; emit( +, E1.place, E2.place, E.place) E.place:=

17、newtemp; emit( *, E1.place, E2.place, E.place) E.place:=newtemp; emit( -, E1.place, _ , E.place) E.place:= E1.place P:=lookup(); if Pnil then E.place:=P else err ,设有文法： (1) S id := E (2) EE1+E2 (3) EE1*E2 (4) E - E1 (5) E( E1) (6) Eid,8.4 简单赋值语句的翻译,赋值语句的文法和语义动作描述：,语义动作 P:=lookup () ; i

18、f Pnil then emit(p:=,E.place) else err E.place:= newtemp; emit( E.place:= E1.place+ E2.place, ) E.place:= newtemp; emit( E.place:= E1.place* E2.place, ) E.place:=newtemp; emit( E.place:= -E.place) E.place:= E1.place P:=lookup(); if Pnil then E.place:=P else err ,设有文法： (1) S id := E (2) EE1+E2

19、 (3) EE1*E2 (4) E - E1 (5) E( E1) (6) Eid,8.4 简单赋值语句的翻译,Eg. a:=b*c+b*d的翻译,S a := E E + E E * E E * E b c b d,t1:=b*c t2:=b*d t3:=t1+t2 a:=t3,8.4 简单赋值语句的翻译,练习 根据上述赋值语句的属性文法，将赋值语句x:=a*(b+c)翻译成四元式。,8.5 布尔表达式的翻译,程序设计语言中的布尔表达式有两个作用： 计算逻辑值 用做改变控制流语句中的表达式 布尔表达式的翻译方法,8.5.1 布尔表达式的翻译方法,计算布尔表达式的值有两种方法： 如同计算算术表

20、达式一样，步步计算出各部分的真假值，最后计算出整个表达式的值。 采取优化措施只计算部分表达式。 Eg. E1 or E2，若E1的值为真就不再计算E2的值。,8.5.1 布尔表达式的翻译方法,第1种翻译方法,语义动作 E.place:= newtemp; emit( E.place := E1.place or E2.place ) E.place:= newtemp; emit( E.place := E1.place and E2.place ) E.place:=newtemp; emit( E.place := not E1.place ) E.place:= E1.place E.p

21、lace:=newtemp; emit( if id1.place rop id2.place goto nextstat+3 ); emit( E.place := 0 ); emit( goto nextstat+2 ); emit( E.place := 1); E.place:=newtemp;emit( E.place := 1 ); E.place:=newtemp;emit( E.place := 0 ); ,设有文法 EE1 or E2 EE1 and E2 E not E1 E( E1) Eid1 rop id2 ETrue EFalse,例：a or b and not c

22、 E E or E a E and E b not E c 翻译为： (1) t1 := not c (2) t2 := b and t1 (3) t3 := a or t2,8.5.1 布尔表达式的翻译方法,设有文法: E E1 or E2 E E1 and E2 E not E1 E ( E1 ) E id1 rop id2 E True E Flase E bid(布尔型),例：ab 可看成等价的条件语句 if ab then 1 else 0 E a b 翻译为： (1) if ab goto (4) (2) t:=0 (3) goto (5) (4) t:=1 (5) ,8.5.1

23、布尔表达式的翻译方法,例： af E E1 or E2 a f,(1) if af goto (12) (10) t3:=0 (11) goto (13) (12) t3:=1 (13) t4:=t2 and t3 (14) t5:=t1 or t4,E1af E2E3 and E4 EE1 or E2,8.5.1 布尔表达式的翻译方法,练习：,设有文法： S id := E E E or E E E and E E not E E (E) E id1 rop id2 E True E False,根据图8.14的文法和相应的语义动作将下列串翻译为四元式序列 af,8.5.2 控制语句中布尔表

24、达式的翻译,出现在if-then; if-then-else和while-do的语句中的布尔表达式的翻译 设有文法GS: S if E then S1 | if E then S1 else S2 | while E do S,8.5.2 控制语句中布尔表达式的翻译,作为条件句E，仅把E翻译成代码是一串条件转和无条件转四元式。翻译的基本思想是： 对E为a rop b的形式生成的代码为： If a rop b goto E.true goto E.false E.true和E. false分别表示E的“真”“假”出口转移目标 对E为E1 or E2的形式，若E1为true，则E.true=E1.

25、true, 无需计算E2；若E1为false，则必须计算E2，E1.false=E2代码的第一个四元式标号, 这时E.true=E2.true, E.false=E2.false 对E为E1 and E2的形式进行类似地处理 对E为 not E1只需调换E1的真假出口即可得到E的真假出口,8.5.2 控制语句中布尔表达式的翻译,例：布尔表达式 af 可翻译为： (1) if af goto E.true (6) goto E.false,注意：E.true和E.false构成链 (1) if af goto (1) E.true链首 (6) goto (4) E.false链首,8.5.2 控

26、制语句中布尔表达式的翻译,例：布尔表达式 af 可翻译为： (1) if af goto (1) E.true链首 (6) goto (4) E.false链首,例：条件语句 If af then S1 else S2 可翻译为： (1) if af goto (7) E.true (6) goto (p+1) E.false (7) (关于S1的四元式) (p) goto (q) (p+1) (关于S2的四元式) (q) if 结束后遇到新的语句才对(P)中的转移地址进行回填,8.5.2 控制语句中布尔表达式的翻译,处理两个函数 Merge(p1,p2) 将链p1,p2合并，合并后的链首为p

27、2，p2的链尾指向p1。 Backpatch(p,t) 把p所链接的每个四元式的转移地址全部填为t。 注: p,p1,p2为指向某个四元式的指针。,8.5.2 控制语句中布尔表达式的翻译,ab E a b,Eab E.t:=n; E.c:=n; E.f:=n+1 n: if ab goto n+1: goto ,根据书P185图8.16进行翻译,8.5.2 控制语句中布尔表达式的翻译,例：ab and cd E E1 and E2 a b c d,E1 ab E1.t:=n; E1.c:=n; E1.f:=n+1 n: if ab goto n+1: goto ,2. E2 cd E2.t:=

28、n+2; E2.c:=n+2; E2.f:=n+3 n: if ab goto n+1: goto n+2: if cd goto n+3: goto ,3. EE1 and E2 E.c:=E1.c; n E.t:=E2.t; n+2 E.f:=E2.fE1.f n+3,n+1 n: if ab goto n+2 n+1: goto n+2: if cd goto - n+3: goto n+1,8.5.2 控制语句中布尔表达式的翻译,例：af E E1 or E2 a f,E1 ab E1.t:=n; E1.c:=n; E1.f:=n+1 n: if ab goto n+1: goto ,

29、2. E3 cd E3.t:=n+2; E3.c:=n+2; E3.f:=n+3 n: if ab goto n+1: goto n+2: if cd goto n+3: goto ,3. E4ef E4.t:=n+4; E4.c:=n+4; E4.f:=n+5 n: if af goto n+5: goto ,4. E2E3 and E4 E2.c:=E3.c; n+2 E2.t:=E4.t; n+4 E2.f:=E4.fE3.f n+5,n+3 n: if af goto n+5: goto n+3,5. EE1 or E2 E.c:=E1.c; E.t:=E2.tE1.t n+4,n E

30、.f:=E2.f n+5,n+3 n: if af goto n n+5: goto n+3,8.5.2 控制语句中布尔表达式的翻译,练习：根据图8.16的文法和相应的语义动作将下列布尔表达式翻译成四元式序列 not af ab or cd or ef ab and cd and ef ab or cd and ef ab and gh or cd and ef,8.5.2 控制语句中布尔表达式的翻译,1. E1ab E1.t:=n; E1.c:=n; E1.f:=n+1 n: if ab goto n+1: goto ,2. E not E1 E.t:=E1.f; n+1 E.c:=E1.c

31、; n E.f:=E1.t n n: if ab goto n+1: goto ,not ab E Not E1 a b,8.5.2 控制语句中布尔表达式的翻译,ab or cd E E or E ab cd,1. E1ab E1.t:=n; E1.c:=n; E1.f:=n+1; n: if ab goto - n+1: goto -,2. E2cd E2.t:=n+2; E2.c:=n+2; E2.f:=n+3; n: if ab goto - n+1: goto n+2: if cd goto n+3: goto -,3. EE1 or E2 E.c:=E1.c=n; E.t:=E2.t

32、E1.t;n+2,n E.f:=E2.f=n+3; n: if ab goto - n+1: goto n+2 n+2: if cd goto n n+3: goto -,ab or cd or ef E E1 or E2 E3 or E4 ef ab cd,1. E3ab E3.t:=n; E3.c:=n; E3.f:=n+1; n: if ab goto - n+1: goto -,2. E4cd E4.t:=n+2; E4.c:=n+2; E4.f:=n+3; n: if ab goto - n+1: goto n+2: if cd goto n+3: goto -,3. E1E3 or

33、 E4 E1.c:=E3.c=n; E1.t:=E4.tE3.t; n+2,n E1.f:=E4.f=n+3; n: if ab goto - n+1: goto n+2 n+2: if cd goto n n+3: goto -,4. E2ef E2.t:=n+4; E2.c:=n+4; E2.f:=n+5; n: if ab goto - n+1: goto n+2 n+2: if cd goto n n+3: goto n+4: if ef goto n+5: goto -,5. EE1 or E2 E.c:=E1.c=n; E.t:=E2.tE1.t;n+4,n+2,n E.f:=E2

34、.f=n+5; n: if ab goto - n+1: goto n+2 n+2: if cd goto n n+3: goto n+4 n+4: if ef goto n+2 n+5: goto -,8.5.2 控制语句中布尔表达式的翻译,ab and gh or cd and ef E E1 or E2 E3 E3.c:=n; E3.f:=n+1; n: if ab goto - n+1:goto ,2. E4gh E4.t:=n+2; E4.c:=n+2; E4.f:=n+3; n: if ab goto - n+1:goto n+2:if gh goto - n+3: goto -,

35、3. E1E3 E1.f:=E4.fE3.fn+3,n+1 n: if ab goto n+2 n+1:goto - n+2:if gh goto - n+3: goto n+1,4. E5cd E5.t:=n+4; E5.c:=n+4; E5.f:=n+5; n: if ab goto n+2 n+1:goto - n+2:if gh goto - n+3: goto n+1 n+4: if cd goto n+5: goto ,5. E6ef E6.t:=n+6; E6.c:=n+6; E6.f:=n+7; n: if ab goto n+2 n+1:goto - n+2:if gh go

36、to - n+3: goto n+1 n+4: if cd goto n+5: goto n+6: if ef goto n+7: goto -,6. E2E5 E1.c:=n: E1.f:=n+1 n: if ab goto n+1: goto -,2. Cif E1 then C.ch:=E1.f n+1 n: if ab goto n+2 n+1: goto -,5. S1A S1.ch=0 n: if ab goto n+2 n+1:goto n+2: x:=1,6. SC S1 S.ch:=S1.chC.chn+1 n: if ab goto n+2 n+1: goto n+2: x

37、:=1,If ab then x:=1 S C S1 If E1 then A a b x := E2 1,根据书P180图8.12和P188控制结构语义动作进行翻译,3. E21 E2.p:=1 n: if ab goto n+2 n+1: goto -,4. Aid:=E2 n: if ab goto n+2 n+1:goto n+2: x:=1,8.6 控制结构的翻译,If ab then x:=1 else x:=0 S Tp S2 C S1 else A If E1 then A x := E3 ab x := E2 0 1,1. E1ab E1.t:=n; E1.c:=n: E1.

38、f:=n+1 n: if ab goto n+1: goto -,2. Cif E1 then C.ch:=E1.f n+1 n: if ab goto n+2 n+1:goto -,4. Aid:=E2 n: if ab goto n+2 n+1:goto n+2: x:=1,3. E21 E2.p:=1 n: if ab goto n+2 n+1: goto -,6. TpC S1 else q:=n+3 Tp.ch:=qS1.ch n+3 n: if ab goto n+2 n+1: goto n+4 n+2: x:=1 n+3: goto -,5. S1A S1.ch:=0 n: if

39、 ab goto n+2 n+1:goto n+2: x:=1,8.6 控制结构的翻译,7. E30 E3.p:=0 n: if ab goto n+2 n+1: goto n+4 n+2: x:=1 n+3: goto -,8. Aid:=E3 n: if ab goto n+2 n+1: goto n+4 n+2: x:=1 n+3: goto - n+4: x:=0,6. TpC S1 else q:=n+3 Tp.ch:=qS1.ch n+3 n: if ab goto n+2 n+1: goto n+4 n+2: x:=1 n+3: goto -,10. STp S2 S.ch:=S

40、2.chTp.ch n+3 n: if ab goto n+2 n+1: goto n+4 n+2: x:=1 n+3: goto - n+4: x:=0,If ab then x:=1 else x:=0 S Tp S2 C S1 else A If E1 then A x := E3 ab x := E2 0 1,9. S2A S2.ch:=0 n: if ab goto n+2 n+1: goto n+4 n+2: x:=1 n+3: goto - n+4: x:=0,8.6 控制结构的翻译,while x2 do x:=x+1 S Wd S1 W E1 do A while x 2 X := E4 E2 + E3 x 1,2. E1x2 E1.t:=n; E1.c:=n; E1.f:=n+1 n: if x2 goto n+1: goto -,1. Wwhile W.c:=n,3. WdW E1 do Wd.ch:=E1.f n+1 Wd.c:=W.c n n: if x2 goto n