06 第六章 属性文法和语法制导翻译.pptx

第1页：第六章属性文法和语法制导翻译

第六章属性文法和语法制导翻译

• 编译原理

第2页：6.1属性文法

6.1属性文法

语义规则

对于文法的每个产生式都配备了一组属性的计算规则

• 属性文法（也称属性翻译文法）
• Knuth在1968年提出
• 在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。
• 属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等
• 属性可以进行计算和传递

第3页：属性综合属性语义规则表

属性综合属性语义规则表

综合属性

“自下而上”传递信息

继承属性

“自上而下”传递信息

• 对应于每个产生式A→
• 都有一套与之相关联的语义规则，每条规则的形式为：b:=f(c1,c2,…,ck)这里，f是一个函数，而且或者1.b是A的一个综合属性并且c1,c2,…,ck是产生式右边文法符号的属性，或者2.b是产生式右边某个文法符号的一个继承属性并且c1,c2,…,ck是A或产生式右边任何文法符号的属性。
• 属性b依赖于属性c1,c2,…,ck。

第4页：终结符只有综合属性

终结符只有综合属性

• 终结符只有综合属性，由词法分析器提供
• 非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值
• 对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性
• 出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供

第5页：语义规则所描述语义规则表

语义规则所描述语义规则表

• 考虑非终结符A，B和C，其中，A有一个继承属性a和一个综合属性b，B有综合属性c，C有继承属性d。产生式A→BC可能有规则C.d:=B.c+1A.b:=A.a+B.c而属性A.a和B.c在其它地方计算

第6页：语义规则表

语义规则表

• → (E)F→digit语义规则print(E.val)E.val= E1.val+T.valE.val :=T.valT.val :=T1.val* F.valT.val :=F.valF.val :=E.valF.val :=digit.lexval

第7页：语义规则表（续）

语义规则表（续）

• 在语法树中，一个结点的综合属性的值由其子结点的属性值确定。
• 使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值

第8页：语义规则表

语义规则表

• → (E)F→digit语义规则print(E.val)E.val= E1.val+T.valE.val :=T.valT.val :=T1.val* F.valT.val :=F.valF.val :=E.valF.val :=digit.lexval

第9页：3*5+4n语义规则表

3*5+4n语义规则表

• =3F.val=3T.val=3*digit.lexval=5F.val=5T.val=15E.val=15+digit.lexval=4F.val=4T.val=4E.val=19nL产生式语义规则L→En print(E.val)E→E1+T E.val= E1.val+T.valE→T E.val :=T.valT→T1*F T.val :=T1.val* F.valT→FT.val :=F.valF→ (E) F.val :=E.valF→digit F.val :=digit.lexval

第10页：3*5+4n语义规则表（续）

3*5+4n语义规则表（续）

• 在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定
• 用继承属性来表示程序设计语言结构中的上下文依赖关系很方便

第11页：语义规则表

语义规则表

• =T.typeT→intT.type:=integerT→realT.type:=realL→L1,idL1.in:=L.inaddtype(id.entry,L.in)L→idaddtype(id.entry,L.in)

第12页：语义规则表（续）

语义规则表（续）

• id2，id3的带注释的语法树id1L,id2L,id3LrealTDT.type=realL.in=realL.in=realL.in=real产生式语义规则D→TLL.in:=T.typeT→intT.type:=integerT→realT.type:=realL→L1,idL1.in:=L.inaddtype(id.entry,L.in)L→idaddtype(id.entry,L.in)

第13页：6.2基于属性文法的的处理方法

6.2基于属性文法的的处理方法

• 由源程序的语法结构所驱动的处理办法就是语法制导翻译法
• 语义规则的计算
• 产生代码
• 在符号表中存放信息
• 给出错误信息
• 执行任何其它动作
• 对输入符号串的翻译也就是根据语义规则进行计算的结果。输入串语法树依赖图语义规则计算次序

第14页：6.2基于属性文法的的处理方法（续）

6.2基于属性文法的的处理方法（续）

• 依赖图
• 树遍历
• 一遍扫描

第15页：6.2.1依赖图

6.2.1依赖图

• 在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描述
• 为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成b:=f(c1,c2,…,ck)的形式
• 依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。

第16页：6.2.1依赖图（续）

6.2.1依赖图（续）

• 每一个属性ado为a在依赖图中建立一个结点for语法树中每一个结点ndofor结点n所用产生式对应的每一个语义规则b:=f(c1,c2,…,ck)dofori:=1tokdo从ci结点到b结点构造一条有向边；

第17页：6.2.1依赖图

6.2.1依赖图

• =E1.val+E2.valE1+E2Evalvalval

第18页：6.2.1依赖图（续）

6.2.1依赖图（续）

• id2，id3的带注释的语法树的依赖图id1L,id2L,id3LrealTD4type5in6-addtype(id.entry, L.in)7in8addtype9in10addtype1entry2entry3entry产生式语义规则D→TLL.in:=T.typeT→intT.type:=integerT→realT.type:=realL→L1,idL1.in:=L.inaddtype(id.entry,L.in)L→idaddtype(id.entry,L.in)

第19页：6.2.1依赖图

6.2.1依赖图

如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的

第20页：属性的计算次序

属性的计算次序

• 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序
• 属性文法说明的翻译是很精确的
• 基础文法用于建立输入符号串的语法分析树
• 根据语义规则建立依赖图
• 从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序输入串语法树依赖图语义规则计算次序

第21页：句子real id1

句子real id1

• id2，id3的带注释的语法树的依赖图id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entrya4:=real;a5:=a4addtype (id3.entry,a5);a7:=a5;addtype (id2.entry,a7);a9:=a7addtype (id1.entry,a9);

第22页：6.2基于属性文法的的处理方法

6.2基于属性文法的的处理方法

• 依赖图
• 树遍历
• 一遍扫描

第23页：6.2.2树遍历的属性计算方法

6.2.2树遍历的属性计算方法

• 通过树遍历的方法计算属性的值
• 假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性
• 以某种次序遍历语法树，直至计算出所有属性
• 深度优先，从左到右的遍历

第24页：While还有未被计算

While还有未被计算

• S)procedure VisitNode (NNode) ;beginif N是一个非终结符thenfor i :=1 to m doif Xi
• VNthen begin计算Xi的所有能够计算的继承属性；VisitNode (Xi)end;计算N的所有能够计算的综合属性end

第25页：语义规则表

语义规则表

= S.aX.c

= Z.gS.b := X.d-2Y.e := S.bX→xX.d :=2*X.cY→yY.f := Y.e*3Z→zZ.g :=Z.h+1例考虑属性的文法G。其中，S有继承属性a，综合属性b；X有继承属性c、综合属性d；Y有继承属性e、综合属性f；Z有继承属性h、综合属性g

第26页：语义规则表（续）

语义规则表（续）

输入串为xyzS

a=0XYZxyzZ:h=0g=1X:c=1d=2S:a=0, b=0Y:e=0f=0产生式语义规则S→XYZ Z.h := S.aX.c := Z.gS.b := X.d-2Y.e := S.bX→x X.d :=2*X.cY→y Y.f := Y.e*3Z→z Z.g :=Z.h+1

第27页：6.2基于属性文法的的处理方法

6.2基于属性文法的的处理方法

• 依赖图
• 树遍历
• 一遍扫描

第28页：6.2.3一遍扫描的处理方法

6.2.3一遍扫描的处理方法

• 一遍扫描的处理方法是在语法分析的同时计算属性值
• 所采用的语法分析方法
• 属性的计算次序
• L－属性文法适合于一遍扫描的自上而下分析
• S－属性文法适合于一遍扫描的自下而上分析

第29页：6.2.3一遍扫描的处理方法（续）

6.2.3一遍扫描的处理方法（续）

• 在自上而下语法分析中，一个产生式匹配输入串成功时
• 在自下而上分析中，当一个产生式被用于进行归约时

第30页：6.2.4抽象语法树

6.2.4抽象语法树

• 在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树(Abstract Syntax Tree)BS1S2if_then_else
• S→if B then S1else S2
• 3*5+4*54+3

第31页：建立表达式的抽象语法树

建立表达式的抽象语法树

• mknode(op,left,right)建立一个运算符号结点，标号是op，两个域left和right分别指向左子树和右子树。
• mkleaf(id,entry)建立一个标识符结点，标号为id，一个域eutry指向标识符在符号表中的入口。
• mkleaf(num,val)建立一个数结点，标号为num，一个域val用于存放数的值。

第32页：建立表达式的抽象语法树（续）

建立表达式的抽象语法树（续）

• .nptr= mknode( ‘+’, E1.nptr, T.nptr )E→E1-TE.nptr := mknode( ‘-’, E1.nptr, T.nptr )E→TE.nptr := T.nptrT→ (E)T.nptr := E.nptrT→idT.nptr := mknode( id, id.entry )T→numT.nptr:=mknode(num,num.val)

第33页：建立表达式的抽象语法树

建立表达式的抽象语法树

• To entry for aETnptrid-Tnptridid-idnum4+To entry for c

第34页：一遍扫描的处理方法

一遍扫描的处理方法

• 一遍扫描的处理方法是在语法分析的同时计算属性值
• 所采用的语法分析方法
• 属性的计算次序
• L－属性文法适合于一遍扫描的自上而下分析
• S－属性文法适合于一遍扫描的自下而上分析

第35页：6.3S-属性文法的自下而上计算

6.3S-属性文法的自下而上计算

S-属性文法

只含有综合属性

• 综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。
• 分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。

第36页：6.3S-属性文法的自下而上计算（续）

6.3S-属性文法的自下而上计算（续）

• =f(X.x,Y.y,Z.z)是对应于产生式A→XYZ的

第37页：语义规则表

语义规则表

• →E1+Tval[ntop]= val[top-2]+val[top]E→TT→T1*Fval[ntop] := val[top-2]*val[top]T→FF→ (E)val[ntop] :=val[top-1]F→digit产生式语义规则L→En print(E.val)E→E1+T E.val := E1.val+T.valE→T E.val :=T.valT→T1*F T.val :=T1.val* F.valT→FT.val :=F.valF→ (E) F.val :=E.valF→digit F.val :=digit.lexval

第38页：语义规则表（续）

语义规则表（续）

0#-*5+4n 05#3-3*5+4n 03#F-3F→digit*5+4n 02#T-3T→F5+4n 027#T*-3-+4n 0275#T*5-3-5产生式代码段L→Enprint(val[top])E→E1+Tval[ntop]= val[top-2]+val[top]E→TT→T1*Fval[ntop] := val[top-2]*val[top]T→FF→ (E)val[ntop] :=val[top-1]F→digit

第39页：语义规则表

语义规则表

5#T*5-3-5+4n 02710#T*F-3-5F→digit+4n 02#T-15T→T*F+4n 01#E-15E→T4n 016#E+-15-n 0165#E+4-15-4产生式代码段L→Enprint(val[top])E→E1+Tval[ntop]= val[top-2]+val[top]E→TT→T1*Fval[ntop] := val[top-2]*val[top]T→FF→ (E)val[ntop] :=val[top-1]F→digit

第40页：语义规则表（续）

语义规则表（续）

#E+4-15-4n 0163 #E+F-15-4F→digitn 0169 #E+T-15-4T→Fn 01#E-19E→E+T#En-19-#L-19L→En产生式代码段L→Enprint(val[top])E→E1+Tval[ntop]= val[top-2]+val[top]E→TT→T1*Fval[ntop] := val[top-2]*val[top]T→FF→ (E)val[ntop] :=val[top-1]F→digit

第41页：一遍扫描的处理方法

一遍扫描的处理方法

• 一遍扫描的处理方法是在语法分析的同时计算属性值
• 所采用的语法分析方法
• 属性的计算次序
• L－属性文法适合于一遍扫描的自上而下分析
• S－属性文法适合于一遍扫描的自下而上分析

第42页：6.4L-属性文法和自顶向下翻译

6.4L-属性文法和自顶向下翻译

LL(1)

自上而下分析方法，深度优先建立语法树

第43页：6.4L-属性文法和自顶向下翻译（续）

6.4L-属性文法和自顶向下翻译（续）

• j
• n)的一个继承属性且这个继承属性仅依赖于：(1)产生式Xj的左边符号X1，X2，…，Xj-1的属性；(2)A的继承属性。

第44页：语义规则表

语义规则表

=l(A.i)M.i

=m(L.s)A→QRR.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s)

第45页：6.4.1翻译模式

6.4.1翻译模式

翻译模式

给出了使用语义规则进行计算的次序，这样就可把某些实现细节表示出来

第46页：6.4.1翻译模式（续）

6.4.1翻译模式（续）

T→num {print(num.val)}例：9-5+2-ETR9{print(‘9’)}TR5{print(‘5’)}{print(‘-’)}+T2{print(‘2’)}R{print(‘+’)}

第47页：设计翻译模式的原则

设计翻译模式的原则

• 设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的。
• L-属性文法本身就能确保每个动作不会引用尚未计算出来的属性。

第48页：设计翻译模式的原则（续）

设计翻译模式的原则（续）

当只需要综合属性时：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾产生式语义规则T→T1*FT.val:=T1.val×F.val建立产生式和语义动作：T→T1*F{T.val:=T1.val×F.val}

第49页：建立翻译模式

建立翻译模式

如果既有综合属性又有继承属性，在建立翻译模式时就必须保证：1.产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。2.一个动作不能引用这个动作右边的符号的综合属性。3.产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。S→A1A2{A1.in:=1; A2.in:=2}A→a{print(A.in)}

第50页：基于数学格式语言EQN

基于数学格式语言EQN

• 给定输入E sub n .valEn.valEn.val

第51页：基于数学格式语言EQN（续）

基于数学格式语言EQN（续）

→BB.ps=10S.ht

=B.htB→B1B2B1.ps :=B.psB2.ps :=B.psB.ht := max(B1.ht, B2.ht)B→B1sub B2B1.ps :=B.psB2.ps :=shrink(B.ps)B.ht :=disp(B1.ht, B2.ht)B→textB.ht :=text.h×B.psEn.valE sub n .val

第52页：基于数学格式语言EQN

基于数学格式语言EQN

=10}B {S.ht:=B.ht}B →{B1.ps:=B.ps}B1{ B2.ps:=B.ps }B2{B.ht:=max(B1.ht,B2.ht)}B →{B1.ps:=B.ps}B1sub {B2.ps:=shrink(B.ps)}B2{B.ht:=disp(B1.ht,B2.ht)}B →text{B.ht:=text.h×B.ps}1.产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。2.一个动作不能引用这个动作右边的符号的综合属性。3.产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常放在产生式右端的末尾。

第53页：6.4.2自顶向下翻译

6.4.2自顶向下翻译

• 动作是在处于相同位置上的符号被展开（匹配成功）时执行的。
• 为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归
• 当消除一个翻译模式的基本文法的左递归时同时考虑属性——适合带综合属性的翻译模式

第54页：6.4.2自顶向下翻译（续）

6.4.2自顶向下翻译（续）

• T → ( E )T → num

第55页：6.4.2自顶向下翻译

6.4.2自顶向下翻译

{R.s

=R.i}T → ( E ){T.val:=E.val}T → num{T.val:=num.val}E → T RR → +TR1R →-TR1R →

第56页：6.4.2自顶向下翻译（续）

6.4.2自顶向下翻译（续）

{ R.s

=R.i }T → ( E ) { T.val:=E.val }T → num { T.val:=num.val }

• .val=9R.i=9-TRnumnum.val=5T.val=5R.i=4+TRnumnum.val=2T.val=2R.i=6
• R.s=6R.s=6R.s=6E.val=6E → 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 →

第57页：一般方法

一般方法

假设有翻译模式

A→A1Y{A.a:=g(A1.a,Y.y)}A→X{A.a:=f(X.x)}它的每个文法符号都有一个综合属性，用小写字母表示，g和f是任意函数。

消除左递归

A→XRR→YR |

翻译模式变为

A → X{R.i:=f (X.x)}R{A.a:=R.s}R → Y{R1.i:=g(R.i,Y.y)}R1{R.s:=R1.s}R →

{R.s

=R.i}R.i: R前面子表达式的值R.s:分析完R时子表达式的值

第58页：一般方法（续）

一般方法（续）

X.x),Y1.y)Y2AA.a=g(g(f(X.x),Y1.y), Y2.y)A→A1Y{A.a=g(A1.a,Y.y)}A→X{A.a:=f(X.x)}

第59页：一般方法

一般方法

{R.s

=R.i}

第60页：一般方法（续）

一般方法（续）

T{E.nptr=mknode(‘+’,E1.nptr,T.nptr)}E→E1-T{E.nptr:=mknode(‘-’,E1.nptr,T.nptr)}E→T{E.nptr:=T.nptr}

第61页：一般方法

一般方法

{R.s

=R.i}T →( E ){T.nptr:=E.nptr}T →id{T.nptr:=mkleaf(id,id.entry)}T →num{T.nptr:=mkleaf(num,num.val)}

第62页：使用继承属性构造a－4＋c

使用继承属性构造a－4＋c

{R.s

=R.i}T → ( E ){T.nptr:=E.nptr}T → id {T.nptr:=mkleaf(id,id.entry)}T → num {T.nptr:=mkleaf(num,num.val)}

• entry for aidT.nptr-Tnumnum4T.nptrR.i-R+TRidTo entry for cidT.nptrR.i+R.i
• R.sR.sR.sE.nptrE → T {R.i:=T.nptr} R {E.nptr:=R.s}R → + T {R1.i:=mknode(‘+’,R.i,T.nptr)} R1{R.s:=R1.s}R →-T {R1.i:=mknode(‘－’,R.i,T.nptr)} R1{R.s:=R.s}R →

第63页：6.4.3递归下降翻译器的设计

6.4.3递归下降翻译器的设计

• 如何在递归下降分析中实现翻译模式，构造递归下降翻译器

第64页：设计递归下降翻译器的方法

设计递归下降翻译器的方法

• 1.
• 对每个非终结符A构造一个函数过程，对A的每个继承属性设置一个形式参数
• 函数的返回值为A的综合属性（作为记录，或指向记录的一个指针，记录中有若干域，每个属性对应一个域）。为了简单，我们假设每个非终结只有一个综合属性
• A对应的函数过程中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。

第65页：设计递归下降翻译器的方法（续）

设计递归下降翻译器的方法（续）

• 2.非终结符A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。

第66页：设计递归下降翻译器的方法

设计递归下降翻译器的方法

• 3.每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作：i)对于带有综合属性x的终结符X，把x的值存入为X.x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号。ii)对于每个非终结符B，产生一个右边带有函数调用的赋值语句c=B(b1,b2,…,bk)，其中，b1,b2,…,bk是为B的继承属性设置的变量，c是为B的综合属性设置的变量。iii)对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用。

第67页：设计递归下降翻译器的方法（续）

设计递归下降翻译器的方法（续）

{R.s

=R.i}T →( E ){T.nptr:=E.nptr}T →id{T.nptr:=mkleaf(id,id.entry)}T →num{T.nptr:=mkleaf(num,num.val)}

第68页：设计递归下降翻译器的方法

设计递归下降翻译器的方法

{R.s

=R.i}

第69页：设计递归下降翻译器的方法（续）

设计递归下降翻译器的方法（续）

的分析过程procedare R;beginif sym=addop then beginadvance;T; Rendelse begin endend;

第70页：设计递归下降翻译器的方法

设计递归下降翻译器的方法

↑AST-node)

↑AST-node;varnptr,i1,s1,s: ↑AST-node;addoplexeme: char;beginif sym=addop then beginaddoplexeme:=lexval;advance;nptr:=T;i1:=mknode (addoplexeme,in,nptr);s1:=R (i1)s:=s1endelse s:=in;returnsend;R → oddopT{R1.i:=mknode(addop.lexme, R.i,T.nptr)}R1{R.s:=R1.s}R→

{R.s

=R.i}

第71页：6.5自下而上计算继承属性

6.5自下而上计算继承属性

• 在自下而上的分析过程中实现L-属性文法的方法
• 可实现任何基于LL(1)文法的L-属性文法，还可以实现许多（不是所有）基于LR(1)文法的L-属性文法

第72页：6.5自下而上计算继承属性（续）

6.5自下而上计算继承属性（续）

• 从翻译模式中去掉嵌入在产生式中间的动作
• 要求把所有的语义动作都放在产生式的末尾
• 转换方法，它可以使所有嵌入的动作都出现在产生式的末尾
• 加入新的产生式M→
• 把嵌入在产生式中的每个语义动作用不同的标记非终结符M代替，并把这个动作放在产生式M→
• 的末尾

第73页：6.5自下而上计算继承属性

6.5自下而上计算继承属性

• T → num {print (num.val)}
• T → num {print (num.val)}M →
• {print (‘＋’)}N →
• {print (‘－’)}

第74页：6.5自下而上计算继承属性（续）

6.5自下而上计算继承属性（续）

• P164-1，2，5，7
• P164-11，12（选作）