南邮《编译原理》练习题解答Word格式.docx
《南邮《编译原理》练习题解答Word格式.docx》由会员分享，可在线阅读，更多相关《南邮《编译原理》练习题解答Word格式.docx（63页珍藏版）》请在冰点文库上搜索。
aidtcAb
aidtcBcAb句型但不是句子；
（2）S
aidtcBcAb
aidtccAb
aidtccBb
aidtccb；
是句型也是句子；
（4）该文法的句子或句型的最后一个字符串一定是字符“b”；
第三次作业：
P3911、试分别描述下列文法所产生的语言（文法开始符号为S）：
（1）S∷＝0S|01
（2）S∷＝aaS|bc
（1）L（G）＝{0n1|n≥1}；
{解题思路：
将文法转换为正规表达式}
（2）L（G）＝{a2nbc|n≥0}。
P3912、试分别构造产生下列语言的文法：
（1）{abna|n=0，1，2，3……}
（3）{aban|n≥1}
（5）{anbmcp|n，m，p≥0}
（1）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，
P：
S∷＝aAa
A∷＝bA|ε
（3）G＝{VN，VT，P，S}，VN＝{S，A}，VT＝{a，b}，
S∷＝abA
A∷＝aA|a
（5）①G＝{VN，VT，P，S}，VN＝{S，A，B，C}，VT＝{a，b，c}，
S∷＝ABC
A∷＝aA|ε
B∷＝bB|ε
C∷＝cC|ε
②G＝{VN，VT，P，S}，VN＝{S}，VT＝{a，b，c}，
S∷＝aS|bS|cS|ε
P3915.设文法G规则为：
S：
：
=AB
B：
=a|Sb
A：
=Aa|bB
对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。
（2）baabaab（3）bBABb
解
（2）S
AB
AaSb
bBAB
abBa
a
句型baabaab的短语a,ba,baa,baab,baabaab，简单短语a，句柄a
S
（3）
AB
bB
Sb
短语bB,AB,ABb，bBABb
简单短语bB,AB，
句柄bB
第四次作业
P4124.下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？
1.S:
:
=aBB:
=cBB:
=bC:
=c
2.S:
=bCC:
=cC:
=ε
3.S:
=aAbaA:
=aBaA:
=aaAB:
=bA:
=a
4.S:
=aCdaC:
=BaC:
=b
5.S:
=ABA:
=aB:
=bCB:
6.S:
7.S:
=aAS:
=εA:
=aAA:
=aBA:
8.S:
=bAbA:
短语结构文法（0）4
上下文有关文法
（1）3
上下文无关文法
（2）568或者25678
正规文法（3）127或者1
P4229.用扩充的BNF表示以下文法规则：
1．Z:
=AB|AC|A
2．A:
=BC|BCD|AXZ|AXY
3．S:
=aABb|ab
4．A:
=Aab|ε
解:
1．Z:
=A（B|C|ε）:
=A[B|C]
2．A:
=BC（ε|D）|{X（Z|Y）}:
=BC[D]|{X（Z|Y）}
3．A:
=a（（AB|ε）b）:
=a[AB]b
4．A:
={ab|ε}:
={ab}
第五次作业：
P744.画出下列文法的状态图：
Z：
=Be
=Af
=e|Ae并使用该状态图检查下列句子是否该文法的合法句子：
f,eeff,eefe。
由状态图可知只有eefe是该文法的合法句子。
P745.设右线性文法G=（{S,A,B},{a,b},S,P），其中P组成如下：
=bAA：
=bBA：
=aAA：
=bB：
画出该文法的状态转换图。
P746.构造下述文法G[Z]的自动机，该自动机是确定的吗？
它相应的语言是什么？
Z：
=A0A：
=A0|Z1|0
解1：
将左线性文法转换为右线性文法，由于在规则中出现了识别符号出现在规则右部的情形，因此不能直接使用书上的左右线性文法对应规则，可以引入非终结符号B，将左线性文法变为Z：
=A0|B1|0B：
=A0，具体为：
A:
=Z1A:
=B1
A:
=A01
Z:
=A0B:
=A0
将所得的新左线性文法转换成右线性文法：
此时利用书上规则，其对应的右线性文法为：
=0A|0B|0Z：
=0AB：
=1A
解2：
先画出该文法状态转换图：
NFA=（{S，A，Z}，{0，1}，M，{S}，{Z}）
其中M：
M（S，0）={A}M（S，1）=ø
M（A，0）={A，Z}M（A，1）=ø
M（Z，0）=ø
M（Z，1）={A}
显然该文法的自动机是非确定的；
它相应的语言为：
{0，1}上所有满足以00开头以0结尾且每个1必有0直接跟在其后的字符串的集合；
那么如何构造其相应的有穷自动机呢？
先构造其转换系统：
根据其转换系统可得状态转换集、状态子集转换矩阵如下表所示：
I
I0
I1
S
01
{S’,S}
{A}
Ф
1Ф
{A,Z,Z’}
1
2Ф
2
21
则其相应的DFA为：
P748.设（NFA）M=（{A,B},{a,b},M,{A},{B}），其中M定义如下：
M（A,a）={A,B}M（A,b）={B}M（B,a）=ø
M（B,b）={A,B}
请构造相应确定有穷自动机（DFA）M’。
解：
构造一个如下的自动机（DFA）M’，（DFA）M’={K,{a,b},M’,S,Z}
K的元素是[A][B][A,B]
由于M（A,a）={A,B}，故有M’（[A],a）=[A,B]
同样M’（[A]，b）=[B]
M’（[B]，a）=ø
M’（[B]，b）=[A，B]
由于M（{A，B}，a）=M（A，a）UM（B，a）={A，B}Uø
={A，B}
故M’（[A，B]，a）=[A，B]
由于M（{A，B}，b）=M（A，b）UM（B，b）={B}U{A，B}={A，B}
故M’（[A，B]，b）=[A，B]
S=[A]，终态集Z={[A，B]，[B]}
重新定义：
令0=[A]1=[B]2=[A,B]，则DFA如下所示：
可以进一步化简，把M’的状态分成终态组{1，2}和非终态组{0}
由于{1，2}a={1，2}b={2}
{1，2}，不能再划分。
至此，整个划分含有两组{1，2}{0}
令状态1代表{1，2}，化简如图：
第六次作业：
P7411
（1）（0|11*0）*
先构造该正规式的转换系统：
由上述转换系统可得状态转换集K={S,1,2,3,4,Z}，状态子集转换矩阵如下表所示：
K
{S,1,Z}
{1,Z}
{2,3,4}
12
{3,4}
13
3
由状态子集转换矩阵可知，状态0和1是等价的，而状态2和3是等价的，因此，合并等价状态之后只剩下2个状态，也即是最少状态的DFA。
P7412.将图3.24非确定有穷自动机NFA确定化和最少化。
设（DFA）M={K,VT,M,S,Z}，其中，K={[0],[0,1],[1]}，VT={a,b}，M：
M（[1],a）=[0]M（[1],b）=ФM（[0,1],a）=[0,1]M（[0,1],b）=[1]
M（[0],a）=[0,1]M（[0],b）=[1]
S=[1]，Z={[0],[0,1]}
令[0,1]=2，则其相应的状态转换图为：
现在对该DFA进行化简，先把状态分为两组：
终态组{0,2}和非终态组{1}，易于发现{0,2}
不可以继续划分，因此化简后的状态转换图如下：
a
b
P7418.根据下面正规文法构造等价的正规表达式：
S:
=cC|a……①
A:
=cA|aB……②
B:
=aB|c……③
C:
=aS|aA|bB|cC|a……④
由③式可得B=aB+c→B=a*c
由②式可得A=cA+aB→A=c*aa*c
由①式可得S=cC+a
由④式可得C=aS+aA+bB+cC+a→C=c*（aS+aA+bB+a）→
C=c*（aS+ac*aa*c+ba*c+a）→S=cc*（aS+ac*aa*c+ba*c+a）+a=cc*aS+cc*（ac*aa*c+ba*c+a）+a=（cc*a）*（cc*（ac*aa*c+ba*c+a）+a）=（cc*a）*（cc*（ac*aa*c|ba*c|a）|a）另一种答案是S=c（ac|c）*（ac*aa*c|ba*c|aa|a）|a
第七次作业：
P1421.试分别消除下列文法的直接左递归（采用两种方法——重复法和改写法）
（1）G[E]:
E:
=T|EAT……①
T:
=F|TMF……②
F:
=（E）|i……③
=+|-……④
M:
=*|/……⑤
先采用“重复法”：
再采用“改写法”：
=T{AT}E:
=TE’
=F{MF}E’:
=ATE’|ε
=（E）|iT:
=FT’
=+|-T’:
=MFT’|ε
M:
=*|/F:
=（E）|i
=+|-
=*|/
P1422.试分别消除下列文法的间接左递归
（2）G[Z]:
Z:
=AZ|b……①
A:
=ZA|a……②
将②式代入①式可得，Z:
=ZAZ|aZ|b消除左递归后得到：
Z:
=（aZ|b）Z’
Z’:
=AZZ’|ε
=ZA|a
P1435.对下面的文法G[E]:
E:
=TE’
E’:
=+E|ε
T:
T’:
=T|ε
F:
=PF’
F’:
=*F’|ε
P∷＝（E）|a|b|∧
（1）计算这个文法的每个非终结符号的FIRST和FOLLOW；
（2）证明这个文法是LL
（1）文法；
（3）构造它的LL
（1）分析表并分析符号串a*b+b;
（1）构造FIRST集：
FIRST（E’）={+,ε}
FIRST（F’）={*,ε}
FIRST（E）=FIRST（T）=FIRST（F）=FIRST（P）={（，a，b，∧}
FIRST（T’）={（，a，b,ε，∧}
构造FOLLOW集：
规则一
＃∈FOLLOW（E）FOLLOW（E）={#}
规则二
）∈FOLLOW（E）FOLLOE（E）={），#}
FIRST（E’）-{ε}
FOLLOW（T）FOLLOW（T）={+}
FIRST（T’）-{ε}
FOLLOW（F）FOLLOW（F）={（，a，b，∧}
FIRST（F’）-{ε}
FOLLOW（P）FOLLOW（P）={*}
规则三
FOLLOW（E）
FOLLOW（E’）FOLLOW（E’）={#，）}
FOLLOW（T）FOLLOW（T）={＋，＃，）}
FOLLOW（T）
FOLLOW（T’）FOLLOW（T’）={＋，＃，）}
FOLLOW（F）FOLLOW（F）={（，），a，b，＋，＃，∧}
FOLLOW（F）
FOLLOW（F’）FOLLOW（F’）={（，），a，b，＋，＃，∧}
FOLLOW（P）FOLLOW（P）={（，），a，b，＋，＃，∧,*}
最后结果为：
FIRST（T’）={（，a，b,ε，∧）
FOLLOE（E）={）,＃}
FOLLOW（E’）={＃，）}
FOLLOW（T）={＋，＃，）}
FOLLOW（T’）={＋，＃，）}
FOLLOW（F）={（，），a，b，＋，＃，∧}
FOLLOW（F’）={（，），a，b，＋，＃，∧}
FOLLOW（P）={（，），a，b，＋，＃，∧,*}
（2）证明该文法是LL
（1）文法：
证明：
对于规则E’:
=+E|ε，T’:
=T|ε，F’:
=*F’|ε（仅有一边能推出空串）
有FIRST（+E）={+}∩FIRST（ε）=ø
，FIRST（T）={（,a,b,∧}∩FIRST（ε）=ø
FIRST（*F’）={*}∩FIRST（ε）=ø
，FIRST（+E）={+}∩FOLLOW（E’）={#,）}=ø
FIRST（T）={（,a,b,∧}∩FOLLOW（T’）={+,#,）}=ø
FIRST（*F’）={*}∩FOLLOW（F’）={（，），a，b，＋，＃，∧}=ø
所以该文法是LL
（1）文法。
（3）构造文法分析表
+
*
（
）
∧
#
E
E→TE’
E’
E’→+E
E’→ε
T
T→FT’
T’
T’→T
T’→ε
F
F→PF’
F’
F’→ε
F’→*F’
P
P→a
P→b
P→（E）
P→∧
下面分析符号串a*b+b
步骤分析栈余留输入串所用的产生式
1#Ea*b+b#E→TE’
2#E’Ta*b+b#T→FT’
3#E’T’Fa*b+b#F→PF’
4#E’T’F’Pa*b+b#P→a
5#E’T’F’aa*b+b#
6#E’T’F’*b+b#F’→*F’
7#E’T’F’**b+b#
8#E’T’F’b+b#F’→ε
9#E’T’b+b#T’→T
10#E’Tb+b#T→FT’
11#E’T’Fb+b#F→PF’
12#E’T’F’Pb+b#P→b
13#E’T’F’bb+b#
14#E’T’F’+b#F’→ε
15#E’T’+b#T’→ε
16#E’+b#E’→+E
17#E++b#
18#Eb#E→TE’
19#E’Tb#T→FT’
20#E’T’Fb#F→PF’
21#E’T’F’Pb#P→b
22#E’T’F’bb#
23#E’T’F’#F’→ε
24#E’T’#T’→ε
25#E’#E’→ε
26##成功
所以符号串a*b+b是该文法的句子；
P1446.对下列文法，构造相应的FIRST和FOLLOW：
（1）S∷＝aAd
A∷＝BC
B∷＝b|ε
C∷＝c|ε
（2）A∷＝BCc|gDB
B∷＝ε|bCDE
C∷＝DaB|ca
D∷＝ε|dD
E∷＝gAf|c
（1）
构造FIRST集
FIRST（S）={a}
FIRST（B）={b，ε}
FIRST（C）={c，ε}
FIRST（A）={b，c，ε}
构造FOLLOW集
＃∈FOLLOW（S）FOLLOW（S）={#}
d∈FOLLOW（A）FOLLOE（A）={d}
FIRST（C）-{ε}
FOLLOW（B）FOLLOW（B）={c}
FOLLOW（A）
FOLLOW（B）FOLLOW（B）={d，c}
FOLLOW（C）FOLLOW（C）={d}
FIRST（S）={a}
FOLLOW（S）={#}
FOLLOW（A）={d}
FOLLOW（B）={d，c}
FOLLOW（C）={d}
（2）
FIRST（A）={g},
FIRST（B）={b，ε},
FIRST（C）={c},
FIRST（D）={d，ε},
FIRST（E）={g，c}.
FIRST（A）={g，b，c},
FIRST（C）={a，c，d},
FIRST（A）={a，b，c，d，g}.
＃∈FOLLOW（A）FOLLOW（A）={#}
f∈FOLLOW（A）FOLLOE（A）={f，＃}
c∈FOLLOW（C）FOLLOE（C）={c}
a∈FOLLOW（D）FOLLOE（D）={a}
FIRST（Cc）-{ε}
FOLLOW（B）FOLLOW（B）={c，d，a}
FIRST（B）-{ε}
FOLLOW（D）FOLLOW（D）={b，a}
FIRST（DE）-{ε}
FOLLOW（C）FOLLOW（C）={d，g，c}
FIRST（E）
FOLLOW（D）FOLLOW（D）={b，c，a，g}
FOLLOW（B）FOLLOW（B）={a，c，d，f，#}
FOLLOW（D）FOLLOW（D）={a，b，c，f，g，＃}
FOLLOW（B）
FOLLOW（E）FOLLOW（E）={a，c，d，f，#}
FOLLOW（C）
FOLLOW（B）FOLLOW（B）={a，c，d，g，f，#}
FOLLOW（E）FOLLOW（E）={a，c，d，g，f，#}
FIRST（A）={a，b，c，d，g},
FIRST（E）={g，c},
FOLLOE（A）={f，＃}
FOLLOW（B）={a，c，d，g，f，#},
FOLLOW（C）={d，g，c},
FOLLOW（D）={a，b，c，f，g，＃},
FOLLOW（E）={a，c，d，g，f，#}.
P1449.设已给文法G[S]:
S∷＝SaB|bB
A∷＝Sa
B∷＝Ac
（1）将此文法改写为LL
（1）文法
（4）构造LL
（1）分析表
此题消除左递归之后，构造LL
（1）分析表存在“多重入口”问题，故采用以下方法：
（1）改写为LL
（1）文法：
S∷＝bB{aB}
（4）
FIRST（S）={b},
FIRST（A）={b},
FIRST（B）={b},
FOLLOE（S）={a，＃},
FOLLOW（A）={c},
FOLLOW（B）
升级会员 