编译原理试题.docx
- 文档编号:16686959
- 上传时间:2023-07-16
- 格式:DOCX
- 页数:18
- 大小:104.88KB
编译原理试题.docx
《编译原理试题.docx》由会员分享,可在线阅读,更多相关《编译原理试题.docx(18页珍藏版)》请在冰点文库上搜索。
编译原理试题
中间语言与语法制导翻译
重点与难点
重点:
语法制导翻译的基本思想,属性文法,翻译模式,说明语句的翻译方案。
三地址码,各种语句的目标代码结构、属性文法与翻译模式。
难点:
属性的意义,对综合属性,继承属性,固有属性的理解,属性计算,怎么通过属性来表达翻译。
布尔表达式的翻译,对各种语句的目标代码结构、属性文法与翻译模式的理解。
基本要求
掌握语法制导翻译的基本思想,属性文法,综合属性,继承属性,固有属性,属性计算,
S_属性文法,L_属性文法,说明语句的翻译方案,翻译模式、属性文法的实现
掌握中间语言与语义分析的基本概念;熟练掌握语法(结构)树、三地址代码、赋值与
控制语句的翻译、说明语句的翻译;掌握组合数据说明的翻译、过程调用翻译。
例题解析
例1给定文法E-->T{R.i:
=T.p}
R{E.p:
=R.s}
R-->addop
T{R1.i:
=mknode(addop.val,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,id.entry)}
T-->num{T.p:
=mkleaf(num,num.val)}
(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定义一个计算器的属性文法,完成一个输入表达式值的计算和显示
【解】计算器的文法
LtE
EtE1+T|T
Ft(e)|digit
引进属性val,计算器的属性文法:
L
t
E
E
t
E1+
T
E
t
T
T
t
T1*
F
T
t
F
F
t
(E)
F
t
digit
print(E.val)(L的虚属性)
E.val:
=El.val+T.val
E.val:
=T.val
T.val:
=Tl.val*F.val
T.val:
=F.val
F.val:
=E.val
F.val:
=digit.lexval
例3给出对输入串6-33*5+4的分析树与属性计算
【解】3*5+4的分析树与属性计算
lexval是单词digit的属性
addtype(id.entry,L.in)
Ltidaddtype(id.entry,L.in)
entry单词id的属性
addtype在符号表中为变量填加类型信息
例5给出输入串realid1,id2,id3的分析树和属性计算
例6设下列文法生成变量的类型说明
DtidL
Lt,idL|:
T
Ttinteger|real
试构造一个翻译模式,把每个标识符的类型存入符号表。
【解】解题思路
这是一个对说明语句进行语义分析的题目,不需要产生代码,但要求把每个标识符的类
型填入符号表中。
解答
对D,L,T设置综合属性type。
过程addtype(id,type)用来把标识符id及其类型type
填入到符号表中。
翻译模式如下:
DtidL{addtype(id.entry,L.type)}
Lt,idL1{addtype(id.entry,L1.type);L.type:
=L1.type;}
Lt:
T{L.type:
=T.type}
Ttinteger{T.type:
=interger}
Ttreal{T.type:
=real}
例7文法G的产生式如下:
St(L)|a
Ltl,S|S
(1)试写出一个语法制导定义,它输出配对括号个数;
(2)写一个翻译方案,打印每个a的嵌套深度。
如((a),a),打印2,1。
【解】解题思路
本题包括两部分,第1部分要求写语法制导定义,第2部分要求写翻译方案。
语法制导
定义(或属性文法)可以看作是关于语言翻译的高级规范说明,其中隐去实现细节,使用户从明确说明翻译顺序的工作中解脱出来。
翻译方案(也称翻译模式)给出了使用语义规则进
行计算的次序,把某些实现细节表示出来。
读者从下面解答中可体会两者的区别。
解答
为S、L引入属性h,代表配对括号个数。
语法制导定义如下:
产生式
语义规则
St(L)
S.h:
=L.h+1
Sta
S.h:
=0
LtL1,S
L.h:
=L1.h+S.h
LtS
L.h:
=S.h
S'ts
print(S.h)
⑵为S、L引入d,代表a的嵌套深度。
翻译方案如下:
S't{S.d:
=O;}S
S('{L.d:
=S.d+1;}
L
')'
Sta{print(S.d);}
Lt{L1.d:
=L.d;}
L1
{S.d:
=L.d;}
S
Lt{S.d:
=L.d}
S
例8下列文法对整型常数和实型常数施用加法运算符“+”生成表达式;当两个整型数相加
时,结果仍为整型数,否则,结果为实型数:
EtE+T|T
Ttnum.num|num
(1)试给出确定每个子表达式结果类型的属性文法。
(2)扩充
(1)的属性文法,使之把表达式翻译成后缀形式,同时也能确定结果的类型。
应该
注意使用一元运算符inttoreal把整型数转换成实型数,以便使后缀形如加法运算符的两个
操作数具有相同的类型。
【解】解题思路
确定每个子表达式结果类型的属性文法是比较容易定义的。
关键是如何扩充此属性文法,使之把表达式翻译成后缀形式。
我们将不在name或num.num向T归约的时候输出该运
算对象,而是把运算对象的输出放在T或E+T向E归约的时候。
这是因为考虑输出类型转
换算符inttoreal的动作可能在E+T归约的时候进行,如果这时两个运算对象都在前面
name或num.num向T归约的时候已输出,需要为第1个运算对象输出类型转换算符时就已
经为时太晚。
还要注意的是,在E+T向E归约时,该加法运算的第1个运算对象已经输出。
所以E
tE+T的语义规则不需要有输出E运算对象的动作。
解答
(1)为文法符号E和T配以综合属性type,用来表示它们的类型。
类型值分别用int和real
来表示。
确定每个子表达式结果类型的属性文法如下:
产生式
iE1+T
iT
Ttnum.num
Ttnum
语义规则
{T.type:
=ifE1.type=intandT.type=intthenintelsereal{E.type:
=T.type}
T.type:
=real
T.type:
=int
(2)下面属性文法将表达式的后缀表示打印输出,其中lexeme属性表示单词的拼写。
产生式
EtE1+T
语义规则
ifE1.type=realandT.type=intthenbegin
E.type:
=real;
print(T.lexeme);
print('inttoreal');
end
elseifE1.type=intandT.type=realthenbegin
E.type:
=real;
print('inttoreal');
print(T.lexeme);
end
elsebegin
E.type:
=E1.type;
print(T.lexeme);
endprint('+');
Ett
Ttnum.num
Ttnum
E.type:
=T.type;print(T.lexeme);
T.type:
=real;T.lexeme:
=num1.lexeme||“.”||num2.lexeme
T.type:
=int;T.lexeme:
=num.lexeme;
例9将下列语句翻译为逆波兰表示(后缀式)、三元式和四元表示:
a:
=(b+c)*e+(b+c)/f
【解】解题思路
把中缀式转换为后缀式的简单方法:
按中缀式中各运算符的优先规则,从最先执行的部
分开始写,一层层套。
如adVa+b丰e,先把b+c写为bc+;然后把aw套上去,成为abc+w;再把a>d表示为ad>;然后把A套上去,成为abc+wad>A,依此类推。
四元式由4个部分组成:
算符op、第1和第2运算量arg1和arg2,以及运算结果result。
运算量和运算结果有时指用户自定义的变量,有时指编译程序引进的临时变量。
如果op是
一个算术或逻辑算符,则result总是一个新引进的临时变量,用于存放运算结果。
三元式只需3个域:
op、arg1和arg2。
与四元式相比,三元式避免了临时变量的填入,而是通过计算这个临时变量的语句的位置来引用这个临时变量。
我们很容易把一个算术表达
式或一个赋值句表示为四元式序列或三元式序列。
解答
逆波兰表示为:
bc+e*bc+f/+:
=
三元式序列为:
(1)(+
b,c)
⑵(*
(1),e)
⑶(+
b,c)
⑷(/
(3),f)
⑸(+
(2),(4))
(6)(:
=
a,(5))
四兀式序列为:
(1)(+
b,c,T1)
⑵(*
T1,e,T2)
⑶(+
b,c,T3)
⑷(/
T3,f,T4)
⑸(+
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,贝Ua>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产生布尔表达式三地址代码的语义规则
产生式
语义规则
iE1orE2
E1.true:
=E.true;
E1.false:
=newlable;
E2.true:
=E.true;
E2.false:
=E.false;
E.code:
=E1.code||gen(E1.false‘:
')||E2.code
iE1andE2
E1.true:
=newlable;
E1.false:
=E.false;
E2.true:
=E.true;
E2.false:
=E.false;
E.code:
=E1.code||gen(E1.true‘:
')||E2.code
inotE1
E1.treu:
=E.false;
E2.false:
=E.true;
E.code:
=E1.code
i(E1)
E1.true:
=E.true;
E1.false:
=E.false;
E.code:
=E1.code
iid1relopid2
E.code:
=gen('if'id1.placerelop.opid2.place‘goto'
E.true)||gen(‘goto'E.false)
itrue
E.code:
=gen(‘goto'E.true)
ifalse
E.code:
=gen(‘goto'E.false)
表2控制流语句的属性文法
产生式
语义规则
StifEthenS1
E.true:
=newlable;
E.false:
=S.next;
S1.next:
=S.next;
S.code:
=E.code||gen(E.true':
')||S1.code
StifEthenS1elseS2
E.true:
=newlable;
E.false:
=newlable;
51.next:
=S.next;
52.next:
=S.next;
S.code:
=E.code||gen(E.true':
')||
S1.code||gen('goto'S.next)||gen(E.false':
')||S2.code
StwhileEdoS1
S.begin:
=newlable;
E.true:
=newlable;
E.false:
=S.next;
S1.next:
=S.begin;
S.code:
=gen(S.begin‘:
')||E.code||
gen(E.true':
')||S1.code||gen(‘goto'S.begin)
解答
所求三地址代码为:
LO:
ifa>0gotoL2
gotoL1
L1:
ifb>0gotoL2gotoLnext
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语句翻译成三地址代码。
【解】解题思路
本题既要求构造属性文法,也要求构造相应的翻译模式。
因此,有必要回忆一下属性文
法和翻译模式的区别。
我们知道,属性文法(有时也称语法制导定义)可以看作是关于语言翻译的高级规范说明,其中隐去实现细节,使用户从明确说明翻译顺序的工作中解脱出来;而翻译模式(也称为翻译方案)是一种适合语法制导翻译的描述形式,它给出了使用语义规则进
行计算的次序,这样就可把某些实现细节表示出来。
IEI的代码
图1卅
屮间代冏结构
为了明确翻译目标,我们首先给出for语句的中间代码结构如图1所示。
根据C语言的for语句的语义和以上中间代码结构可以构造出属性文法。
为了构造属性文法相应的翻译模式,通常可采用两种方法:
一种方法是在原有产生式中
引入必要的标记非终结符;另一种方法是对文法进行分解和改造。
两种方法的目的都是为了
便于语法制导翻译。
翻译
把C语言的for语句翻译成三地址代码的属性文法如下:
产生式
语义动作
Stfor(E1;E2;E3)S1
E2.lable:
=newlable;
E3.lable:
=newlable;
E2.true:
=newlable;
E2.false:
=S.next;
S1.next:
=E3.lable;
S.code:
=E1.code||gen(E2.lable':
')||
E2.code||gen(E3.lable':
')||
E3.code||gen('goto'E2.lable)||
gen(E2.true':
')||S1.code||
gen(‘goto'E3.lable)
F面我们用两种方法构造相应上述属性文法的翻译模式。
方法一:
引入M1M2和N这3个标记非终结符。
M1用来记住E2的开始地址,M2用来记住M3
的开始地址。
N是用来产生E3后面的goto语句,从上面的中间代码结构来看,产生这个goto
语句时,转移地址应该是已知的了,但语句是在NR&归约时产生的,这时不能访问M1的
属性,因此这个转移的目标地址是回填。
所求的翻译模式如下:
Stfor(E1;M1E2;M2E3)NS1
{emit('goto'M2.next);
backpatch(E2.truelist,N.next);backpatch(S1.nextlist,M2.next);
backpatch(N.nextlist,M1.next);
S.nextlist:
=E2.falselist;}MTe{M.next:
=nextquad}NTe{N.nextlist:
=makelist(nextquad);
emit('goto_');
N.next:
=nextquad}方法二:
把产生式Stfor(E1;E2;E3)S1改写为:
F1tfor(E1;
F2tF1E2;
F3tF2E3)
StF3S1
这样写是因为,语法制导翻译过程中,在产生E2的代码之前要记下E2的代码地址;在产生E3的代码之前要记下E3的代码地址,并要对E2的“真”出口进行“回填”;而在产生E3的代码之后要生成一条goto语句。
所求翻译模式如下:
F1tfor(E1;{F1.quad:
=nextquad}
F2~F1E2;
F3~F2E3)
StF3S1
{F2.quad1:
=F1.quad;
F2.quad2:
=nextquad;
F2.truelist:
=E2.truelist;
F2.nextlist:
=E2.falselist;}
{emit('goto'F2.quad1);
backpatch(F2.truelist,nextquad);
F3.quad:
=F2.quad2;
F3.nextlist:
=F2.nextlist}
{emit('goto'F3.quad);
S.nextlist:
=F3.nextlist}
为L0):
例12将下列C程序的执行语句翻译成三地址代码(设S.next
if(i s=10*s else i=-j 【解】 ifi L1: t0=10*s s=t0 gotoL0 L2: t1=-j i=t1 L0: ...
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 试题