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

《第五章 语法制导翻译和中间代码产生.ppt》由会员分享，可在线阅读，更多相关《第五章 语法制导翻译和中间代码产生.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理,第六章 属性文法和语法制导翻译,编译原理,编译原理,6.1 属性文法,属性文法（也称属性翻译文法）Knuth在1968年提出在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等属性可以进行计算和传递语义规则：对于文法的每个产生式都配备了一组属性的计算规则,编译原理,属性综合属性：“自下而上”传递信息继承属性：“自上而下”传递信息在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条规则的形式为：b:=f(c1,c2,ck)这里，f是一个函数，而且或者1. b是A的一

2、个综合属性并且c1,c2,ck是产生式右边文法符号的属性，或者2. b是产生式右边某个文法符号的一个继承属性并且c1,c2,ck 是A或产生式右边任何文法符号的属性。属性b依赖于属性c1,c2,ck。,编译原理,说明终结符只有综合属性，由词法分析器提供非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属

3、性计算器的参数提供,编译原理,语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等等。例，考虑非终结符A，B和C，其中，A有一个继承属性a和一个综合属性b，B有综合属性c，C有继承属性d。产生式ABC可能有规则 C.d:=B.c+1 A.b:=A.a+B.c而属性A.a和B.c在其它地方计算,编译原理,产 生 式 LEn EE1+T ETTT1*FTFF (E)Fdigit,语 义 规 则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 :=

4、E.val F.val :=digit.lexval,编译原理,综合属性在语法树中，一个结点的综合属性的值由其子结点的属性值确定。使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值仅仅使用综合属性的属性文法称S属性文法,编译原理,产 生 式 LEn EE1+T ETTT1*FTFF (E)Fdigit,语 义 规 则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+4n的带注释的

5、语法树,digit.lexval=3,F.val=3,T.val=3,*,digit.lexval=5,F.val=5,T.val=15,E.val=15,+,digit.lexval=4,F.val=4,T.val=4,E.val=19,n,L,产 生 式 语 义 规 则 LEn print(E.val) EE1+T E.val := E1.val+T.val ET E.val :=T.val TT1*F T.val :=T1.val* F.val TF T.val :=F.val F (E) F.val :=E.val Fdigit F.val :=digit.lexval,编译原理,继承

6、属性在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定用继承属性来表示程序设计语言结构中的上下文依赖关系很方便,编译原理,产 生 式 语 义 规 则 DTLL.in := T.type TintT.type := integer TrealT.type := real LL1, idL1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in),编译原理,句子real id1，id2，id3的带注释的语法树,id1,L,id2,L,id3,L,real,T,D,T.type=real,L.in=real,

7、L.in=real,L.in=real,产 生 式 语 义 规 则 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in),编译原理,6.2 基于属性文法的的处理方法,由源程序的语法结构所驱动的处理办法就是语法制导翻译法语义规则的计算产生代码在符号表中存放信息给出错误信息执行任何其它动作对输入符号串的翻译也就是根据语义规则进行计算的结果。,输入串,语法树,依赖图,语义规则计算次序,

8、编译原理,6.2 基于属性文法的的处理方法,依赖图树遍历一遍扫描,编译原理,6.2.1 依赖图,在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描述为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成b:=f(c1,c2,ck)的形式依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。,编译原理,for 语法树中每一结点n do for 结点n的文法符号的每一个属性a do 为a在依赖图中建立一个结点；for语法树中每一个结点n do for 结点n所用产生式对应的每一个语义规

9、则b:=f(c1,c2,ck ) dofor i:=1 to k do 从ci结点到b结点构造一条有向边；,编译原理,EE1E2 E.val:=E1.val+E2.val,E1,+,E2,E,val,val,val,编译原理,句子real id1，id2，id3的带注释的语法树的依赖图,id1,L,id2,L,id3,L,real,T,D,4type,5in,6 - addtype(id.entry, L.in),7in,8 addtype,9in,10 addtype,1entry,2entry,3entry,产 生 式 语 义 规 则 DTL L.in := T.type Tint T.t

10、ype := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in),编译原理,如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的,编译原理,属性的计算次序,一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序属性文法说明的翻译是很精确的基础文法用于建立输入符号串的语法分析树根据语义规则建立依赖图从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序,输入串,语法树,依赖图,语义规则计算次序,编译原理,句子real

11、id1，id2，id3的带注释的语法树的依赖图,a4:=real;a5:=a4addtype (id3.entry,a5);a7:=a5;addtype (id2.entry,a7);a9:=a7addtype (id1.entry,a9);,编译原理,6.2 基于属性文法的的处理方法,依赖图树遍历一遍扫描,编译原理,6.2.2 树遍历的属性计算方法,通过树遍历的方法计算属性的值 假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性 以某种次序遍历语法树，直至计算出所有属性深度优先，从左到右的遍历,编译原理,While 还有未被计算的属性 doVisitNode(S) /*S是开

12、始符号*/procedure VisitNode (N:Node) ;begin if N是一个非终结符 then /*假设它的产生式为NX1Xm*/ for i :=1 to m do if XiVN then /*即Xi是非终结符*/ begin 计算Xi的所有能够计算的继承属性； VisitNode (Xi) end; 计算N的所有能够计算的综合属性end,编译原理,产 生 式语 义 规 则 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.bXx X.d :=2*X.cYy Y.f := Y.e*3Zz Z.g :=Z.h+1,例 考虑

13、属性的文法G。其中，S有继承属性a，综合属性b；X有继承属性c、综合属性d；Y有继承属性e、综合属性f；Z有继承属性h、综合属性g,编译原理,假设S.a的初始值为0，输入串为xyz,S:a=0,X,Y,Z,x,y,z,Z:h=0 g=1,X:c=1 d=2,S:a=0, b=0,Y:e=0 f=0,产 生 式语 义 规 则 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.bXx X.d :=2*X.cYy Y.f := Y.e*3Zz Z.g :=Z.h+1,编译原理,6.2 基于属性文法的的处理方法,依赖图树遍历一遍扫描,编译原理,6.2.

14、3 一遍扫描的处理方法,一遍扫描的处理方法是在语法分析的同时计算属性值 所采用的语法分析方法属性的计算次序L属性文法适合于一遍扫描的自上而下分析S属性文法适合于一遍扫描的自下而上分析,编译原理,所谓语法制导翻译法，直观上说就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则 语义规则就被计算的时机在自上而下语法分析中，一个产生式匹配输入串成功时在自下而上分析中，当一个产生式被用于进行归约时,编译原理,6.2.4 抽象语法树,在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树(Abstract Syntax Tree

15、),Sif B then S1 else S2,3*5+4,编译原理,建立表达式的抽象语法树,mknode (op,left,right) 建立一个运算符号结点，标号是op，两个域left和right分别指向左子树和右子树。mkleaf (id,entry) 建立一个标识符结点，标号为id，一个域eutry指向标识符在符号表中的入口。mkleaf (num,val) 建立一个数结点，标号为num，一个域val用于存放数的值。,编译原理,建立抽象语法树的语义规则,产 生 式 语 义 规 则 EE1+TE.nptr := mknode( +, E1.nptr, T.nptr ) EE1-TE.np

16、tr := mknode( -, E1.nptr, T.nptr ) ETE.nptr := T.nptr T (E) T.nptr := E.nptr TidT.nptr := mknode( id, id.entry ) Tnum T.nptr := mknode( num, num.val ),编译原理,a4c的抽象语法树,E nptr,T nptr,E nptr,To entry for a,E,T nptr,id,-,T nptr,id,To entry for c,编译原理,一遍扫描的处理方法,一遍扫描的处理方法是在语法分析的同时计算属性值 所采用的语法分析方法属性的计算次序L属性

17、文法适合于一遍扫描的自上而下分析S属性文法适合于一遍扫描的自下而上分析,编译原理,6.3 S-属性文法的自下而上计算,S-属性文法：只含有综合属性综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。,编译原理,在分析栈中使用一个附加的域来存放综合属性值 假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应于产生式AXYZ的,编译原理,产生式 代 码 段 LEnprint(valtop) EE1+Tvalntop := valtop-2+valtop ETTT1*F

18、valntop := valtop-2*valtop TFF (E)valntop :=valtop-1Fdigit,产 生 式 语 义 规 则 LEn print(E.val) EE1+T E.val := E1.val+T.val ET E.val :=T.val TT1*F T.val :=T1.val* F.val TF T.val :=F.val F (E) F.val :=E.val Fdigit F.val :=digit.lexval,编译原理,输入 statesym val 用到的产生式 3*5+4n 0 # - *5+4n 05#3 -3 *5+4n 03 #F -3 Fd

19、igit *5+4n 02 #T -3 TF 5+4n 027#T* -3 - +4n 0275 #T*5 -3 - 5,产生式 代 码 段 LEnprint(valtop) EE1+Tvalntop := valtop-2+valtop ETTT1*Fvalntop := valtop-2*valtop TFF (E)valntop :=valtop-1Fdigit,编译原理,输入 statesym val 用到的产生式 +4n 0275 #T*5 -3 - 5 +4n 02710#T*F -3 - 5 Fdigit +4n 02 #T -15 TT*F +4n 01 #E -15 ET 4

20、n 016 #E+ -15- n 0165 #E+4 -15- 4,产生式 代 码 段 LEnprint(valtop) EE1+Tvalntop := valtop-2+valtop ETTT1*Fvalntop := valtop-2*valtop TFF (E)valntop :=valtop-1Fdigit,编译原理,输入 statesym val 用到的产生式 n 0165 #E+4 -15- 4 n 0163 #E+F -15- 4Fdigit n 0169 #E+T -15- 4TF n 01#E -19EE+T #En -19- #L -19 LEn,产生式 代 码 段 LEn

21、print(valtop) EE1+Tvalntop := valtop-2+valtop ETTT1*Fvalntop := valtop-2*valtop TFF (E)valntop :=valtop-1Fdigit,编译原理,一遍扫描的处理方法,一遍扫描的处理方法是在语法分析的同时计算属性值 所采用的语法分析方法属性的计算次序L属性文法适合于一遍扫描的自上而下分析S属性文法适合于一遍扫描的自下而上分析,编译原理,6.4 L-属性文法和自顶向下翻译,通过深度优先的方法对语法树进行遍历，计算属性文法的所有属性值LL(1)：自上而下分析方法，深度优先建立语法树,编译原理,一个属性文法称为L-

22、属性文法，如果对于每个产生式AX1X2Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj(1jn)的一个继承属性且这个继承属性仅依赖于：(1) 产生式Xj的左边符号X1，X2，Xj-1的属性；(2) A的继承属性。S-属性文法一定是L-属性文法,编译原理,产 生 式 语 义 规 则 ALM L.i := l(A.i) M.i :=m(L.s) AQR R.i := r(A.i) Q.i :=q(R.s) A.s :=f(Q.s),编译原理,6.4.1 翻译模式,翻译模式：给出了使用语义规则进行计算的次序，这样就可把某些实现细节表示出来在翻译模式中，和文法符号相关的属性和语义规则（这里我

23、们也称语义动作），用花括号 括起来，插入到产生式右部的合适位置上,编译原理,翻译模式示例：把带加号和减号的中缀表达式翻译成相应的后缀表达式,ETR Raddop T print(addop.lexeme) R1 | Tnum print(num.val) 例：9-5+2,-,E,T,R,9,print(9),T,R,5,print(5),print(-),+,T,2,print(2),R,print(+),编译原理,设计翻译模式的原则,设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的。L-属性文法本身就能确保每个动作不会引用尚未计算出来的属性。,编译原理,建立翻译模式,当只需要

24、综合属性时：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾 产生式 语义规则 TT1*FT.val:=T1.valF.val建立产生式和语义动作： TT1*F T.val:=T1.valF.val,编译原理,建立翻译模式,如果既有综合属性又有继承属性，在建立翻译模式时就必须保证：1. 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。2. 一个动作不能引用这个动作右边的符号的综合属性。3. 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。 SA1A2A1.in:=1; A2.i

25、n:=2 Aa print(A.in),编译原理,基于数学格式语言EQN,给定输入 E sub n .val,En.val,编译原理,识别输入并进行格式安放的L-属性文法,产生式 语义规则 SB B.ps :=10 S.ht :=B.htBB1B2 B1.ps :=B.ps B2.ps :=B.ps B.ht := max(B1.ht, B2.ht)BB1 sub B2B1.ps :=B.ps B2.ps :=shrink(B.ps) B.ht :=disp(B1.ht, B2.ht)Btext B.ht :=text.hB.ps,编译原理,翻译模式,S B.ps:=10 B S.ht:=B.

26、ht B B1.ps:=B.ps B1 B2.ps:=B.ps B2 B.ht:=max(B1.ht,B2.ht) B B1.ps:=B.ps B1 sub B2.ps:=shrink(B.ps) B2 B.ht:=disp(B1.ht,B2.ht) B textB.ht:=text.hB.ps,1. 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。2. 一个动作不能引用这个动作右边的符号的综合属性。3. 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常放在产生式右端的末尾。,编译原理,6.4.2 自顶向下翻译,动作是在处于相同位

27、置上的符号被展开（匹配成功）时执行的。 为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归当消除一个翻译模式的基本文法的左递归时同时考虑属性适合带综合属性的翻译模式,编译原理,关于算术表达式的左递归文法相应的翻译模式EE1+TE.val:=E1.val+T.valEE1-T E.val:=E1.val-T.valET E.val:=T.valT(E)T.val:=E.valTnumT.val:=num.val,E T RR + T R1R - T R1R T ( E )T num,编译原理,消除左递归，构造新的翻译模式 E TR.i:=T.val RE.val:=R.sR + TR1.

28、i:=R.i+T.val R1R.s:=R1.sR - TR1.i:=R.i-T.val R1R.s:=R1.sR R.s:=R.iT ( E )T.val:=E.valT numT.val:=num.val,E T RR +TR1R -TR1R T ( E )T numR.i: R前面子表达式 的值R.s: 分析完R时子表 达式的值,编译原理,计算表达式952,E,T,R,num,num.val=9,T.val=9,R.i=9,-,T,R,num,num.val=5,T.val=5,R.i=4,+,T,R,num,num.val=2,T.val=2,R.i=6,R.s=6,R.s=6,R.s

29、=6,E.val=6,E T R.i:=T.val R E.val:=R.s R + T R1.i:=R.i+T.val R1 R.s:= R1.s R - T R1.i:=R.i-T.val R1 R.s:= R1.s R R.s:=R.i T ( E ) T.val:=E.val T num T.val:=num.val ,编译原理,一般方法,假设有翻译模式： AA1YA.a:=g(A1.a,Y.y) AXA.a:=f(X.x)它的每个文法符号都有一个综合属性，用小写字母表示，g和f是任意函数。,消除左递归： AXR RYR | ,翻译模式变为 ：A XR.i:=f (X.x) RA.a:

30、=R.sR Y R1.i:=g(R.i,Y.y) R1R.s:=R1.sR R.s:=R.i,R.i: R前面子表达式 的值R.s: 分析完R时子表 达式的值,编译原理,XYY,X,A,A.a=f(X.x),Y1,A,A.a=g(f(X.x),Y1.y),Y2,A,A.a=g(g(f(X.x),Y1.y), Y2.y),AA1YA.a:=g(A1.a,Y.y)AXA.a:=f(X.x),编译原理,XYY,A,X,R,R.i=f(X.x),Y1,R,R.i= g(f(X.x),Y1.y),Y2,R,R.i= g(g(f(X.x),Y1.y), Y2.y),R.s= g(g(f(X.x),Y1.y

31、), Y2.y),R.s= g(g(f(X.x),Y1.y), Y2.y),R.s= g(g(f(X.x),Y1.y), Y2.y),A.a= g(g(f(X.x),Y1.y), Y2.y),A X R.i:=f (X.x) R A.a:=R.sR Y R1.i:=g(R.i,Y.y) R1 R.s:=R1.sR R.s:=R.i,编译原理,构造抽象语法树的属性文法定义转化成翻译模式,EE1+TE.nptr:=mknode(+,E1.nptr,T.nptr)EE1-TE.nptr:=mknode(-,E1.nptr,T.nptr)ETE.nptr:=T.nptr,编译原理,构造抽象语法树的属性

32、文法定义转化成翻译模式,E TR.i:=T.nptr RE.nptr:=R.sR + TR1.i:=mknode(+,R.i,T.nptr) R1R.s:=R1.sR - TR1.i:=mknode(,R.i,T.nptr) R1R.s:=R.sR R.s:=R.iT ( E )T.nptr:=E.nptrT idT.nptr:=mkleaf(id,id.entry)T numT.nptr:=mkleaf(num,num.val),编译原理,使用继承属性构造a4c的抽象语法树,E,T,R,id,T.nptr,-,T,num,T.nptr,R. i,R,+,T,R,id,T.nptr,R. i,

33、R. i,R. s,R. s,R. s,E.nptr,E T R.i:=T.nptr R E.nptr:=R.sR + T R1.i:=mknode(+,R.i,T.nptr) R1 R.s:=R1.sR - T R1.i:=mknode(,R.i,T.nptr) R1 R.s:=R.sR R.s:=R.iT ( E ) T.nptr:=E.nptrT id T.nptr:=mkleaf(id,id.entry)T num T.nptr:=mkleaf(num,num.val),编译原理,6.4.3 递归下降翻译器的设计,如何在递归下降分析中实现翻译模式，构造递归下降翻译器,编译原理,设计递归

34、下降翻译器的方法,1. 对每个非终结符A构造一个函数过程，对A的每个继承属性设置一个形式参数函数的返回值为A的综合属性（作为记录，或指向记录的一个指针，记录中有若干域，每个属性对应一个域）。为了简单，我们假设每个非终结只有一个综合属性A对应的函数过程中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。,编译原理,设计递归下降翻译器的方法,2. 非终结符A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。,编译原理,设计递归下降翻译器的方法,3. 每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作：i) 对于带有

35、综合属性x的终结符X，把x的值存入为X.x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号。ii) 对于每个非终结符B，产生一个右边带有函数调用的赋值语句c=B(b1,b2,bk)，其中，b1,b2,bk是为B的继承属性设置的变量，c是为B的综合属性设置的变量。iii) 对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用。,编译原理,构造抽象语法树的属性文法定义转化成翻译模式,E TR.i:=T.nptr RE.nptr:=R.sR + TR1.i:=mknode(+,R.i,T.nptr) R1R.s:=R1.sR - TR1.i:=mknode(

36、,R.i,T.nptr) R1R.s:=R.sR R.s:=R.iT ( E )T.nptr:=E.nptrT idT.nptr:=mkleaf(id,id.entry)T numT.nptr:=mkleaf(num,num.val),编译原理,非终结符E、R、T的函数及其参数类型 functionE:AST-node;functionR(in:AST-node): AST-node;functionT: AST-node;用oddop代表和 R oddop TR1.i:=mknode(addop.lexme, R.i,T.nptr) R1R.s:=R1.s R R.s:=R.i,编译原理,产

37、生式Raddop TR|的分析过程,procedare R; begin if sym=addop then begin advance;T; R end else begin /*do nothing*/ end end;,编译原理,function R (in:AST-node): AST-node; var nptr, i1,s1,s: AST-node; addoplexeme: char; begin if sym=addop then begin /*产生式Raddop TR */ addoplexeme:=lexval; advance; nptr:=T; i1:=mknode

38、(addoplexeme, in, nptr); s1:=R (i1) s:=s1 end else s:= in; return s end;,R oddop TR1.i:=mknode(addop.lexme, R.i, T.nptr) R1 R.s:=R1.s R R.s:=R.i,编译原理,6.5 自下而上计算继承属性,在自下而上的分析过程中实现L-属性文法的方法可实现任何基于LL(1)文法的L-属性文法，还可以实现许多（不是所有）基于LR(1)文法的L-属性文法,编译原理,6.5.1 从翻译模式中去掉嵌入在产生式中间的动作,要求把所有的语义动作都放在产生式的末尾转换方法，它可以使所有嵌入的动作都出现在产生式的末尾 加入新的产生式M把嵌入在产生式中的每个语义动作用不同的标记非终结符M代替，并把这个动作放在产生式M的末尾,编译原理,翻译模式 E TRR T print () R | T print () R | T num print (num.val)转换为 E TRR TMR | TNR | T num print (num.val)M print ()N print (),