7.2属性文法和语法制导翻译程序设计 语言的语义静态语义 是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，
它可以分为类型规则和作用域 /可见性规则两大类如：类型相容性 变量先声明后引用 名称相关要求动态语义 程序单位描述的计算编译程序的语义处理工作 静态语义审查执行动态语义 （计算）生成代码,..
语 法 分 析 后 的 源 程 序? 语义处理语义形式化 语义建模形式语义学 (如指称语义学、公理语义学、
操作语义学等 )的研究已取得了许多重大的进展
文法模型 ---- 属性文法
命令式或操作式模型 ----- 操作语义学
应用式模型 -----指称语义学
公理式模型 -----公理语义学属性文法和语法制导翻译在实际应用中比较流行的语义描述和语义处理的方法
1 属性文法概述
2 基于属性文法的处理方法
3 S-属性文法的自下而上计算
4 L-属性文法
L-属性文法和自顶向下翻译自下而上的分析中实现 L-属性文法
7.2.1属性文法概述表达式文法 E—>T+T| T or T
T—>n | b
E?T1 + T2 { T1.type = int
T2.type = T1.type
E.type,=int}
E?T1 or T2 { T1.type = bool
T2.type = T1.type
E.type,=bool}
T? n { T.type,= int}
T? b { T.type,= bool}
input,/* empty string */
| input line;
line,'\n'
| exp '\n' { printf ("\t%.10g\n",$1); }
| error?\n‘;
exp,NUM { $$ = $1; }
| exp '+' exp { $$ = $1 + $3; }
| exp '-' exp { $$ = $1 - $3; }
| exp '*' exp { $$ = $1 * $3; }
| exp '/' exp { $$ = $1 / $3; }
| '-' exp %prec NEG { $$ = -$2; }
| exp '^' exp { $$ = pow ($1,$3); }
| '(' exp ')' { $$ = $2; };
属性文法属性文法 (attribute grammar)是一个三元组：
A=(G,V,F),其中
G:是一个上下文无关文法
V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息，
如它的类型、值、代码序列、符号表内容等等,属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。
F:关于属性的属性断言或一组属性的计算规则 (称为语义规则 ),断言或语义规则与一个产生式相联,引用该产生式左端或右端的终结符或非终结符相联的属性,
属性通常分为两类,综合属性和继承属性 。简单地说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。
属性文法中,对应于每个产生式 A都有一套与之相关联的语义规则,每条规则的形式为 b:=f(c1,c2… ck)
f是一个函数,b和 c1,c2… ck是该产生式文法符号的属性,
并且
（ 1） 如果 b是 A的一个属性,c1,c2… ck是产生式右部文法符号的属性或 A的其他属性,则称 b是 A的综合属性
（ 2） 如果 b是产生式右部某个文法符号 X的一个属性,
并且 c1,c2… ck是 A或产生式右边任何文法符号的属性,则称 b是文法符号 X 的继承属性在两种情况下,我们都说属性 b依赖于属性 c1,c2… ck
一般，对出现在产生式左边的继承属性和出现在产生式右边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，
然而,出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算,它们由其它产生式的属性规则计算或者由属性计算器的参数提供 。
A?X1 X2 … Xn
A的综合属性 S(A)计算公式 S(A):=f(I(X1),…,I(Xn))
Xj的继承属性 T(Xj)计算公式 T(Xj):=f(I(A),..,I(Xn))
1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性,
2)终结符只有综合属性,它们由词法程序提供,
如非终结符 A,B和 C，其中 A有一个继承属性 a和一个综合属性 b,B有综合属性 c,C有继承属性 d,对 产生式
A?BC可能有语义规则 C.d:=B.c+1和 A.b:=A.a+B.c
而属性 A.a和 B.c是在其他地方计算的。
语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码（中间）生成等等。有些语义规则可能产生副作用（如产生代码），也可能是个函数，通常把这样的语义规则写成过程调用或过程段一个 属性文法 和 综合属性 的例子 例,1
非终结符 E,T及 F都有一个综合属性 val,符号 digit有一个综合属性，
它的值由词法分析器提供。与产生式 L→E 对应的语义规则仅仅是打印由 E产生的算术表达式的值的一个过程，我们可认为这条规则定义了 L的一个虚属性。某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现语 义 规 则
L E
E E1+T
E T
T T1 * F
T F
F (E)
F digit
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+4，则语义动作打印数值
19
.
L
E.val=19
E.val=15 T.val=4
T.val=15 F.val=4
T.val=3
F.val=3
F.val=5
digit.lexval=4
digit.lexval=5
digit.lexval=3
+
*
3*5+4的带注释的分析树继承属性
一个结点的继承属性值是由此结点的父结点和 /或兄弟结点的某些属性来决定的。
例 2 继承属性 L.in
生 产 式 语 义 规 则
D?TL
T? int
T?real
L? L1,id
L? id
L.in:=T.type
T.type:=integer
T.type:=real
L1.in:=L.inaddtype(id.entry,L.in)
addtype(id.entry,L.in)
D
L.in= real
L.in= real
L.in= real
T.type=real
real
id2
id1
id3
.
Real id1,id2,id3
每个 L结点都带有继承属性的语法树
，
，
例 3
P –> DS
D –> var V; D |?
S –> V,= e; S |?
V –> x | y | z
现在使用两个属性,name和 dl，每当一个新的变量声明时，就把它的 name
属性附给它,name属性是综合属性。
将所声明的变量都放到一个变量名字清单中（用语义函数 addlist实现），用属性收集声明块中声明的所有变量。然后这个 dl属性又作为继承属性传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变量名字清单中
P –> DS {S.dl,= D.dl}
D1 –> var V; D2 |?{D1.dl,= addlist(V.name,D2.dl)} |
{D1.dl,= NULL}
S1 –> V,= e; S2 |?{check(V.name,S1.dl); S2.dl,= S1.dl}
V –> x | y | z {V.name,= 'x'} | {V.name,= 'y'} |
{V.name,= 'z'}
var x； var y； y:=e；
P
D dl={x,y} S dl={x,y}
var V ； D dl={y} V,= e ； S
x var V ； D dl={ } y?
y?
例 4：定义定点二进制数的 CFG:
(1) N?S?S
(2) S?SB
(3) S?B
(4) B?0
(5) B?1
(1) N?S?S(2) S?SB(3) S?B(4) B?0(5) B?1
非终结符 N表示整个二进制数的数值，综合属性 v附加在 N上,N v 非终结符 B 表示一个二进制数字，它有自己的值 v,但该值分配给
N的值与它的位置有关，是与 2成比例，比例因子 f是从 S继承的属性,所以,B v f
非终结符 S 表示一个二进制数字串，它也有值，但该值与串的位置 (f)有关,与串的长度 l有关,S f v l
构造数值的属性断言可以如下,
N?v——>S?f1?v 1? l1? S? f 2? v 2? l2
{v:=v1+v2; f 1,=1; f2:=2-l2}
S? f? v? l——> S? f1?v1? l 1B? f 2?v2
{f1:=2f ; f 2:=f; v:=v 1+v2 ;l:=l1+1}
——> B? f? v {l:=1}
B? f? v——>0 {v:=0}
——>1 {v:=f}
(1) N?S?S(2) S?SB(3) S?B(4)
B?0(5) B?1
文法定义的二进制数的形式为 dmdm-1…d1d0,fkf
k-1…f1f0,其中 dmdm-1…d1d0 和 fkf k-1…f1f0
都是二进制数字，这种形式的二进制数的数值计算公式是：
dm × 2m + dm-1× 2m-1 +…d1 × 21 +d0+fk× 2-1 +fk-
1× 2-2 +…f1 × 2 -k +f0× 2-(k+1)
= dm × 2m + dm-1× 2m-1 +…d1 × 21 +d0+(fk× 2k
+fk-1× 2 (k-1) …+f1 × 21 +f0)/ 2k+1
为了计算小数部分的值，需要知道二进制数字的个数，也即 S定义的数串的长度，因此对非终结符 S附加两个属性 val和 length
N? S1 ―?‖ S2 { N.val,= S1.val +
2 –S2.len *S2,val ; }
S? S1 B { S.val,= 2 * S1.val + B.val;
S.len,= S1.len + 1 }
S? B { S.val,= B.val; S.len:= 1 }
B?―0‖ {B.val,=0}
B?―1‖ {B.val:= 1}
N?v?S? i1? l1 ―?‖ S? i2? l2 {v:= i1+ 2-l2? i2 }
S? i? l? S? i1? l 1 B?i2 { i,=2 i1+ i2; ;l:=l1+1}
B? i {l:=1}
B? i?―0‖ {i,=0}
―1‖ {i,=1}
7.2.2基于属性文法的处理过程从概念上讲,基于属性文法的处理过程即语法制导翻译通常是这样的：对单词符号串进行语法分析,构造语法分析树,然后根据需要构造属性依赖图,遍历语法树并在语法树的各结点处按语义规则进行计算输入符号串
分析树
属性依赖图
语义规则的计算顺序依赖图由称为依赖图的一个有向图 描述分析树中的继承属性和属性中间的相互依赖关系。
依赖图的构造算法：
for分析树中每一个结点 n do
for 结点的文法符号的每一个属性 a do
为 a在依赖图中建立一个结点；
for 分析树中每一个结点 n do
for结点 n所用产生式对应的每一个语义规则
b:=f(c1,c2,…c k) do
for i,=1 to k do
从 ci结点到 b结点构造一条有向边依赖图 ----例 2
例 2 继承属性 L.in
生 产 式 语 义 规 则
D?TL
T? int
T?real
L? L1,id
L? id
L.in:=T.type
T.type:=integer
T.type:=real
L1.in:=L.inaddtype(id.entry,L.in)
addtype(id.entry,L.in)
例 2 Real id1,id2,id3分析树的依赖图 (图中的结点用数字表示 )
5 6
7 8
9 10
T 4
D
L
L
L
Real
type
in
in
in
3 entry
2 entry
entry
id3
id2
id1
,
,
1
例 2 Real id1,id2,id3分析树的依赖图的说明
依赖图中的结点由数字来标识。
从代表 T.type的结点 4有一条有向边连到代表
L.in的结点 5，因为根据产生式 D→TL 的语义规则 L.in:=T.type,可知 L.in依赖于 T.type.
根据产生式 L? L1,id的语义规则 L1.in:=L.in，
可知 L1.in依赖于 L.in，所以有两条向下的有向边分别进入结点 7和 9。
每一个与 L产生式有关的语义规则 addtype(id,
Entry,L.in)都产生一个虚属性，结点 6,8和
10都是为这些虚属性构造的。
良定义的属性文法。
很显然，一条求值规则只有在其各变元值均已求得的情况下才可以使用。但有时候可能会出现一个属性对另一个属性的循环依赖关系。如，
p,c1,c2都是属性，若有下求值规则：
p,= f1(c1),c1,= f2(c2),c2,= f3(p)时，就无法对 p求值。如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。
属性的计算顺序一个有向非循环图的拓扑序是图中结点的任何顺序 m1,m2,…,
mk，使得边必须是从序列中前面的结点指向后面的结点。
也就是说，如果 mi→m j是 mi到 mj的一条边，那么在序列中
mi必须出现在 mj之前。
一个依赖图的任何拓扑排序都给出一个分析树中结点的语义规则计算的有效顺序。 这就是说，在拓扑排序中，在一个结点，语义规则 b:=f(c1,c2,…c k)中的属性 c1,c2,…c k在计算 b以前都是可用的。
属性文法 说明的翻译是很精确的。最基本的文法用于建立输入符号串的分析树。依赖图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。
再考查例 2Real id1,id2,id3分析树的依赖图每一条边都是从序号较低的结点指向序号较高的结点。历此，依赖图的一个拓扑排序可以从低序号到高序号顺序写出。从这个拓扑排序中我们可以得到下列程序，用 an来代表依赖图中与序号 n的结点有关的属性：
a4,= real
a5,= a4
addtype (id3.entry,a5);
a7,= a5;
addtype (id2.entry,a7)
a9,= a7
addtype (id1.entry,a9)
这些语义规则的计算将把 real类型填入到每个标识符对应的符号表项中。
属性计算方法
树遍历的属性计算方法设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。
最常 用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历（或称遍）。
一遍扫描的处理方法与树遍历的属性计算文法不同,一遍扫描的处理方法是在语法分析的同时计算属性值,而不是语法分析构造语法树之后进行属性的计算,而且并无需构造实际的语法树 。
因为一遍扫描的处理方法与语法分析器的相互作用,它与下面两个因素密切相关：
（ 1） 所采用的语法分析方法
（ 2） 属性的计算次序 。
构造数值的属性断言可以如下,
N?v——>S?f1?v 1? l1? S? f 2? v 2? l2
{v:=v1+v2; f 1,=1; f2:=2-l2}
S? f? v? l——> S? f1?v1? l 1B? f 2?v2
{f1:=2f ; f 2:=f; v:=v 1+v2 ;l:=l1+1}
——> B? f? v {l:=1}
B? f? v——>0 {v:=0}
——>1 {v:=f}
在某些情况下可用一遍扫描实现属性文法的语义规则计算 。 也就是说在语法分析的同时完成语义规则的计算,无须明显地构造语法树或构造属性之间的依赖图 。 因为单遍实现对于编译效率非常重要具体的实现希望在单遍扫描中完成翻译研究怎样实现这种翻译器。一个一般的属性文法的翻译器可能是很难建立的，然而有一大类属性文法的翻译器是很容易建立的
s-属性 适用于 自底向上的计算
L-属性 适用于自顶向下的计算，也可用于 自底向上。
7.2.3 S－属性文法的自下而上计算
S－属性文法，它只含有综合属性。
综合属性可以在分析输入符号串的同时自下而上的来计算 。 分析器可以保存与栈中文法符号有关的综合属性值,每当进行归约时,
新的属性值就由栈中正在归约的产生式右边符号的属性值来计算 。
S－属性文法的翻译器通常可借助于 LR分析器实现 。 在 S－属性文法的基础上,LR分析器可以改造为一个翻译器,在对输入串进行语法分析的同时对属性进行计算 。
产生式 语义规则
０）Ｌ → Ｅ ｐｒｉｎｔ（Ｅ,ｖａｌ）
１）Ｅ → Ｅ 1＋Ｔ Ｅ,ｖａｌ ∶ ＝Ｅ 1.ｖａｌ＋Ｔ,ｖａｌ
２）Ｅ → Ｔ Ｅ,ｖａｌ ∶ ＝Ｔ,ｖａ l
３）Ｔ → Ｔ 1*Ｆ Ｔ,ｖａｌ ∶ ＝Ｔ 1.ｖａｌ × Ｆ,ｖ ａｌ
４）Ｔ → F Ｔ,ｖａｌ ∶ ＝ F.ｖａｌ
５）Ｆ → （Ｅ） Ｆ,ｖａｌ ∶ ＝Ｅ,ｖａｌ
６）Ｆ → ｄ iｇ iｔ Ｆ,ｖａｌ,＝ｄｉｇｉｔ,ｌｅｘｖａｌ
LR分析器可以改造为一个翻译器 增加语义栈,
在对输入串进行语法分析的同时对属性进行计算 。
ＬＲ分析 器模型总控程序 output
Input#
S1 Xm
…
S1
…
X1
S0 #
栈状态 符号
ACTION GOTO
LR分析表产生式表
Vm
V1
-
语义
…
S0
２＋３ *５的分析和计值过程步骤 动作 状态栈 语义栈 (值栈 ) 符号栈 余留输入串
１） ０ － ＃ ２＋ 3*５＃
２） ０５ －－ ＃ 2 ＋ 3 *５＃
３） ｒ６ ０３ －２ ＃Ｆ ＋３ *５＃
４）ｒ４ ０２ －２ ＃Ｔ ＋３ *５＃
５）ｒ２ ０１ －２ ＃Ｅ ＋３ *５＃
６） ０１６ －２－ ＃Ｅ＋ ３ *５＃
７） ０１６５ －２－－ *５＃
８）ｒ６ ０１６３ －２－３ *５＃
９）ｒ４ ０１６９ －２－３ *５＃
１０） ０１６９７ －２－３－ ＃Ｅ＋Ｔ *
１１） ０１６９７５ －２－３－－ ＃Ｅ＋Ｔ *５ ＃
１２）ｒ６ ０１６９７（１０） －２－３－５ ＃Ｅ＋Ｔ *Ｆ #
１３）ｒ３ ０１６９ －２－（１５） ＃Ｅ＋Ｔ ＃
１４）ｒ１ － （１７） ＃Ｅ ＃
１５）接受
BOTTOM—UP
语义处理是作类型检查,对二目运算符的运算对象进行类型匹配审查 。
(LR分 析 ）,增加语义栈 归约 时进行语义动作,
例 5 G[E]:
(1) E?T+T
(2) E?T or T
(3) T?n
(4) T?b
E?T1 + T2
{ if T1.type = int and T2.type= int
then E.type,=int
else error}
E?T1 or T2
{ if T1.type = bool and T2.type= bool
then E.type,=bool
else error}
T? n { T.type,= int}
T? b { T.type,= bool}
w =n + n#
4 n --
o # --
2 T int
o # --
5 + --
2 T int
o # --
4 n --
5 + - -
2 T int
o # --
6 T int
5 + --
2 T int
o # --
1 E int
0 # --
G[E],的 L R (0) 分析表
ac t i on GO TO
状态 + o n b # E T
0 S4 S3 1 2
1 ac c
2 s5 s7
3 r4 r4 r4 r4 r4
4 r3 r3 r3 r3 r3
5 s4 s3 6
6 r1 r1 r1 r1 r1
7 s4 s3 8
8 r2 r2 r2 r2 r2
G[E]:
(1) E?T+T
(2) E?T or T
(3) T?n
(4) T?b
w =n +b
4 n --
o # --
2 T int
o # --
5 + --
2 T int
o # --
3 b --
5 + ---
2 T int
o # --
6 T bo o l
5 + --
2 T int
o # --
1 E error
o # --
7.2.4 L－属性文法一个属性文法称为 L－属性文法,如果对于每个产生式
A→X 1X2… Xn,其每个语义规则中的每个属性或者是综合属性,或者是 Xj（ 1≤j≤n） 的一个继承属性且这个继承属性仅依赖于：
（ 1） 产生式 Xj在左边符号 X1,X2,…,Xj-1的属性；
（ 2） A的继承属性 。
S－属性文法一定是 L－属性文法,因为 （ 1）,（ 2） 限制只用于继承属性 。
L－属性文法 例,1
非终结符 E,T及 F都有一个综合属性 val,符号 digit有一个综合属性，
它的值由词法分析器提供。与产生式 L→E 对应的语义规则仅仅是打印由 E产生的算术表达式的值的一个过程，我们可认为这条规则定义了 L的一个虚属性。某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现语 义 规 则
L E
E E1+T
E T
T T1 * F
T F
F (E)
F digit
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
产 生式
L－属性文法
一个结点的继承属性值依赖于父结点的继承属性和 /或左部兄弟结点的某些属性来决定的。
例 2 继承属性 L.in
生 产 式 语 义 规 则
D?TL
T? int
T?real
L? L1,id
L? id
L.in:=T.type
T.type:=integer
T.type:=real
L1.in:=L.inaddtype(id.entry,L.in)
addtype(id.entry,L.in)
L－属性文法和自顶向下翻译
L－属性文法允许一次遍历就计算出所有属性值 。
LL（ 1） 这种自上而下分析文法的分析过程,从概念上说可以看成是深度优先建立语法树的过程,因此,我们可以在自上而下语法分析的同时实现 L属性文法的计算 。
例 2 Real id1,id2,id3分析树的依赖图 (图中的结点用数字表示 )
5 6
7 8
9 10
T 4
D
L
L
L
Real
type
in
in
in
3 entry
2 entry
entry
id3
id2
id1
,
,
1
例 6:中缀表达式翻译成相应的后缀表达式
LR分析,E→E addop T print(addop,Lexeme) | T
T→num print(num.val)
LL（ 1）分析,
E→TR R→addop T R| ε T→num
9－ 5＋ 2的语法树
E
T+E
2T-
T
9
5
E
说明语义动作的语法树
E
T+E
2T-
T
9
5
{print‘+‘}
E
{print‘9‘}
{print‘5‘}
{print‘-‘} {print‘2‘}
（消除左递归） 9-5+2的语法树
E
RT
T-9
T+5 R
R
2?
说明语义动作的语法树
E
RT
Print‘-‘-9
T+5
R
R
2
print‘9‘ T
print‘5‘
print‘2‘
Print‘+‘
翻译模式（ Translation schemes）适合语法制导翻译的另一种描述形式。翻译模式给出了使用语义规则进行计算的次序，可把某些实现细节表示出来。在翻译模式中，
和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号｛｝括起来，插入到产生式右部的合适位置上。
例（中缀表达式翻译成相应的后缀表达式）
E→TR
R→ addop T {print(addop,Lexeme)} R1|ε
T→ num {print(num.val)}
( E→TR R→addop T R| ε T→num )
( E→E addop T | T T→num)
输入串 9－ 5 + 2的语法树
E
T R
9 - T R
5 + T R
2 ε
输入串 9－ 5 + 2的说明动作的语法树,每个语义动作都作为相应产生式左部符号的结点的儿子,把语义动作看作是终结符,按深度优先次序执行图中的动作后，打印输出 95
－ 2+。
E
T R
9 print(?9‘) - T print(?-‘) R
5 print(?5‘) + T print(?+‘) R
2 print(?2‘) ε
L－属性文法在自顶向下分析中的实现带左递归的文法的翻译模式
E→E 1 + T {E.val,= E1.val + T.val}
E→E 1－ T {E.val,= E1.val－ T.val}
E→T {E.val,= T.val}
T→(E) {T.val,= E.val}
T→num {T.val,= num.val}
消除左递归的同时考虑属性，构造新的 翻译模式
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}
计算表达式 9-5+2
,E
R.i=9
T.val=5
T.val=9
R.i=4
R.i=6
T.val=2
num.val=9
num.val=5
num.val=2
_
+?
在这个翻译模式中，每个数都是由 T产生的，并且 T.val的值就是由属性 num.val给出的数的词法值。
子表达式 9－ 5中的数字 9是由最左边的 T生成的，但是减号和 5是由根的右子结点 R生成的。继承属性 R.i从 T.val得到值 9。
通过产生式中嵌入的下面动作：
{R1.i,= R.i－ T.val}
实现计算 9－ 5并把结果 4传递到中间的 R结点,
类似的动作把 2加到 9－ 5的值上，在最下面的 R结点处产生结果 R.i＝ 6。这个结果将成为根结点处 E.val的值,
R的 综合属性 s在图中没有表示出来，它用来向上复制这一结果一直到树根。
对于自顶向下分析,我们假设动作是在处于相同位置上的符号被展开 （ 匹配成功 ）
时执行的 。 如图中的第二个产生式中,
第一个动作 （ 对 R1.i赋值 ） 是在 T被完全展开成终结符号后执行的,第二个动作是在 R1被完全展开成终结符号后执行的 。
正如前面我们所讨论的,一个符号的继承属性必须由出现在这个符号之前的动作来计算,产生式左边非终结符的综合属性必须在它所依赖的所有属性都计算出来以后才能计算 。
转换左递归翻译模式的方法推广到一般假设翻译模式 1：
A→A 1Y {A.a,= g(A1.a,Y.y)}
A→X {A.a,= f(X.x)}
每个文法符号都有一个综合属性,用相应的小写字母表示,
g和 f是任意函数消除左递归,文法转换成：
A→XR R→YR ｜ ε
再考虑语义动作,翻译模式变为 2
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}
翻译模式 1和翻译模式 2的结果是一样的。
可以给出串 XY1Y2两棵带注释的语法树看出来，一棵是根据翻译模式 1自下而上计算属性的。一棵是根据翻译模式 2自上而下计算的。
A→A 1Y {A.a,= g(A1。 a,Y.y)}
A→X {A.a,= f(X.x)}
A.a=g(g(f(X.x),Y1.y),Y2.y)
A.a=g(f(X.x),Y1.y) Y2
A.a=f(X.x) Y1
X
A
A Y
A Y
X
A→X{R.i,= f(X.x)} R→Y {R1.i,= g((R.i),Y.y)}
R {A.a,=R.s} R1{R.s,= R1.s}
A→XR R→YR ｜ ε
A
X R
Y1 R
Y2 R
A
X R.i=f(X.x)
Y1 R.i=g(f(X.x),Y1.y)
Y2 R.i=g(g(f(X.x),Y1.y),Y2.y)
自下而上计算继承属性 --自下而上的分析中实现 L-属性文法
从翻译模式中去掉嵌入在产生式中间的动作
分析栈中的继承属性
用综合属性代替继承属性从翻译模式中去掉嵌入在产生式中间的动作转换方法,
引入新的非终结符 N和产生式 N→ ε,把嵌入在产生式中间的动作用非终结符 N代替,并把这个动作放在产生式后面,
例,
E→T R
R→ + T {print (?+‘) } R1
R→ - T {print(?-‘) } R1
R→ε
T→num {print (num.val) }
文法变换后,接受的语言相同,
E→T R
R→ + T M R1
R→ - T N R1
R→ε
T→num {print (num.val) }
M→ε {print (?+‘) }
N→ε {print (? -‘) }
目的,使所有嵌入的动作都出现在产生式的末尾,可以自下而上处理继承属性,
一个属性文法称为 L－属性文法,如果对于每个产生式
A→X 1X2… Xn,其每个语义规则中的每个属性或者是综合属性,或者是 Xj（ 1≤j≤n） 的一个继承属性且这个继承属性仅依赖于：
（ 1） 产生式 Xj在左边符号 X1,X2,…,Xj-1的属性；
（ 2） A的继承属性 。
分析栈中的继承属性
自下而上分析器对产生式 A→XY 的右部是通过把 X和 Y从分析栈中移出并用 A代替它们 。
假设 X有一个综合属性 X.s,按照前面所介绍的方法我们把它与 X一起放在分析栈中 。
由于 X.s的值在 Y以下的子树中的任何归约之前已经放在栈中,这个值可以被 Y继承 。 也就是说,如果继承属性 Y.i是由复写规则 Y.i:
= X.s定义的,则可以在需要 y.i值的地方使用
X.s的值 。 在自下而上分析中计算属性值时复写规则起非常重要的作用 。 看下面例子 。
标识符的类型通过继承属性的复写规则来传递翻译模式为：
D→T {L.in,= T.type}
L
T→int {T.type,= integer}
T→real {T.type,= real}
L→ {L1.in,= L.in}
L1,id {addtype (id.entry,L.in)}
L→id {addtype (id.entry,L.in)}
回顾例 2 Real id1,id2,id3分析树的依赖图
5 6
7 8
9 10
T 4
D
L
L
L
Real
type
in
in
in
3 entry
2 entry
entry
id3
id2
id1
.
.
1
例 2输入串 real Real id1,id2,id3的 分析过程 当 L的右部被归约时，
T恰好在这个右部的下面输入 状态 (符号） 使用产生式
Real id1,id2,id3#
id1,id2,id3# real
id1,id2,id3# T T?real
,id2,id3# Tid1
,id2,id3# TL L? id
id2,id3# TL,
,id3# TL,id2
,id3# TL L? L,id
id3# TL,
# TL,id3
# TL L? L,id
# D D? TL
扩充分析栈 Val[i]存放文法符号 X
的综合属性 X.s
D→T L
T→int {Val[top],= integer}
T→real {Val[top],= real}
L→L,id {addtype (Val[top],Val[top-3]}
L→id {addtype (Val[top],Val[top-1}}
用综合属性代替继承属性有时,改变基础文法可能避免继承属性 。 例如,一个
Pascal的说明由一标识符序列后跟类型组成,如,m,
n,integer。 这样的说明的文法可由下面形式的产生式构成
D→L,T
T→integer|char
L→L,id|id
因为标识符由 L产生而类型不在 L的子树中，我们不能仅仅使用综合属性就把类型与标识符联系起来。事实上，如果非终结符 L从第一个产生式中它的右边 T
中继承了类型，则我们得到的属性文法就不是 L－
属性的，因此，基于这个属性文法的翻译工作不能在语法分析的同时进行。
一个解决的方法是重新构造文法使类型作为标识符表 (identifiers list)的最后一个元素：
D→id L
L→,id L|,T
T→integer|char
这样,类型可以通过综合属性 L.type进行传递,当通过 L产生每个标识符时,它的类型就可以填入到符号表中 。
Yacc或 bison作为编译程序的生成工具，利用的就是语法制导翻译方法。它使用符号 $$表示产生式左端的属性，
$n表示存取产生式右端第 n个文法符号相联的属性如例 3作为 Yacc的输入，可写成：
P → DS {$2.dl=$1.dl}
D1 → var V ； D{$$.dl=addlist($2.name,$4.dl)}
| {$$.dl=null}
S1 → V:=e ； S{check($1.name,$$.dl)；
$5.dl=$$.dl}
|
V → x {$$.name= ’x’}
|y {$$.name=’y’}
|z {$$.name=’z’}
如果数据结构 attribute定义属性 name和 dl，可以具体化为：
type struct_attribute {
char *name；
struct_attribute *list；
} attribute；
P → DS {$2.list=$1.list}
D1 → var V ； D{$$.list=add_to_list($2.name,$4.list)}
| {$$.list=null}
S1 → V:=e ； S{check($1.name,$$.list)；
$5.list=$$.list}
|
V → x {$$.name= ’x’}
|y {$$.name=’y’}
|z {$$.name=’z’}
Review- attribute grammars
We augment the conventional grammar with information to
control the semantic analysis and translation,Such grammars
are called attribute grammars.
We augment a grammar by associating attributes with each
grammar symbol that describes its properties,An attribute has
a name and an associated value— a string,a number,a type,a
memory location,an assigned register,generated
code,whatever information we need.
With each production in a grammar,we give semantic rules or
actions,which describe how to compute the attribute values
associated with each grammar symbol in a production,The
attribute value for a parse node may depend on information
from its children nodes below or its siblings and parent node
above.
Review- synthesized or inherited
attributes
There are two types of attributes we might encounter,
synthesized or inherited,
Synthesized attributes are those attributes that are
passed up a parse tree,i.e.,the left-side attribute is
computed from the right-side attributes.
Inherited attributes are those that are passed down a
parse tree,i.e.,the right-side attributes are derived
from the left-side attributes (or other right-side
attributes),These attributes are used for passing
information about the context to nodes further down
the tree.
Review- Syntax-directed translation
Syntax-directed translation refers to a
method of compiler implementation
where the source language translation
is completely driven by the parser
Review-
E' –> E
E –> T | E A T
T –> F | T M F
F –> (E) | int
A –> + | -
M –> * | /
E' -> E { printf("%d\n",E.val); }
E -> T { E.val = T.val; }
| E A T { switch(A.op) {
case ADD,E.val = E.val + T.val; break;
case SUB,E.val = E.val - T.val; break;}
}
T -> F { T.val = F.val;}
| T M F { switch(M.op) {
case MUL,T.val = T.val * F.val; break;
case DIV,T.val = T.val / F.val; break;}
}
F -> (E) { F.val = E.val; }
| int { F.val = int.val; }
A -> + { A.op = ADD; }
| - { A.op = SUB; }
M -> * { M.op = MUL; }
| / { M.op = DIV; }
Attributes and Yacc
E' -> E { printf("%d\n",$1); }
E -> T { $$ = $1; }
| E A T { switch($2) {
case ADD,$$ = $1 + $3; break;
case SUB,$$ = $1 - $3; break;}
}
T -> F {$$ = $1;}
| T M F { switch($2) {
case MUL,$$= $1 * $3; break;
case DIV,$$ = $1 / $3; break;}
}
F -> (E) { $$= $2; }
| int { $$ = $1; }
A -> + { $$ = ADD; }
| - { $$ = SUB; }
M -> * { $$ = MUL; }
| / { $$ = DIV; }.
表达式文法 G[E],E? E＋ T｜ E – T | T T? id |
num | (E)
1.请为表达式建立抽象语法树设计一个属性文法，
给出语义函数如下，每个函数都返回一个指向新建立结点的指针：
（ 1） mknode (op,left,right)建立一个运算符号结点，
标记是 op，两个域 left和 right分别指向左子树和右子树。
（ 2） mkleaf(id,entry)建立一个标识符结点，标记为 id，一个域 entry指向标识符在符号表中的入口。
（ 3） mkleaf(num,val)建立一个数结点，标记为
num，一个域 val用于存放数的值。
2.这是 S-属性文法还是 L-属性文法？
抽象语法树 -精简的语法树运算符和关键字作为内部结点如,if B then S1 else S2 和 3*5+3
if-then-else +
* 3
B S1 S2 3 5
1.为每个非终结符附上一个属性 Ptr，表示指向树结点的指针。
E? E1＋ T{E.Ptr,= mknode(―+‖ E1.Ptr,T.Ptr)}
E? E1 –T {E.Ptr,= mknode(―-‖ E1.Ptr,T.Ptr)}
E? T {E.Ptr,=T.Ptr}
T? id {T.Ptr,= mkleaf(id,entry)}
T? num {T.Ptr,= mkleaf(num,val)}
T? (E) {T.Ptr,=E.Ptr}
2.这是 S-属性文法也是 L-属性文法。
现有如下的 YACC程序片段,
%{
int num = 1;
%}
%%
S,A {printf(―S %d num %d\n‖,$1,num);};
A,B{$$ = num * 2;}AB{num = $2; $$ = $3+1; }
| a{$$ = 1};
B,b {$$ = 10; printf(―B %d\n‖,num);};
请写出输入串为 bbabb时的输出结果,
参考书
ALFRED V.AHO
RAVI SETHI
JEFFREY D.ULLMAN
Compilers
Principles,Techniques,and Tools
Chapter 5
它可以分为类型规则和作用域 /可见性规则两大类如：类型相容性 变量先声明后引用 名称相关要求动态语义 程序单位描述的计算编译程序的语义处理工作 静态语义审查执行动态语义 （计算）生成代码,..
语 法 分 析 后 的 源 程 序? 语义处理语义形式化 语义建模形式语义学 (如指称语义学、公理语义学、
操作语义学等 )的研究已取得了许多重大的进展
文法模型 ---- 属性文法
命令式或操作式模型 ----- 操作语义学
应用式模型 -----指称语义学
公理式模型 -----公理语义学属性文法和语法制导翻译在实际应用中比较流行的语义描述和语义处理的方法
1 属性文法概述
2 基于属性文法的处理方法
3 S-属性文法的自下而上计算
4 L-属性文法
L-属性文法和自顶向下翻译自下而上的分析中实现 L-属性文法
7.2.1属性文法概述表达式文法 E—>T+T| T or T
T—>n | b
E?T1 + T2 { T1.type = int
T2.type = T1.type
E.type,=int}
E?T1 or T2 { T1.type = bool
T2.type = T1.type
E.type,=bool}
T? n { T.type,= int}
T? b { T.type,= bool}
input,/* empty string */
| input line;
line,'\n'
| exp '\n' { printf ("\t%.10g\n",$1); }
| error?\n‘;
exp,NUM { $$ = $1; }
| exp '+' exp { $$ = $1 + $3; }
| exp '-' exp { $$ = $1 - $3; }
| exp '*' exp { $$ = $1 * $3; }
| exp '/' exp { $$ = $1 / $3; }
| '-' exp %prec NEG { $$ = -$2; }
| exp '^' exp { $$ = pow ($1,$3); }
| '(' exp ')' { $$ = $2; };
属性文法属性文法 (attribute grammar)是一个三元组：
A=(G,V,F),其中
G:是一个上下文无关文法
V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息，
如它的类型、值、代码序列、符号表内容等等,属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。
F:关于属性的属性断言或一组属性的计算规则 (称为语义规则 ),断言或语义规则与一个产生式相联,引用该产生式左端或右端的终结符或非终结符相联的属性,
属性通常分为两类,综合属性和继承属性 。简单地说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。
属性文法中,对应于每个产生式 A都有一套与之相关联的语义规则,每条规则的形式为 b:=f(c1,c2… ck)
f是一个函数,b和 c1,c2… ck是该产生式文法符号的属性,
并且
（ 1） 如果 b是 A的一个属性,c1,c2… ck是产生式右部文法符号的属性或 A的其他属性,则称 b是 A的综合属性
（ 2） 如果 b是产生式右部某个文法符号 X的一个属性,
并且 c1,c2… ck是 A或产生式右边任何文法符号的属性,则称 b是文法符号 X 的继承属性在两种情况下,我们都说属性 b依赖于属性 c1,c2… ck
一般，对出现在产生式左边的继承属性和出现在产生式右边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，
然而,出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算,它们由其它产生式的属性规则计算或者由属性计算器的参数提供 。
A?X1 X2 … Xn
A的综合属性 S(A)计算公式 S(A):=f(I(X1),…,I(Xn))
Xj的继承属性 T(Xj)计算公式 T(Xj):=f(I(A),..,I(Xn))
1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性,
2)终结符只有综合属性,它们由词法程序提供,
如非终结符 A,B和 C，其中 A有一个继承属性 a和一个综合属性 b,B有综合属性 c,C有继承属性 d,对 产生式
A?BC可能有语义规则 C.d:=B.c+1和 A.b:=A.a+B.c
而属性 A.a和 B.c是在其他地方计算的。
语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码（中间）生成等等。有些语义规则可能产生副作用（如产生代码），也可能是个函数，通常把这样的语义规则写成过程调用或过程段一个 属性文法 和 综合属性 的例子 例,1
非终结符 E,T及 F都有一个综合属性 val,符号 digit有一个综合属性，
它的值由词法分析器提供。与产生式 L→E 对应的语义规则仅仅是打印由 E产生的算术表达式的值的一个过程，我们可认为这条规则定义了 L的一个虚属性。某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现语 义 规 则
L E
E E1+T
E T
T T1 * F
T F
F (E)
F digit
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+4，则语义动作打印数值
19
.
L
E.val=19
E.val=15 T.val=4
T.val=15 F.val=4
T.val=3
F.val=3
F.val=5
digit.lexval=4
digit.lexval=5
digit.lexval=3
+
*
3*5+4的带注释的分析树继承属性
一个结点的继承属性值是由此结点的父结点和 /或兄弟结点的某些属性来决定的。
例 2 继承属性 L.in
生 产 式 语 义 规 则
D?TL
T? int
T?real
L? L1,id
L? id
L.in:=T.type
T.type:=integer
T.type:=real
L1.in:=L.inaddtype(id.entry,L.in)
addtype(id.entry,L.in)
D
L.in= real
L.in= real
L.in= real
T.type=real
real
id2
id1
id3
.
Real id1,id2,id3
每个 L结点都带有继承属性的语法树
，
，
例 3
P –> DS
D –> var V; D |?
S –> V,= e; S |?
V –> x | y | z
现在使用两个属性,name和 dl，每当一个新的变量声明时，就把它的 name
属性附给它,name属性是综合属性。
将所声明的变量都放到一个变量名字清单中（用语义函数 addlist实现），用属性收集声明块中声明的所有变量。然后这个 dl属性又作为继承属性传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变量名字清单中
P –> DS {S.dl,= D.dl}
D1 –> var V; D2 |?{D1.dl,= addlist(V.name,D2.dl)} |
{D1.dl,= NULL}
S1 –> V,= e; S2 |?{check(V.name,S1.dl); S2.dl,= S1.dl}
V –> x | y | z {V.name,= 'x'} | {V.name,= 'y'} |
{V.name,= 'z'}
var x； var y； y:=e；
P
D dl={x,y} S dl={x,y}
var V ； D dl={y} V,= e ； S
x var V ； D dl={ } y?
y?
例 4：定义定点二进制数的 CFG:
(1) N?S?S
(2) S?SB
(3) S?B
(4) B?0
(5) B?1
(1) N?S?S(2) S?SB(3) S?B(4) B?0(5) B?1
非终结符 N表示整个二进制数的数值，综合属性 v附加在 N上,N v 非终结符 B 表示一个二进制数字，它有自己的值 v,但该值分配给
N的值与它的位置有关，是与 2成比例，比例因子 f是从 S继承的属性,所以,B v f
非终结符 S 表示一个二进制数字串，它也有值，但该值与串的位置 (f)有关,与串的长度 l有关,S f v l
构造数值的属性断言可以如下,
N?v——>S?f1?v 1? l1? S? f 2? v 2? l2
{v:=v1+v2; f 1,=1; f2:=2-l2}
S? f? v? l——> S? f1?v1? l 1B? f 2?v2
{f1:=2f ; f 2:=f; v:=v 1+v2 ;l:=l1+1}
——> B? f? v {l:=1}
B? f? v——>0 {v:=0}
——>1 {v:=f}
(1) N?S?S(2) S?SB(3) S?B(4)
B?0(5) B?1
文法定义的二进制数的形式为 dmdm-1…d1d0,fkf
k-1…f1f0,其中 dmdm-1…d1d0 和 fkf k-1…f1f0
都是二进制数字，这种形式的二进制数的数值计算公式是：
dm × 2m + dm-1× 2m-1 +…d1 × 21 +d0+fk× 2-1 +fk-
1× 2-2 +…f1 × 2 -k +f0× 2-(k+1)
= dm × 2m + dm-1× 2m-1 +…d1 × 21 +d0+(fk× 2k
+fk-1× 2 (k-1) …+f1 × 21 +f0)/ 2k+1
为了计算小数部分的值，需要知道二进制数字的个数，也即 S定义的数串的长度，因此对非终结符 S附加两个属性 val和 length
N? S1 ―?‖ S2 { N.val,= S1.val +
2 –S2.len *S2,val ; }
S? S1 B { S.val,= 2 * S1.val + B.val;
S.len,= S1.len + 1 }
S? B { S.val,= B.val; S.len:= 1 }
B?―0‖ {B.val,=0}
B?―1‖ {B.val:= 1}
N?v?S? i1? l1 ―?‖ S? i2? l2 {v:= i1+ 2-l2? i2 }
S? i? l? S? i1? l 1 B?i2 { i,=2 i1+ i2; ;l:=l1+1}
B? i {l:=1}
B? i?―0‖ {i,=0}
―1‖ {i,=1}
7.2.2基于属性文法的处理过程从概念上讲,基于属性文法的处理过程即语法制导翻译通常是这样的：对单词符号串进行语法分析,构造语法分析树,然后根据需要构造属性依赖图,遍历语法树并在语法树的各结点处按语义规则进行计算输入符号串
分析树
属性依赖图
语义规则的计算顺序依赖图由称为依赖图的一个有向图 描述分析树中的继承属性和属性中间的相互依赖关系。
依赖图的构造算法：
for分析树中每一个结点 n do
for 结点的文法符号的每一个属性 a do
为 a在依赖图中建立一个结点；
for 分析树中每一个结点 n do
for结点 n所用产生式对应的每一个语义规则
b:=f(c1,c2,…c k) do
for i,=1 to k do
从 ci结点到 b结点构造一条有向边依赖图 ----例 2
例 2 继承属性 L.in
生 产 式 语 义 规 则
D?TL
T? int
T?real
L? L1,id
L? id
L.in:=T.type
T.type:=integer
T.type:=real
L1.in:=L.inaddtype(id.entry,L.in)
addtype(id.entry,L.in)
例 2 Real id1,id2,id3分析树的依赖图 (图中的结点用数字表示 )
5 6
7 8
9 10
T 4
D
L
L
L
Real
type
in
in
in
3 entry
2 entry
entry
id3
id2
id1
,
,
1
例 2 Real id1,id2,id3分析树的依赖图的说明
依赖图中的结点由数字来标识。
从代表 T.type的结点 4有一条有向边连到代表
L.in的结点 5，因为根据产生式 D→TL 的语义规则 L.in:=T.type,可知 L.in依赖于 T.type.
根据产生式 L? L1,id的语义规则 L1.in:=L.in，
可知 L1.in依赖于 L.in，所以有两条向下的有向边分别进入结点 7和 9。
每一个与 L产生式有关的语义规则 addtype(id,
Entry,L.in)都产生一个虚属性，结点 6,8和
10都是为这些虚属性构造的。
良定义的属性文法。
很显然，一条求值规则只有在其各变元值均已求得的情况下才可以使用。但有时候可能会出现一个属性对另一个属性的循环依赖关系。如，
p,c1,c2都是属性，若有下求值规则：
p,= f1(c1),c1,= f2(c2),c2,= f3(p)时，就无法对 p求值。如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。
属性的计算顺序一个有向非循环图的拓扑序是图中结点的任何顺序 m1,m2,…,
mk，使得边必须是从序列中前面的结点指向后面的结点。
也就是说，如果 mi→m j是 mi到 mj的一条边，那么在序列中
mi必须出现在 mj之前。
一个依赖图的任何拓扑排序都给出一个分析树中结点的语义规则计算的有效顺序。 这就是说，在拓扑排序中，在一个结点，语义规则 b:=f(c1,c2,…c k)中的属性 c1,c2,…c k在计算 b以前都是可用的。
属性文法 说明的翻译是很精确的。最基本的文法用于建立输入符号串的分析树。依赖图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。
再考查例 2Real id1,id2,id3分析树的依赖图每一条边都是从序号较低的结点指向序号较高的结点。历此，依赖图的一个拓扑排序可以从低序号到高序号顺序写出。从这个拓扑排序中我们可以得到下列程序，用 an来代表依赖图中与序号 n的结点有关的属性：
a4,= real
a5,= a4
addtype (id3.entry,a5);
a7,= a5;
addtype (id2.entry,a7)
a9,= a7
addtype (id1.entry,a9)
这些语义规则的计算将把 real类型填入到每个标识符对应的符号表项中。
属性计算方法
树遍历的属性计算方法设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。
最常 用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历（或称遍）。
一遍扫描的处理方法与树遍历的属性计算文法不同,一遍扫描的处理方法是在语法分析的同时计算属性值,而不是语法分析构造语法树之后进行属性的计算,而且并无需构造实际的语法树 。
因为一遍扫描的处理方法与语法分析器的相互作用,它与下面两个因素密切相关：
（ 1） 所采用的语法分析方法
（ 2） 属性的计算次序 。
构造数值的属性断言可以如下,
N?v——>S?f1?v 1? l1? S? f 2? v 2? l2
{v:=v1+v2; f 1,=1; f2:=2-l2}
S? f? v? l——> S? f1?v1? l 1B? f 2?v2
{f1:=2f ; f 2:=f; v:=v 1+v2 ;l:=l1+1}
——> B? f? v {l:=1}
B? f? v——>0 {v:=0}
——>1 {v:=f}
在某些情况下可用一遍扫描实现属性文法的语义规则计算 。 也就是说在语法分析的同时完成语义规则的计算,无须明显地构造语法树或构造属性之间的依赖图 。 因为单遍实现对于编译效率非常重要具体的实现希望在单遍扫描中完成翻译研究怎样实现这种翻译器。一个一般的属性文法的翻译器可能是很难建立的，然而有一大类属性文法的翻译器是很容易建立的
s-属性 适用于 自底向上的计算
L-属性 适用于自顶向下的计算，也可用于 自底向上。
7.2.3 S－属性文法的自下而上计算
S－属性文法，它只含有综合属性。
综合属性可以在分析输入符号串的同时自下而上的来计算 。 分析器可以保存与栈中文法符号有关的综合属性值,每当进行归约时,
新的属性值就由栈中正在归约的产生式右边符号的属性值来计算 。
S－属性文法的翻译器通常可借助于 LR分析器实现 。 在 S－属性文法的基础上,LR分析器可以改造为一个翻译器,在对输入串进行语法分析的同时对属性进行计算 。
产生式 语义规则
０）Ｌ → Ｅ ｐｒｉｎｔ（Ｅ,ｖａｌ）
１）Ｅ → Ｅ 1＋Ｔ Ｅ,ｖａｌ ∶ ＝Ｅ 1.ｖａｌ＋Ｔ,ｖａｌ
２）Ｅ → Ｔ Ｅ,ｖａｌ ∶ ＝Ｔ,ｖａ l
３）Ｔ → Ｔ 1*Ｆ Ｔ,ｖａｌ ∶ ＝Ｔ 1.ｖａｌ × Ｆ,ｖ ａｌ
４）Ｔ → F Ｔ,ｖａｌ ∶ ＝ F.ｖａｌ
５）Ｆ → （Ｅ） Ｆ,ｖａｌ ∶ ＝Ｅ,ｖａｌ
６）Ｆ → ｄ iｇ iｔ Ｆ,ｖａｌ,＝ｄｉｇｉｔ,ｌｅｘｖａｌ
LR分析器可以改造为一个翻译器 增加语义栈,
在对输入串进行语法分析的同时对属性进行计算 。
ＬＲ分析 器模型总控程序 output
Input#
S1 Xm
…
S1
…
X1
S0 #
栈状态 符号
ACTION GOTO
LR分析表产生式表
Vm
V1
-
语义
…
S0
２＋３ *５的分析和计值过程步骤 动作 状态栈 语义栈 (值栈 ) 符号栈 余留输入串
１） ０ － ＃ ２＋ 3*５＃
２） ０５ －－ ＃ 2 ＋ 3 *５＃
３） ｒ６ ０３ －２ ＃Ｆ ＋３ *５＃
４）ｒ４ ０２ －２ ＃Ｔ ＋３ *５＃
５）ｒ２ ０１ －２ ＃Ｅ ＋３ *５＃
６） ０１６ －２－ ＃Ｅ＋ ３ *５＃
７） ０１６５ －２－－ *５＃
８）ｒ６ ０１６３ －２－３ *５＃
９）ｒ４ ０１６９ －２－３ *５＃
１０） ０１６９７ －２－３－ ＃Ｅ＋Ｔ *
１１） ０１６９７５ －２－３－－ ＃Ｅ＋Ｔ *５ ＃
１２）ｒ６ ０１６９７（１０） －２－３－５ ＃Ｅ＋Ｔ *Ｆ #
１３）ｒ３ ０１６９ －２－（１５） ＃Ｅ＋Ｔ ＃
１４）ｒ１ － （１７） ＃Ｅ ＃
１５）接受
BOTTOM—UP
语义处理是作类型检查,对二目运算符的运算对象进行类型匹配审查 。
(LR分 析 ）,增加语义栈 归约 时进行语义动作,
例 5 G[E]:
(1) E?T+T
(2) E?T or T
(3) T?n
(4) T?b
E?T1 + T2
{ if T1.type = int and T2.type= int
then E.type,=int
else error}
E?T1 or T2
{ if T1.type = bool and T2.type= bool
then E.type,=bool
else error}
T? n { T.type,= int}
T? b { T.type,= bool}
w =n + n#
4 n --
o # --
2 T int
o # --
5 + --
2 T int
o # --
4 n --
5 + - -
2 T int
o # --
6 T int
5 + --
2 T int
o # --
1 E int
0 # --
G[E],的 L R (0) 分析表
ac t i on GO TO
状态 + o n b # E T
0 S4 S3 1 2
1 ac c
2 s5 s7
3 r4 r4 r4 r4 r4
4 r3 r3 r3 r3 r3
5 s4 s3 6
6 r1 r1 r1 r1 r1
7 s4 s3 8
8 r2 r2 r2 r2 r2
G[E]:
(1) E?T+T
(2) E?T or T
(3) T?n
(4) T?b
w =n +b
4 n --
o # --
2 T int
o # --
5 + --
2 T int
o # --
3 b --
5 + ---
2 T int
o # --
6 T bo o l
5 + --
2 T int
o # --
1 E error
o # --
7.2.4 L－属性文法一个属性文法称为 L－属性文法,如果对于每个产生式
A→X 1X2… Xn,其每个语义规则中的每个属性或者是综合属性,或者是 Xj（ 1≤j≤n） 的一个继承属性且这个继承属性仅依赖于：
（ 1） 产生式 Xj在左边符号 X1,X2,…,Xj-1的属性；
（ 2） A的继承属性 。
S－属性文法一定是 L－属性文法,因为 （ 1）,（ 2） 限制只用于继承属性 。
L－属性文法 例,1
非终结符 E,T及 F都有一个综合属性 val,符号 digit有一个综合属性，
它的值由词法分析器提供。与产生式 L→E 对应的语义规则仅仅是打印由 E产生的算术表达式的值的一个过程，我们可认为这条规则定义了 L的一个虚属性。某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现语 义 规 则
L E
E E1+T
E T
T T1 * F
T F
F (E)
F digit
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
产 生式
L－属性文法
一个结点的继承属性值依赖于父结点的继承属性和 /或左部兄弟结点的某些属性来决定的。
例 2 继承属性 L.in
生 产 式 语 义 规 则
D?TL
T? int
T?real
L? L1,id
L? id
L.in:=T.type
T.type:=integer
T.type:=real
L1.in:=L.inaddtype(id.entry,L.in)
addtype(id.entry,L.in)
L－属性文法和自顶向下翻译
L－属性文法允许一次遍历就计算出所有属性值 。
LL（ 1） 这种自上而下分析文法的分析过程,从概念上说可以看成是深度优先建立语法树的过程,因此,我们可以在自上而下语法分析的同时实现 L属性文法的计算 。
例 2 Real id1,id2,id3分析树的依赖图 (图中的结点用数字表示 )
5 6
7 8
9 10
T 4
D
L
L
L
Real
type
in
in
in
3 entry
2 entry
entry
id3
id2
id1
,
,
1
例 6:中缀表达式翻译成相应的后缀表达式
LR分析,E→E addop T print(addop,Lexeme) | T
T→num print(num.val)
LL（ 1）分析,
E→TR R→addop T R| ε T→num
9－ 5＋ 2的语法树
E
T+E
2T-
T
9
5
E
说明语义动作的语法树
E
T+E
2T-
T
9
5
{print‘+‘}
E
{print‘9‘}
{print‘5‘}
{print‘-‘} {print‘2‘}
（消除左递归） 9-5+2的语法树
E
RT
T-9
T+5 R
R
2?
说明语义动作的语法树
E
RT
Print‘-‘-9
T+5
R
R
2
print‘9‘ T
print‘5‘
print‘2‘
Print‘+‘
翻译模式（ Translation schemes）适合语法制导翻译的另一种描述形式。翻译模式给出了使用语义规则进行计算的次序，可把某些实现细节表示出来。在翻译模式中，
和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号｛｝括起来，插入到产生式右部的合适位置上。
例（中缀表达式翻译成相应的后缀表达式）
E→TR
R→ addop T {print(addop,Lexeme)} R1|ε
T→ num {print(num.val)}
( E→TR R→addop T R| ε T→num )
( E→E addop T | T T→num)
输入串 9－ 5 + 2的语法树
E
T R
9 - T R
5 + T R
2 ε
输入串 9－ 5 + 2的说明动作的语法树,每个语义动作都作为相应产生式左部符号的结点的儿子,把语义动作看作是终结符,按深度优先次序执行图中的动作后，打印输出 95
－ 2+。
E
T R
9 print(?9‘) - T print(?-‘) R
5 print(?5‘) + T print(?+‘) R
2 print(?2‘) ε
L－属性文法在自顶向下分析中的实现带左递归的文法的翻译模式
E→E 1 + T {E.val,= E1.val + T.val}
E→E 1－ T {E.val,= E1.val－ T.val}
E→T {E.val,= T.val}
T→(E) {T.val,= E.val}
T→num {T.val,= num.val}
消除左递归的同时考虑属性，构造新的 翻译模式
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}
计算表达式 9-5+2
,E
R.i=9
T.val=5
T.val=9
R.i=4
R.i=6
T.val=2
num.val=9
num.val=5
num.val=2
_
+?
在这个翻译模式中，每个数都是由 T产生的，并且 T.val的值就是由属性 num.val给出的数的词法值。
子表达式 9－ 5中的数字 9是由最左边的 T生成的，但是减号和 5是由根的右子结点 R生成的。继承属性 R.i从 T.val得到值 9。
通过产生式中嵌入的下面动作：
{R1.i,= R.i－ T.val}
实现计算 9－ 5并把结果 4传递到中间的 R结点,
类似的动作把 2加到 9－ 5的值上，在最下面的 R结点处产生结果 R.i＝ 6。这个结果将成为根结点处 E.val的值,
R的 综合属性 s在图中没有表示出来，它用来向上复制这一结果一直到树根。
对于自顶向下分析,我们假设动作是在处于相同位置上的符号被展开 （ 匹配成功 ）
时执行的 。 如图中的第二个产生式中,
第一个动作 （ 对 R1.i赋值 ） 是在 T被完全展开成终结符号后执行的,第二个动作是在 R1被完全展开成终结符号后执行的 。
正如前面我们所讨论的,一个符号的继承属性必须由出现在这个符号之前的动作来计算,产生式左边非终结符的综合属性必须在它所依赖的所有属性都计算出来以后才能计算 。
转换左递归翻译模式的方法推广到一般假设翻译模式 1：
A→A 1Y {A.a,= g(A1.a,Y.y)}
A→X {A.a,= f(X.x)}
每个文法符号都有一个综合属性,用相应的小写字母表示,
g和 f是任意函数消除左递归,文法转换成：
A→XR R→YR ｜ ε
再考虑语义动作,翻译模式变为 2
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}
翻译模式 1和翻译模式 2的结果是一样的。
可以给出串 XY1Y2两棵带注释的语法树看出来，一棵是根据翻译模式 1自下而上计算属性的。一棵是根据翻译模式 2自上而下计算的。
A→A 1Y {A.a,= g(A1。 a,Y.y)}
A→X {A.a,= f(X.x)}
A.a=g(g(f(X.x),Y1.y),Y2.y)
A.a=g(f(X.x),Y1.y) Y2
A.a=f(X.x) Y1
X
A
A Y
A Y
X
A→X{R.i,= f(X.x)} R→Y {R1.i,= g((R.i),Y.y)}
R {A.a,=R.s} R1{R.s,= R1.s}
A→XR R→YR ｜ ε
A
X R
Y1 R
Y2 R
A
X R.i=f(X.x)
Y1 R.i=g(f(X.x),Y1.y)
Y2 R.i=g(g(f(X.x),Y1.y),Y2.y)
自下而上计算继承属性 --自下而上的分析中实现 L-属性文法
从翻译模式中去掉嵌入在产生式中间的动作
分析栈中的继承属性
用综合属性代替继承属性从翻译模式中去掉嵌入在产生式中间的动作转换方法,
引入新的非终结符 N和产生式 N→ ε,把嵌入在产生式中间的动作用非终结符 N代替,并把这个动作放在产生式后面,
例,
E→T R
R→ + T {print (?+‘) } R1
R→ - T {print(?-‘) } R1
R→ε
T→num {print (num.val) }
文法变换后,接受的语言相同,
E→T R
R→ + T M R1
R→ - T N R1
R→ε
T→num {print (num.val) }
M→ε {print (?+‘) }
N→ε {print (? -‘) }
目的,使所有嵌入的动作都出现在产生式的末尾,可以自下而上处理继承属性,
一个属性文法称为 L－属性文法,如果对于每个产生式
A→X 1X2… Xn,其每个语义规则中的每个属性或者是综合属性,或者是 Xj（ 1≤j≤n） 的一个继承属性且这个继承属性仅依赖于：
（ 1） 产生式 Xj在左边符号 X1,X2,…,Xj-1的属性；
（ 2） A的继承属性 。
分析栈中的继承属性
自下而上分析器对产生式 A→XY 的右部是通过把 X和 Y从分析栈中移出并用 A代替它们 。
假设 X有一个综合属性 X.s,按照前面所介绍的方法我们把它与 X一起放在分析栈中 。
由于 X.s的值在 Y以下的子树中的任何归约之前已经放在栈中,这个值可以被 Y继承 。 也就是说,如果继承属性 Y.i是由复写规则 Y.i:
= X.s定义的,则可以在需要 y.i值的地方使用
X.s的值 。 在自下而上分析中计算属性值时复写规则起非常重要的作用 。 看下面例子 。
标识符的类型通过继承属性的复写规则来传递翻译模式为：
D→T {L.in,= T.type}
L
T→int {T.type,= integer}
T→real {T.type,= real}
L→ {L1.in,= L.in}
L1,id {addtype (id.entry,L.in)}
L→id {addtype (id.entry,L.in)}
回顾例 2 Real id1,id2,id3分析树的依赖图
5 6
7 8
9 10
T 4
D
L
L
L
Real
type
in
in
in
3 entry
2 entry
entry
id3
id2
id1
.
.
1
例 2输入串 real Real id1,id2,id3的 分析过程 当 L的右部被归约时，
T恰好在这个右部的下面输入 状态 (符号） 使用产生式
Real id1,id2,id3#
id1,id2,id3# real
id1,id2,id3# T T?real
,id2,id3# Tid1
,id2,id3# TL L? id
id2,id3# TL,
,id3# TL,id2
,id3# TL L? L,id
id3# TL,
# TL,id3
# TL L? L,id
# D D? TL
扩充分析栈 Val[i]存放文法符号 X
的综合属性 X.s
D→T L
T→int {Val[top],= integer}
T→real {Val[top],= real}
L→L,id {addtype (Val[top],Val[top-3]}
L→id {addtype (Val[top],Val[top-1}}
用综合属性代替继承属性有时,改变基础文法可能避免继承属性 。 例如,一个
Pascal的说明由一标识符序列后跟类型组成,如,m,
n,integer。 这样的说明的文法可由下面形式的产生式构成
D→L,T
T→integer|char
L→L,id|id
因为标识符由 L产生而类型不在 L的子树中，我们不能仅仅使用综合属性就把类型与标识符联系起来。事实上，如果非终结符 L从第一个产生式中它的右边 T
中继承了类型，则我们得到的属性文法就不是 L－
属性的，因此，基于这个属性文法的翻译工作不能在语法分析的同时进行。
一个解决的方法是重新构造文法使类型作为标识符表 (identifiers list)的最后一个元素：
D→id L
L→,id L|,T
T→integer|char
这样,类型可以通过综合属性 L.type进行传递,当通过 L产生每个标识符时,它的类型就可以填入到符号表中 。
Yacc或 bison作为编译程序的生成工具，利用的就是语法制导翻译方法。它使用符号 $$表示产生式左端的属性，
$n表示存取产生式右端第 n个文法符号相联的属性如例 3作为 Yacc的输入，可写成：
P → DS {$2.dl=$1.dl}
D1 → var V ； D{$$.dl=addlist($2.name,$4.dl)}
| {$$.dl=null}
S1 → V:=e ； S{check($1.name,$$.dl)；
$5.dl=$$.dl}
|
V → x {$$.name= ’x’}
|y {$$.name=’y’}
|z {$$.name=’z’}
如果数据结构 attribute定义属性 name和 dl，可以具体化为：
type struct_attribute {
char *name；
struct_attribute *list；
} attribute；
P → DS {$2.list=$1.list}
D1 → var V ； D{$$.list=add_to_list($2.name,$4.list)}
| {$$.list=null}
S1 → V:=e ； S{check($1.name,$$.list)；
$5.list=$$.list}
|
V → x {$$.name= ’x’}
|y {$$.name=’y’}
|z {$$.name=’z’}
Review- attribute grammars
We augment the conventional grammar with information to
control the semantic analysis and translation,Such grammars
are called attribute grammars.
We augment a grammar by associating attributes with each
grammar symbol that describes its properties,An attribute has
a name and an associated value— a string,a number,a type,a
memory location,an assigned register,generated
code,whatever information we need.
With each production in a grammar,we give semantic rules or
actions,which describe how to compute the attribute values
associated with each grammar symbol in a production,The
attribute value for a parse node may depend on information
from its children nodes below or its siblings and parent node
above.
Review- synthesized or inherited
attributes
There are two types of attributes we might encounter,
synthesized or inherited,
Synthesized attributes are those attributes that are
passed up a parse tree,i.e.,the left-side attribute is
computed from the right-side attributes.
Inherited attributes are those that are passed down a
parse tree,i.e.,the right-side attributes are derived
from the left-side attributes (or other right-side
attributes),These attributes are used for passing
information about the context to nodes further down
the tree.
Review- Syntax-directed translation
Syntax-directed translation refers to a
method of compiler implementation
where the source language translation
is completely driven by the parser
Review-
E' –> E
E –> T | E A T
T –> F | T M F
F –> (E) | int
A –> + | -
M –> * | /
E' -> E { printf("%d\n",E.val); }
E -> T { E.val = T.val; }
| E A T { switch(A.op) {
case ADD,E.val = E.val + T.val; break;
case SUB,E.val = E.val - T.val; break;}
}
T -> F { T.val = F.val;}
| T M F { switch(M.op) {
case MUL,T.val = T.val * F.val; break;
case DIV,T.val = T.val / F.val; break;}
}
F -> (E) { F.val = E.val; }
| int { F.val = int.val; }
A -> + { A.op = ADD; }
| - { A.op = SUB; }
M -> * { M.op = MUL; }
| / { M.op = DIV; }
Attributes and Yacc
E' -> E { printf("%d\n",$1); }
E -> T { $$ = $1; }
| E A T { switch($2) {
case ADD,$$ = $1 + $3; break;
case SUB,$$ = $1 - $3; break;}
}
T -> F {$$ = $1;}
| T M F { switch($2) {
case MUL,$$= $1 * $3; break;
case DIV,$$ = $1 / $3; break;}
}
F -> (E) { $$= $2; }
| int { $$ = $1; }
A -> + { $$ = ADD; }
| - { $$ = SUB; }
M -> * { $$ = MUL; }
| / { $$ = DIV; }.
表达式文法 G[E],E? E＋ T｜ E – T | T T? id |
num | (E)
1.请为表达式建立抽象语法树设计一个属性文法，
给出语义函数如下，每个函数都返回一个指向新建立结点的指针：
（ 1） mknode (op,left,right)建立一个运算符号结点，
标记是 op，两个域 left和 right分别指向左子树和右子树。
（ 2） mkleaf(id,entry)建立一个标识符结点，标记为 id，一个域 entry指向标识符在符号表中的入口。
（ 3） mkleaf(num,val)建立一个数结点，标记为
num，一个域 val用于存放数的值。
2.这是 S-属性文法还是 L-属性文法？
抽象语法树 -精简的语法树运算符和关键字作为内部结点如,if B then S1 else S2 和 3*5+3
if-then-else +
* 3
B S1 S2 3 5
1.为每个非终结符附上一个属性 Ptr，表示指向树结点的指针。
E? E1＋ T{E.Ptr,= mknode(―+‖ E1.Ptr,T.Ptr)}
E? E1 –T {E.Ptr,= mknode(―-‖ E1.Ptr,T.Ptr)}
E? T {E.Ptr,=T.Ptr}
T? id {T.Ptr,= mkleaf(id,entry)}
T? num {T.Ptr,= mkleaf(num,val)}
T? (E) {T.Ptr,=E.Ptr}
2.这是 S-属性文法也是 L-属性文法。
现有如下的 YACC程序片段,
%{
int num = 1;
%}
%%
S,A {printf(―S %d num %d\n‖,$1,num);};
A,B{$$ = num * 2;}AB{num = $2; $$ = $3+1; }
| a{$$ = 1};
B,b {$$ = 10; printf(―B %d\n‖,num);};
请写出输入串为 bbabb时的输出结果,
参考书
ALFRED V.AHO
RAVI SETHI
JEFFREY D.ULLMAN
Compilers
Principles,Techniques,and Tools
Chapter 5
