编译原理习题解答参考
1.计算机执行用高级语言编写的程序的途径有哪些？它们之间主要区别是什么？
答：计算机执行用高级语言编写的程序途径有两种：解释方式和编译方式。
解释方式下直接对源程序进行解释执行，并得到计算结果，特点是计算机并不事先对高级语言进行全盘翻译将其全部变为机器代码，而是每读入一条语句，就用解释器将其翻译为机器代码，予以执行，然后再读入下一条高级语句，翻译为机器代码，再执行，如些反复，即边翻译边执行；编译方式下对源程序的执行需要经过翻译阶段和运行阶段才能得到计算结果，其特点是计算机事先对高级语言进行全盘翻译将其全部变为机器代码，再统一执行，即先翻译后执行。
简单来说解释方式不生成目标代码，编译方式生成目标代码。
2.名字与标识符的区别是什么？
答：在程序设计语言中，凡是以字母开头的有限个字母数字的序列都是标识符。
当给予一个标识符确切的含义后，该标识符就叫做一个名字。
标识符是一个没有意义的字符序列，而名字有确切的含义，一个名字代表一个存储单元，该单存放该名字的值。
此外，名字还有属性（如类型和作用域等）。
如objectint, 作为标识符，它没有任何含义，但作为名字，它可能表示变量名、函数名等。
3.许多编译程序在真正编译之前都要进行预处理操作，请问预处理的目的是什么？预处理主要做哪些工作？
答：在源程序中有时存在多个连续的空格、回车、换行及注释等编辑性字符，它们不是程序的必要组成部分，它们的意义只是改善程序的易读性和易理解性。
为了降低编译程序的处理负担，许多编译程序在编译之前通过预处理工作将这些部分删除。
预处理的主要工作是对源程序进行格式方面的规范化处理，如去掉注释、将回车换行变成空格、将多个空格替换为一个空格等。
P35 4，6，7，8，9，11（1，2）
4．答：256，8
6．（1）答：所产生的语言是：所有正整数集，且可以以0打头；
0127，34，568的推导略。
7．答：S→ABD|AD|D
A→2|4|6|8|D
B→0|A|B0|BA
D→1|3|5|7|9
8．答：略。
9．答：文法对于句子iiieii存在两棵不同的语法树，所以该文法是二义性文法。
11．（1）答：S→AB|A S→AB
A→aAb|ab A→aAb|ab
B→Bc|c B→Bc|c|ε
（2）答：S→AB|B
A→aA|a
B→bBc|bc
1.化简文法G[S]：
S→Be
B →Ce|Af
A →Ae|e
C →Cf
D →f
答：S →Be
B →Af A →Ae|e
2.给出描述语言L(G)={a2nbn|n ≥1}的2型文法。
答：语言中语句的特点是a 的个数是b 的个数的2倍，且a 全部在句子的前部分，b 全部在句子的后部分，2型文法为：S →aab|aaSb
3.构造一个文法，使其描述的语言是不能被5整除的偶整数集合。
S →（+|-）AB|B
A →0|1|2|3|4|5|6|7|8|9|AA
B →2|4|6|8
如果不以0打头，则文法描述如下： S →（+|-）（AD|D ） A →AB|C B →0|C|BB
C →1|2|3|4|5|6|7|8|9
D →2|4|6||8 P64 7（1），8（123）12 7．答：1|（0|1）*101 1)NFA 如下：
3）DFA 自己画 8．（1）（
0|1）*01 （2）（0|1|…… |9）*(0|5) (3)（00|11）*（10|01） 0
下面用分割法将其最小化：
首先得到两个子集：非终态K1={A，C}和终态K2={B}，由于状态A和状态C输入a后分别到达状态B和A，故状态A和状态C不等价，K1不能再分割，所以该DFA已经是最小化的DFA了。
（b）答：观察原图已经是DFA了，最小化如下：
首先得到两个子集：非终态和终态：{2，3，4，5}和{0，1}
{0，1}a={1}∈{0,1}
{0,1}b={2,4}∈{2,3,4,5}
所以{0，1}是不可分割的
因为{2，3，4，5}a={1，3，0，5}
又因为{2，4}a={0，1}∈{0,1}
{3，5}a={3，5}
所以该状态集划分为两个状态集{2，4}和{3，5}
{2，4}b={3，5}∈{3，5}
{3，5}b={2，4}∈{2，4}
所以状态{2，4}和{3，5}不可分割，最终状态集划分三个状态集：
{0，1} {2，4} {3，5}，得到最小化的DFA如下：
b
P81 2
3、文法G[A]如下：
4、已知文法G[S]如下：
A→BaC|CbB S →aABbcd|ε
B →Ac|c A →ASd| ε
C →Bb|b B →SAh|eC| ε
消除其左递归 C →Sf|Cg| ε
D →aBD| ε
求每一非终结符的FIRST 合和FOLLOW集合，
该文法是LL（1）文法吗？为什么？
2 解答：1) FIRST(E)={(,a,b,^}
FIRST(E′)={+, ε}
FIRST(T)= {(,a,b,^}
FIRST(T′)={ (,a,b,^,ε}
FIRST(F)= {(,a,b,^}
FIRST(F′)={ *,ε}
FIRST(P) {(,a,b,^}
FOLLOW(E)={),#}
FOLLOW(E′)={ ),#}
FOLLOW(T)={ ),+,#}
FOLLOW(T′)={ ),+,#}
FOLLOW(F)={ ),+,#, (,a,b,^}
FOLLOW(F′)={ ),+,#, (,a,b,^}
FOLLOW(P)={ ),+,#, (,a,b,^}
2) 由上知，文法的所有首符集两两不相交。
FIRST（E′）与FOLLOW（E′）=Φ
FIRST（T′）与FOLLOW（T′）=Φ
FIRST（F′）与FOLLOW（F′）=Φ
所以，该文法是LL（1）文法。
3）分析表和递归下降分析程序自己完成。
3解答：利用消除左递归的算法，将非终结符排序为：U1=A，U2=B，U3=C，执行算法得：U1代入U2得：B→BaCc|CbBc|c,消除B的左递归，
B→C bBc B′|c B′
B′→aCc B′|ε
U2代入U3得：C→CbBcB′b|cB′|b
C→c B′bC′|b C′
C′→bBc B′b C′|ε
所以，方法消除左递归后的结果为：
A→BaC|CbB
B→C bBc B′|c B′
B′→aCc B′|ε
C→c B′bC′|b C′
C′→bBc B′b C′|ε
4解答：首先将文法化简得到如下文法：
S →aABbcd|ε
A →ASd| ε
B →SAh|eC| ε
C →Sf|Cg| ε
非终结符的FIRST集合如下：
FIRST（S）={a, ε}
FIRST(A)={a,d, ε}
FIRST(B)={a,d,e,h, ε}
FIRST(C)={a,f,g, ε}
非终结符的FOLLOW集合如下：
FOLLOW(S)={#,a,d,h,f}
FOLLOW(A)={b,a,d,h,e}
FOLLOW(B)={b}
FOLLOW(C)={b,g}
该文法不是LL（1）文法，因为FIRST（C →Sf）∩FIRST（C →Cg）≠Φ
FIRST(A) ∩FOLLOW(A) ≠Φ
作业：P133 1,3,5
1．解答：
E=>E+T=>E+T*F
短语：T*F，E+T*F
直接短语：T*F
句柄：T*F
3．解答：
FIRSTVT（S）={a ^ (}
FIRSTVT（T）={, a ^ (}
LASTVT（S）={, a ^ (}
LASTVT（T）={, a ^ (}
1)=
S→(T)有（=）
2）>
T, 则有LASTVT（T）> ，
T), 则有LASTVT（T）> )
3) <
(T，则有（<FIRSTVT(T)
后面的答案略。
5．解答：
4、文法G[S]如下,是LR（1）文法但不是LALR（1）文法，对吗？为什么？（武大）
S →aAa|aBb|bAb|bBa
A →c
B →c
解答：识别扩展后文法活前缀的DFA如图所示：
由于不存在移进---归约冲突和归约---归约冲突，所以文法是LALR（1）文法。
若将同心集I6和I9合并，则会出现归约—归约冲突，所以文法不是LALR（1）文法。
原题说法不正确。
5、已知文法G[S]如下，请构造该文法的算符优先关系矩阵，并判断是否为算符优先文法？（清华）
S →iBtS|iBtAeS|a
A →iBtAeS|a
B →b
解答：求该非终结符的FIRSTVT集合和LASTVT集合FIRSTVT（S）={i,a}
FIRSTVT（A）={ i,a }
FIRSTVT（B）={b}
LASTVT（S）={t,e,a}
LASTVT（A）={e,a}
LASTVT（B）={b}
根据算符优先关系的定义得算符优先关系如下：
i=t,t=e
i<FIRSTVT(B)
t<FIRSTVT(S)
t<FIRSTVT(A)
e<FIRSTVT(S)
LASTVT(B)>t
LASTVT(A)>e
#<FIRSTVT(S)
法为算符优先文法。