蒋立源《编译原理》第3版桂电期末复习作业答案概论Word格式.docx
《蒋立源《编译原理》第3版桂电期末复习作业答案概论Word格式.docx》由会员分享，可在线阅读，更多相关《蒋立源《编译原理》第3版桂电期末复习作业答案概论Word格式.docx（33页珍藏版）》请在冰点文库上搜索。
G（S）=（{S,W,R},{0,1,#},{S→W#,W→0W0|1W1|#},S）
（5）任何不是以0打头的所有奇整数所组成的集合
G（S）=（{S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|e,I→J|2|4|6|8,Jà
1|3|5|7|9},S）
（6）所有偶数个0和偶数个1所组成的符号串集合
对应文法为S→0A|1B|e，A→0S|1CB→0C|1SC→1A|0B
7.解：
aacb是文法G[S]中的句子，相应语法树是：
最右推导：
S=>
aAcB=>
aAcb=>
aacb
最左推导：
aacB=>
（2）aabacbadcd不是文法G[S]中的句子
因为文法中的句子不可能以非终结符d结尾
（3）aacbccb不是文法G[S]中的句子
可知，aacbccb仅是文法G[S]的一个句型的一部分，而不是一个句子。
（4）aacabcbcccaacdca不是文法G[S]中的句子
因为终结符d后必然要跟终结符a，所以不可能出现…dc…这样的句子。
（5）aacabcbcccaacbca不是文法G[S]中的句子
由
（1）可知：
aacb可归约为S，由文法的产生式规则可知，终结符c后不可能跟非终结符S，所以不可能出现…caacb…这样的句子。
8.证明：
用归纳法于n，n=1时，结论显然成立。
设n=k时，对于α1α2...αkT*b,存在βi：
i=1,2,..,k，αiT*bi成立，现在设
α1α2...αkαk+1T*b，因文法是前后文无关的，所以α1α2...αk可推导出b的一个前缀b'
，αk+1可推导出b的一个后缀=b"
（不妨称为bk+1）。
由归纳假设，对于b'
，存在βi：
i=1,2,..,k，b'
=β1β2...βk,使得
αiT*bi成立，另外,我们有αk+1T*b"
（=bk+1）。
即n=k+1时亦成立。
证毕。
9.证明：
（1）用反证法。
假设α首符号为终结符时，β的首符号为非终结符。
即设：
α=aω；
β=Aω’且α=>
*β。
由题意可知：
α=aωT…TAω’=β，由于文法是CFG，终结符a不可能被替换空串或非终结符，因此假设有误。
得证；
（2）同
（1），假设：
β的首符号为非终结符时，α首符号为终结符。
β=Aω’且α=aωT…TAω’=β，与
（1）同理，得证。
10.证明：
因为存在句子：
abc，它对应有两个语法树（或最右推导）：
STABTAbcTabc
STDCTDcTabc
所以，本文法具有二义性。
11.解：
（1）STABTAaSbTAacbTbAacbTbbAacbTbbaacb
上面推导中，下划线部分为当前句型的句柄。
对应的语法树为：
全部的短语：
第一个a（a1）是句子bbaacb相对于非终结符A（A1）（产生式A?
a）的短语（直接短语）；
b1a1是句子bbaacb相对于非终结符A2的短语；
b2b1a1是句子bbaacb相对于非终结符A3的短语；
c是句子bbaacb相对于非终结符S1（产生式S?
c）的短语（直接短语）；
a2cb3是句子bbaacb相对于非终结符B的短语；
b2b1a1a2cb3是句子bbaacb相对于非终结符S2的短语；
注：
符号的下标是为了描述方便加上去的。
（2）句子（（（b）a（a））（b））的最右推导：
ST（AS）T（A（b））T（（SaA）（b））T（（Sa（a））（b））
T（（（b）a（a））（b））
相应的语法树是：
（3）解：
iii*i+↑对应的语法树略。
ETT=>
F=>
FP↑TFE↑TFET+↑TFEF+↑TFEP+↑TFEi+↑
TFTi+↑TFTF*i+↑TFTP*i+↑TFTi*i+↑TFFi*i+↑TFPi*i+↑
TFii*i+↑TPii*i+↑Tiii*i+↑
13.化简下列各个文法
（1）解：
S→bCACdA→cSA|cCCC→cS|c
（2）解：
S→aAB|fA|gA→e|dDAD→eAB→f
S→ac
第三章
7
（1）其对应的右线性文法是:
A→0D,B→0A,B→1C,C→1|1F,C→1|0A,F→0|0E|1A,D→0B|1C,E→1C|0B
（2）最短输入串011
（3）任意接受的四个串
011,0110,0011,000011
（4）任意以1打头的串.
11将右线性文法化为左线性文法的算法：
o
（1）对于G中每一个形如A→aB的产生式且A是开始符，将其变为B→a,否则若A不是开始符，B→Aa;
o
（2）对于G中每一个形如A→a的产生式,将其变为S→Aa
12
（1）
状态矩阵是：
记[S]=q0[B]=q1[AB]=q2[SA]=q3,最小化和确定化后如图
（2）记[S]=q0,[A]=q1,[BS]=q2最小化和确定化后的状态转换图如下
13
（1）将具有ε动作的NFA确定化后，其状态转换图如图：
记{S0,S1,S3}=q0{S1}=q1{S2S3}=q2{S3}=q3
（2）记{S}=q0{Z}=q1{UR}=q2{SX}=q3{YUR}=q4{XSU}=q5{YURZ}=q6{ZS}=q7
14
（1）从略
（2）化简后S0和S1作为一个状态，S5和S6作为一个状态。
状态转换图如图
22构造NFA
其余从略。
第四章
（1）S→（S）Z21|（）Z21|[S]Z31|[]Z31
A→（S）Z22|（）Z22|[S]Z32|[]Z32
B→（S）Z23|（）Z23|[S]Z33|[]Z33
Z11→ε|AZ11|BZ21
Z12→AZ12|BZ22Z13→AZ13|BZ23
Z21→Z11Z22→ε|Z12
Z23→Z13Z31→Z21
Z32→Z22Z33→ε|Z23
（2）S→bZ11|aZ21A→bZ12|aZ22
Z11→ε|AZ21Z12→AZ22Z21→SZ21Z22→ε|SZ22
（3）S→（T）Z11|aZ11|Z11S→（T）Z12|aZ12|Z12
Z11→ε|Z21Z12→Z22Z21→,SZ21Z22→ε|,SZ22
∙4.解：
∙
∙5.证：
因为是左递归文法，所以必存在左递归的非终结符A，及形如A→α|β的产生式,且αT*Ad.
则first（Ad）∩first（β）≠φ,从而
first（α）∩first（β）≠φ，即文法不满足LL
（1）文法条件。
得证。
∙6.证：
LL
（1）文法的分析句子过程的每一步，永远只有唯一的分析动作可进行。
现在，假设LL
（1）文法G是二义性文法，则存在句子α，它有两个不同的语法树。
即存在着句子α有两个不同的最左推导。
从而可知，用LL
（1）方法进行句子α的分析过程中的某步中，存在两种不同的产生式替换，且均能正确进行语法分析，即LL
（1）分析动作存在不确定性。
与LL
（1）性质矛盾。
所以，G不是LL
（1）文法。
∙7.解：
（1）D产生式两个候选式fD和f的first集交集不为空，所以不是LL
（1）的。
（2）此文法具有左递归性，据第5题结论，不是LL
（1）的。
∙12.解：
（1）
S
A
（
a
）
b
=
<
>
不是简单优先文法。
（2）
R
T
∧
是简单优先文法。
（3）
o首先消去无用产生式Z→E,Z→E+T
Z
#
i
I
化简后的文法是简单优先文法；
31.
（1）算符优先矩阵：
+
*
↑
（2）用Floyd方法将优先矩阵线性化得到得的优先函数为：
F
3
5
1
7
G
2
4
6
35解：
（1）识别全部活前缀的DFA如下：
（以表格的形式来表示，很容易可以转化为图的形式，本章中其余的题目也是采用这种形式表示。
状态
项目集
经过的符号
到达的状态
I0
S’→·
S→·
aSb
aSc
ab
I1
I2
S’→S·
S→a·
Sb
Sc
I3
I4
S→aS·
c
I5
I6
S→ab·
S→aSb·
S→aSc·
（2）识别全部活前缀的DFA如下：
cA
ccB
·
S→c·
cB
A→·
S→cA·
S→cc·
B
A→c·
B→·
I7
I8
A→a·
S→ccB·
B→c·
C
I9
I10
B→b·
B→cc·
I11
A→cA·
B→ccB·
所求的LR（0）项目规范族C={I0,I1,…,I11}
（3）
aSSb
aSSS
SSb
SSS
SS
S→aSS·
S→aSSb·
S→aSSS·
（4）
Ab
S→A·
S→Ab·
38解：
Sab
bR
（冲突项目）
S→S·
acc
S→b·
R→·
S→Sa·
S→bR·
r2
R→S·
R→a·
S→Sab·
项目I1,I5同时具有移进和归约项目，对于I5={R→S·
S→S·
ab},follow（R）={a},follow（R）∩{a}={a},所以SLR
（1）规则不能解决冲突，从而该文法不是SLR
（1）文法。
aSAB
BA
S’→S·
SAB
S→B·
aA
r5
AB
S→BA·
A→B·
r4
S→aSA·
A→aA·
r3
S→aSAB·
r1
不存在冲突项目，故该文法是LR（0）文法，也是SLR
（1）文法。
SLR
（1）分析表如下：
ACTION
GOTO
S2
S4
ACC
S7
8
R5
9
R2
10
R4
11
R3
R1
40解：
求LR
（1）项目集和状态转换表：
S#
A#
BA#
aB#,a,b
b#,a,b
B→a·
B#,a,b
#,a,b
A→BA·
B→aB·
相应的LR
（1）分析表为：
STATE
S5
用LR
（1）分析表对输入符号串abab的分析过程：
步骤
栈中符号
余留符号
分析动作
下一状态
abab#
04
#a
bab#
045
#ab
ab#
047
#aB
03
#B
034
#Ba
b#
0345
#Bab
0347
#BaB
033
#BB
0336
#BBA
036
#BA
12
01
#A
第五章
5.4解：
∙A-BC+*DE-^
∙ad*c+d/e+f*g+
∙ax+4<
=cd3*/\\/
∙de*c+b/\a\/f^
∙s0=;
i1=;
i100<
=BZssii*+=;
ii1+=;
BRS2’
5.5解：
∙a+b*c
∙a*（b-c）-（c+d）/e
∙有误
∙if（a<
b）x=（a-b）^c;
elseg=h;
5.8解：
∙（+,B,C,T1）
（*,A,T1,T2）
（+,T2,D,T3）
（=,T3,0,X）
2）如下所示：
∙当前句型（方框括起来部分为句柄）A/\（BV（CVD/\?
F））用产生式Expr→iden归约，得
（1）Expr.TC→（jnz,A,0,0）;
（2）Expr.FC→（j,0,0,0）;
∙当前句型Expr/\（BV（CVD/\?
F））用产生式Expr^→Expr’/\’归约，得
（1）（jnz,A,0,3）;
（2）Expr^.FC→（j,0,0,0）;
∙当前句型Expr^（BV（CVD/\?
（1）（jnz,A,0,0）;
（3）Expr.TC→（jnz,B,0,0）;
（4）Expr.FC→（j,0,0,0）;
∙当前句型Expr^（ExprV（CVD/\?
F））用产生式Exprv→Expr'
V'
归约，得
（3）Exprv.TC→（jnz,A,0,0）;
（4）（j,0,0,5）;
∙当前句型Expr^（Exprv（CVD/\?
（5）Expr.TC→（jnz,C,0,0）;
（6）Expr.FC→（j,0,0,0）;
∙当前句型Expr^（Exprv（ExprVD/\?
F））,用产生式Exprv→Expr’V’归约，得
（5）Exprv.TC→（jnz,C,0,0）;
（6）（j,0,0,7）;
升级会员 