72节要点 属性文法(语法制导的定义)( Syntax-Directed Definition) 形式:CFG的每个产生式A→α对应与之相关联的一个语义规则( semantIc rules)集合,每条规则形如b=f(cl,c2,,ck),其中f是一个函数,b,c1,c2,…,k 是该产生式中文法符号的属性( attributes),b有两个可能:(1)是A的一个属 性,cl,c,…,ck是产生式右部文法符号的属性或A的其它属性称b是A的综合 属性( synthesized attribute),(2)是产生式右部某个文法符号x的一个属性并且 c1,c2,,q是A或产生式右部任何文法符号的属性,则称b是文法符号ⅹ的继承 属性( inherited attribute 函数f通常以表达式的形式出现。 有时,某些语义规则的目的只是为了表达副作用,这类语义规则可以表达为 过程调用或代码段。这可以理解为是定义相关产生式左部非终结符A的综合属 性值,只是没有把此虚设的属性和=号显现出来而已。 2.综合属性用于“自下而上传递信息,而继承属性用于自上而下传递信息。 3.基于属性文法的处理,或语法制导的翻译( Synta- Directed Translation 两类处理方法:(1)通过遍历分析树进行属性计算(树遍历方法);(2)语 法分析遍的同时进行属性计算( On-the-fly方法,即一遍扫描方法 树遍历方法步骤1)构造对应输入串的语法分析树;2)构造属性依赖图; (3)若该依赖图是无圈的,则按造此无圈图的_种拓扑排序( topological sort) 对分析树进行遍历,则可以计算所有的属性。依赖图的概念和构造方法见教材
7.2 节要点： 1． 属性文法(语法制导的定义)（Syntax-Directed Definition）。 形式：CFG 的每个产生式 A→ 对应与之相关联的一个语义规则（semantic rules）集合，每条规则形如 b:=f(c1, c2, …, ck)，其中 f 是一个函数，b,c1, c2, …, ck 是该产生式中文法符号的属性（attributes），b 有两个可能：（1）是 A 的一个属 性, c1, c2, …, ck 是产生式右部文法符号的属性或 A 的其它属性,称 b 是 A 的综合 属性（synthesized attribute），（2）是产生式右部某个文法符号 x 的一个属性,并且 c1, c2, …, ck 是 A 或产生式右部任何文法符号的属性,则称 b 是文法符号 x 的继承 属性（inherited attribute）。 函数 f 通常以表达式的形式出现。 有时，某些语义规则的目的只是为了表达副作用，这类语义规则可以表达为 过程调用或代码段。这可以理解为是定义相关产生式左部非终结符 A 的综合属 性值，只是没有把此虚设的属性和:=号显现出来而已。 2． 综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。 3． 基于属性文法的处理，或语法制导的翻译（Syntax-Directed Translation）。 两类处理方法：（1）通过遍历分析树进行属性计算（树遍历方法）；（2）语 法分析遍的同时进行属性计算（On-the-fly 方法，即一遍扫描方法）。 树遍历方法步骤：（1）构造对应输入串的语法分析树；（2）构造属性依赖图； （3）若该依赖图是无圈的，则按造此无圈图的一种拓扑排序（topological sort） 对分析树进行遍历，则可以计算所有的属性。依赖图的概念和构造方法见教材
172页。 遍扫描方法只适合于特定的属性文法(语法制导定义)。本课程只讨论S- 属性文法和L-属性文法的情形 4.S-属性文法中只包含综合属性。L-属性文法中可以有继承属性,但产生式右 端某文法符号的继承属性的计算只取决于该符号左边文法符号(包括产生式左边 的文法符号)的属性,可参见教材174页。S-属性文法是L-属性文法的一个特例。 5.S-属性文法的翻译通常采用自下而上的方式进行。若采用LR分析技术,可 以通过扩充分析栈中的域,形成语义栈来存放综合属性的值,计算相应产生式左 部文法符号的综合属性值刚好发生在每一步归约之前的时刻。 例如,假设有相应于产生式A→XYZ的语义规则Aa=f(Xx,Yy,Zz 在XYZ归约到A之前,Xx,Yy,和Z.z分别存放于语义栈的top,top-1和top2 的相应域中,因此Aa可以顺利求出。归约后,Xx,Yy,Zz被弹出,而在栈顶 top的位置上存放A 6.L-属性文法的翻译可以采用深度优先后序遍历的方式进行,参考如下算法 procedure dfvisit(: node); b forn的每一孩子m,从左到右do begin 计算m的继承属性值; dfvisit(m 计算n的综合属性值 d
172 页。 一遍扫描方法只适合于特定的属性文法(语法制导定义)。本课程只讨论 S- 属性文法和 L-属性文法的情形。 4． S-属性文法中只包含综合属性。L-属性文法中可以有继承属性，但产生式右 端某文法符号的继承属性的计算只取决于该符号左边文法符号（包括产生式左边 的文法符号）的属性，可参见教材 174 页。S-属性文法是 L-属性文法的一个特例。 5．S-属性文法的翻译通常采用自下而上的方式进行。若采用 LR 分析技术，可 以通过扩充分析栈中的域，形成语义栈来存放综合属性的值，计算相应产生式左 部文法符号的综合属性值刚好发生在每一步归约之前的时刻。 例如，假设有相应于产生式 A→XYZ 的语义规则 A.a := f（X.x, Y.y, Z.z）。 在 XYZ 归约到 A 之前，X.x, Y.y, 和 Z.z 分别存放于语义栈的 top，top-1 和 top-2 的相应域中，因此 A.a 可以顺利求出。归约后，X.x, Y.y, Z.z 被弹出，而在栈顶 top 的位置上存放 A.a。 6．L-属性文法的翻译可以采用深度优先后序遍历的方式进行，参考如下算法： procedure dfvisit(n: node); begin for n 的每一孩子 m, 从左到右 do begin 计算 m 的继承属性值; dfvisit(m) end; 计算 n 的综合属性值 end
该算法可以和自上而下预测分析的过程对应。因此,基于LL(1)文法的L 属性定义可以采用这种方法进行翻译。 7.翻译模式( Translation Scheme)形式上类似于属性文法,但允许由{}括起来 的语义规则集合(即语义动作)出现在产生式右端的任何位置。这样做的好处是 可以显式地表达动作和属性计算的次序,而在前述的语法制导定义不体现计算次 序。 在设计翻译模式时,必须作某些限制,以确保毎个属性值在被访问到的时候 已经存在。我们仅讨论两类受限的翻译模式 一是受S属性文法的启示,对于仅需要综合属性的情形,只要创建一个语 义规则集合,放在相应产生式右端的末尾,把属性的赋值规则加入其中即可。 二是受L-属性文法的启示,对于即包含继承属性又包含综合属性的情形, 必须注意1)产生式右端某个符号的继承属性的计算必须位于该符号之前12) 每个计算规则不访问位于它右边符号的综合属性;(3)产生式左部非终结符的综 合属性的计算只能在所用到的属性都已计算岀来之后迸行通常放在相应产生式 右端的末尾。 8.继承属性的自下而上计算。本课程主要涉及到三种技术:(1)从翻译模 式中去掉嵌入在产生式中间的动作yacc的处理方法);(2)分析栈中的继承属性 处理;(3)用综合属性代替继承属性。对于(1)(3),通过教材176页82.4 中的例子理解即可。对于(2),要点是复写规则( copy rules)的处理及其应用, 简述如下 自下而上翻译程序根据产生式A→XY的归约过程中,假设ⅹ的综合属性
该算法可以和自上而下预测分析的过程对应。因此，基于 LL(1)文法的 L- 属性定义可以采用这种方法进行翻译。 7． 翻译模式（Translation Scheme）形式上类似于属性文法，但允许由{}括起来 的语义规则集合（即语义动作）出现在产生式右端的任何位置。这样做的好处是 可以显式地表达动作和属性计算的次序，而在前述的语法制导定义不体现计算次 序。 在设计翻译模式时，必须作某些限制，以确保每个属性值在被访问到的时候 已经存在。我们仅讨论两类受限的翻译模式： 一是受 S-属性文法的启示，对于仅需要综合属性的情形，只要创建一个语 义规则集合，放在相应产生式右端的末尾，把属性的赋值规则加入其中即可。 二是受 L-属性文法的启示，对于即包含继承属性又包含综合属性的情形， 必须注意：（1）产生式右端某个符号的继承属性的计算必须位于该符号之前；（2） 每个计算规则不访问位于它右边符号的综合属性；（3）产生式左部非终结符的综 合属性的计算只能在所用到的属性都已计算出来之后进行，通常放在相应产生式 右端的末尾。 8．继承属性的自下而上计算。本课程主要涉及到三种技术：（1）从翻译模 式中去掉嵌入在产生式中间的动作(yacc 的处理方法)；（2）分析栈中的继承属性 处理；（3）用综合属性代替继承属性。对于（1）、（3），通过教材 176 页 8.2.4 中的例子理解即可。对于（2），要点是复写规则（copy rules）的处理及其应用， 简述如下： 自下而上翻译程序根据产生式 A→XY 的归约过程中，假设 X 的综合属性
Xs已经出现在语义栈上。因为在Y以下子树的任何归约之前,Xs的值一直存 在,因此它可以被Y继承。如果用复写规则Yi=Xs来定义Y的继承属性Yi, 则在需要Yi时,可以使用ⅹs。这一点可以通过阅读课堂讲稿中的例子加以理 解。 课堂讲稿中倒数第2页中的Yacc程序片断。 输入串为 babb时的输出结果为: BI S3 NUM2 是将A:B{Ss=num*2;}AB{num=$2;$S=$3+1;}用如下两条产生式 替换 A:BMAB{num=$2;$$=$3+l;} M:{$$=num*2;} 此外,请大家通过阅读Yacc文档,理解一下$$出现在不同位置时的 含义。如出现在产生式的末尾、中间的语义规则集(语义动作)中,出现在=的 左边和右边
X.s 已经出现在语义栈上。因为在 Y 以下子树的任何归约之前，X.s 的值一直存 在，因此它可以被 Y 继承。如果用复写规则 Y.i:=X.s 来定义 Y 的继承属性 Y.i， 则在需要 Y.i 时，可以使用 X.s。这一点可以通过阅读课堂讲稿中的例子加以理 解。 课堂讲稿中倒数第 2 页中的 Yacc 程序片断。 输入串为 bbabb 时的输出结果为： B1 B1 B1 B2 S3 NUM2 是将 A: B {$$ = num * 2;} A B {num = $2; $$ = $3+1; } 用如下两条产生式 替换： A: B M A B {num = $2; $$ = $3+1; } M: {$$ = num * 2;} 此外，请大家通过阅读 Yacc 文档，理解一下 $$ 出现在不同位置时的 含义。如出现在产生式的末尾、中间的语义规则集（语义动作）中，出现在:=的 左边和右边