语法制导翻译
-
2023年2月27日发(作者：74HC154)1
中间语言与语法制导翻译
重点与难点
重点：语法制导翻译的基本思想，属性文法，翻译模式，说明语句的翻译方案。
三地址码，各种语句的目标代码结构、属性文法与翻译模式。
难点：属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，怎么通过属性来
表达翻译。布尔表达式的翻译，对各种语句的目标代码结构、属性文法与翻译模式的理解。
基本要求
掌握语法制导翻译的基本思想，属性文法，综合属性，继承属性，固有属性，属性计算，
S_属性文法，L_属性文法，说明语句的翻译方案，翻译模式、属性文法的实现
掌握中间语言与语义分析的基本概念；熟练掌握语法（结构）树、三地址代码、赋值与
控制语句的翻译、说明语句的翻译；掌握组合数据说明的翻译、过程调用翻译。
例题解析
例1给定文法E-->T{R.i:=T.p}
R{E.p:=R.s}
R-->addop
T{R1.i:=mknode(,R.i,T.p)}
R{R.s:=R1.s}
R-->{R.s:=R1.s}
T-->(E){T.p:=E.p}
T-->id{T.p:=mkleaf(id,)}
T-->num{T.p:=mkleaf(num,)}
(1)指出文法中的各非终结符具有哪些综合属性和哪些继承属性
⑵画出按本翻译模式处理表达式a+20+(b-10)时所生成的语法树
【解】
(1)E的综合属性p，R的继承属性i，综合属性s；T的综合属性p
(2)处理表达式a+20+(b-10)时所生成的语法树如下
+
(ID,a)+
（NUM,20）-
(ID,b)(NUM,10)
例2定义一个计算器的属性文法,完成一个输入表达式值的计算和显示,
【解】计算器的文法
L→E
E→E1+T|T
2
T→T1*F|F
F→(E)|digit
引进属性val，计算器的属性文法：
L→Eprint()（L的虚属性）
E→E1+:=+
E→:=
T→T1*:=*
T→:=
F→(E):=
F→:=
lexval是单词digit的属性
例3给出对输入串6-33*5+4的分析树与属性计算
【解】3*5+4的分析树与属性计算
例4定义一个说明语句的属性文法
【解】说明语句的文法
D→TL
T→int
T→real
L→L1,id
L→id
要解决的问题：记录标识符的类型和类型信息传递
方法：引进属性type,和in,用记录类型信息，并传给,
说明语句的属性文法如下:
D→:=
T→:=‘integer’
T→:=‘real’
+
*
=19
=15
=4
==4
===3
=3
=3
L
Print(19)
=5
3
L→L1,:=
addtype(,)
L→idaddtype(,)
entry单词id的属性
addtype在符号表中为变量填加类型信息
例5给出输入串realid1,id2,id3的分析树和属性计算
例6设下列文法生成变量的类型说明
D→idL
L→,idL|:T
T→integer|real
试构造一个翻译模式，把每个标识符的类型存入符号表。
【解】解题思路
这是一个对说明语句进行语义分析的题目，不需要产生代码，但要求把每个标识符的类
型填入符号表中。
解答
对D，L，T设置综合属性type。过程addtype(id,type)用来把标识符id及其类型type
填入到符号表中。
翻译模式如下：
D→idL｛addtype(,)｝
L→,idL1{addtype(,);:=;}
L→:T{:=}
T→integer{:=interger}
T→real{:=real}
例7文法G的产生式如下：
S→(L)|a
L→L,S|S
(1)试写出一个语法制导定义，它输出配对括号个数;
(2)写一个翻译方案，打印每个a的嵌套深度。如((a),a),打印2,1。
D
=real
=real
real
,
Id3
,
Id2
=real
=real
Id1
addtype
addtype
4
【解】解题思路
本题包括两部分，第1部分要求写语法制导定义，第2部分要求写翻译方案。语法制导
定义（或属性文法）可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户
从明确说明翻译顺序的工作中解脱出来。翻译方案（也称翻译模式）给出了使用语义规则进
行计算的次序，把某些实现细节表示出来。读者从下面解答中可体会两者的区别。
解答
为S、L引入属性h,代表配对括号个数。语法制导定义如下：
产生式语义规则
S→(L)S.h:=L.h+1
S→aS.h:=0
L→L1,SL.h:=L1.h+S.h
L→SL.h:=S.h
S’→Sprint(S.h)
(2)为S、L引入d，代表a的嵌套深度。翻译方案如下：
S’→｛S.d:=0;｝S
S→‘(’{L.d:=S.d+1;}
L
‘)’
S→a{print(S.d);}
L→{L1.d:=L.d;}
L1
{S.d:=L.d;}
S
L→{S.d:=L.d}
S
例8下列文法对整型常数和实型常数施用加法运算符“+”生成表达式;当两个整型数相加
时，结果仍为整型数，否则，结果为实型数：
E→E+T|T
T→|num
(1)试给出确定每个子表达式结果类型的属性文法。
(2)扩充(1)的属性文法，使之把表达式翻译成后缀形式，同时也能确定结果的类型。应该
注意使用一元运算符inttoreal把整型数转换成实型数，以便使后缀形如加法运算符的两个
操作数具有相同的类型。
【解】解题思路
确定每个子表达式结果类型的属性文法是比较容易定义的。关键是如何扩充此属性文
法，使之把表达式翻译成后缀形式。我们将不在name或向T归约的时候输出该运
算对象，而是把运算对象的输出放在T或E＋T向E归约的时候。这是因为考虑输出类型转
换算符inttoreal的动作可能在E＋T归约的时候进行，如果这时两个运算对象都在前面
name或向T归约的时候已输出，需要为第1个运算对象输出类型转换算符时就已
经为时太晚。
还要注意的是，在E＋T向E归约时，该加法运算的第1个运算对象已经输出。所以E
→E＋T的语义规则不需要有输出E运算对象的动作。
解答
5
（1）为文法符号E和T配以综合属性type,用来表示它们的类型。类型值分别用int和real
来表示。确定每个子表达式结果类型的属性文法如下：
产生式语义规则
E→E1＋T{:===intthenintelsereal
E→T{:=}
T→:=real
T→:=int
(2)下面属性文法将表达式的后缀表示打印输出，其中lexeme属性表示单词的拼写。
产生式语义规则
E→E1＋==intthen
begin
:=real;
print();
print(‘inttoreal’);
end
==realthen
begin
:=real;
print(‘inttoreal’);
print();
end
elsebegin
:=;
print();
end
print(‘+’);
E→:=;print();
T→:=real;:=||“.”||
T→:=int;:=;
例9将下列语句翻译为逆波兰表示(后缀式)、三元式和四元表示：
a:=(b+c)*e+(b+c)/f
【解】解题思路
把中缀式转换为后缀式的简单方法：按中缀式中各运算符的优先规则，从最先执行的部
分开始写，一层层套。如a≤b+c∧a＞d∨a+b≠e，先把b+c写为bc+；然后把a≤套上去，
成为abc+≤；再把a＞d表示为ad＞；然后把∧套上去，成为abc+≤ad＞∧，依此类推。
四元式由4个部分组成：算符op、第1和第2运算量arg1和arg2，以及运算结果result。
运算量和运算结果有时指用户自定义的变量，有时指编译程序引进的临时变量。如果op是
一个算术或逻辑算符，则result总是一个新引进的临时变量，用于存放运算结果。
三元式只需3个域：op、arg1和arg2。与四元式相比，三元式避免了临时变量的填入，
而是通过计算这个临时变量的语句的位置来引用这个临时变量。我们很容易把一个算术表达
式或一个赋值句表示为四元式序列或三元式序列。
解答
逆波兰表示为：bc+e*bc+f/+:=
6
三元式序列为：
(1)(+，b，c)
(2)(*，(1)，e)
(3)(+，b，c)
(4)(/，(3)，f)
(5)(+，(2)，(4))
(6)(:=，a，(5))
四元式序列为：
(1)(+，b，c，T1)
(2)(*，T1，e，T2)
(3)(+，b，c，T3)
(4)(/，T3，f，T4)
(5)(+，T2，T4，T5)
(6)(:=，T5，-，a)
例10利用回填技术把语句
whilea>0orb>0do
ifc>0andd<0thenx:=y+1;
翻译为三地址代码。
【解】解题思路
把表达式或赋值语句翻译为三地址代码是容易理解的，如x:=y*z+1翻译为：
T1:=y*z
T2:=T1+1
x:=T2
while语句和if语句的翻译涉及到布尔表达式，我们一并讨论。产生布尔表达式三地
址代码的语义规则如表7.1所示。按表1的定义，每个形如ArelopB的表达式(其中relop
为任一关系运算符)将被翻译为如下形式的两条转移指令：
ifArelopBgoto„
goto„
因此，假定表达式的待确定的真假出口已分别为Ltrue和Lfalse，则a>0orb>0将被
翻译为：
ifa>0gotoLtrue
gotoL1
L1:ifb>0gotoLtrue
gotoLfalse
而c>0andd<0将被翻译为：
ifc>0gotoL3
gotoLfalse
L3:ifd<0gotoLtrue
gotoLfalse
有关if和while语句的属性文法如表2所示。
应用表1和表2不难生成含if和while的语句的三地址代码。
表1产生布尔表达式三地址代码的语义规则
产生式语义规则
7
E→:=;
:=newlable;
:=;
:=;
:=||gen(‘:’)||
E→:=newlable;
:=;
:=;
:=;
:=||gen(‘:’)||
E→:=;
:=;
:=
E→(E1):=;
:=;
:=
E→:=gen(‘if’‘goto’
)||gen(‘goto’)
E→:=gen(‘goto’)
E→:=gen(‘goto’)
表2控制流语句的属性文法
产生式语义规则
S→:=newlable;
:=;
:=;
:=||gen(‘:’)||
S→:=newlable;
:=newlable;
:=;
:=;
:=||gen(‘:’)||
||gen(‘goto’)||
gen(‘:’)||
S→:=newlable;
:=newlable;
:=;
:=;
:=gen(‘:’)||||
gen(‘:’)||||
gen(‘goto’)
解答
所求三地址代码为：
L0：ifa>0gotoL2
gotoL1
8
L1：ifb>0gotoL2
gotoLnext
L2：ifc>0gotoL3
gotoL0
L3：ifd<0gotoL4
GotoL0
L4：T1:=y+1
x:=T1
gotoL0
Lnext：
例11C语言中的for语句的一般形式为：
for(E1;E2;E3)s
其意义如下：
E1；
while(E2)dobegin
S;
E3;
end
试构造一个属性文法和翻译模式，把C语言的for语句翻译成三地址代码。
【解】解题思路
本题既要求构造属性文法，也要求构造相应的翻译模式。因此，有必要回忆一下属性文
法和翻译模式的区别。我们知道，属性文法(有时也称语法制导定义)可以看作是关于语言翻
译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来；而
翻译模式(也称为翻译方案)是一种适合语法制导翻译的描述形式，它给出了使用语义规则进
行计算的次序，这样就可把某些实现细节表示出来。
为了明确翻译目标，我们首先给出for语句的中间代码结构如图1所示。
根据C语言的for语句的语义和以上中间代码结构可以构造出属性文法。
为了构造属性文法相应的翻译模式，通常可采用两种方法：一种方法是在原有产生式中
图1
9
引入必要的标记非终结符；另一种方法是对文法进行分解和改造。两种方法的目的都是为了
便于语法制导翻译。
翻译
把C语言的for语句翻译成三地址代码的属性文法如下：
产生式语义动作
S→for(E1;E2;E3):=newlable;
:=newlable;
:=newlable;
:=;
:=;
:=||gen(‘:’)||
||gen(‘:’)||
||gen(‘goto’)||
gen(‘:’)||||
gen(‘goto’)
下面我们用两种方法构造相应上述属性文法的翻译模式。
方法一：
引入M1、M2和N这3个标记非终结符。M1用来记住E2的开始地址，M2用来记住M3
的开始地址。N是用来产生E3后面的goto语句，从上面的中间代码结构来看，产生这个goto
语句时，转移地址应该是已知的了，但语句是在N→ε归约时产生的，这时不能访问M1的
属性，因此这个转移的目标地址是回填。
所求的翻译模式如下：
S→for(E1;M1E2;M2E3)NS1
{emit(‘goto’);
backpatch(st,);
backpatch(st,);
backpatch(st,);
st:=ist;}
M→ε{:=nextquad}
N→ε{st:=makelist(nextquad);
emit(‘goto_’);
:=nextquad}
方法二：
把产生式S→for(E1;E2;E3)S1改写为：
F1→for(E1;
F2→F1E2;
F3→F2E3)
S→F3S1
这样写是因为，语法制导翻译过程中，在产生E2的代码之前要记下E2的代码地址；在
产生E3的代码之前要记下E3的代码地址，并要对E2的“真”出口进行“回填”；而在产生
E3的代码之后要生成一条goto语句。
所求翻译模式如下：
F1→for(E1;{:=nextquad}
10
F2→F1E2;{1:=;
2:=nextquad;
st:=st;
st:=ist;}
F3→F2E3){emit(‘goto’1);
backpatch(st,nextquad);
:=2;
st:=st}
S→F3S1{emit(‘goto’);
st:=st}
例12将下列Ｃ程序的执行语句翻译成三地址代码(设为L0)：
if(i s=10*s else i=-j 【解】 ifi gotoL2 L1:t0=10*s s=t0 gotoL0 L2:t1=-j i=t1 L0:...