编译原理习题解答.docx
《编译原理习题解答.docx》由会员分享，可在线阅读，更多相关《编译原理习题解答.docx（51页珍藏版）》请在冰点文库上搜索。
编译原理习题解答
第二章：
习题2-4Table表
varx,y;
procedurep;
vara;
procedureq;
varb;
begin
b:
=10;
end;
procedures;
varc,d;
procedurer;
vare,f;
begin
callq;
end;
begin
callr;
end;
begin
calls;
end;
begin
callp;
end
根据：
Page289，变量table:
array[0..txmax]ofrecord结构体以及block函数得到下表，而表中各部分的含义，见教材Page18,Page19
Name
Kink
Val/Level
Adr
Size
x
variable
0
3
0
y
variable
0
4
0
p
procedur
0
1
0
a
variable
1
3
0
q
procedur
1
3
4
s
procedur
1
7
0
c
variable
2
3
0
d
variable
2
4
0
r
procedur
2
0
0
第三章文法和语言
5.写一文法，使其语言是偶正整数的集合
要求：
（1）允许0打头
（2）不允许0打头
解：
（1）G[S]=（{S,P,D,N},{0,1,2,…,9},P,S）
P:
SPD|D
P->NP|N
D0|2|4|6|8
N->0|1|2|3|4|5|6|7|8|9
（2）G[S]=（{S,P,R,D,N,Q},{0,1,2,…,9},P,S）
P:
SPD|P0|D
P->NR|N
R->QR|Q
D2|4|6|8
N->1|2|3|4|5|6|7|8|9
Q->0|1|2|3|4|5|6|7|8|9
6.已知文法G：
<表达式>:
:
=<项>|<表达式>+<项>|<表达式>-<项>
<项>:
:
=<因子>|<项>*<因子>|<项>/<因子>
<因子>:
:
=（<表达式>）|i。
试给出下述表达式的推导及语法树。
（1）i;
（2）（i）（3）i*i;
（4）i*i+i;（5）i+（i+i）;（6）i+i*i。
解：
（1）v=<表达式>=><项>=><因子>=>i=w
（2）v=<表达式>=><项>=><因子>=>（<表达式>）=>（<项>）=>（<因子>）=>（i）=w
（3）v=<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i=w
（4）v=<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>
=><因子>*<因子>+<因子>=>i*i+i=w
（5）v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+（<表达式>）
=>i+（<表达式>+<项>）=>i+（<项>+<项>）=>i+（<因子>+<因子>）=>i+（i+i）=w
（6）v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>
=>i+<项>*<因子>=>i+<因子>*<因子>=>i+i*i=w
语法树见下图:
7.为句子i+i*i构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。
（6）i+i*i
<表达式>:
:
=i|（<表达式>）|<表达式><运算符><表达式>
<运算符>:
:
=+|-|*|/
解：
为句子i+i*i构造的两棵语法树如下：
i
所以，该文法是二义的。
8.习题1中的文法G[S]是二义的吗？
为什么？
答：
是二义的。
因为对于句子abc可以有两种不同的生成树，即：
S=>Ac=>abc和S=>aB=>abc
11.令文法G[E]为：
ET|E+T|E-T
TF|T*F|T/F
F（E）|i
证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
解：
可为E+T*F构造一棵语法树（见下图），所以它是句型。
T*F
从语法树中容易看出，E+T*F的短语有：
T*F是句型E+T*F的相对于T的短语，也是相对于规则TT*F的直接短语。
E+T*F是句型E+T*F的相对于E的短语。
句型E+T*F的句柄（最左直接短语）是T*F。
12.下述文法G[E]生成的语言是什么？
给出该文法的一个句子，该句子至少含五个终结符，构造该句子的语法树。
证明：
是G[]的句型，并指出该句型的所有短语、直接短语和句柄。
|
|
a|b|c
+|-
*|/
解：
（1）计算文法G[E]的语言：
由于L（T）={（a|b|c）（（a|b|c）（*|/））n|n>=0}
所以L（E）={L（T）（L（T）（+|-））n|n>=0}
（2）该文法的一个句子是aab*+,它的语法树是：
+
（3）证明：
是G[]的句型，并指出该句型的所有短语、直接短语和句柄。
由于下面的语法树可以生成，所以它是G[]的句型。
由于=>,且=>,所以是句型相对于的短语，也是相对于规则的直接短语。
由于=>且=>,所以是句型相对于的短语。
显然，句型的句柄是。
14.给出生成下述语言的上下文无关文法：
（1）{anbnambm|n,m>=0}
（2）{1n0m1m0n|n,m>=0}
（3）{WaWt|W属于{0|a}*,W表示Wt的逆}
解：
（1）所求文法为G[S]=（{S,A},{a,b},P,S）,其中P为：
SAA
AaAb|ε
（2）所求文法为G[S]=（{S,A},{0,1},P,S）,其中P为：
S1S0|A
A0A1|ε
（3）W属于{0|a}*是指W可以的取值为{ε,0,a,00,a0,aa0,00aa,a0a0,…}
如果W=aa0a00,则Wt=00a0aa。
所求文法为G[S]=（{S,P,Q},{0,a},P,S）,其中P为：
S0S0|aSa|a
15.语言{WaW}和{anbmcndm}是上下文无关的吗？
能看出它们反映程序设计语言的什么特性吗？
答：
生成语言{WaW}的文法非常简单，如
G[S]:
SWaW
WaW|bW|ε
可见G[S]是上下文无关的。
生成语言{anbmcndm}的文法非常复杂，用上下文无关文法不可能办到，只能用上下文有关文法。
这是因为要在ancn的中间插入bm而同时要在其后面插入dm。
即a,c相关联，b,d相关联。
这说明对语言的限定越多（特别是语言中的符号前后关联越多），生成它的文法越复杂，甚至于很难找到一个上下文法无关文法。
16．给出生成下述语言的三型文法：
（1）{an|n>=0}
（2）{anbm|n,m>=1}
（3）{anbmck|n,m,k>=0}
解：
（1）生成的3型文法是：
G[S]：
SaS|ε
（2）生成的2型文法是：
G[S]:
SAB
AaA|a
BbB|b
生成的3型文法是：
G[S]：
SaP
PaP|bD
DbD|ε
（3）生成的2型文法是：
G[S]:
SABC
AaA|ε
BbB|ε
C->cC|ε
生成的3型方法是：
G[S]：
AaA|bB|cC|ε
BbB|cC|ε
CcC|ε
第四章词法分析
1．构造下列正规式相应的DFA：
（1）1（0|1）*101
（2）1（1010*|1（010）*1）*0
（3）a（（a|b）*|ab*a）*b
（4）b（（ab）*|bb）*ab
解：
（1）1（0|1）*101对应的NFA为
0
下表由子集法将NFA转换为DFA：
I
I0=ε-closure（MoveTo（I,0））
I1=ε-closure（MoveTo（I,1））
A[0]
B[1]
B[1]
B[1]
C[1,2]
C[1,2]
D[1,3]
C[1,2]
D[1,3]
B[1]
E[1,4]
E[1,4]
B[1]
B[1]
1
（2）1（1010*|1（010）*1）*0对应的NFA为
1
下表由子集法将NFA转换为DFA：
I
I0=ε-closure（MoveTo（I,0））
I1=ε-closure（MoveTo（I,1））
A[0]
B[1,6]
B[1,6]
C[10]
D[2,5,7]
C[10]
D[2,5,7]
E[3,8]
B[1,6]
E[3,8]
F[1,4,6,9]
F[1,4,6,9]
G[1,2,5,6,9,10]
D[2,5,7]
G[1,2,5,6,9,10]
H[1,3,6,9,10]
I[1,2,5,6,7]
H[1,3,6,9,10]
J[1,6,9,10]
K[2,4,5,7]
I[1,2,5,6,7]
L[3,8,10]
I[1,2,5,6,7]
J[1,6,9,10]
J[1,6,9,10]
D[2,5,7]
K[2,4,5,7]
M[2,3,5,8]
B[1,6]
L[3,8,10]
F[1,4,6,9]
M[2,3,5,8]
N[3]
F[1,4,6,9]
N[3]
O[4]
O[4]
P[2,5]
P[2,5]
N[3]
B[1,6]
1
（3）a（（a|b）*|ab*a）*b（略）
（4）b（（ab）*|bb）*ab（略）
2．已知NFA=（{x,y,z},{0,1},M,{x},{z}）其中：
M（x,0）={z},M（y,0）={x,y},M（z,0）={x,z},M（x,1）={x},M（y,1）=φ,M（z,1）={y},构造相应的DFA。
0
解：
根据题意有NFA图如下
下表由子集法将NFA转换为DFA：
I
I0=ε-closure（MoveTo（I,0））
I1=ε-closure（MoveTo（I,1））
A[x]
B[z]
A[x]
B[z]
C[x,z]
D[y]
C[x,z]
C[x,z]
E[x,y]
D[y]
E[x,y]
E[x,y]
F[x,y,z]
A[x]
F[x,y,z]
F[x,y,z]
E[x,y]
0
1
1
0
0
B
C
E
F
0
0
D
A
1
1
0
1
下面将该DFA最小化：
（1）首先将它的状态集分成两个子集：
P1={A,D,E},P2={B,C,F}
（2）区分P2:
由于F（F,1）=F（C,1）=E,F（F,0）=F并且F（C,0）=C,所以F，C等价。
由于F（B,0）=F（C,0）=C,F（B,1）=D,F（C,1）=E,而D，E不等价（见下步），从而B与C，F可以区分。
有P21={C,F},P22={B}。
（3）区分P1:
由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。
（4）由于F（A,0）=B,F（E,0）=F,而B，F不等价，所以A，E可以区分。
（5）综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。
所以最小化的DFA如下：
1
1
0
1
0
F
0
B
E
1
0
D
A
0
3.将图4.16确定化：
1
图4.16
解：
下表由子集法将NFA转换为DFA：
I
I0=ε-closure（MoveTo（I,0））
I1=ε-closure（MoveTo（I,1））
A[S]
B[Q,V]
C[Q,U]
B[Q,V]
D[V,Z]
C[Q,U]
C[Q,U]
E[V]
F[Q,U,Z]
D[V,Z]
G[Z]
G[Z]
E[V]
G[Z]
F[Q,U,Z]
D[V,Z]
F[Q,U,Z]
G[Z]
G[Z]
G[Z]
0，1
4.把图4.17的（a）和（b）分别确定化和最小化：
b
a
（a）（b）
解：
（a）:
下表由子集法将NFA转换为DFA：
I
Ia=ε-closure（MoveTo（I,a））
Ib=ε-closure（MoveTo（I,b））
A[0]
B[0,1]
C[1]
B[0,1]
B[0,1]
C[1]
C[1]
A[0]
可得图（a1），由于F（A,b）=F（B,b）=C,并且F（A,a）=F（B,a）=B,所以A,B等价，可将DFA最小化，即：
删除B，将原来引向B的引线引向与其等价的状态A，有图（a2）。
（DFA的最小化，也可看作将上表中的B全部替换为A，然后删除B所在的行。
）
a
a
（a1）确定化的DFA（a2）最小化的DFA
（b）:
该图已经是DFA。
下面将该DFA最小化：
（6）首先将它的状态集分成两个子集：
P1={0},P2={1,2,3,4,5}
（7）区分P2：
由于F（4,a）=0属于终态集，而其他状态输入a后都是非终态集，所以区分P2如下：
P21={4},P22={1,2,3,5}。
（8）区分P22:
由于F（1,b）=F（5,b）=4属于P21,而F（2,b）与F（3,b）不等于4,即不属于P21，所以区分P22如下：
P221={1,5},P222={2,3}。
（9）区分P221:
由于F（1,b）=F（5,b）=4,即F（1,a）=1,F（5,a）=5,所以1,5等价。
（10）区分P222:
由于F（2,a）=1属于P221，而F（3,a）=3属于P222,所以2，3可区分。
P222区分为P2221{2}，P2222{3}。
（11）
b
结论：
该DFA的状态集可分为：
P={{0},{1,5},{2},{3},{4}},其中1,5等价。
删去状态5，将原来引向5的引线引向与其等价的状态1，有图（b1）。
（b1）最小化的DFA
5．构造一个DFA，它接收Σ={0，1}上所有满足如下条件的字符串：
每个1都有0直接跟在右边。
然后再构造该语言的正则文法。
解：
根据题意，DFA所对应的正规式应为：
（0|（10））*。
所以，接收该串的NFA如下：
ε
0
1
2
1
0
0
下表由子集法将NFA转换为DFA：
I
I0=ε-closure（MoveTo（I,0））
I1=ε-closure（MoveTo（I,1））
A[0]
B[0,2]
C[1]
B[0,2]
B[0,2]
C[1]
C[1]
B[0,2]
1
1
0
0
0
B
C
A
显然，A，B等价，所以将上述DFA最小化后有：
0
C
1
A
0
对应的正规文法为：
G[A]：
A1C|0A|ε
C0A
6．设无符号数的正规式为θ：
θ=dd*|dd*.dd*|.dd*|dd*e（s|ε）dd*|e（s|ε）dd*|.dd*e（s|ε）dd*|dd*.dd*e（s|ε）dd*
化简θ,画出θ的DFA，其中d={0,1,2,…9},s={+,-}
解：
把原正规式的每2，3项，4，5项，6，7项分别合并后化简有：
θ=dd*|d*.dd*|d*e（s|ε）dd*|d*.dd*e（s|ε）dd*
=dd*|d*.dd*|（d*|d*.dd*）e（s|ε）dd*
=（ε|d*.|（d*|d*.dd*）e（s|ε））dd*
=（ε|d*.|d*（ε|.dd*）e（s|ε））dd*
下面构造化简后的θ对应的NFA：
ε
下表由子集法将NFA转换为DFA：
I
Id=ε-closure（MoveTo（I,d））
Ie=ε-closure（MoveTo（I,e））
Is=ε-closure（MoveTo（I,s））
I.=ε-closure（MoveTo（I,.））
A[0,1,4,6]
B[1,7]
C[5,6]
D[2,6]
B[1,7]
B[1,7]
D[2,6]
C[5,6]
E[7]
F[6]
D[2,6]
G[3,4,7]
E[7]
E[7]
F[6]
E[7]
G[3,4,7]
G[3,4,7]
C[5,6]
d
7．给文法G[S]：
SaA|bQ
AaA|bB|b
BbD|aQ
QaQ|bD|b
DbB|aA
EaB|bF
FbD|aE|b
构造相应的最小的DFA。
解：
由于从S出发任何输入串都不能到达状态E和F，所以，状态E，F为多余的状态，不予考虑。
这样，可以写出文法G[S]对应的NFA：
a
下表由子集法将NFA转换为DFA：
I
Ia=ε-closure（MoveTo（I,a））
Ib=ε-closure（MoveTo（I,b））
1[S]
2[A]
3[Q]
2[A]
2[A]
4[B,Z]
3[Q]
3[Q]
5[D,Z]
4[B,Z]
3[Q]
6[D]
5[D,Z]
2[A]
7[B]
6[D]
2[A]
7[B]
7[B]
3[Q]
6[D]
由上表可知：
（1）因为4，5是DFA的终态，其他是非终态，可将状态集分成两个子集：
P1={1，2，3，6，7}，P2={4，5}
（2）在P1中因为2,3输入b后是终态，而1，6，7输入b后是非终态，所以P1可区分为：
P11={1，6，7}，P12={2，3}
（3）在P11中由于1输入b后为3，6输入b后为7，而3，7分属P11和P12，所以1与6不等价，同理，1与7不等价。
所以P11可区分为：
P111={1}，P112={6，7}
（4）查看P112={6，7}，由于输入a后为2，3，所以6，7是否等价由2，3是否等价决定。
（5）查看P12={2，3}，由于输入b后为4，5，所以2，3是否等价由4，5是否等价决定。
（6）查看P2={4，5}，显然4，5是否等价由2，3与6，7是否同时等价决定。
由于有（4）即6，7是否等价由2，3是否等价决定，所以，4，5是否等价由2，3是否等价决定。
由于有（5）即2，3是否等价由4，5是否等价决定，所以有4，5等价，2，3等价,进而6，7也等价。
（7）删除上表中的第3，5，7行，并将剩余行中的3，5，7分别改为对应的等价状态为2，4，6有下表：
I
Ia
Ib
1[S]
2[A]
2[A]
2[A]
2[A]
4[B,Z]
4[B,Z]
2[A]
6[D]
6[D]
2[A]
6[D]
这样可得最小化的DFA如下：
a
4
1
b
2
a
a
a
b
b
6
b
8．给出下述文法所对应的正规式：
S0A|1B
A1S|1
B0S|0
解：
把后两个产生式代入第一个产生式有：
S=01|01S
S=10|10S
有:
S=01S|10S|01|10=（01|10）S|（01|10）=（01|10）*（01|10）
即:
（01|10）*（01|10）为所求的正规式。
9．将图4.18的DFA最小化，并用正规式描述它所识别的语言：
b
图4.18
解：
（1）因为6，7是DFA的终态，其他是非终态，可将状态集分成两个子集：
P1={1，2，3，4，5}，P2={6，7}。
（2）由于F（6,b）=F（7,b）=6,而6，7又没有其他输入，所以6，7等价。
（3）由于F（3,c）=F（4,c）=3,F（3,d）=F（4,d）=5,F（3,b）=6,F（4,b）=7,而6，7等价，所以3,4等价。
（4）由于F（1,b）=F（2,b）=2,F（1,a）=3,F（2,a）=4,而3，4等价，所以1,2等价。
（5）由于状态5没有输入字符b,所以与1，2，3，4都不等价。
（6）综上所述，上图DFA的状态可最细分解为：
P={{1，2}，{3，4}，{5}，{6，7}}。
a
该DFA用正规式表示为：
b*a（c|da）*bb*
10．构造下述文法G[S]的自动机：
SA0
AA0|S1|0
该自动机是确定的吗？
若不确定，则对它确定化。
该自动机相应的语言是什么？
解：
由于该文法的产生式SA0，AA0|S1中没有字符集VT的输入，所以不是确定的自动机。
要将其他确定化，必须先用代入法得到它对应的正规式。
把SA0代入产生式AS1有：
A=A0|A01|0=A（0|01）|0=0（0|01）*。
代入SA0有该文法的正规式：
0（0|01）*0，所以，改写该文法为确定的自动机为：
1
由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化：
下表由子集法将NFA转换为DFA：
I
I0=ε-closure（MoveTo（I,0））
Ib=ε-closure（MoveTo（I,1））
A[W]
B[X]
B[X]
C[X,Y,Z]
C[X,Y,Z]
C[X,Y,Z]
B[X]
1
0
0
C
B
A
0
由上表可知DFA为：
第五章自顶向下语法分析方法
1．对文法G[S]
Sa|∧|（T）
TT,S|S
（1）给出（a,（a,a））和（（（a,a）,∧,（a））,a）的最左推导。
（2）对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。
（3）经改写后的文法是否是LL
（1）的？
给出它的预测分析表。
（4）给出输入串（a,a）#的分析过程，并说明该串是否为G的句子。
解：
（1）（a,（a,a））的最左推导为S（T）（T,S）（S,S）（a,（T））（a,（T,S））（a,（S,a））（a,（a,a））
（（（a,a）,∧,（a））,a）的最左推导为
S（T）（T,S）（S,a）（（T）,a）（（T,S）,a）（（T,S,S）,a）（（S,∧,（T））,a）（（（T）,∧,（S））,a）
（（（T,S）,
升级会员 