编译原理教程第四版答案.docx
《编译原理教程第四版答案.docx》由会员分享，可在线阅读，更多相关《编译原理教程第四版答案.docx（13页珍藏版）》请在冰点文库上搜索。
编译原理教程第四版答案
编译原理教程第四版答案
【篇一：
编译原理教程课后习题答案——第三章】
.1完成下列选择题：
（1）文法g：
s→xsx|y所识别的语言是
a.xyxb.（xyx）*
c.xnyxn（n≥0）d.x*yx*
a.最左推导和最右推导对应的语法树必定相同
b.最左推导和最右推导对应的语法树可能不同
c.最左推导和最右推导必定相同
d.可能存在两个不同的最左推导，但它们对应的语法树相同
（3）采用自上而下分析，必须。
a.消除左递a.必有ac归b.消除右递归
c.消除回溯d.提取公共左因子
（4）设a、b、c是文法的终结符，且满足优先关系ab和bc，则。
b.必有ca
c.必有bad.a～c都不一定成立
（5）在规范归约中，用
a.直接短语b.句柄
c.最左素短语d.素短语
a.归约b.移进
c.接受d.待约
a.lalr文法b.lr（0）文法
c.lr
（1）文法d.slr
（1）文法
（8）同心集合并有可能产生新的冲突。
a.归约b.“移进”/“移进”
c.“移进”/“归约”d.“归约”/“归约”
【解答】
（1）c
（2）a（3）c（4）d（5）b（6）b（7）d（8）d
3.2令文法g[n]为
g[n]:
n→d|nd
d→0|1|2|3|4|5|6|7|8|9
（1）g[n]的语言l（g[n]）是什么?
（2）给出句子0127、34和568的最左推导和最右推导。
【解答】
（1）g[n]的语言l（g[n]）是非负整数。
（2）最左推导：
nndnddnddddddd0ddd01dd012d0127
nnddd3d34
nndnddddd5dd56d568
最右推导：
nndn7nd7n27nd27n127d1270127
nndn4d434
nndn8nd8n68d68568
3.3已知文法g[s]为s→asb|sb|b，试证明文法g[s]为二义文法。
【解答】由文法g[s]：
s→asb|sb|b，对句子aabbbb可对应如图3-1所示的两棵语法树。
ss
asbsb
asbasb
sbasb
bb
图3-1句子aabbbb对应的两棵不同语法树
因此，文法g[s]为二义文法（对句子abbb也可画出两棵不同语法树）。
sassas
sas?
?
sas
?
?
?
?
（a）（b）
图3-2句子aa对应的两棵不同的语法树
由图3-2可知，文法g[s]为二义文法。
3.5按指定类型，给出语言的文法。
（1）l={aibj|j＞i≥0}的上下文无关文法；
（3）由相同个数a和b组成句子的无二义文法。
【解答】
（1）由l={aibj|j＞i≥0}知，所求该语言对应的上下文无关文法首先应有s→asb型产生式，以保证b的个数不少于a的个数；其次，还需有s→sb或s→b型的产生式，用以保证b的个数多于a的个数。
因此，所求上下文无关文法g[s]为
g[s]：
s→asb|sb|b
由图3-3可直接得到正规文法
g[s]：
s→aa|bba→as|bc|b
图3-3习题3.5的
（3）我们用一个非终结符a代表一个a（即有a→a），用一个非终结符b代表一个b（即有b→b）；为了保证a和b的个数相同，则在出现一个a时应相应地出现一个b，出现一个b时则相应出现一个a。
假定已推导出ba，如果下一步要推导出连续两个b时，则应有babbaa。
也即为了保证b和a的个数一致，应有a→baa；同理有b→abb。
此外，为了保证递归地推出所要求的ab串，应有s→abs和s→bas。
由此得到无二义文法g[s]为
a→baa|a
b→abb|b
3.6有文法g[s]:
s→aacb|bd
a→aab|c
b→bsca|b
（1）试求句型aaabcbbdcc和aacbbdcc的句柄；
（2）写出句子acabcbbdcc的最左推导过程。
【解答】
（1）分别画出对应句型aaabcbbdcc和aacbbdcc的语法树如图3-4的（a）、
s（b）所示。
saacb
aacbaabbsca
bscabdc图3-4习题3.6的语法树
bdcb（a）（b）（a）aaabcbbdcc;（b）aacbbdcc对树（a），直接短语有3个：
aab、b和c，而aab为最左直接短语（即为句柄）。
对树（b），直接短语有两个：
bd和c，而bd为最左直接短语。
能否不画出语法树，而直接由定义（即在句型中）寻找满足某个产生式的候选式这样一个最左子串（即句柄）呢？
例如，对句型aaabcbbdcc，我们可以由左至右扫描找到第一个子串aab，它恰好是满足a→aab右部的子串；与树（a）对照，aab的确是该句型的句柄。
是否这一方法始终正确呢？
我们继续检查句型aacbbdcc，由左至右找到第一个子串c，这是满足a→c右部的子串，但由树（b）可知，c不是该句型的句柄。
由此可知，画出对应句型的语法树然后寻找最左直接短语是确定句柄的好方法。
（2）句子acabcbbdcc的最左推导如下：
saacbaaabcbacabcbacabcbacabcbscaacabcbbdca
acabcbbdcaacabcbbdcc
3.7对于文法g[s]:
s→（l）|as|a
l→l,s|s
（1）画出句型（s,（a））的语法树；
（2）写出上述句型的所有短语、直接短语、句柄、素短语和最左素短语。
【解答】
（1）句型（s,（a））的语法树如图3-5所示。
s
（l）
l,s
s（l）图3-5句型（s,（a））的语法树s
a
（2）由图3-5可知：
短语：
s、a、（a）、s,（a）、（s,（a））；
直接短语：
a、s；
句柄：
s；
素短语：
素短语可由图3-5中相邻终结符之间的优先关系求得，即：
#?
（?
，?
（?
a?
）?
）?
#
因此，素短语为a。
3.8下述文法描述了c语言整数变量的声明语句：
g[d]:
d→tl
t→int|long|short
l→id|l,id
（1）改造上述文法，使其接受相同的输入序列，但文法是右递归的；
（2）分别用上述文法g[d]和改造后的文法g[d′]为输入序列inta,b,c构造分析树。
【解答】
（1）消除左递归后，文法g[d′]如下：
d→tld
t→int|long|shortdtll→idl
intal′
intl,c,bl′
l,b,cl′图3-6两种文法为inta,b,c构造的分析树
a?
（a）（b）（a）文法g（d）；（b）文法g′（d）
3.9考虑文法g[s]:
s→（t）|a+s|a
t→t,s|s
消除文法的左递归及提取公共左因子，然后对每个非终结符写出不带回溯的递归子程序。
【解答】消除文法g[s]的左递归：
s→（t）|a+s|a
t→st′
提取公共左因子：
s→（t）|as′
t→st′
改造后的文法已经是ll
（1）文法，不带回溯的递归子程序如下：
voidmatch（tokent）
{
if（lookahead==t）
lookahead=nexttoken;
elseerror（）;
}
voids（）
{
if（lookahead==′a′）
match（′a′）;
elseif（lookahead==′（′）
{
match（′（′）;
t（）;
voids′（）
{
if（lookahead==′+′）
{
match（′+′）;
s（）;
}
}
voidt（）
{
s（）;
t′（）;
}
voidt′（）
{
if（lookahead==′,′）
{
match（′,′）;
s（）;
t′（）;
}
}
3.10已知文法g[a]:
a→aabl|a
b→bb|d
（1）试给出与g[a]等价的ll
（1）文法g[a′]；
（2）构造g[a′]的ll
（1）分析表；
（3）给出输入串aadl#的分析过程。
来消除左递归。
由此，将产生式b→bb|d改造为
b→db′
其次，应通过提取公共左因子的方法来消除g[a]中的回溯，即将产生式a→aabl|a改造为
a→aa′
【篇二：
编译原理教程课后习题答案——第一章】
完成下列选择题：
（1）构造编译程序应掌握
a.源程序b.目标语言
c.编译方法d.以上三项都是
（2）编译程序绝大多数时间花在上。
a.出错处理b.词法分析
c.目标代码生成d.表格管理
（3）编译程序是对。
a.汇编程序的翻译b.高级语言程序的解释执行
c.机器语言的执行d.高级语言的翻译
【解答】
（1）d
（2）d（3）d
1.2计算机执行用高级语言编写的程序有哪些途径？
它们之间的主要区别是什么？
【解答】计算机执行用高级语言编写的程序主要有两种途径：
解释和编译。
在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释（翻译）成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。
这种方法是按源程序中语句的动态执行顺序逐句解释（翻译）执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。
在编译方式下，高级语言程序的执行是分两步进行的：
第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。
因此，编译对源程序的处理是先翻译，后执行。
从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。
这两种途径的主要区别在于：
解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。
1.3请画出编译程序的总框图。
如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？
【解答】编译程序总框图如图1-1所示。
作为一个编译程序的总设计师，首先要深刻理解被编译的源语言其语法及语义；其次，要充分掌握目标指令的功能及特点，如果目标语言是机器指令，还要搞清楚机器的硬件结构以及操作系统的功能；第三，对编译的方法及使用的软件工具也必须准确化。
总之，总设计师在设计编译程序时必须估量系统功能要求、硬件设备及软件工具等诸因素对编译程序构造的影响等。
程序
子程序或分程序
语句
表达式
数据引用
算符函数调用
【篇三：
编译原理课后答案】
下列正规式描述的语言
（a）0（0|1）*0
在字母表{0,1}上,以0开头和结尾的长度至少是2的01串
在字母表{0,1}上,所有的01串,包括空串在字母表{0,1}上,含有3个1的01串
（e）（00|11）*（（01|10）（00|11）*（01|10）（00|11）*）*
在字母表{0,1}上,含有偶数个0和偶数个1的01串
2.4为下列语言写正规定义c语言的注释，即以/*开始和以*/结束的任意字符串，但它的任何前缀（本身除外）不以*/结尾。
［解答］other→a|b|…other指除了*以外c语言中的其它字符
other1→a|b|…other1指除了*和/以外c语言中的其它字符comment→/*other*（***other1other*）****/
（f）由偶数个0和偶数个1构成的所有0和1的串。
［解答］由题目分析可知，一个符号串由0和1组成，则0和1的个数只能有四种情况：
x偶数个0和偶数个1（用状态0表示）；x偶数个0和奇数个1（用状态1表示）；x奇数个0和偶数个1（用状态2表示）；x奇数个0和奇数个1（用状态3表示）；所以，
x状态0（偶数个0和偶数个1）读入1，则0和1的数目变为：
偶数个0和奇数个1（状态1）
x状态0（偶数个0和偶数个1）读入0，则0和1的数目变为：
奇数个0和偶数个1（状态2）
x状态1（偶数个0和奇数个1）读入1，则0和1的数目变为：
偶数个0和偶数个1（状态0）
x状态1（偶数个0和奇数个1）读入0，则0和1的数目变为：
奇数个0和奇数个1（状态3）
x状态2（奇数个0和偶数个1）读入1，则0和1的数目变为：
奇数个0和奇数个1（状态3）
x状态2（奇数个0和偶数个1）读入0，则0和1的数目变为：
偶数个0和偶数个1（状态0）
x状态3（奇数个0和奇数个1）读入1，则0和1的数目变为：
奇数个0和偶数个1（状态2）
x状态3（奇数个0和奇数个1）读入0，则0
和1的数目变为：
偶数个0和奇数个1（状态1）
因为，所求为由偶数个0和偶数个1构成的所有0和1的串，故状态0既为初始状态又为终结状态，其状态转换图：
由此可以写出其正规文法为：
（1）s3=（00|11）s3+（01|10）s0+01+10
（2）解
（2）式得：
s3=（00|11）*（（01|10）s0+（01|10））代入
（1）式得：
s0=（00|11）s0+（01|10）（00|11）*（（01|10）s0+（01|10））+（00|11）=s0=（（00|11）+（01|10）（00|11）*（01|10））s0+（01|10）（00|11）*（01|10）+（00|11）=s0=（（00|11）|（01|10）（00|11）*（01|10））*（（00|11）+（01|10）（00|11）*（01|10））=s0=（（00|1
1）|（01|10）（00|11）*（01|10））+
［解答］此题目我们可以借鉴上题的结论来进行处理。
对于由偶数个0和奇数个1构成的所有0和1的串，我们分情况讨论：
（1）若符号串首字符为0，则剩余字符串必然是奇数个0和奇数个1，因此我们必须在上题偶数个0和偶数个1的符号串基础上再读入10（红色轨迹）或01（蓝色轨迹），又因为在0→1和1→3的过程中可以进行多次循环（红色虚线轨迹），同理0→2和2→3（蓝色虚线轨迹），所以还必须增加符号串（00|11）*，我们用s0表示偶数个0和偶数个1，用s表示偶数个0和奇数个1则其正规定义为：
s→0（00|11）*（01|10）s0s0→（（00|11）|（01|10）（00|11）*（01|10））*
（2）若符号串首字符为1，则剩余字符串必然是偶数个0和偶数个1，其正规定义为：
s→1s0
s0→（（00|11）|（01|10）（00|11）*（01|10））*综合
（1）和
（2）可得，偶数个0和奇数个1构成的所有0和1串其正规定义为：
s→0（00|11）*（01|10）s0|1s0s0→（（00|11）|（01|10）（00|11）*（01|10））*
ababbab:
s-4-0-1-5-6-7-8-4-0-1-5-6-7-6-7-8-4-0-1-5-6-7-8-f
2.12为下列正规式构造最简的dfa
（b）（a|b）*a（a|b）（a|b）
（1）根据算法2.4构造该正规式所对应的nfa，如图所示。
（2）根据算法2.2（子集法）将nfa转换成与之等价的dfa（确定化过程）初始状态
（3）根据算法2.3过将dfa最小化
第一次划分：
{s0,s1,s2,s3,s4}{s5,s6,s7,s8}{s0,s1,s2,s3,s4}a={s1,s3,s1,s5,s7}
第二次划分：
{s0,s1,s2}{s3,s4}{s5,s6,s7,s8}{s0,s1,s2}a={s1,s3,s1}
第三次划分：
{s0,s2}{s1}{s3,s4}{s5,s6,s7,s8}{s0,s2}a={s1}{s0,s2}b={s2}s0,s2不可区分，即等价。
{s5,s6,s7,s8}a={s5,s7,s3,s1}
第四次划分：
{s0,s2}{s1}{s3,s4}{s5,s6}{s7,s8}{s3,s4}a={s5,s7}
第五次划分：
{s0,s2}{s1}{s3}{s4}{s5,s6}{s7,s8}{s5,s6}a={s5,s7}
第六次划分：
{s0,s2}{s1}{s3}{s4}{s5}{s6}{s7,s8}{s7,s8}a={s3,s1}
第七次划分：
{s0,s2}{s1}{s3}{s4}{s5}{s6}{s7}{s8}集合不可再划分，
所以s0,s2
等价，选取s0
表示
{s0,s2}，其状态转换图，即题目所要求的最简dfa如下所示：
第三章
3.1
3.2
3.10
3.11
3.20
3.23
升级会员 