编译原理教程课后习题答案——第四章
- 格式:docx
- 大小:39.33 KB
- 文档页数:7
第四章语义分析和中间代码生成
4.1完成下列选择题:
(1) 四元式之间的联系是通过 _实现的。
a. 指示器b•临时变量
c.符号表
d.程序变量
(2) 间接三元式表示法的优点为_____ 。
a. 采用间接码表,便于优化处理
b. 节省存储空间,不便于表的修改
c. 便于优化处理,节省存储空间
d. 节省存储空间,不便于优化处理
(3) ________________________________________ 表达式(n A V B) A (C V D)的逆波兰表示为 _________________________________________________ 。
a. n AB VA CD V
b. A n B V CD VA
c. AB V n CD VA
d. A n B VA CD V
(4) 有一语法制导翻译如下所示:
S T bAb {print 〃T }
A T (
B {print 〃2〃}
A T a {print 〃3〃}
B T Aa) {print 〃4〃}
若输入序列为b(((aa)a)a)b,且采用自下而上的分析方法,则输出序列为_________ 。
a.32224441
b.34242421
c.12424243
d.34442212
【解答】
(1) b ⑵a ⑶b ⑷b
4.2何谓语法制导翻译”?试给出用语法制导翻译生成中间代码的要点,并用一简例予以说明。
【解答】语法制导翻译(SDTS)直观上说就是为每个产生式配上一个翻译子程序
(称语义动作或语义子程序),并且在语法分析的同时执行这些子程序。也即在语法分析过程中,当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时,此产生
式相应的语义子程序进入工作,完成既定的翻译任务。
用语法制导翻译(SDTS)生成中间代码的要点如下:
(1) 按语法成分的实际处理顺序生成,即按语义要求生成中间代码。
(2) 注意地址返填问题。
(3) 不要遗漏必要的处理,如无条件跳转等。
例如下面的程序段:
if (i>0) a=i+e-b*d; else a=0;
在生成中间代码时,条件卜0”为假的转移地址无法确定,而要等到处理else”时方可确定,这时就存在一个地址返填问题。此外,按语义要求,当处理完(i>0)后的语句(即i>0”为
真时执行的语句)时,则应转出当前的if语句,也即此时应加入一条无条件跳转指令,并且这个转移地址也需要待处理完else之后的语句后方可获得,就是说同样存在着地址返填问
题。对于赋值语句a=i+e-b*d,其处理顺序(也即生成中间代码顺序)是先生成i+e的代码,再生成b*d
的中间代码,最后才产生丁运算的中间代码,这种顺序不能颠倒。
4.3 令S.val为文法G[S]生成的二进制数的值,例如对输入串101.101,贝U S.val=
5.625。按照语法制导翻译方法的思想,给出计算S.val的相应的语义规则,G(S)如下:
G[S]: S T L.L|L
L T LB|B
B t 0|1
【解答】产生式计算S.val的文法G' [S]及语义动作如下:语义
动作
G ' [S]: S'T S {print(S.val)}
S T L1 L2 {S.val:=L1.val + L2.val/2L2」e ngth}
S t L { S.val:=L.val }
L t L1B {L.val:=L1.val*2 + B.val
L.length:=L1.length +1}
L t B {L.val:=B.val
L.length:=2}
B t1 {B.val:=1}
B t0 {B.val:=0}
4.4 下面的文法生成变量的类型说明:
D t id L
L t,id L|:T
T t integer|real 试构造一个翻译方案,仅使用综合属性,把每个标识符的类型填入符号表中
(对所用到的过程,仅说明功能即可,不必具体写出)。
【解答】此题只需要对说明语句进行语义分析而不需要产生代码,但要求把每个标识符的类型填入符号表中。对D、L、T,为其设置综合属性type,而过程enter(name,type)用来把
名字name填入到符号表中,并且给出此名字的类型type。翻译方案如下:
D t id L
{enter (, L.type);}
L t,id L(1)
{enter (, L(1).type);
L.type=L(1).type;}
L t:T
{L.type=T.type;}
T t integer
{T.type=integer;}
T t real
{T.type=real;}
4.5 写出翻译过程调用语句的语义子程序。在所生成的四元式序列中,要求在转子指令之前的参数四元式par 按反序出现(与实现参数的顺序相反)。此时,在翻译过程调用语句时,是否需要语义变量(队列)queue?
【解答】为使过程调用语句的语义子程序产生的参数四元式par按反序方式出现,过程调
用语句的文法为
S t call i(arglist) arglist t E arglist t arglist(1),E
按照该文法,语法制导翻译程序不需要语义变量队列queue,但需要一个语义变量
栈STACK,用来实现按反序记录每个实在参数的地址。翻译过程调用语句的产生式及语义子程序如下:
(1) arglist T E {建立一个arglist.STACK 栈,它仅包含一项 E.place}
(2) arglist T arglist(1) , E {将 E.place 压入arglist(1). STACK 栈,arglist. STACK=arglist⑴.STACK}
(3) S T call i (arglist) {while arglist.STACK 丰 null do
begin
将arglist.STACK栈顶项弹出并送入p单元之中;
emit (par,_ ,_ ,p);
en d;
emit (call,_ ,_ , entry (i));}
4.6设某语言的while语句的语法形式为
S T while E do S(1)
其语义解释如图4-1所示。
(1) 写出适合语法制导翻译的产生式;
(2) 写出每个产生式对应的语义动作。
图4-1习题4.6的语句结构图
【解答】本题的语义解释图已经给出了翻译后的中间代码结构。在语法制导翻译过程中,
当扫描到while时,应记住E的代码地址;当扫描到do时,应对E的真出口”进行回填,使之转到S(1)代码的入口处;当扫描到S(1)时,除了应将E的入口地址传给S(1).chain之外,还要形成一个转向E入口处的无条件转移的四元式,并且将E.fc继续传下去。因此,应把S
T while E do S(1)改写为如下的三个产生式:
W T while
A T W E do
S T A S(1)
每个产生式对应的语义子程序如下:
W T while
{ W.quad=nxq;}
A T W E do