72节要点 属性文法(语法制导的定义)( Syntax- Directed Definition 飛式:每个产生式A→α对应与之相关联的一个语义规则( semantic rules) 集合,每条规则形如b=f(c1,c2,…,k),其中f是一个函数,b,c,c2,,k是该产 生式中文法符号的属性( attributes),b有两个可能:(1)是A的综合属性 ( synthesized attribute),(2)是a中文法符号的继承属性( inherited attribute b 函数f通常以表达式的形式出现 有时,某些语义规则的目的只是为了表达副作用,这类语义规则可以表达为 过程调用或代码段。这可以理解为是定义相关产生式左部非终结符A的综合属 性值,只是没有把此虚设的属性和=号显现出来而已。 2.综合属性用于“自下而上传递信息,而继承属性用于“自上而下ˆ传递信息。 3.基于属性文法的处理,或语法制导的翻译( Syntax- Directed translation) 两类处理方法:(1)通过遍历分析树进行属性计算(树遍历方法);(2)语 法分析遍的同时进行属性计算(On-the-Ⅳy方法,即一遍扫描方法知 树遍历方法步骤:(1)构造对应输入串的语法分析数;(2)构造依赖图;(3) 若该依赖图是无圈的,则按造此无圈图的一种拓扑排序( topological sort)对分 析树进行遍历,则可以计算所有的属性。依赖图的概念和构造方法见教材172 页 遍扫描方法只适合于特定的语法制导定义。本课程只讨论S-属性定义(对 应讲稿中的S-属性文法)和L属性定义(对应讲稿中的L-属性文法)的情形
7.2 节要点： 1． 属性文法(语法制导的定义)（Syntax-Directed Definition）。 形式：每个产生式 A→ 对应与之相关联的一个语义规则（semantic rules） 集合，每条规则形如 b:=f(c1, c2, …, ck)，其中 f 是一个函数，b,c1, c2, …, ck 是该产 生式中文法符号的属性（attributes），b 有两个可能：（1）是 A 的综合属性 （synthesized attribute），（2）是 中文法符号的继承属性（inherited attribute）。 函数 f 通常以表达式的形式出现。 有时，某些语义规则的目的只是为了表达副作用，这类语义规则可以表达为 过程调用或代码段。这可以理解为是定义相关产生式左部非终结符 A 的综合属 性值，只是没有把此虚设的属性和:=号显现出来而已。 2． 综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。 3． 基于属性文法的处理，或语法制导的翻译（Syntax-Directed Translation）。 两类处理方法：（1）通过遍历分析树进行属性计算（树遍历方法）；（2）语 法分析遍的同时进行属性计算（On-the-fly 方法，即一遍扫描方法）。 树遍历方法步骤：（1）构造对应输入串的语法分析数；（2）构造依赖图；（3） 若该依赖图是无圈的，则按造此无圈图的一种拓扑排序（topological sort）对分 析树进行遍历，则可以计算所有的属性。依赖图的概念和构造方法见教材 172 页。 一遍扫描方法只适合于特定的语法制导定义。本课程只讨论 S-属性定义（对 应讲稿中的 S-属性文法）和 L-属性定义（对应讲稿中的 L-属性文法）的情形
4.S-属性定义中只包含综合属性。L-属性定义中可以有继承属性,但产生式右 端某文法符号的继承属性的计算只取决于该符号左边文法符号(包括产生式左边 的文法符号)的属性,可参见教材174页。S-属性定义是L属性定义的一个特例。 5.S-属性定义的翻译通常采用自下而上的方式进行。若采用LR分析技术,可 以通过扩充分析栈中的域,形成语义栈来存放综合属性的值,计算相应产生式左 部文法符号的综合属性值刚好发生在每一步归约之前的时刻。 例如,假设有相应于产生式A→XYZ的语义规则Aa=f(Xx,Yy,Zz) 在ⅩYZ归约到A之前,Xx,Yy,和Zz分别存放于语义栈的top,top-1和top-2 的相应域中,因此Aa可以顺利求出。归约后,Xx,Yy,Z.z被弹出,而在栈顶 top的位置上存放Aa 6.L-属性定义的翻译可以采用深度优先后序遍历的方式进行,参考如下算法(见 影印板龙书297页) procedure dfvisit(n: node); forn的每一孩子m,从左到右do begin 计算m的继承属性值; dfvisit(m) end 计算n的综合属性值 end 该算法可以和自上而下预测分析的过程对应。因此,基于LL(1)文法的L 属性定义可以采用这种方法进行翻译。 7.翻译模式( Translation Scheme)形式上类似于属性文法,但允许由{括起来
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-属性定义的翻译可以采用深度优先后序遍历的方式进行，参考如下算法（见 影印板龙书 297 页）： 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)产生式右端某个符号的继承属性的计算必须位于该符号之前(2) 每个计算规则不访问位于它右边符号的综合属性;(3)产生式左部非终结符的综 合属性的计算只能在所用到的属性都已计算出来之后进行,通常放在相应产生式 右端的未尾 8.为借助于自上而下的预测分析技术进行语法制导翻译,可以采用如教材第 175页的方法将含有左递归的翻译模式转换成不含左递归的翻译模式 9.对基于适合于自上而下预测技术的翻译模式,语法制导翻译程序可以如下构 造 对每个非终结符A,构造一个函数,以A的每个继承属性为形参( call by reference),以A的综合属性为返回值。如同预测分析程序的构造,该函数代码 的流程是根据当前的输入符号来决定调用哪个产生式。与每个产生式相关的代码 根据产生式右端的终结符,非终结符,和语义规则集(语义动作),依从左右的 次序完成下列工作
的语义规则集合（即语义动作）出现在产生式右端的任何位置。这样做的好处是 可以显式地表达动作和属性计算的次序，而在前述的语法制导定义不体现计算次 序。 在设计翻译模式时，必须作某些限制，以确保每个属性值在被访问到的时候 已经存在。我们仅讨论两类受限的翻译模式： 一是受 S-属性定义的启示，对于仅需要综合属性的情形，只要创建一个语 义规则集合，放在相应产生式右端的末尾，把属性的赋值规则加入其中即可。 二是受 L-属性定义的启示，对于即包含继承属性又包含综合属性的情形， 必须注意：（1）产生式右端某个符号的继承属性的计算必须位于该符号之前；（2） 每个计算规则不访问位于它右边符号的综合属性；（3）产生式左部非终结符的综 合属性的计算只能在所用到的属性都已计算出来之后进行，通常放在相应产生式 右端的末尾。 8． 为借助于自上而下的预测分析技术进行语法制导翻译，可以采用如教材第 175 页的方法将含有左递归的翻译模式转换成不含左递归的翻译模式。 9． 对基于适合于自上而下预测技术的翻译模式，语法制导翻译程序可以如下构 造： 对每个非终结符 A，构造一个函数，以 A 的每个继承属性为形参（call by reference），以 A 的综合属性为返回值。如同预测分析程序的构造，该函数代码 的流程是根据当前的输入符号来决定调用哪个产生式。与每个产生式相关的代码 根据产生式右端的终结符，非终结符，和语义规则集（语义动作），依从左右的 次序完成下列工作：
(1)对终结符ⅹ,保存其综合属性ⅹ的值至专为ⅹⅹ而声明的变量;然后 调用匹配终结符( match token)和取下一输入符号( next token)的函数。 (2)对非终结符B,利用相应的函数调用产生赋值语句c=B(b,b,…,bk) 其中变量bl,b2,…,bk对应B的个继承属性,变量c对应B的综合属性。 (3)对语义规则集,直接copy其中每一语义规则(动作)来产生代码,只 是将对属性的访问替换为属性对应的变量。 10.继承属性的自下而上计算。本课程主要涉及到三种技术:(1)从翻译模式中 去掉嵌入在产生式中间的动作;(2)分析栈中的继承属性处理;(3)用综合属性 代替继承属性。对于(1)(3),通过教材176页824中的例子理解即可。对于 (2),课堂上没来及讲,要点是复写规则( copy rules)的处理及其应用,这里 对其进行一些简述 自下而上翻译程序根据产生式A→XY的归约过程中,假设ⅹ的综合属性 X.s已经出现在语义栈上。因为在Y以下子树的任何归约之前,X.s的值一直存 在,因此它可以被Y继承。如果用复写规则Yi=Xs来定义Y的继承属性Yi, 则在需要Yi时,可以使用ⅹs。这一点可以通过阅读课堂讲稿中的例子加以理 解。 下面补充两个这种复写规则处理的应用例子,以加深理解。 考虑如下翻译模式 S→>aA{Ci=As}C S→>bAB{Ci=A.s}C C→c{C.s=g(C.n) 若直接应用上述复写规则的处理方法,则在使用C→c迸行归约时,Ci的
（1）对终结符 X，保存其综合属性 x 的值至专为 X.x 而声明的变量；然后 调用匹配终结符（match_token）和取下一输入符号（next_token）的函数。 （2） 对非终结符 B，利用相应的函数调用产生赋值语句 c:=B(b1, b2, …, bk)， 其中变量 b1, b2, …, bk 对应 B 的个继承属性，变量 c 对应 B 的综合属性。 （3）对语义规则集，直接 copy 其中每一语义规则（动作）来产生代码，只 是将对属性的访问替换为属性对应的变量。 10．继承属性的自下而上计算。本课程主要涉及到三种技术：（1）从翻译模式中 去掉嵌入在产生式中间的动作；（2）分析栈中的继承属性处理；（3）用综合属性 代替继承属性。对于（1）、（3），通过教材 176 页 8.2.4 中的例子理解即可。对于 （2），课堂上没来及讲，要点是复写规则（copy rules）的处理及其应用，这里 对其进行一些简述： 自下而上翻译程序根据产生式 A→XY 的归约过程中，假设 X 的综合属性 X.s 已经出现在语义栈上。因为在 Y 以下子树的任何归约之前，X.s 的值一直存 在，因此它可以被 Y 继承。如果用复写规则 Y.i:=X.s 来定义 Y 的继承属性 Y.i， 则在需要 Y.i 时，可以使用 X.s。这一点可以通过阅读课堂讲稿中的例子加以理 解。 下面补充两个这种复写规则处理的应用例子，以加深理解。 考虑如下翻译模式： S → a A {C.i := A.s} C S → b A B {C.i := A.s} C C → c {C.s := g(C.i)} 若直接应用上述复写规则的处理方法，则在使用 C → c 进行归约时，C.i 的
值或存在于次栈顶(top-1),或存在于次次栈顶(top-2),不能确定用哪一个。 种可行的做法是引入新的非终结符M,将以上翻译模式改造为 S→>aA{Ci=A.s}C S>bABIM.: =AS)MC. i: MS)C {C.s=g(C.)} yac这样处理 S→aAMC S→ bab m o C→c{C.s=g(C.i)} M→>E{C.i=A.s} 这样在使用C→c进行归约时Ci的值就一定可以通过访问次栈页top-1) 得到。想一想,为什么? 另一个例子,考虑如下翻译模式 S→>aA{C.i=f(A.s)}C 这里,继承属性Ci不是通过复写规则来求值,而是通过普通函数f(A.s)调 用来计算。在计算Ci时,As在语义栈上,但f(A.s)并未不存在于语义栈。同样, 种做法是引入新的非终结符M,将以上翻译模式改造为: SaAM.i =AS) Ci: =Ms)C M→E{Ms:=f(Mi)} yacc这样处理 S→aAMC M→e{Ci:=f(A.s)} 这样就解决了上述问题。想一想,为什么? I1.课堂讲稿中倒数第2页中的Yac程序片断
值或存在于次栈顶（top-1），或存在于次次栈顶（top-2），不能确定用哪一个。 一种可行的做法是引入新的非终结符 M，将以上翻译模式改造为： S → a A {C.i := A.s} C S → b A B {M.i := A.s} M {C.i := M.s} C C → c {C.s := g(C.i)} M → ε {M.s := M.i } yacc 这样处理 S → a A M C S → b A B M C C → c {C.s := g(C.i)} M → ε {C.i := A.s} 这样，在使用 C → c 进行归约时，C.i 的值就一定可以通过访问次栈顶（top-1） 得到。想一想，为什么？ 另一个例子，考虑如下翻译模式： S → a A {C.i := f(A.s)} C 这里，继承属性 C.i 不是通过复写规则来求值，而是通过普通函数 f(A.s) 调 用来计算。在计算 C.i 时，A.s 在语义栈上，但 f(A.s)并未不存在于语义栈。同样， 一种做法是引入新的非终结符 M，将以上翻译模式改造为： S → a A {M.i := A.s} M {C.i := M.s} C M → ε {M.s := f(M.i)} yacc 这样处理 S → a A M C M → ε {C.i := f(A.s)} 这样就解决了上述问题。想一想，为什么？ 11．课堂讲稿中倒数第 2 页中的 Yacc 程序片断
输入串为 babb时的输出结果为 BI BI BI S3 NUM2 若将A:B{$s=num*2;}AB{num=$2;$$=$3+1;}用如下两条产生式 替换 A:BMAB{num=S2;$$=$3+1;} M:{$$=num*2;} 请给出新的程序片断在输入串为 babb时的输出结果,与前面的结果进行比 此外,请大家通过阅读Yac文档,理解一下$s出现在不同位置时的含义 如出现在产生式的末尾、中间的语义规则集(语义动作)中,出现在=的左边和 右边 注:本材料中所提到的龙书是指 ALFRED VAHO RAVISETHI JEFFREY DULLMAN Compilers Principles, Techniques, and Tools
输入串为 bbabb 时的输出结果为： B1 B1 B1 B1 S3 NUM2 若将 A: B {$$ = num * 2;} A B {num = $2; $$ = $3+1; } 用如下两条产生式 替换： A: B M A B {num = $2; $$ = $3+1; } M: {$$ = num * 2;} 请给出新的程序片断在输入串为 bbabb 时的输出结果，与前面的结果进行比 较。 此外，请大家通过阅读 Yacc 文档，理解一下 $$ 出现在不同位置时的含义。 如出现在产生式的末尾、中间的语义规则集（语义动作）中，出现在:=的左边和 右边。 注：本材料中所提到的龙书是指： ALFRED V.AHO，RAVI SETHI， JEFFREY D.ULLMAN Compilers Principles,Techniques,and Tools