编译原理第7章中间语言(2)

1、7.3.1 7.3.1 属性文法属性文法A=(G, V, E);A=(G, V, E); 【定义定义】 属性文法是上下文无关文法在语义上的属性文法是上下文无关文法在语义上的扩展，可定义为如下三元组：扩展，可定义为如下三元组：其中：其中：G(G(文法文法) )；V(V(属性集属性集) )；E(E(属性规则集属性规则集) )。 属性属性 代表与代表与文法符号文法符号相关的信息，这里相关的信息，这里主要指语主要指语义信息义信息( (类型、种类、值和值地址类型、种类、值和值地址) )；文法产生式文法产生式中中的的每个每个文法符号文法符号都附有若干个这样的都附有若干个这样的属性属性。 属性属性可以进行计

2、算和传递，可以进行计算和传递，属性规则属性规则就是在就是在同一同一产生式中产生式中，相互关联的，相互关联的属性求值规则属性求值规则。 属性属性分两类（按分两类（按属性求值规则属性求值规则区分区分）：）： 综合属性综合属性：其值由：其值由子女子女属性值来计算属性值来计算( (自底向上求值自底向上求值) )； 继承属性继承属性：其值由：其值由父兄父兄属性值来计算属性值来计算( (自顶向下求值自顶向下求值) )。说明说明【例例7.77.7】 算术表达式的算术表达式的属性文法属性文法; ; 设：设：X.val X.val 为文法符号为文法符号 X X 的的值属性值属性； 下述下述属性文法属性文法用于算

3、术表达式的用于算术表达式的求值运算求值运算：E - EE - E1 1 + T ; | E.val:= E + T ; | E.val:= E1 1.val + T.val.val + T.valT - TT - T1 1 * * F ; | T.val:= T F ; | T.val:= T1 1.val .val * * F.val F.valE - T ; | E.val:= T.valE - T ; | E.val:= T.valT - F ; | T.val:= F.valT - F ; | T.val:= F.valF - ( E ) ; | F.val:= E.valF - (

4、E ) ; | F.val:= E.valF - i ; | F.val:= i.valF - i ; | F.val:= i.valE - EE - E1 1 - T ; | E.val:= E - T ; | E.val:= E1 1.val - T.val.val - T.valT - TT - T1 1 / F ; | T.val:= T / F ; | T.val:= T1 1.val / F.val.val / F.val【注注】可以看出：可以看出： X.val X.val 属性是属性是综合属性。综合属性。 根据算术表达式根据算术表达式属性文法属性文法及其相应的及其相应的属性求值规

5、则属性求值规则， 2+4 2+4* *(5-9/3)(5-9/3)的属性语法树：的属性语法树：E.E.1010E E1 1. .2 2 + T. + T.8 8 T. T.2 2 T.T.4 4 * * F. F.2 2 F. F.2 2 F F.4 .4 ( E.( E.2 2 ) ) 2 4 E. 2 4 E.5 5 - T. - T.3 3 T. T.5 5 T. T.9 9 / F. / F.3 3 F. F.5 5 F F.9 .9 3 3 5 9 5 9按按 最左推导最左推导或或 最左归约最左归约 传递规则：传递规则： 计算规则：计算规则： 【定义定义】语法制导语法制导(synta

6、x_directed)(syntax_directed)是指根据语言是指根据语言的的形式文法形式文法对输入序列进行分析、翻译处理；对输入序列进行分析、翻译处理；核心技术核心技术是构造是构造 翻译文法翻译文法 - 在源文法产生式中插入在源文法产生式中插入语义动作符号语义动作符号( (翻译子程翻译子程序序) )，借以指明借以指明属性文法属性文法中中属性求值属性求值时机时机和和顺序顺序。 以以算术表达式文法算术表达式文法为例为例，探讨探讨翻译文法翻译文法的构造！的构造！ 通俗地说，所谓通俗地说，所谓语法制导翻译技术语法制导翻译技术，是指：，是指： 语法分析技术语法分析技术 翻译文法构造技术翻译文法构

7、造技术 + +注注 为叙述简便起见，为叙述简便起见，除非临时详细指明除非临时详细指明，标识符标识符 X X 的的属性属性一律视为一律视为符号表项指针，符号表项指针，同时用：同时用：X X 表示表示 X.pointX.point ! !符号串符号串 a a* *(b+c)(b+c)的分析的分析( (翻译翻译) )过程过程( (推导法推导法):):E E =T=T =T=T* *F F * * =F=F* *F F * * =a=a a a * *F F * * =a=a a a * *(E)(E) * * =a=a a a * *(E+T(E+T + + ) ) * * =a=a i i * *

8、(T+T(T+T + + ) ) * * 导出序列导出序列a a a a * *(b(b b b +c+c c c+ + ) ) * * =+ + 分解分解导出序列：导出序列：去掉动作符号：去掉动作符号： a a* *(b+c) (b+c) . . 源表达式；源表达式；去掉文法符号：去掉文法符号： abc+abc+* * . . 逆波兰式；逆波兰式；【例例7.87.8】 算术表达式算术表达式逆波兰式逆波兰式翻译文法翻译文法 a:a:动作符号；动作符号；含义：含义：输出输出( (a a) )E - T | E+TE - T | E+T + + | E-T | E-T - - T - F | TT

9、 - F | T* *F F * * | T/F | T/F / / F - iF - i i i | (E) | (E) G(E)G(E)注注. . 从从逆波兰式逆波兰式的的翻译翻译到到四元式四元式的的翻译：翻译： t1 = c / d t1 = c / d t2 = t1 - e t2 = t1 - e t3 = b t3 = b * * t2 t2 t4 = a + t3 t4 = a + t3四元式四元式 则则 算术表达式算术表达式 a+ba+b* *(c/d-e) (c/d-e) 的的逆波兰式算符进栈之日，逆波兰式算符进栈之日，也就是四元式生成之时。也就是四元式生成之时。重要重要结论

10、结论逆波兰式逆波兰式( (生成生成) )计算计算顺序：顺序： a a 即为即为 PUSH(PUSH(a a) )- - 逆波兰式逆波兰式在在栈栈中！中！假定：假定：t3t3a at1t1t2t2t4t4 ( (结果结果) )b b c c d d / / e e - - * * + + GEQ( GEQ( ) ) 表达式四元式生成函数表达式四元式生成函数: :G(E)G(E)：E - T | E+TE - T | E+T GEQ(+)GEQ(+) | E-T | E-T GEQ(-)GEQ(-) T - F | T T - F | T* *F F GEQ(GEQ(* *) ) | T/F |

11、T/F GEQ(/)GEQ(/) F - i F - i PUSH(i)PUSH(i) | ( E ) | ( E ) . . 算术表达式算术表达式四元式翻译文法四元式翻译文法设计设计假定：假定：SEM(m)- SEM(m)- 语义栈语义栈( (属性传递、赋值场所属性传递、赋值场所) )； PUSH(i PUSH(i) ) 压栈函数压栈函数( (把当前把当前 i i 压入语义栈压入语义栈) )；则：则：其中：其中：QTq QTq 四元式区；四元式区； t := NEWT; t := NEWT; 申请临时变量函数申请临时变量函数； SEND( SEND( SEMm-1,SEMm,t) SEMm-

12、1,SEMm,t) POP;POP;PUSH(t) POP;POP;PUSH(t)生成一个生成一个四元式送四元式送QTqQTq语义栈语义栈次栈顶次栈顶、栈顶栈顶G(E)G(E)：E - T | E+TE - T | E+T GEQ(+)GEQ(+) | E-T | E-T GEQ(-)GEQ(-) T - F | T T - F | T* *F F GEQ(GEQ(* *) ) | T/F | T/F GEQ(/)GEQ(/) F - i F - i PUSH(i)PUSH(i) | ( E ) | ( E ) 对比对比 算术表达式算术表达式 a a* *(b/c-d) (b/c-d) 的逆波

13、兰式动作序列：的逆波兰式动作序列：abc/d-abc/d-* * ；可得可得四元式动作序列四元式动作序列： QTq QTq SEMm 动作序列动作序列 a a b b c c t2 t2 PUSH(d) PUSH(d) GEQ(-) GEQ(-) GEQ(/) GEQ(/) GEQ( GEQ(* *) ) PUSH(c) PUSH(c) PUSH(b) PUSH(b) PUSH(a) PUSH(a)执行过程执行过程 a a a b a b a t1 d a t1 d a b c a b c a a t1 t1 d d ( * * a t2 t3 ) a t2 t3 )( - t1 d t2 )

14、( - t1 d t2 )( / b c t1 )( / b c t1 ) t3 t3 a a. . 赋值语句赋值语句四元式翻译文法：四元式翻译文法： S - vS - v PUSH(v)PUSH(v) =E=E ASSI(=)ASSI(=) ; ; ASSI(=)ASSI(=) - - 赋值函数；赋值函数； SEND(:= SEMm,_ ,SEMm-1 ); SEND(:= SEMm,_ ,SEMm-1 ); POP;POP; POP;POP; . . 标号、转向语句标号、转向语句四元式翻译文法：四元式翻译文法： S - i S - i PUSH(i)PUSH(i) : : LABER(i)

15、LABER(i) S ; S ; S - goto iS - goto i GOTO(i)GOTO(i) ; ; LABER(i)LABER(i) - - 标号函数；标号函数； SEND( lb _ ,_ ,SEMm ); SEND( lb _ ,_ ,SEMm ); POP; POP; GOTO(i)GOTO(i) - - 转向函数；转向函数； SEND( gt _ ,_ ,i ); SEND( gt _ ,_ ,i ); . . 条件语句条件语句四元式翻译文法：四元式翻译文法： S - if(R)S - if(R) IF(if)IF(if) S S; ; elseelse EL(el)EL

16、(el) S SIE(ie)IE(ie) IF(if)IF(if) - if - if 函数；函数； SEND( if SEMm, _ , _ ); SEND( if SEMm, _ , _ ); POP; POP; IE(i)IE(i) - ifend - ifend 函数；函数； SEND( ie _ ,_ ,_ ); SEND( ie _ ,_ ,_ ); EL(el)EL(el) - else - else 函数；函数； SEND( el _ ,_ ,_ ); SEND( el _ ,_ ,_ ); R - E R - E E E GEQ(GEQ( ) ) GEQ GEQ( ( ) )

17、 - - 表达式四元式生成函数表达式四元式生成函数； 其中的其中的 为当前匹配的为当前匹配的关系算符关系算符。. . 循环语句循环语句四元式翻译文法：四元式翻译文法： S - whileS - while WH()WH() (R)(R) DO(do)DO(do) S S WE(we)WE(we); WH(wh)WH(wh) - - 循环头循环头 函数；函数； SEND( wh _ , _ , _ ); SEND( wh _ , _ , _ ); WE(we)WE(we) - - 循环尾循环尾 函数；函数； SEND( we _ ,_ ,_ ); SEND( we _ ,_ ,_ ); 【注注】

18、文法中的文法中的 R R 为为 关系表达式（关系表达式（见见条件语句四元式条件语句四元式翻译文法翻译文法）。 DO(el)DO(el) - DO - DO 函数；函数； SEND( do SEMm ,_ ,_ ); SEND( do SEMm ,_ ,_ ); POP ; POP ; . . 说明语句说明语句四元式翻译文法：四元式翻译文法： 说明语句的翻译目标：填写符号表说明语句的翻译目标：填写符号表 （1 1）原文法：）原文法： D - id:T;D | id:TD - id:T;D | id:TT T - integer | real | array num of T | integer

19、| real | array num of T | T T（2 2）文法变换：）文法变换： D D - id:TD id:TDD D - ;id:TD - ;id:TD | | T T - integer | real | array num of T | integer | real | array num of T | T T（3 3）翻译文法：）翻译文法： D D - INI()INI() idid NAME()NAME() :T:T ENT()ENT() D DD D -;id -;id NAME()NAME() :T:T ENT()ENT() D D | | T T -integer

20、integer TYP(i)TYP(i) -real -real TYP(r)TYP(r) -array num -array num NUM()NUM() of T of T TYP(a)TYP(a) - - T T TYP(TYP( ) ) INI()INI()- -初始化初始化 函数；函数； offset := 0 offset := 0 ; ; NAME()NAME()-标识符标识符 名字处理名字处理 函数；函数； := entry(id) := entry(id) ; ; ENT()ENT()-填写符号表填写符号表 函数；函数； enter( id.n

21、ame, T.type, offset ); enter( , T.type, offset );(2)offset := offset + T.width;(2)offset := offset + T.width; TYP(x)TYP(x)-标识符类型处理标识符类型处理 函数；函数； T.type := x; T.width := x.width;T.type := x; T.width := x.width; NUM()NUM()-标识符类型处理标识符类型处理 函数；函数； num.val := val(num);num.val := val(num);【例例7.97.9】

22、 已知条件语句已知条件语句 if(a0)a=a+1;if(a if( R ) S = if( R ) IF(if)IF(if) S S ; ; IE(ie)IE(ie) E E E E GEQ(GEQ( ) ) a a push(a)push(a) a a PUSH(a)PUSH(a) = E= E ASSI(=)ASSI(=) E + TE + T GEQ(+)GEQ(+) T TF Fa a push(a)push(a) T TF FF F1 1 push(1)push(1) T TF Fb b push(b)push(b) if(a0)a=a+1 if(a0)a=a+1 四元式翻译四元式翻译的动作序列：的动作序列： push(a)push(a), push(a)push(a), push(b)push(b), GEQ(GEQ( ) ), IF(if)IF(if), PUSH(a)PUSH(a) push(1)push(1), GEQ(GEQ(+ +) ), ASSI(=)ASSI(=), IE(ie)IE(ie) 根据上述根据上述条件语句条件语句四元式翻译四元式翻译的动作序列，的动作序列，