编译原理第二版课后答案张素琴.docx
《编译原理第二版课后答案张素琴.docx》由会员分享，可在线阅读，更多相关《编译原理第二版课后答案张素琴.docx（17页珍藏版）》请在冰点文库上搜索。
编译原理第二版课后答案张素琴
编译原理第二版课后答案张素琴
【篇一：
清华大学编译原理第二版课后习答案】
ss=txt>第1章引论
第1题
解释下列术语：
（1）编译程序
（2）源程序
（3）目标程序
（4）编译程序的前端
（5）后端
（6）遍
答案：
（1）编译程序：
如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。
（2）源程序：
源语言编写的程序称为源程序。
（3）目标程序：
目标语言书写的程序称为目标程序。
（4）编译程序的前端：
它由这样一些阶段组成：
这些阶段的工作主要依赖于源语言而与目标机无关。
通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。
（5）后端：
指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。
（6）遍：
是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。
第2题
一个典型的编译程序通常由哪些部分组成？
各部分的主要功能是什么？
并画出编译程序的总体结构图。
答案：
一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。
其各部分的主要功能简述如下。
词法分析程序：
输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。
语法分析程序：
检查源程序中存在的形式语法错误，输出错误处理信息。
语义分析程序：
进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。
中间代码生成程序：
按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。
《编译原理》课后习题答案第一章
目标代码生成程序：
将优化后的中间代码程序转换成目标代码程序。
表格管理程序：
负责建立、填写和查找等一系列表格工作。
表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。
可以说整个编译过程就是造表、查表的工作过程。
需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。
错误处理程序：
处理和校正源程序中存在的词法、语法和语义错误。
当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。
注意：
如果问编译程序有哪些主要构成成分，只要回答六部分就可以。
如果搞不清楚，就回答八部分。
第3题
何谓翻译程序、编译程序和解释程序？
它们三者之间有何种关系？
答案：
翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。
编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。
《编译原理》课后习题答案第一章
是哪种方式，其加工结果都是源程序的执行结果。
目前很多解释程序采取上述两种方式的综合实现方案，即先把源程序翻译成较容易解释执行的某种中间代码程序，然后集中解释执行中间代码程序，最后得到运行结果。
广义上讲，编译程序和解释程序都属于翻译程序，但它们的翻译方式不同，解释程序是边翻译（解释）边执行，不产生目标代码，输出源程序的运行结果。
而编译程序只负责把源程序翻译成目标程序，输出与源程序等价的目标程序，而目标程序的执行任务由操作系统来完成，即只翻译不执行。
第4题
对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。
（1）else没有匹配的if
（2）数组下标越界
（3）使用的函数没有定义
（4）在数中出现非数字字符
答案：
（1）语法分析
（2）语义分析
（3）语法分析
（4）词法分析
第5题
编译程序大致有哪几种开发技术？
答案：
（1）自编译：
用某一高级语言书写其本身的编译程序。
（2）交叉编译：
a机器上的编译程序能产生b机器上的目标代码。
（3）自展：
首先确定一个非常简单的核心语言l0，用机器语言或汇编语言书写出它的编译程序t0，再把语言l0扩充到l1，此时l0?
l1,并用l0编写l1的编译程序t1，再把语言l1扩充为l2，有l1l2,并用l1编写l2的编译程序t2，?
?
，如此逐步扩展下去，好似滚雪球一样，直到我们所要求的编译程序。
?
（4）移植：
将a机器上的某高级语言的编译程序搬到b机器上运行。
《编译原理》课后习题答案第一章
第６题
计算机执行用高级语言编写的程序有哪些途径?
它们之间的主要区别是什么?
答案：
计算机执行用高级语言编写的程序主要途径有两种，即解释与编译。
像basic之类的语言，属于解释型的高级语言。
它们的特点是计算机并不事先对高级语
言进行全盘翻译，将其变为机器代码，而是每读入一条高级语句，就用解释器将其翻译为一条机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如此反复。
总而言之，是边翻译边执行。
像c，pascal之类的语言，属于编译型的高级语言。
它们的特点是计算机事先对高级语
言进行全盘翻译，将其全部变为机器代码，再统一执行，即先翻译，后执行。
从速度上看，编译型的高级语言比解释型的高级语言更快。
《编译原理》课后习题答案第二章
第2章pl/0编译程序的实现
第1题
pl/0语言允许过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的存储管理。
答案：
pl/0语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。
（数组code存放的只读目标程序，它在运行时不改变。
）运行时的数据区s是由解释程序定义的一维整型数组，解释执行时对数据空间s的管理遵循后进先出规则，当每个过程（包括主程序）被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。
应用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题。
第2题
若pl/0编译程序运行时的存储分配策略采用栈式动态分配，并用动态链和静态链的方
式分别解决递归调用和非局部变量的引用问题，试写出下列程序执行到赋值语句b∶=10时运行栈的布局示意图。
varx,y;
procedurep;
vara;
procedureq;
varb;
begin（q）
b∶=10;
end（q）;
procedures;
varc,d;
procedurer;
vare,f;
begin（r）
callq;
end（r）;
begin（s）
callr;
end（s）;
begin（p）
calls;
《编译原理》课后习题答案第二章
end（p）;
begin（main）
callp;
end（main）.
答案：
程序执行到赋值语句b∶=10时运行栈的布局示意图为：
第3题
写出题2中当程序编译到r的过程体时的名字表table的内容。
namekindlevel/valadrsize
答案：
题2中当程序编译到r的过程体时的名字表table的内容为：
namekindlevel/valadrsize
xvariable0dx
yvariable0dx+1
pprocedure0过程p的入口（待填）5
《编译原理》课后习题答案第二章
avariable1dx
qprocedure1过程q的入口4
sprocedure1过程s的入口（待填）5
cvariable2dx
dvariable2dx
rprocedure2过程r的入口5
evariable3dx
fvariable3dx+1
注意：
q和s是并列的过程，所以q定义的变量b被覆盖。
第4题
指出栈顶指针t，最新活动记录基地址指针b，动态链指针dl，静态链指针sl与返回地址ra的用途。
答案：
栈顶指针t，最新活动记录基地址指针b，动态链指针dl，静态链指针sl与返回地址
ra的用途说明如下：
t：
栈顶寄存器t指出了当前栈中最新分配的单元（t也是数组s的下标）。
b：
基址寄存器，指向每个过程被调用时，在数据区s中给它分配的数据段起始地址，也称基地址。
sl：
静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，用以引用非局部（包围它的过程）变量时，寻找该变量的地址。
dl：
动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放数据空间时，恢复调用该过程前运行栈的状态。
ra：
返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程执行结束后返回调用过程时的下一条指令继续执行。
在每个过程被调用时在栈顶分配3个联系单元，用以存放sl，dl，ra。
第5题
pl/0编译程序所产生的目标代码是一种假想栈式计算机的汇编语言，请说明该汇编语言中下列指令各自的功能和所完成的操作。
（１）int0a
（２）opr00
（３）calla
答案：
pl/0编译程序所产生的目标代码中有3条非常重要的特殊指令，这3条__________指令在code中
的位置和功能以及所完成的操作说明如下：
《编译原理》课后习题答案第二章
int0a
在过程目标程序的入口处，开辟a个单元的数据段。
a为局部变量的个数+3。
opr00
在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址寄存器b和栈顶寄存器t的值，并将返回地址送到指令地址寄存器p中，以使调用前的程序从断点开始继续执行。
calla
调用过程，完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器b中，目标程序的入口地址a的值送指令地址寄存器p中，使指令从a开始执行。
第6题
给出对pl/0语言作如下功能扩充时的语法图和ebnf的语法描述。
（1）扩充条件语句的功能使其为：
if〈条件〉then〈语句〉[else〈语句〉]
（2）扩充repeat语句为：
repeat〈语句〉{；〈语句〉}until〈条件〉
答案：
对pl/0语言作如下功能扩充时的语法图和ebnf的语法描述如下：
（1）扩充条件语句的语法图为：
ebnf的语法描述为：
〈条件语句〉:
:
=if〈条件〉then〈语句〉[else〈语句〉]
（2）扩充repeat语句的语法图为：
ebnf的语法描述为：
〈重复语句〉:
:
=repeat〈语句〉{；〈语句〉}until〈条件〉
【篇二：
编译原理复习题2（第二版张素琴吕映芝蒋维杜戴桂兰编著）】
|e+t|e-t
t?
f|t*f|t/ff?
（e）|i
1）2）
给出i+i*i的最左推导和最右推导；给出i-i-i的语法树。
∵e=e+t=e+t*f∴e+t*f是文法g[e]的一个句型∴此句型相对于e的短语有:
e+t*f；相对于t的短语有t*f,直接短语为：
t*f；。
句柄为：
t*f
2、设有文法g[s]:
（12分）
1）请给出句子（a,（a,a））的最左,最右推导2）给出（a,（a,a））的语法树
3、下面的文法生成的是以x和y为操作数、二元运算符+、*和-为运算符的前缀表达式：
e?
+ee|*ee|-ee|x|y
1）给出串+*-xyxy的最左推导和最右推导；2）给出+*-xyxy的语法树。
4、将下图中的自动机确定化并最小化。
5、将下图中的自动机确定化并最小化。
6、设有dfam=（k,∑,f,s,z）
其中：
k={0，1，2，3}∑={a,b}s=0z={3}f为：
f（0,a）=1f（1,b）=1f（0,b）=2
f（2,a）=1f（1,a）=3f（2,b）=3试画出其状态转换矩阵和状态转换图。
7、将下图中的自动机确定化。
8、考虑下面文法g1：
（18分）
s?
a|?
|（t）t?
t，s|s
1）消去g1的左递归；
2）经改写后的文法是否是ll
（1）的？
给出它的预测分析表（要求写出详细过程，应先
求出每个非终结符的first和follow集合）。
9、构造正规式1（0|1）101相应的自动机
*
10、考虑下面文法g1：
e?
e+t|tt?
t*f|ff?
i|（e）
3）消去g1的左递归；
4）经改写后的文法是否是ll
（1）的？
（要求写出详细过程，应先求出改写后的每个非
终结符的first和follow集合）。
11、对于文法g（s）：
s?
（l）|as|al?
l,s|s
1）画出句型（s,（a））的语法树。
2）写出上述句型的所有短语、直接短语、句柄和素短语。
12、对于文法g（s）：
s?
（l）|as|al?
l,s|s
1）画出句型（s,（a））的语法树。
2）写出上述句型的所有短语、直接短语、句柄和素短语。
13、对于文法g（e）：
e?
t|e+t
t?
f|t*ff?
（e）|i|j|k
1）画出句型i*j+k的语法树。
2）写出上述句型的所有短语、直接短语、句柄和素短语。
14、设文法g（s）：
s?
（a）|aa?
a+s|s
1）构造各非终结符的firstvt集合和lastvt集合。
2）构造优先关系表。
15、设文法g（s）：
s?
（a）|aa?
a+s|s
1）构造各非终结符的firstvt集合和lastvt集合。
2）构造优先关系表。
16、设文法g（s）：
s?
（a）|aa?
a+s|s
1）构造各非终结符的firstvt集合和lastvt集合。
2）构造优先关系表。
【篇三：
编译原理课后习题答案（清华大学_张素琴）复习例题】
、lr
（1）、lalr
（1）等。
但要求至少要按照作业题的范围复习。
）
一选择题
1．编译的各阶段工作都涉及。
[a]词法分析[b]表格管理[c]语法分析[d]语义分析
2．型文法也称为正规文法。
[a]0[b]1[c]2[d]3
3．文法不是ll
（1）的。
[a]递归[b]右递归[c]2型[d]含有公共左因子的
4．文法e→e+e|e*e|i的句子i*i+i*i有棵不同的语法树。
[a]1[b]3[c]5[d]7
5．文法s→aas|abc定义的语言是。
[a]{a2kbc|k0}
[c]{a2k-1bc|k0}[b]{akbc|k0}[d]{akakbc|k0}
6．若b为非终结符，则a→?
.b?
为。
[a]移进项目[b]归约项目[c]接受项目[d]待约项目
7．同心集合并可能会产生新的冲突。
[a]二义[b]移进/移进[c]移进/归约[d]归约/归约
8．代码优化时所依据的是。
[a]语法规则[b]词法规则
[c]等价变换规则[d]语义规则
9．表达式a-（-b）*c的逆波兰表示（@为单目减）为。
[a]a-b@c*[b]ab@c*-[c]ab@-[d]ab@c-*
10．过程的display表是用于存取过程的。
[a]非局部变量[b]嵌套层次[c]返回地址[d]入口地址
二填空题
1．词法分析阶段的任务式从左到右扫描字符流，从而逐个识别一个个的单词。
2．对于文法g[e]：
e→t|e+tt→f|t*ff→p^f|pp→（e）|i，句型t+t*f+i的句柄是。
3．最右推导的逆过程称为规范归约，也称为最
左归约。
4．符号表的每一项是由名字栏和两个栏目组成。
在目标代码生成阶段，符号表是的依据。
三判断题（认为正确的填“t”，错的填“f”）
【】1．同心集的合并有可能产生“归约/归约”冲突。
【】2．一个文法所有句子的集合构成该文法定义的语言。
【】3．非终结符可以有综合属性，但不能有继承属性。
【】4．逆波兰表示法表示表达式时无需使用括号。
【】5．一个有穷自动机有且只有一个终态。
【】6．若过程p第k次被调用，则p的display表中就有
k+1个元素。
四解答题
1．给定文法g和句型（t+f）*i+t,
g:
e→e+t|tt→t*f|ff→（e）|i
（1）画出句型的语法树；
（2）写出句型的全部短语、简单短语和句柄。
解：
（略）
2．设有文法g：
s→s+s|s*s|i|（s）。
（1）对于输入串i+i*i给出一个最左推导；
（2）该文法是否是二义性文法？
请证明你的结论。
解：
（1）i+i*i的最左推导：
s=s+s=i+s=i+s*s=i+i*s=i+i*i
（2）该文法是二义性的。
因为对于句子i+i*i可以画出两棵
语法树（语法树略）。
3．给出语言{ambmcn|m≥1,n≥0}的上下文无关文法（2型）。
解：
g:
s→ab|a
a→aab|ab
b→cb|c
4．给出语言{akbmcn|k,m,n≥1}的正规文法（3型）。
解：
g:
a→aa|ab
b→bb|bc
c→cc|c
5．将文法g改写成等价的正规文法（3型）。
g:
s→dab
a→aa|a
b→bb|b
解：
g:
s→da
a→aa|ab
b→bb|b
6．构造一文法产生任意长的a，b串，使得
|a|≤|b|≤2|a|
其中，“|a|”和“|b|”分别表示串中的字符a和b的个数。
解：
b的个数在a的个数和其2倍之间，串的结构形如asbs和
bsas，其中b为1或2个b。
故得文法
b→b|bb
7．设有字母表{a，b}上的正规式r=（ab|a）*。
（1）构造r的相应有限自动机；
解：
（2）构造r的相应确定有限自动机；
（3）构造r的相应最小确定有限自动机；
解：
对
（2）得到的dfa化简，合并状态0和2为状态2：
+
（4）构造与r等价的正规文法
解：
令状态1和2分别对应非终结符b和a
可化简为：
8．写出如图所示的自动机描述的语言的正规式
解：
abb*|abb*aa*b|aaa*b
9．写出在{a,b}上，不以a开头，但以aa结尾的字符串集合的正规式（并构造与之等价的最简dfa）。
解：
依题意，“不以a开头”，则必以b开头，又要“以aa
结尾”，
故正规式为：
b（a|b）*aa
（构造与之等价的最简dfa，此略）
10．写一个
ll
（1）文法g，使其语言是
l（g）={ambnc2n|m=0,n0}
并证明文法是ll
（1）。
解：
文法g（s）：
s?
as|e
e?
be’
e’?
ecc|cc
故文法为ll
（1）的
11．将文法g改写成等价的ll
（1）文法，并构造预测分析表。
g：
s→s*at|at|*at
t→+at|+a
（编写递归下降子程序）
解：
消除左递归后的文法g’:
s→ats’|*ats’
t→+at|+a
提取左公因子得文法g’’:
s→ats’|*ats’
t→+at’
select（s→ats’）={a}
select（s→*ats’）={*}
select（s’→*ats’）={*}
select（t→+at’）={+}
select（t’→t）=first（t）={+}
所以该文法是ll
（1）文法。
12．对文法g[s]:
s→asb|p
p→bpc|bqc
q→qa|a
（递归下降子程序，略）
升级会员 