第八章语法制导翻译和中间代码生成
8.1概述
8.2属性文法和 语法制导翻译
8.3语义分析
8.4中间代码
8.5一些语句的翻译概述 语义处理
程序设计 语言的语义
静态语义是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为类型规则和作用域 /可见性规则两大类 类型相容性 变量先声明后引用 名称相关要求动态语义 程序单位描述的计算
编译程序的语义处理工作 静态语义审查 解释执行动态语义（计算）生成代码,..
语 法 分 析 后 的 源 程 序? 语义处理概述语义形式化 语义建模
文法模型 ---- 属性文法
命令式或操作式模型 ----- 操作语义学
应用式模型 -----指称语义学
公理式模型 -----公理语义学属性文法表达式文法 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}
操作语义描述一段程序的含义是通过执行该段程序所改变的计算机（虚拟计算机）状态来反映。这个计算机的状态与程序执行时的状态相对应：包括变量的所有值，可执行程序本身，各种系统定义的内部数据结构。计算机里所有的寄存器的值和存储单元的值作为计算机的状态，用一组形式定义的操作来说明执行一条指令相应的状态怎样变化。
For (expr1;expr2;expr3){ expr1;
..,Loop:if expr2=0 goto out
} …
expr3;
goto loop
out,...
公理语义一个语言的每个语法成分的含义定义为公理和演绎规则，
用于推导出该成分执行的效果。
公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时表明程序执行它的规格说明所描述的计算。在一个证明中，每一个语句之前之后都有一个逻辑表达式对程序的变量进行约束,以此说明这个语句的含义。
一般的记号 {P} S {Q}
如果在语句 S执行前 P为真，则在语句 S执行并终止后 Q为真。
演绎规则的例子规则 前驱 后继赋值,x:=expr {P(expr)}x:=expr{P(x)}
While,{P ∧ B} S {P}
{P} while B do S end {P ∧ (not B)}
if--then--else
{B ∧ P} S1 {Q},{(not B) ∧ P} S2 {Q}
{P} if B then S1 else S2{Q}
指称语义
指称语义的基本概念是给每一段程序实体定义一个数学意义上的对象，和一个从实体实例向数学意义对象的映射的函数
特点,不但对全部程序赋予全文而且对程序设计语法每一个语法成分短语（表达式，命令，声明 … ）
都给予含义。
每一个语法成分（短语）的含义是以它的自成分的含义的术语来定义的。
即 语义结构 平行于语法结构。
语义函数,程序设计语言的语义利用映射函数来证明。
语义函数将短语映射到它的指称。
例：
二进制数语言 110或 10101 语法实体指称（自然数） 6 或 21 语义实体二进制数文法 Numeral::=0
::=1
::= Numeral 0
::=Numeral 1
自然数 Natrual={0,1,2,3,… }
语义函数 Valuation:Numeral?Natural
Valuation[101] 表示把 Valuation施用于 101
Valuation[N] ------ 把它施用于 N
定义,Valuation（用四个方程 )因为有四个形式 numeral
Valuation[0]?0
Valuation[1]?1
Valuation[N0]?2?Valuation [N]
Valuation[N1]?2?Valuation [N]+1
所以：
Valuation[110]=2? Valuation[11]
= 2? (2? Valuation[1]+1)
=2?(2? 1+1)
=6
属性文法和语法制导翻译虽然形式语义学 (如指称语义学、公理语义学、操作语义学等 )的研究已取得了许多重大的进展，但目前在实际应用中比较流行的语义描述和语义处理的方法主要还是属性文法和语法制导翻译方法属性文法属性文法 (attribute grammar)是一个三元组,A=(G,V,F),其中
G:是一个上下文无关文法
V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等,属性与变量一样，可以进行计算和传递。
属性加工的过程即是语义处理的过程。
F:关于属性的属性断言或一组属性的计算规则 (称为语义规则 ),断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性,
属性有两种 继承的和综合的属性属性通常分为两类：综合属性和继承属性 。 简单地说,综合属性用于,自下而上,传递信息,而继承属性用于
,自上而下,传递信息 。
出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算,它们由其它产生式的属性规则计算或者由生计算器的参数提供 。
A?X1 X2 … Xn
A的综合属性,计算 S(A):=f(I(X1),…,I(Xn))
Xj的继承属性,计算 T(Xj):=f(I(A),..,I(Xn))
1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性,
2)终结符只有综合属性,
在一个属性文法中,对应于每个产生式 A都有一套与之相关联的语义规则,每条规则的形式为
b:=f(c1,c2… ck)
这里,f是一个函数,而且或者
（ 1） b是 A的一个综合属性并且 c1,c2… ck是产生式右边文法符号的属性 ;或者
（ 2） b是产生式右边某个文法符号的一个继承属性并且 c1,c2… ck是 A或产生式右边任何文法符号的属性 。
在两种情况下,我们都说属性 b依赖于属性 c1,c2… ck 。
一个属性文法的例子 例 8.1
非终结符 E,T及 F都有一个综合属性 val,符号 digit有一个综合属性，
它的值由词法分析器提供。与产生式 L→En 对应的语义规则仅仅是打印由 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的带注释的分析树继承属性
一个结点的继承属性值是由此结点的父结点和 /或兄弟结点的某些属性来决定的。
例 8.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
，
，
例 8.3
P –> DS
D –> var V; D |?
S –> V,= E; S |?
V –> x | y | z
现在使用两个属性,name和 dl，每当一个新的变量声明时，就把它的 name
属性附给它,name属性是综合属性。
将所声明的变量都放到一个变量名字清单中（用语义函数 addlist实现），用属性 dl综合声明块中声明的所有变量。然后这个 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； x:=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?
语法制导的翻译
一个 翻译 是符号串对的一个集合。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。
各个编译阶段定义一个翻译，词法分析：（字符串，单词串）语法分析：（单词串，语法树）代码生成（语法树，汇编语言）
设?是输入字母表且?是输出字母表。定义由语言
L1*到语言 L2*的一个翻译是由?*到?*的一个关系 T,使得 T的定义域为 L1且 T的值域为 L2 。
使 (x,y) ∈ T的句子 y叫做 x的一个输出,
语法制导的翻译
直观地说，一个语法制导翻译的基础是一个文法，
其中翻译成分依附在每一产生式上。
例 8.4,下列翻译模式，它定义翻译，即对每个输入 x，
其输出 y是 x的逆转。定义此翻译的规则是产生式 翻译规则
(1)s?0s
(2)s?1s
(3)s?ε
(1)s=s0
(2)s=s1
(3)s=ε
输入输出对可由 (?,?)表示，其中?是输入句子形式而?是输出句子形式。
(S,S)开始用产生式 s?0s来扩展得到 (0S,S0).
再用一次规则 (1)，得到 (00S,S00)。
再用规则 (2)，就得到 (001S,S100).
然后应用规则 (3)并得到 (001,100)。
例 8.5：
把下述产生式定义的算术表达式映射到后缀波兰表示：
E?E+T
E?T
T?T?F
T?F
F?(E)
F?a
E=ET+
E=T
T=TF?
T=F
F=E
F=a
产生式 翻译规则
确定输入 a+a?a的输出：
(E,E)?(E+T,ET+)
(T+T,TT+)
(F+T,FT+)
(a+T,aT+)
(a+T?F,aFF?+)
(a+F?F,aFF?+)
(a+a?F,aaF?+)
(a+a?a,aaa?+)
定义：
一个语法制导的翻译模式是一个五元组 T=(N,?,?，
R,S),其中
(1) N是非终结符的有限集。
(2)?是有限的输入字母表。
(3)?是有限的输出字母表。
(4) R是形如 A,?的规则的有限集,其中
∈ (N∪?)*,?∈ (N∪?)*且?中那组非终结符是?中 那组非终结符的置换。
(5) S是 N中一个特别的非终结符，即开始符。
定义：
若 T= (N,?,?,R,S)是 SDTS,?(T)则称为语法制导的翻译 (SDT)，文法 Gi=(N,?,P,S)，其中 P={A|A,?属于 R)，称为 SDTS T的基础（或输入）文法。文法
G0=( N,?,P?,S),，其中 P?={A| A,?属于 R},称为 T的输出文法。
把语法制导的翻译方法看成是将输入文法 Gi中的推导树变换成输出文法 G0中的推导树。给了输入句子 x，
可以按如下方式得到 x的一个翻译：先为推导 x构造一棵推导树，再变换该树到输出文法中的一棵树，然后取此输出树的边缘作为 x的一个翻译。
语义制导翻译中的规则 A,?
对应于每一个文法产生式 A? 都有与之相关联的一套语义描述?
属性文法 (attribute grammar)是一个三元组,A=(G,V,F)
属性文法可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来语法制导翻译实现从概念上讲,语法制导翻译即基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析,构造语法分析树,
然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算输入符号串
分析树
属性依赖图
语义规则的计算顺序依赖图由称为依赖图的一个有向图 描述分析树中的继承属性和属性中间的相互依赖关系。
依赖图的构造算法：
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结点构造一条有向边依赖图 ----例 8.2
例 8.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)
例 8.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
依赖图中的结点由数字来标识。从代表
T.type的结点 4有一条有向边连到代表 L.in
的结点 5，因为根据产生式 E→TL 的语义规则 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以前都是可用的。
属性文法 说明的翻译是很精确的。最基本的文法用于建立输入符号串的分析树。依赖图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。
例 8.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） 属性的计算次序 。
例：定义定点二进制数的 CFG:
(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 f1v1 l 1B f 2v2
[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]
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]
在某些情况下可用一遍扫描实现属性文法的语义规则计算 。 也就是说在语法分析的同时完成语义规则的计算,无须明显地构造语法树或构造属性之间的依赖图 。 因为单遍实现对于编译效率非常重要具体的实现希望在单遍扫描中完成翻译研究怎样实现这种翻译器。一个一般的属性文法的翻译器可能是很难建立的，然而有一大类属性文法的翻译器是很容易建立的
s-属性 适用于 自底向上的计算
L-属性 适用于自顶向下的分析，也可用于 自底向上。
S－属性文法的自下而上计算
S－属性文法，它只含有综合属性。
综合属性可以在分析输入符号串的同时自下而上的分析器来计算 。 分析器可以保存与栈中文法符号有关的综合属性值,每当进行归约时,
新的属性值就由栈中正在归约的产生式右边符号的属性值来计算 。
S－属性文法的翻译器通常可借助于 LR分析器实现 。 在 S－属性文法的基础上,LR分析器可以改造为一个翻译器,在对输入串进行语法分析的同时对属性进行计算 。
产生式 语义规则
０）Ｌ → Ｅ ｐｒｉｎｔ（Ｅ,ｖａｌ）
１）Ｅ → Ｅ 1＋Ｔ Ｅ,ｖａｌ ∶ ＝Ｅ 1.ｖａｌ＋Ｔ,ｖａｌ
２）Ｅ → Ｔ Ｅ,ｖａｌ ∶ ＝Ｔ,ｖａ l
３）Ｔ → Ｔ 1*Ｆ Ｔ,ｖａｌ ∶ ＝Ｔ 1.ｖａｌ × Ｆ,ｖ ａｌ
４）Ｔ → F Ｔ,ｖａｌ ∶ ＝ F.ｖａｌ
５）Ｆ → （Ｅ） Ｆ,ｖａｌ ∶ ＝Ｅ,ｖａｌ
６）Ｆ → ｄ iｇ iｔ Ｆ,ｖａｌ,＝ｄｉｇｉｔ,ｌｅｘｖａｌ
LR分析器可以改造为一个翻译器,在对输入串进行语法分析的同时对属性进行计算 。
LR分析器 增加语义栈
２＋３ *５的分析和计值过程步骤 动作 状态栈 语义栈 (值栈 ) 符号栈 余留输入串
１） ０ － ＃ ２＋ 3*５＃
２） ０５ －－ ＃ ２＋ 3 *５＃
３） ｒ６ ０３ －２ ＃Ｆ ＋３ *５＃
４）ｒ４ ０２ －２ ＃Ｔ ＋３ *５＃
５）ｒ２ ０１ －２ ＃Ｅ ＋３ *５＃
６） ０１６ －２－ ＃Ｅ＋ ３ *５＃
７） ０１６５ －２－－ *５＃
８）ｒ６ ０１６３ －２－３ *５＃
９）ｒ４ ０１６９ －２－３ *５＃
１０） ０１６９７ －２－３－ ＃Ｅ＋Ｔ *
１１） ０１６９７５ －２－３－－ ＃Ｅ＋Ｔ *５ ＃
１２）ｒ６ ０１６９７（１０） －２－３－５ ＃Ｅ＋Ｔ *Ｆ #
１３）ｒ３ ０１６９ －２－（１５） ＃Ｅ＋Ｔ ＃
１４）ｒ１ － （１７） ＃Ｅ ＃
１５）接受
BOTTOM—UP
语义处理是作类型检查,对二目运算符的运算对象进行类型匹配审查 。
(LR分 析 ）,增加语义栈 归约 时进行语义动作,
例 8.7G[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 in t
o # --
2 T in t
o # --
5 + ---
2 T in t
o # --
4 n in t
5 + ---
2 T in t
o # --
6 T in t
5 + ---
2 T in t
o # --
1 E in t
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 in t
o # --
2 T in t
o # --
5 + ---
2 T in t
o # --
3 b b ool
5 + ---
2 T in t
o # --
6 T b ool
5 + ---
2 T in t
o # --
1 E e r r o r
o # --
L－属性文法和自顶向下翻译一个属性文法称为 L－属性文法,如果对于每个产生式
A→X 1X2… Xn,其每个语义规则中的每个属性或者是综合属性,或者是 Xj（ 1≤j≤n） 的一个继承属性且这个继承属性仅依赖于：
（ 1） 产生式 Xj在左边符号 X1,X2,…,Xj-1的属性；
（ 2） A的继承属性 。
S－属性文法一定是 L－属性文法,因为 （ 1）,（ 2） 限制只用于继承属性 。
L－属性文法允许一次遍历就计算出所有属性值 。
LL（ 1） 这种自上而下分析文法的分析过程,从概念上说可以看成是深度优先建立语法树的过程,因此,我们可以在自上而下语法分析的同时实现 L属性文法的计算 。
例（中缀表达式翻译成相应的后缀表达式）
E→TR
R→addop T {print(addop,Lexeme)} R 1|ε
T→num {print(num.val)}
翻译模式 （ Translation schemes） 适合语法制导翻译的另一种描述形式 。 翻译模式给出了使用语义规则进行计算的次序,可把某些实现细节表示出来 。 在翻译模式中,和文法符号相关的属性和语义规则 （ 这里我们也称语义动作 ）,用花括号 ｛ ｝
括起来,插入到产生式右部的合适位置上 。
输入串 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。计算 9－ 5并把结果 4传递到中间的 R结点这是通过产生式中嵌入的下面动作实现：
{R1.i,= R.i－ T.val}
类似的动作把 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)
思考问题 -把建立语法树的翻译模式变换成适合预测分析的模式
E?E1+T {E.nptr:=mknode(?+?,E1.nptr,T.nptr)
E? E1-T {E.nptr:=mknode(?-?,E1.nptr,T.nptr)
E? T {E.nptr:=T.nptr)
自下而上计算继承属性
讨论在自下而上的分析过程中实现 L－属性文法的方法。这种方法可以实现任何基于 LL（ 1）文法的 L－属性文法，它还可以实现许多（不是所有）基于 LR（ 1）
文法的 L－属性文法。这种方法是 S-属性文法的自下而上翻译技术的一般化
自下而上分析器对产生式 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)}
回顾例 8.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
例 8.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? Li,d
id3# TL,
# TL,id3
# TL L? Li,d
# D D? TL
用综合属性代替继承属性有时,改变基础文法可能避免继承属性 。 例如,一个
Pascal的说明由一标识符序列后跟类型组成,如,m,
n,integer。 这样的说明的文法可由下面形式的产生式构成
D→L,T
T→integer|char
L→L,id|id
因为标识符由 L产生而类型不在 L的子树中，我们不能仅仅使用综合属性就把类型与标识符联系起来。事实上，如果非终结符 L从第一个产生式中它的右边 T
中继承了类型，则我们得到的属性文法就不是 L－
属性的，因此，基于这个属性文法的翻译工作不能在语法分析的同时进行。
一个解决的方法是重新构造文法使类型作为标识符表的最后一个元素：
D→id L
L→,id L|,T
T→integer|char
这样,类型可以通过综合属性 L.type进行传递,当通过 L产生每个标识符时,它的类型就可以填入到符号表中 。
语义制导翻译的 编译实现,
例 8.6
E –> TE'
E' –> A T E' |?
T –> FT'
T' –> M F T' |?
F –> (E) | int
A –> + | -
M –> * | /
E -> TE'
E' -> A T E' { rhs = PopOperand();lhs = PopOperand();
switch (PopOperator()) {
case ADD,PushOperand(lhs+rhs); break;
case SUB,PushOperand(lhs-rhs); break;}}
|? { /* empty,do nothing */ }
T -> FT'
T' -> M F T' { rhs = PopOperand();lhs = PopOperand();
switch (PopOperator()) {
case MUL,PushOperand(lhs*rhs); break;
case DIV,PushOperand(lhs/rhs); break;}}
|? { /* empty,do nothing */ }
A -> + { PushOperator(ADD);}| - { PushOperator(SUB);}
M -> * { PushOperator(MUL);}| / { PushOperator(DIV);}
F -> int { PushOperand(intval);}| (E) { /* handled during
parsing of E */ }
parse 2 + 4 * 3:
分析动作桥 分析栈 运算对象栈 运算符栈
Predict E –> TE‘ E#
Predict T –> FT' TE‘#
Predict F –> int FT'E‘#
Match int intT'E‘#
Predict T' –>? T'E‘# 2
Predict E' –> ATE' ATE' # 2
Predict A –> + ATE‘# 2
Match + +TE‘# 2
Predict T –> FT' TE‘# 2 +
Predict F –> int FT'E‘# 2 +
Match int intT'E‘# 2 +
Predict T' –> MFT' T'E‘# 4 2 +
Predict M –> * MFT'E‘# 4 2 +
Match * *FT'E‘# 4 2 +
Predict F –> int FT'E‘# 4 2 * +
Match int intT'E‘# 4 2 * +
Predict T' –>? T'E‘# 3 4 2 * +
Predict E' –>? E‘#
Yacc或 bison作为编译程序的生成工具，利用的就是语法制导翻译方法。它使用符号 $$表示产生式左端的属性，
$n表示存取产生式右端第 n个文法符号相联的属性如例 8.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’}
语义分析
语义分析
属性文法和语法制导翻译方法和技术应用于语义分析中 。
语义分析通常包括：
（ 1） 类型检查 。 验证程序中执行的每个操作是否遵守语言的类型系统的过程,,编译程序必须报告不符合类型系统的信息 。
（ 2） 控制流检查 。 控制流语句必须使控制转移到合法的地方 。
例如,在 C语言中 break语句使控制跳离包括该语句的最小
while,for或 switch语句 。 如果不存在包括它的这样的语句,
则就报错 。
（ 3） 一致性检查 。 在很多场合要求对象只能被定义一次 。 例如 Pascal语言规定同一标识符在一个分程序中只能被说明一次,同一 case语句的标号不能相同,枚举类型的元素不能重复出现等等 。
（ 4） 相关名字检查 。 有时,同一名字必须出现两次或多次 。
例如,Ada 语言程序中,循环或程序块可以有一个名字,出现在这些结构的开头和结尾,编译程序必须检查这两个地方用的名字是相同的 。
(5)名字的作用域分析类型和声明（ Types and declarations）
一个类型是一组值和在这些值上的一组操作，程序设计语言中有三种类型,
基本类型,int,float,double,char,bool等等,也可能允许在 基本类型基础上 用户自己定义的类型，如枚举型,
复合类型：数组,指针，记录 /结构 /联合,类等等,这些类型由基本类型构成,
复杂类型：链表，栈，队，树，堆，表格等等,可以把它们组织成 ADT,一个语言不一定支持这类高级的抽象。
声明是程序中的一个语句,是把数据对象的名称和类型，以及生命周期信息传给编译,声明的地方传递生命周期信息也有些语言允许声明初始化变量 。 如,double calculate(int a,double
b); // function prototype
int x = 0; // global variables available throughout
double y; // the program
int main() {
int m[3]; // local variables available only in main
char *n;
,..
}
强类型的 -任何数据 类型都可以在 编译时确定弱类型的,
进行类型检查的时间：编译时，运行时，或者两者结合,
静态类型检查 编译时进行类型检查动态类型检查，将类型信息并到运行时每个数据单元中,
隐含类型转换,
P→ D； E
D→ D； |id:T
T→ char | integer | aray [num]of T| ↑ T
E→ literal|num | id| E mod E| E [E]|E↑
P代表程序； D代表说明； E代表表达式 。 如程序语句：
key,integer;
key mod 1999
语言本身提供两种基本类型,char和 integer。
除此之外还有缺省的基本类型 type_ error和 void。 假定所有数组都从下标 1开始确定标识符类型的部分翻译模式
（ 1） P→D ； E
（ 2） D→D ； D
（ 3） D→id,T {addtype (id,Entry,T,type)}
（ 4） T→char {T,Type:= char}
（ 5） T→integer {T,Type:= integer}
（ 6） T→↑T 1 {T,Type:= pointer (T1,type)}
（ 7） T→array [num]of T1
{T,Type,= array (num.Val,T1.type)}
语句的类型检查的翻译模式
S→id,=E { if id,Type= E,Type
Then S,Type:= void
else S,Type:= type_ error}
S→if E then S1 {if E,type= boolean
then S,Type:= S1,type
else S,type,= type_ error}
S→ while E do S1 {if E,type= boolean
Then S,type:= S1,Type
else S,type:= type_ error}
设计 类型检查程序
1.辨认语言中可用的类型
2.辨认具有类型的语言结构
3.辨认语言的语义规则
In Decaf
base types,int,double,bool,string
compound types,arrays and classes,
An array can be made of any type (either a base type,
a class,or out of other arrays).
Classes are a bit special in that the class name must
be declared before it can be used in a declaration,
ADTs can be constructed using classes,but they
aren?t handled in any way differently than classes,
so we don?t need to consider them specially.
In Decaf the relevant language constructs
constants,every constant has an associated type,A scanner tells
us these types as well as the associated lexeme.
variables,all variables (global,local,and instance) must have a
declared type of either int,double,bool,string,array,or class.
functions,functions have a return type,and each parameter in
the function definition has a type,as does each argument in a
function call.
expressions an expression can be a constant,variable,function
call,or some operator (binary or unary) applied to expressions,
Each of the various expressions have a type based on the type of
the constant,variable,return type of the function,or type of
operands.
The other language constructs in Decaf (if,while,Print,
assignments,etc.) also have types associated with them,because
somewhere in each of these we find an expression.
The semantic rules ——govern what types are
allowable in the various language constructs,In
Decaf,
operand to a unary minus must either be double or int,
the expression used in a loop test must be of bool type,
general rules,such as all variables must be declared before
use,all classes are global,and so on.
arrays,the index used in an array selection expression must be of integer
type
expressions,? the two operands to % must both be int,The result type is
int.
this is bound to the receiving object within class scope,it is an error
outside class scope
variables,a variable declared of class type must refer to a defined class
name
functions,the type of each actual argument in a function call must be
compatible with the formal parameter。 if a function has a void return
type,it may only use the empty return statement
实现 类型检查程序
.
首先，将每个名字（标识符）的类型信息记录在符号表中作用域检查 作用域和可见性基本作用域规则（ lexical rule)
int a;
void Binky(int a) {
int a;
a = 2;
...
}
作用域检查实现：
1每个作用域一个独立的符号表，这些符号表组织成作用域栈
2对所有作用域的全局符号表，每个作用域有一个作用域号
？各自的优缺点,PL/0用的是哪种运算符（函数）的重载 多态函数重载运算符 （ overloading operator） 根据上下文可以执行不同的运算 。 ＋是重载符号,在 A＋ B中,当 A和 B为整数,实数,
复数或者矩阵时,运算符执行不同类型的运算当出现重载运算符时,要确定它所表示的唯一的意义,称为运算符识别 。
检查运算符的操作数 。
多态函数 ----能实现对数据结构进行操作的算法,不管数据结构的元素类型是什么多态函数的特点是，每次被调用时，传递过来的参数可以具有不同类型。
,
.
,
何谓中间代码 ( Intermediate code )
( Intermediate representation )
( Intermediate language )
源程序的一种内部表示，不依赖目标机的结构，易于机械生成目 标代码的中间表示。
为什麽要此阶段逻辑结构清楚；利于不同目标机上实现同一种语言；
（ 参考第 12 章的 275,276页 ）
利于进行与机器无关的优化 ；这些内部形式也能用于解释。
中间代码的几种形式逆波兰 四元式 三元式 间接三元式 树中间代码逆波兰,A B C D - * + E C D – N ^ / +
四元式,( 1 ) ( - C D T1 )
( 2 ) ( * B T1 T2)
( 3 ) ( + A T2 T3)
( 4 ) ( - C D T4)
( 5 ) ( ^ T4 N T5)
( 6 ) ( / E T5 T6)
( 7 ) ( + T3 T6 T7)
例,A + B * ( C - D ) + E / ( C - D ) ^N
三元式,( 1) ( - C D )
(2) ( * B (1 ) )
(3) ( + A (2 ) )
(4) ( - C D )
(5) ( ^ (4) N )
(6) ( / E (5 ) )
(7) ( + (3 ) (6 ) )
例,A + B * ( C - D ) + E / ( C - D ) ^N
间接三元式,间接三元式序列 间接码表
( 1) ( - C D ) （ 1 ）
( 2) ( * B ( 1) ) （ 2 ）
( 3) ( + A ( 2) ) （ 3 ）
( 4 ) ( ^ ( 1 ) N ) （ 1 ）
( 5) ( / E ( 4) ) （ 4 ）
( 6) ( + ( 3) (5 ) ) （ 5 ）
（ 6 ）
例,A + B * ( C - D ) + E / ( C - D ) ^N
简单赋值语句的 (四元式）翻译四元式形式,
result,= arg1 op arg2
语义属性,id.name,E.place
函数,lookup( id.name) ;
过程,emit(t,= arg1 op arg2);
newtemp;
产生式和语义描述：
(1) S? id,= E
{ P:=lookup (id.name) ;
if P? nil then emit( P ―,=‖ E.place)
else error }
(op,arg1,arg2,result) 或
(2) E?E1+E2
{E.place:= newtemp;
emit(E.place―:=‖ E1.place―+‖E2.place)}
(3) E? - E1
{ E.place:=newtemp;
emit(E.place―:=‖―uminus‖ E1.place)}
(4) E?( E1)
{ E.place:= E1.place}
(5) E?id
{E.place:=newtemp;
P:=lookup(id.name);
if P?nil then E.place:=P
else error}
简单说明句的翻译 -翻译是指在符号表中登录名字和性质。
最简单的说明句的语法：
Ｄ → integer〈 namelist〉 ｜ real〈 namelist〉
〈 namelist〉 → 〈 namelist〉,id｜ id
用自下而上翻译 文法改写：
Ｄ → Ｄ 1,id
｜ integer id
| real id
(1)Ｄ → integer id｛ enter(id,int） ;D.att:=int}
(2)Ｄ → real id｛ enter(id,real） ;D.att:=real}
(3)Ｄ → Ｄ １,id｛ enter(id，Ｄ １,att）；
D.att:=Ｄ １,att｝
不改写文法，用自下而上翻译 --请你自己设计用自上而下翻译 -------------------请你自己设计如 i f B t h e n S 1 e l s e S 2
B 的 代 码条 件 假转
S1的 代 码转 移
S2的 代 码
B
S1 S2
N
Y
控制语句的翻译 -
结构的翻译
E.false
控制语句中布尔表达式的翻译控制语句 S?if E then S 1 else S 2
E 的代码 E.true
E.true,S1 的代码
goto out
E.false,S2 的代码
out:
,把条件转移的布尔表达式 E 翻译成仅含条件真 转 和 无条件 转 的四元式
E,a rop b
if a rop b goto E.true
goto E.false
如,a<b or c<d and e<f
可 翻译成如下四元式：
(1) if a<b goto E.true
(2) goto (3)
(3) if c<d goto (5)
(4) goto E.false
(5) if e<f goto E.true
(6) goto E.false
(翻译 不是最优 )
语句 if a<b or c<d and e<f then S1 else S2的四元式
(1) if a<b goto (7) //转移至 (E.true )
(2) goto (3)
(3) if c<d goto (5)
(4) goto (p+1) //转移至 (E.false)
(5) if e<f goto (7)
(6) goto (p+1)
(7)( S1的四元式
……
(p-1) …… ）
(p) goto (q)
(p+1) (S2的四元式
……
(q-1) …… ）
(q)
//转移至 (E.true )
//转移至 (E.false)
//(E.false)入口
// (E.true ) 入口记录需回填地址的四元式，把需回填Ｅ．ｔｒｕｅ的四元式拉成一链，把需回填Ｅ．ｆａｌｓｅ的四元式拉成一链，分别称做,真,链和,假,链
（１０） … ｇ oｔｏ Ｅ．ｔｒｕｅ
…
（２０） … ｇｏｔｏ Ｅ．ｔｒｕｅ
…
（３０） … ｇｏｔｏ Ｅ．ｔｒｕｅ
则链成
（１０） … ｇｏｔｏ （０）
…
（２０） … ｇｏｔｏ （１０）
…
（３０） … ｇｏｔｏ （２０）
把地址（３０）称作,真,链链首，０为链尾标志，即地址（１
０）为,真,链链尾。
语义描述使用的变量和过程：
E.true,―真,链,E.false,―假,链 。
E.codebegin,E 的第一个四元式
Nextstat,下一四元式地址过程,emit( ) 输出一条四元式，而 nextstat+1
merge(p1,p2) 把 p1 的链首填在 p2 的链尾例,merge(p1,p2)
(p10) goto ( 0)
……
p1 链 (p100) goto (p10)
…… `
(p1) goto (p100)
(p20) goto( 0) (p100)
……
p2 链 (p200) goto (p20)
……
(p2) goto (p200)
backpatch(p,t) 把 链首 p 所链接的每个四元式的第四区段都填为 t
语句 i f a < b o r c<d a n d e<f t h en S
1
el s e S
2
的四元式
(1 ) i f a < b g o t o ( 7 ) ( E,t ru e ) ( 1 ) 和 ( 5 ）
( 2 ) g o t o ( 3 ) 拉链 （真）
( 3 ) i f c<d g o t o ( 5 )
( 4 ) g o t o ( p + 1 ) ( E,f a l se) ( 4 ) 和 ( 6 )
( 5 ) i f e<f g o t o ( 7 ) 拉链 （假）
( 6 ) g o t o ( p + 1 )
( 7 ) ( S
1
的四元式
( p - 1 )）
( p ) g o t o (q)
( p + 1 ) ( S
2
的四元式
( q - 1 )）
(q)
自下而上分析中的一种翻译方案：
(1) E→ E1 or E 2 { backpatch(E 1.false,E 2.Codebegin);
E.Codebegin:= E 1.codebegin;
E.true:=merge(E 1.true,E 2.true)
E.false:= E 2.false}
(2)E→ E1 and E 2 { backpatch(E 1.true,E 2.codebegin);
E.Codebegin:= E 1.codebegin;
E.true:= E 2.true;
E.false:= merge(E 1.false,E 2false);}
(3) E→ not E1 { E.true:= E 1.false;
E.Codebegin:= E 1.codebegin;
E.false:= E 1.true
( 4 ) E → (E
1
) { E,t r u e,= E
1
,t r u e ;
E,C o d e b e g i n,= E
1
,c o d e b e g i n ;
E,f a l se,= E
1
,f a l se }
( 5 ) E → i d 1 r o p i d 2 { E,t r u e,=n e x t st a t ;
E,C o d e b e g i n,=n e x t st a t ;
E,f a l se,=n e x t st a t + 1 ;
e m it (? if ‘ id 1,p la c e? r o p ‘ id 2,p la c e?g o to ‘– ) ;
em it (? g o t o ‘ - ) }
( 6 ) E → i d { E,t r u e,=n e x t st a t ;
E,c o d e b e g i n,=n e x t st a t ;
E,f a l se,=n e x t st a t + 1 ;
e m it (? if ‘ id,p la c e?g o to ‘ – ) ;
e m it (? g o t o ‘ - ) }
GOTO语句翻译 —拉链返填
……
（ 10） goto L （ 10） goto 0
…… …… 链尾 （ 10）
（ 20） goto L （ 20） goto 10
…… ……
（ 30） goto L (30) goto 20
…… …… 链头 （ 30）
（ 40） L,…… （ 40） L,….
符号表
name type def add
…
L label not r
(p) goto 0
…
(q) goto p
…
(r) goto q
建链的方法是：若ｇｏｔｏ Ｌ中的标号Ｌ尚未在符号表中出现，则把Ｌ填入表中，置Ｌ的
,定义否,标志为,未,,把ｎｅｘｔｓｔａ
ｔ填进Ｌ的地址栏中 作为新链首，然后，产生四元式（ｇｏｔｏ ０），其中０为链尾标志。
若Ｌ已在符号表中出现（但,定义否,标志为
,未,），则把它的地址栏中的编号（记为ｑ）
取出，把 nextstat填进该栏作新链首，然后，产生四元式（ｇｏｔｏ ｑ）。
定义标号语句的产生式
Ｓ → <label> Ｓ
<label>→ ｉ：
那么，当用 <label>→ ｉ：进行归约时，应做如下的语义动作：
1.若ｉ所指的标识符（假定为Ｌ）不在符号表中，则把它填入，置,类型,为,标号,,,定义否,为
,已,,,地址,为 nextstat。
2.若Ｌ已在符号表中但,类型,不为,标号,或,定义否,为,已,,则报告出错。
3.若Ｌ已在符号表中，则把标志,未,改为,已,,
然后，把地址栏中的链首（设为ｑ）取出，同时把
nextstat填在其中，最后，执行 backpatch（ｑ，
nextstat）。
翻译ｇｏｔｏ语句时，还有两点必须注意第一：相同名字的标号可以在不同名字作用域中定义。如：
（１） ｂｅｇｉｎ
（２） Ｌ：ｂｅｇｉｎ
（３） ｇｏｔｏ Ｌ； //延迟使用
（４） ……
（５） Ｌ,…
（６） ｅｎｄ
（７） ｅｎｄ
第二，转移标号是非法的
（１） for ｉ ∶ =１ to 10 do
（２） begin gotoＬ；
（３） for ｊ ∶ =１ to 20 do
（４） begin goto Ｌ；
… …
（ｎ） L,end ｛ forｊ｝
end ｛ for i｝
处理到第（ｎ）行后，第（４）行的 goto目标得以解决。而第（２）行的 goto Ｌ是非法的，但只有当循环关闭时才能确定。
中间表示的不同层次源 中层 IR 低层 IR
float a[10][20]; t1 = j + 2 …
a[i][j+2]; t2 = i * 20
t3 = t1 + t2
高层 IR t4 = 4 * t3
t1 = a[i,j+2] t5 = addr a
t6 = t5 + t4
t7 = *t6
抽象语法树和 DAG图语法树可以作为一种合适的中间语言形式。在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树（ Abstract Syntax Tree）。
在抽象语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点，即这些叶结点的父结点如产生式 S→if B then S 1 else S2抽象语法树表示
if-then-else
B S1 S2
语法树和抽象语法树
directed acyclic graph (DAG).
b*c+b*c
+
*
b c
in Decaf compiler
Three-address code (TAC)
a = b * c + b * d
t1 = b * c;
t2 = b * d;
t3 = t1 + t2;
a = t3;
控制流
if (a < b + c)
a = a - c;
c = b * c;
t1 = b + c;
t2 = a < t1;
IfZ t2 Goto L0;
t3 = a - c;
a = t3;
L0,t4 = b * c;
c = t4;
函数调用，数组访问
int n;
n = ReadInteger();
Binky(arr[n]);
n = LCall
_ReadInteger();
t1 = 4;
t2 = t1 * n;
t3 = arr + t2;
t4 = *(t3);
LCall _Binky(t4);
void main() {
int a;
int b;
int c;
a = 1;
b = 2;
c = a + b;
Print(c);
}
main:
BeginFuncWithParams;
Var a;
Var b;
Var c;
Var _t0;
_t0 = 1;
a = _t0;
Var _t1;
_t1 = 2;
b = _t1;
Var _t2;
_t2 = a + b;
c = _t2;
LCall _PrintInt(c);
EndFunc;
void main() {
Print("hello world");
}
main:
BeginFuncWithParam
s;
Var _t0;
_t0 = "hello world";
LCall _PrintString(_t0);
EndFunc;
void main() {
int a;
a = 2 + a;
Print(a);
}
main:
BeginFuncWithParams;
Var a;
Var _t0;
_t0 = 2;
Var _t1;
_t1 = _t0 + a;
a = _t1;
LCall _PrintInt(a);
EndFunc;
void Binky(int[] arr) {
arr[1] = arr[0] * 2;
}
_
Binky:
BeginFuncWithParams arr;
Var _t0; _t0 = 1;
Var _t1; _t1 = 4;
Var _t2; _t2 = _t1 * _t0;
Var _t3; _t3 = arr + _t2;
Var _t4; _t4 = 0;
Var _t5; _t5 = 4;
Var _t6; _t6 = _t5 * _t4;
Var _t7; _t7 = arr + _t6;
Var _t8; _t8 = *(_t7);
Var _t9; _t9 = 2;
Var _t10; _t10 = _t8 * _t9;
*(_t3) = _t10;
EndFunc;
int foo(int a,int b) {
return a + b;
}
void main() {
int c;
int d;
foo(c,d);
}
_foo:
BeginFuncWithParams a,b;
Var _t0;
_t0 = a + b;
Return _t0;
EndFunc;
main:
BeginFuncWithParams;
Var c;
Var d;
Var _t1;
_t1 = LCall _foo(c,d);
EndFunc;
class Animal {
int height;
void InitAnimal(int h) {
this.height = h;
}
}
_
_Animal_InitAnimal:
BeginFuncWithParam
s this,h;
*(this + 4) = h;
EndFunc;
VTable Animal =
__Animal_InitAnimal,；
class Cow extends
Animal {
void InitCow(int h) {
InitAnimal(h);
}
}
__Cow_InitCow:
BeginFuncWithParams this,
h;
Var _t0;
_t0 = *(this);
Var _t1;
_t1 = *(_t0);
ACall _t1(this,h);
EndFunc;
VTable Cow =
__Animal_InitAnimal,
__Cow_InitCow,;
void Binky(class Cow
betsy) {
betsy.InitCow(5);
}
_Binky:
BeginFuncWithParams
betsy;
Var _t2;
_t2 = 5;
Var _t3;
_t3 = *(betsy);
Var _t4;
_t4 = *(_t3 + 4);
ACall _t4(betsy,_t2);
EndFunc;
8.1概述
8.2属性文法和 语法制导翻译
8.3语义分析
8.4中间代码
8.5一些语句的翻译概述 语义处理
程序设计 语言的语义
静态语义是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为类型规则和作用域 /可见性规则两大类 类型相容性 变量先声明后引用 名称相关要求动态语义 程序单位描述的计算
编译程序的语义处理工作 静态语义审查 解释执行动态语义（计算）生成代码,..
语 法 分 析 后 的 源 程 序? 语义处理概述语义形式化 语义建模
文法模型 ---- 属性文法
命令式或操作式模型 ----- 操作语义学
应用式模型 -----指称语义学
公理式模型 -----公理语义学属性文法表达式文法 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}
操作语义描述一段程序的含义是通过执行该段程序所改变的计算机（虚拟计算机）状态来反映。这个计算机的状态与程序执行时的状态相对应：包括变量的所有值，可执行程序本身，各种系统定义的内部数据结构。计算机里所有的寄存器的值和存储单元的值作为计算机的状态，用一组形式定义的操作来说明执行一条指令相应的状态怎样变化。
For (expr1;expr2;expr3){ expr1;
..,Loop:if expr2=0 goto out
} …
expr3;
goto loop
out,...
公理语义一个语言的每个语法成分的含义定义为公理和演绎规则，
用于推导出该成分执行的效果。
公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时表明程序执行它的规格说明所描述的计算。在一个证明中，每一个语句之前之后都有一个逻辑表达式对程序的变量进行约束,以此说明这个语句的含义。
一般的记号 {P} S {Q}
如果在语句 S执行前 P为真，则在语句 S执行并终止后 Q为真。
演绎规则的例子规则 前驱 后继赋值,x:=expr {P(expr)}x:=expr{P(x)}
While,{P ∧ B} S {P}
{P} while B do S end {P ∧ (not B)}
if--then--else
{B ∧ P} S1 {Q},{(not B) ∧ P} S2 {Q}
{P} if B then S1 else S2{Q}
指称语义
指称语义的基本概念是给每一段程序实体定义一个数学意义上的对象，和一个从实体实例向数学意义对象的映射的函数
特点,不但对全部程序赋予全文而且对程序设计语法每一个语法成分短语（表达式，命令，声明 … ）
都给予含义。
每一个语法成分（短语）的含义是以它的自成分的含义的术语来定义的。
即 语义结构 平行于语法结构。
语义函数,程序设计语言的语义利用映射函数来证明。
语义函数将短语映射到它的指称。
例：
二进制数语言 110或 10101 语法实体指称（自然数） 6 或 21 语义实体二进制数文法 Numeral::=0
::=1
::= Numeral 0
::=Numeral 1
自然数 Natrual={0,1,2,3,… }
语义函数 Valuation:Numeral?Natural
Valuation[101] 表示把 Valuation施用于 101
Valuation[N] ------ 把它施用于 N
定义,Valuation（用四个方程 )因为有四个形式 numeral
Valuation[0]?0
Valuation[1]?1
Valuation[N0]?2?Valuation [N]
Valuation[N1]?2?Valuation [N]+1
所以：
Valuation[110]=2? Valuation[11]
= 2? (2? Valuation[1]+1)
=2?(2? 1+1)
=6
属性文法和语法制导翻译虽然形式语义学 (如指称语义学、公理语义学、操作语义学等 )的研究已取得了许多重大的进展，但目前在实际应用中比较流行的语义描述和语义处理的方法主要还是属性文法和语法制导翻译方法属性文法属性文法 (attribute grammar)是一个三元组,A=(G,V,F),其中
G:是一个上下文无关文法
V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等,属性与变量一样，可以进行计算和传递。
属性加工的过程即是语义处理的过程。
F:关于属性的属性断言或一组属性的计算规则 (称为语义规则 ),断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性,
属性有两种 继承的和综合的属性属性通常分为两类：综合属性和继承属性 。 简单地说,综合属性用于,自下而上,传递信息,而继承属性用于
,自上而下,传递信息 。
出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算,它们由其它产生式的属性规则计算或者由生计算器的参数提供 。
A?X1 X2 … Xn
A的综合属性,计算 S(A):=f(I(X1),…,I(Xn))
Xj的继承属性,计算 T(Xj):=f(I(A),..,I(Xn))
1)非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性,
2)终结符只有综合属性,
在一个属性文法中,对应于每个产生式 A都有一套与之相关联的语义规则,每条规则的形式为
b:=f(c1,c2… ck)
这里,f是一个函数,而且或者
（ 1） b是 A的一个综合属性并且 c1,c2… ck是产生式右边文法符号的属性 ;或者
（ 2） b是产生式右边某个文法符号的一个继承属性并且 c1,c2… ck是 A或产生式右边任何文法符号的属性 。
在两种情况下,我们都说属性 b依赖于属性 c1,c2… ck 。
一个属性文法的例子 例 8.1
非终结符 E,T及 F都有一个综合属性 val,符号 digit有一个综合属性，
它的值由词法分析器提供。与产生式 L→En 对应的语义规则仅仅是打印由 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的带注释的分析树继承属性
一个结点的继承属性值是由此结点的父结点和 /或兄弟结点的某些属性来决定的。
例 8.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
，
，
例 8.3
P –> DS
D –> var V; D |?
S –> V,= E; S |?
V –> x | y | z
现在使用两个属性,name和 dl，每当一个新的变量声明时，就把它的 name
属性附给它,name属性是综合属性。
将所声明的变量都放到一个变量名字清单中（用语义函数 addlist实现），用属性 dl综合声明块中声明的所有变量。然后这个 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； x:=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?
语法制导的翻译
一个 翻译 是符号串对的一个集合。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。
各个编译阶段定义一个翻译，词法分析：（字符串，单词串）语法分析：（单词串，语法树）代码生成（语法树，汇编语言）
设?是输入字母表且?是输出字母表。定义由语言
L1*到语言 L2*的一个翻译是由?*到?*的一个关系 T,使得 T的定义域为 L1且 T的值域为 L2 。
使 (x,y) ∈ T的句子 y叫做 x的一个输出,
语法制导的翻译
直观地说，一个语法制导翻译的基础是一个文法，
其中翻译成分依附在每一产生式上。
例 8.4,下列翻译模式，它定义翻译，即对每个输入 x，
其输出 y是 x的逆转。定义此翻译的规则是产生式 翻译规则
(1)s?0s
(2)s?1s
(3)s?ε
(1)s=s0
(2)s=s1
(3)s=ε
输入输出对可由 (?,?)表示，其中?是输入句子形式而?是输出句子形式。
(S,S)开始用产生式 s?0s来扩展得到 (0S,S0).
再用一次规则 (1)，得到 (00S,S00)。
再用规则 (2)，就得到 (001S,S100).
然后应用规则 (3)并得到 (001,100)。
例 8.5：
把下述产生式定义的算术表达式映射到后缀波兰表示：
E?E+T
E?T
T?T?F
T?F
F?(E)
F?a
E=ET+
E=T
T=TF?
T=F
F=E
F=a
产生式 翻译规则
确定输入 a+a?a的输出：
(E,E)?(E+T,ET+)
(T+T,TT+)
(F+T,FT+)
(a+T,aT+)
(a+T?F,aFF?+)
(a+F?F,aFF?+)
(a+a?F,aaF?+)
(a+a?a,aaa?+)
定义：
一个语法制导的翻译模式是一个五元组 T=(N,?,?，
R,S),其中
(1) N是非终结符的有限集。
(2)?是有限的输入字母表。
(3)?是有限的输出字母表。
(4) R是形如 A,?的规则的有限集,其中
∈ (N∪?)*,?∈ (N∪?)*且?中那组非终结符是?中 那组非终结符的置换。
(5) S是 N中一个特别的非终结符，即开始符。
定义：
若 T= (N,?,?,R,S)是 SDTS,?(T)则称为语法制导的翻译 (SDT)，文法 Gi=(N,?,P,S)，其中 P={A|A,?属于 R)，称为 SDTS T的基础（或输入）文法。文法
G0=( N,?,P?,S),，其中 P?={A| A,?属于 R},称为 T的输出文法。
把语法制导的翻译方法看成是将输入文法 Gi中的推导树变换成输出文法 G0中的推导树。给了输入句子 x，
可以按如下方式得到 x的一个翻译：先为推导 x构造一棵推导树，再变换该树到输出文法中的一棵树，然后取此输出树的边缘作为 x的一个翻译。
语义制导翻译中的规则 A,?
对应于每一个文法产生式 A? 都有与之相关联的一套语义描述?
属性文法 (attribute grammar)是一个三元组,A=(G,V,F)
属性文法可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来语法制导翻译实现从概念上讲,语法制导翻译即基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析,构造语法分析树,
然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算输入符号串
分析树
属性依赖图
语义规则的计算顺序依赖图由称为依赖图的一个有向图 描述分析树中的继承属性和属性中间的相互依赖关系。
依赖图的构造算法：
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结点构造一条有向边依赖图 ----例 8.2
例 8.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)
例 8.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
依赖图中的结点由数字来标识。从代表
T.type的结点 4有一条有向边连到代表 L.in
的结点 5，因为根据产生式 E→TL 的语义规则 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以前都是可用的。
属性文法 说明的翻译是很精确的。最基本的文法用于建立输入符号串的分析树。依赖图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。
例 8.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） 属性的计算次序 。
例：定义定点二进制数的 CFG:
(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 f1v1 l 1B f 2v2
[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]
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]
在某些情况下可用一遍扫描实现属性文法的语义规则计算 。 也就是说在语法分析的同时完成语义规则的计算,无须明显地构造语法树或构造属性之间的依赖图 。 因为单遍实现对于编译效率非常重要具体的实现希望在单遍扫描中完成翻译研究怎样实现这种翻译器。一个一般的属性文法的翻译器可能是很难建立的，然而有一大类属性文法的翻译器是很容易建立的
s-属性 适用于 自底向上的计算
L-属性 适用于自顶向下的分析，也可用于 自底向上。
S－属性文法的自下而上计算
S－属性文法，它只含有综合属性。
综合属性可以在分析输入符号串的同时自下而上的分析器来计算 。 分析器可以保存与栈中文法符号有关的综合属性值,每当进行归约时,
新的属性值就由栈中正在归约的产生式右边符号的属性值来计算 。
S－属性文法的翻译器通常可借助于 LR分析器实现 。 在 S－属性文法的基础上,LR分析器可以改造为一个翻译器,在对输入串进行语法分析的同时对属性进行计算 。
产生式 语义规则
０）Ｌ → Ｅ ｐｒｉｎｔ（Ｅ,ｖａｌ）
１）Ｅ → Ｅ 1＋Ｔ Ｅ,ｖａｌ ∶ ＝Ｅ 1.ｖａｌ＋Ｔ,ｖａｌ
２）Ｅ → Ｔ Ｅ,ｖａｌ ∶ ＝Ｔ,ｖａ l
３）Ｔ → Ｔ 1*Ｆ Ｔ,ｖａｌ ∶ ＝Ｔ 1.ｖａｌ × Ｆ,ｖ ａｌ
４）Ｔ → F Ｔ,ｖａｌ ∶ ＝ F.ｖａｌ
５）Ｆ → （Ｅ） Ｆ,ｖａｌ ∶ ＝Ｅ,ｖａｌ
６）Ｆ → ｄ iｇ iｔ Ｆ,ｖａｌ,＝ｄｉｇｉｔ,ｌｅｘｖａｌ
LR分析器可以改造为一个翻译器,在对输入串进行语法分析的同时对属性进行计算 。
LR分析器 增加语义栈
２＋３ *５的分析和计值过程步骤 动作 状态栈 语义栈 (值栈 ) 符号栈 余留输入串
１） ０ － ＃ ２＋ 3*５＃
２） ０５ －－ ＃ ２＋ 3 *５＃
３） ｒ６ ０３ －２ ＃Ｆ ＋３ *５＃
４）ｒ４ ０２ －２ ＃Ｔ ＋３ *５＃
５）ｒ２ ０１ －２ ＃Ｅ ＋３ *５＃
６） ０１６ －２－ ＃Ｅ＋ ３ *５＃
７） ０１６５ －２－－ *５＃
８）ｒ６ ０１６３ －２－３ *５＃
９）ｒ４ ０１６９ －２－３ *５＃
１０） ０１６９７ －２－３－ ＃Ｅ＋Ｔ *
１１） ０１６９７５ －２－３－－ ＃Ｅ＋Ｔ *５ ＃
１２）ｒ６ ０１６９７（１０） －２－３－５ ＃Ｅ＋Ｔ *Ｆ #
１３）ｒ３ ０１６９ －２－（１５） ＃Ｅ＋Ｔ ＃
１４）ｒ１ － （１７） ＃Ｅ ＃
１５）接受
BOTTOM—UP
语义处理是作类型检查,对二目运算符的运算对象进行类型匹配审查 。
(LR分 析 ）,增加语义栈 归约 时进行语义动作,
例 8.7G[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 in t
o # --
2 T in t
o # --
5 + ---
2 T in t
o # --
4 n in t
5 + ---
2 T in t
o # --
6 T in t
5 + ---
2 T in t
o # --
1 E in t
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 in t
o # --
2 T in t
o # --
5 + ---
2 T in t
o # --
3 b b ool
5 + ---
2 T in t
o # --
6 T b ool
5 + ---
2 T in t
o # --
1 E e r r o r
o # --
L－属性文法和自顶向下翻译一个属性文法称为 L－属性文法,如果对于每个产生式
A→X 1X2… Xn,其每个语义规则中的每个属性或者是综合属性,或者是 Xj（ 1≤j≤n） 的一个继承属性且这个继承属性仅依赖于：
（ 1） 产生式 Xj在左边符号 X1,X2,…,Xj-1的属性；
（ 2） A的继承属性 。
S－属性文法一定是 L－属性文法,因为 （ 1）,（ 2） 限制只用于继承属性 。
L－属性文法允许一次遍历就计算出所有属性值 。
LL（ 1） 这种自上而下分析文法的分析过程,从概念上说可以看成是深度优先建立语法树的过程,因此,我们可以在自上而下语法分析的同时实现 L属性文法的计算 。
例（中缀表达式翻译成相应的后缀表达式）
E→TR
R→addop T {print(addop,Lexeme)} R 1|ε
T→num {print(num.val)}
翻译模式 （ Translation schemes） 适合语法制导翻译的另一种描述形式 。 翻译模式给出了使用语义规则进行计算的次序,可把某些实现细节表示出来 。 在翻译模式中,和文法符号相关的属性和语义规则 （ 这里我们也称语义动作 ）,用花括号 ｛ ｝
括起来,插入到产生式右部的合适位置上 。
输入串 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。计算 9－ 5并把结果 4传递到中间的 R结点这是通过产生式中嵌入的下面动作实现：
{R1.i,= R.i－ T.val}
类似的动作把 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)
思考问题 -把建立语法树的翻译模式变换成适合预测分析的模式
E?E1+T {E.nptr:=mknode(?+?,E1.nptr,T.nptr)
E? E1-T {E.nptr:=mknode(?-?,E1.nptr,T.nptr)
E? T {E.nptr:=T.nptr)
自下而上计算继承属性
讨论在自下而上的分析过程中实现 L－属性文法的方法。这种方法可以实现任何基于 LL（ 1）文法的 L－属性文法，它还可以实现许多（不是所有）基于 LR（ 1）
文法的 L－属性文法。这种方法是 S-属性文法的自下而上翻译技术的一般化
自下而上分析器对产生式 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)}
回顾例 8.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
例 8.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? Li,d
id3# TL,
# TL,id3
# TL L? Li,d
# D D? TL
用综合属性代替继承属性有时,改变基础文法可能避免继承属性 。 例如,一个
Pascal的说明由一标识符序列后跟类型组成,如,m,
n,integer。 这样的说明的文法可由下面形式的产生式构成
D→L,T
T→integer|char
L→L,id|id
因为标识符由 L产生而类型不在 L的子树中，我们不能仅仅使用综合属性就把类型与标识符联系起来。事实上，如果非终结符 L从第一个产生式中它的右边 T
中继承了类型，则我们得到的属性文法就不是 L－
属性的，因此，基于这个属性文法的翻译工作不能在语法分析的同时进行。
一个解决的方法是重新构造文法使类型作为标识符表的最后一个元素：
D→id L
L→,id L|,T
T→integer|char
这样,类型可以通过综合属性 L.type进行传递,当通过 L产生每个标识符时,它的类型就可以填入到符号表中 。
语义制导翻译的 编译实现,
例 8.6
E –> TE'
E' –> A T E' |?
T –> FT'
T' –> M F T' |?
F –> (E) | int
A –> + | -
M –> * | /
E -> TE'
E' -> A T E' { rhs = PopOperand();lhs = PopOperand();
switch (PopOperator()) {
case ADD,PushOperand(lhs+rhs); break;
case SUB,PushOperand(lhs-rhs); break;}}
|? { /* empty,do nothing */ }
T -> FT'
T' -> M F T' { rhs = PopOperand();lhs = PopOperand();
switch (PopOperator()) {
case MUL,PushOperand(lhs*rhs); break;
case DIV,PushOperand(lhs/rhs); break;}}
|? { /* empty,do nothing */ }
A -> + { PushOperator(ADD);}| - { PushOperator(SUB);}
M -> * { PushOperator(MUL);}| / { PushOperator(DIV);}
F -> int { PushOperand(intval);}| (E) { /* handled during
parsing of E */ }
parse 2 + 4 * 3:
分析动作桥 分析栈 运算对象栈 运算符栈
Predict E –> TE‘ E#
Predict T –> FT' TE‘#
Predict F –> int FT'E‘#
Match int intT'E‘#
Predict T' –>? T'E‘# 2
Predict E' –> ATE' ATE' # 2
Predict A –> + ATE‘# 2
Match + +TE‘# 2
Predict T –> FT' TE‘# 2 +
Predict F –> int FT'E‘# 2 +
Match int intT'E‘# 2 +
Predict T' –> MFT' T'E‘# 4 2 +
Predict M –> * MFT'E‘# 4 2 +
Match * *FT'E‘# 4 2 +
Predict F –> int FT'E‘# 4 2 * +
Match int intT'E‘# 4 2 * +
Predict T' –>? T'E‘# 3 4 2 * +
Predict E' –>? E‘#
Yacc或 bison作为编译程序的生成工具，利用的就是语法制导翻译方法。它使用符号 $$表示产生式左端的属性，
$n表示存取产生式右端第 n个文法符号相联的属性如例 8.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’}
语义分析
语义分析
属性文法和语法制导翻译方法和技术应用于语义分析中 。
语义分析通常包括：
（ 1） 类型检查 。 验证程序中执行的每个操作是否遵守语言的类型系统的过程,,编译程序必须报告不符合类型系统的信息 。
（ 2） 控制流检查 。 控制流语句必须使控制转移到合法的地方 。
例如,在 C语言中 break语句使控制跳离包括该语句的最小
while,for或 switch语句 。 如果不存在包括它的这样的语句,
则就报错 。
（ 3） 一致性检查 。 在很多场合要求对象只能被定义一次 。 例如 Pascal语言规定同一标识符在一个分程序中只能被说明一次,同一 case语句的标号不能相同,枚举类型的元素不能重复出现等等 。
（ 4） 相关名字检查 。 有时,同一名字必须出现两次或多次 。
例如,Ada 语言程序中,循环或程序块可以有一个名字,出现在这些结构的开头和结尾,编译程序必须检查这两个地方用的名字是相同的 。
(5)名字的作用域分析类型和声明（ Types and declarations）
一个类型是一组值和在这些值上的一组操作，程序设计语言中有三种类型,
基本类型,int,float,double,char,bool等等,也可能允许在 基本类型基础上 用户自己定义的类型，如枚举型,
复合类型：数组,指针，记录 /结构 /联合,类等等,这些类型由基本类型构成,
复杂类型：链表，栈，队，树，堆，表格等等,可以把它们组织成 ADT,一个语言不一定支持这类高级的抽象。
声明是程序中的一个语句,是把数据对象的名称和类型，以及生命周期信息传给编译,声明的地方传递生命周期信息也有些语言允许声明初始化变量 。 如,double calculate(int a,double
b); // function prototype
int x = 0; // global variables available throughout
double y; // the program
int main() {
int m[3]; // local variables available only in main
char *n;
,..
}
强类型的 -任何数据 类型都可以在 编译时确定弱类型的,
进行类型检查的时间：编译时，运行时，或者两者结合,
静态类型检查 编译时进行类型检查动态类型检查，将类型信息并到运行时每个数据单元中,
隐含类型转换,
P→ D； E
D→ D； |id:T
T→ char | integer | aray [num]of T| ↑ T
E→ literal|num | id| E mod E| E [E]|E↑
P代表程序； D代表说明； E代表表达式 。 如程序语句：
key,integer;
key mod 1999
语言本身提供两种基本类型,char和 integer。
除此之外还有缺省的基本类型 type_ error和 void。 假定所有数组都从下标 1开始确定标识符类型的部分翻译模式
（ 1） P→D ； E
（ 2） D→D ； D
（ 3） D→id,T {addtype (id,Entry,T,type)}
（ 4） T→char {T,Type:= char}
（ 5） T→integer {T,Type:= integer}
（ 6） T→↑T 1 {T,Type:= pointer (T1,type)}
（ 7） T→array [num]of T1
{T,Type,= array (num.Val,T1.type)}
语句的类型检查的翻译模式
S→id,=E { if id,Type= E,Type
Then S,Type:= void
else S,Type:= type_ error}
S→if E then S1 {if E,type= boolean
then S,Type:= S1,type
else S,type,= type_ error}
S→ while E do S1 {if E,type= boolean
Then S,type:= S1,Type
else S,type:= type_ error}
设计 类型检查程序
1.辨认语言中可用的类型
2.辨认具有类型的语言结构
3.辨认语言的语义规则
In Decaf
base types,int,double,bool,string
compound types,arrays and classes,
An array can be made of any type (either a base type,
a class,or out of other arrays).
Classes are a bit special in that the class name must
be declared before it can be used in a declaration,
ADTs can be constructed using classes,but they
aren?t handled in any way differently than classes,
so we don?t need to consider them specially.
In Decaf the relevant language constructs
constants,every constant has an associated type,A scanner tells
us these types as well as the associated lexeme.
variables,all variables (global,local,and instance) must have a
declared type of either int,double,bool,string,array,or class.
functions,functions have a return type,and each parameter in
the function definition has a type,as does each argument in a
function call.
expressions an expression can be a constant,variable,function
call,or some operator (binary or unary) applied to expressions,
Each of the various expressions have a type based on the type of
the constant,variable,return type of the function,or type of
operands.
The other language constructs in Decaf (if,while,Print,
assignments,etc.) also have types associated with them,because
somewhere in each of these we find an expression.
The semantic rules ——govern what types are
allowable in the various language constructs,In
Decaf,
operand to a unary minus must either be double or int,
the expression used in a loop test must be of bool type,
general rules,such as all variables must be declared before
use,all classes are global,and so on.
arrays,the index used in an array selection expression must be of integer
type
expressions,? the two operands to % must both be int,The result type is
int.
this is bound to the receiving object within class scope,it is an error
outside class scope
variables,a variable declared of class type must refer to a defined class
name
functions,the type of each actual argument in a function call must be
compatible with the formal parameter。 if a function has a void return
type,it may only use the empty return statement
实现 类型检查程序
.
首先，将每个名字（标识符）的类型信息记录在符号表中作用域检查 作用域和可见性基本作用域规则（ lexical rule)
int a;
void Binky(int a) {
int a;
a = 2;
...
}
作用域检查实现：
1每个作用域一个独立的符号表，这些符号表组织成作用域栈
2对所有作用域的全局符号表，每个作用域有一个作用域号
？各自的优缺点,PL/0用的是哪种运算符（函数）的重载 多态函数重载运算符 （ overloading operator） 根据上下文可以执行不同的运算 。 ＋是重载符号,在 A＋ B中,当 A和 B为整数,实数,
复数或者矩阵时,运算符执行不同类型的运算当出现重载运算符时,要确定它所表示的唯一的意义,称为运算符识别 。
检查运算符的操作数 。
多态函数 ----能实现对数据结构进行操作的算法,不管数据结构的元素类型是什么多态函数的特点是，每次被调用时，传递过来的参数可以具有不同类型。
,
.
,
何谓中间代码 ( Intermediate code )
( Intermediate representation )
( Intermediate language )
源程序的一种内部表示，不依赖目标机的结构，易于机械生成目 标代码的中间表示。
为什麽要此阶段逻辑结构清楚；利于不同目标机上实现同一种语言；
（ 参考第 12 章的 275,276页 ）
利于进行与机器无关的优化 ；这些内部形式也能用于解释。
中间代码的几种形式逆波兰 四元式 三元式 间接三元式 树中间代码逆波兰,A B C D - * + E C D – N ^ / +
四元式,( 1 ) ( - C D T1 )
( 2 ) ( * B T1 T2)
( 3 ) ( + A T2 T3)
( 4 ) ( - C D T4)
( 5 ) ( ^ T4 N T5)
( 6 ) ( / E T5 T6)
( 7 ) ( + T3 T6 T7)
例,A + B * ( C - D ) + E / ( C - D ) ^N
三元式,( 1) ( - C D )
(2) ( * B (1 ) )
(3) ( + A (2 ) )
(4) ( - C D )
(5) ( ^ (4) N )
(6) ( / E (5 ) )
(7) ( + (3 ) (6 ) )
例,A + B * ( C - D ) + E / ( C - D ) ^N
间接三元式,间接三元式序列 间接码表
( 1) ( - C D ) （ 1 ）
( 2) ( * B ( 1) ) （ 2 ）
( 3) ( + A ( 2) ) （ 3 ）
( 4 ) ( ^ ( 1 ) N ) （ 1 ）
( 5) ( / E ( 4) ) （ 4 ）
( 6) ( + ( 3) (5 ) ) （ 5 ）
（ 6 ）
例,A + B * ( C - D ) + E / ( C - D ) ^N
简单赋值语句的 (四元式）翻译四元式形式,
result,= arg1 op arg2
语义属性,id.name,E.place
函数,lookup( id.name) ;
过程,emit(t,= arg1 op arg2);
newtemp;
产生式和语义描述：
(1) S? id,= E
{ P:=lookup (id.name) ;
if P? nil then emit( P ―,=‖ E.place)
else error }
(op,arg1,arg2,result) 或
(2) E?E1+E2
{E.place:= newtemp;
emit(E.place―:=‖ E1.place―+‖E2.place)}
(3) E? - E1
{ E.place:=newtemp;
emit(E.place―:=‖―uminus‖ E1.place)}
(4) E?( E1)
{ E.place:= E1.place}
(5) E?id
{E.place:=newtemp;
P:=lookup(id.name);
if P?nil then E.place:=P
else error}
简单说明句的翻译 -翻译是指在符号表中登录名字和性质。
最简单的说明句的语法：
Ｄ → integer〈 namelist〉 ｜ real〈 namelist〉
〈 namelist〉 → 〈 namelist〉,id｜ id
用自下而上翻译 文法改写：
Ｄ → Ｄ 1,id
｜ integer id
| real id
(1)Ｄ → integer id｛ enter(id,int） ;D.att:=int}
(2)Ｄ → real id｛ enter(id,real） ;D.att:=real}
(3)Ｄ → Ｄ １,id｛ enter(id，Ｄ １,att）；
D.att:=Ｄ １,att｝
不改写文法，用自下而上翻译 --请你自己设计用自上而下翻译 -------------------请你自己设计如 i f B t h e n S 1 e l s e S 2
B 的 代 码条 件 假转
S1的 代 码转 移
S2的 代 码
B
S1 S2
N
Y
控制语句的翻译 -
结构的翻译
E.false
控制语句中布尔表达式的翻译控制语句 S?if E then S 1 else S 2
E 的代码 E.true
E.true,S1 的代码
goto out
E.false,S2 的代码
out:
,把条件转移的布尔表达式 E 翻译成仅含条件真 转 和 无条件 转 的四元式
E,a rop b
if a rop b goto E.true
goto E.false
如,a<b or c<d and e<f
可 翻译成如下四元式：
(1) if a<b goto E.true
(2) goto (3)
(3) if c<d goto (5)
(4) goto E.false
(5) if e<f goto E.true
(6) goto E.false
(翻译 不是最优 )
语句 if a<b or c<d and e<f then S1 else S2的四元式
(1) if a<b goto (7) //转移至 (E.true )
(2) goto (3)
(3) if c<d goto (5)
(4) goto (p+1) //转移至 (E.false)
(5) if e<f goto (7)
(6) goto (p+1)
(7)( S1的四元式
……
(p-1) …… ）
(p) goto (q)
(p+1) (S2的四元式
……
(q-1) …… ）
(q)
//转移至 (E.true )
//转移至 (E.false)
//(E.false)入口
// (E.true ) 入口记录需回填地址的四元式，把需回填Ｅ．ｔｒｕｅ的四元式拉成一链，把需回填Ｅ．ｆａｌｓｅ的四元式拉成一链，分别称做,真,链和,假,链
（１０） … ｇ oｔｏ Ｅ．ｔｒｕｅ
…
（２０） … ｇｏｔｏ Ｅ．ｔｒｕｅ
…
（３０） … ｇｏｔｏ Ｅ．ｔｒｕｅ
则链成
（１０） … ｇｏｔｏ （０）
…
（２０） … ｇｏｔｏ （１０）
…
（３０） … ｇｏｔｏ （２０）
把地址（３０）称作,真,链链首，０为链尾标志，即地址（１
０）为,真,链链尾。
语义描述使用的变量和过程：
E.true,―真,链,E.false,―假,链 。
E.codebegin,E 的第一个四元式
Nextstat,下一四元式地址过程,emit( ) 输出一条四元式，而 nextstat+1
merge(p1,p2) 把 p1 的链首填在 p2 的链尾例,merge(p1,p2)
(p10) goto ( 0)
……
p1 链 (p100) goto (p10)
…… `
(p1) goto (p100)
(p20) goto( 0) (p100)
……
p2 链 (p200) goto (p20)
……
(p2) goto (p200)
backpatch(p,t) 把 链首 p 所链接的每个四元式的第四区段都填为 t
语句 i f a < b o r c<d a n d e<f t h en S
1
el s e S
2
的四元式
(1 ) i f a < b g o t o ( 7 ) ( E,t ru e ) ( 1 ) 和 ( 5 ）
( 2 ) g o t o ( 3 ) 拉链 （真）
( 3 ) i f c<d g o t o ( 5 )
( 4 ) g o t o ( p + 1 ) ( E,f a l se) ( 4 ) 和 ( 6 )
( 5 ) i f e<f g o t o ( 7 ) 拉链 （假）
( 6 ) g o t o ( p + 1 )
( 7 ) ( S
1
的四元式
( p - 1 )）
( p ) g o t o (q)
( p + 1 ) ( S
2
的四元式
( q - 1 )）
(q)
自下而上分析中的一种翻译方案：
(1) E→ E1 or E 2 { backpatch(E 1.false,E 2.Codebegin);
E.Codebegin:= E 1.codebegin;
E.true:=merge(E 1.true,E 2.true)
E.false:= E 2.false}
(2)E→ E1 and E 2 { backpatch(E 1.true,E 2.codebegin);
E.Codebegin:= E 1.codebegin;
E.true:= E 2.true;
E.false:= merge(E 1.false,E 2false);}
(3) E→ not E1 { E.true:= E 1.false;
E.Codebegin:= E 1.codebegin;
E.false:= E 1.true
( 4 ) E → (E
1
) { E,t r u e,= E
1
,t r u e ;
E,C o d e b e g i n,= E
1
,c o d e b e g i n ;
E,f a l se,= E
1
,f a l se }
( 5 ) E → i d 1 r o p i d 2 { E,t r u e,=n e x t st a t ;
E,C o d e b e g i n,=n e x t st a t ;
E,f a l se,=n e x t st a t + 1 ;
e m it (? if ‘ id 1,p la c e? r o p ‘ id 2,p la c e?g o to ‘– ) ;
em it (? g o t o ‘ - ) }
( 6 ) E → i d { E,t r u e,=n e x t st a t ;
E,c o d e b e g i n,=n e x t st a t ;
E,f a l se,=n e x t st a t + 1 ;
e m it (? if ‘ id,p la c e?g o to ‘ – ) ;
e m it (? g o t o ‘ - ) }
GOTO语句翻译 —拉链返填
……
（ 10） goto L （ 10） goto 0
…… …… 链尾 （ 10）
（ 20） goto L （ 20） goto 10
…… ……
（ 30） goto L (30) goto 20
…… …… 链头 （ 30）
（ 40） L,…… （ 40） L,….
符号表
name type def add
…
L label not r
(p) goto 0
…
(q) goto p
…
(r) goto q
建链的方法是：若ｇｏｔｏ Ｌ中的标号Ｌ尚未在符号表中出现，则把Ｌ填入表中，置Ｌ的
,定义否,标志为,未,,把ｎｅｘｔｓｔａ
ｔ填进Ｌ的地址栏中 作为新链首，然后，产生四元式（ｇｏｔｏ ０），其中０为链尾标志。
若Ｌ已在符号表中出现（但,定义否,标志为
,未,），则把它的地址栏中的编号（记为ｑ）
取出，把 nextstat填进该栏作新链首，然后，产生四元式（ｇｏｔｏ ｑ）。
定义标号语句的产生式
Ｓ → <label> Ｓ
<label>→ ｉ：
那么，当用 <label>→ ｉ：进行归约时，应做如下的语义动作：
1.若ｉ所指的标识符（假定为Ｌ）不在符号表中，则把它填入，置,类型,为,标号,,,定义否,为
,已,,,地址,为 nextstat。
2.若Ｌ已在符号表中但,类型,不为,标号,或,定义否,为,已,,则报告出错。
3.若Ｌ已在符号表中，则把标志,未,改为,已,,
然后，把地址栏中的链首（设为ｑ）取出，同时把
nextstat填在其中，最后，执行 backpatch（ｑ，
nextstat）。
翻译ｇｏｔｏ语句时，还有两点必须注意第一：相同名字的标号可以在不同名字作用域中定义。如：
（１） ｂｅｇｉｎ
（２） Ｌ：ｂｅｇｉｎ
（３） ｇｏｔｏ Ｌ； //延迟使用
（４） ……
（５） Ｌ,…
（６） ｅｎｄ
（７） ｅｎｄ
第二，转移标号是非法的
（１） for ｉ ∶ =１ to 10 do
（２） begin gotoＬ；
（３） for ｊ ∶ =１ to 20 do
（４） begin goto Ｌ；
… …
（ｎ） L,end ｛ forｊ｝
end ｛ for i｝
处理到第（ｎ）行后，第（４）行的 goto目标得以解决。而第（２）行的 goto Ｌ是非法的，但只有当循环关闭时才能确定。
中间表示的不同层次源 中层 IR 低层 IR
float a[10][20]; t1 = j + 2 …
a[i][j+2]; t2 = i * 20
t3 = t1 + t2
高层 IR t4 = 4 * t3
t1 = a[i,j+2] t5 = addr a
t6 = t5 + t4
t7 = *t6
抽象语法树和 DAG图语法树可以作为一种合适的中间语言形式。在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树（ Abstract Syntax Tree）。
在抽象语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点，即这些叶结点的父结点如产生式 S→if B then S 1 else S2抽象语法树表示
if-then-else
B S1 S2
语法树和抽象语法树
directed acyclic graph (DAG).
b*c+b*c
+
*
b c
in Decaf compiler
Three-address code (TAC)
a = b * c + b * d
t1 = b * c;
t2 = b * d;
t3 = t1 + t2;
a = t3;
控制流
if (a < b + c)
a = a - c;
c = b * c;
t1 = b + c;
t2 = a < t1;
IfZ t2 Goto L0;
t3 = a - c;
a = t3;
L0,t4 = b * c;
c = t4;
函数调用，数组访问
int n;
n = ReadInteger();
Binky(arr[n]);
n = LCall
_ReadInteger();
t1 = 4;
t2 = t1 * n;
t3 = arr + t2;
t4 = *(t3);
LCall _Binky(t4);
void main() {
int a;
int b;
int c;
a = 1;
b = 2;
c = a + b;
Print(c);
}
main:
BeginFuncWithParams;
Var a;
Var b;
Var c;
Var _t0;
_t0 = 1;
a = _t0;
Var _t1;
_t1 = 2;
b = _t1;
Var _t2;
_t2 = a + b;
c = _t2;
LCall _PrintInt(c);
EndFunc;
void main() {
Print("hello world");
}
main:
BeginFuncWithParam
s;
Var _t0;
_t0 = "hello world";
LCall _PrintString(_t0);
EndFunc;
void main() {
int a;
a = 2 + a;
Print(a);
}
main:
BeginFuncWithParams;
Var a;
Var _t0;
_t0 = 2;
Var _t1;
_t1 = _t0 + a;
a = _t1;
LCall _PrintInt(a);
EndFunc;
void Binky(int[] arr) {
arr[1] = arr[0] * 2;
}
_
Binky:
BeginFuncWithParams arr;
Var _t0; _t0 = 1;
Var _t1; _t1 = 4;
Var _t2; _t2 = _t1 * _t0;
Var _t3; _t3 = arr + _t2;
Var _t4; _t4 = 0;
Var _t5; _t5 = 4;
Var _t6; _t6 = _t5 * _t4;
Var _t7; _t7 = arr + _t6;
Var _t8; _t8 = *(_t7);
Var _t9; _t9 = 2;
Var _t10; _t10 = _t8 * _t9;
*(_t3) = _t10;
EndFunc;
int foo(int a,int b) {
return a + b;
}
void main() {
int c;
int d;
foo(c,d);
}
_foo:
BeginFuncWithParams a,b;
Var _t0;
_t0 = a + b;
Return _t0;
EndFunc;
main:
BeginFuncWithParams;
Var c;
Var d;
Var _t1;
_t1 = LCall _foo(c,d);
EndFunc;
class Animal {
int height;
void InitAnimal(int h) {
this.height = h;
}
}
_
_Animal_InitAnimal:
BeginFuncWithParam
s this,h;
*(this + 4) = h;
EndFunc;
VTable Animal =
__Animal_InitAnimal,；
class Cow extends
Animal {
void InitCow(int h) {
InitAnimal(h);
}
}
__Cow_InitCow:
BeginFuncWithParams this,
h;
Var _t0;
_t0 = *(this);
Var _t1;
_t1 = *(_t0);
ACall _t1(this,h);
EndFunc;
VTable Cow =
__Animal_InitAnimal,
__Cow_InitCow,;
void Binky(class Cow
betsy) {
betsy.InitCow(5);
}
_Binky:
BeginFuncWithParams
betsy;
Var _t2;
_t2 = 5;
Var _t3;
_t3 = *(betsy);
Var _t4;
_t4 = *(_t3 + 4);
ACall _t4(betsy,_t2);
EndFunc;
