编译原理清华大学第2版课后习题答案.docx
《编译原理清华大学第2版课后习题答案.docx》由会员分享，可在线阅读，更多相关《编译原理清华大学第2版课后习题答案.docx（74页珍藏版）》请在冰点文库上搜索。
编译原理清华大学第2版课后习题答案
第三章
N=>D=>{0,1,2,3,4,5,6,7,8,9}
N=>ND=>NDD
L={a|a（0|1|3..|9）n且n>=1}
（0|1|3..|9）n且n>=1
{ab,}
anbnn>=1
第6题.
（1）<表达式>=><项>=><因子>=>i
（2）<表达式>=><项>=><因子>=>（<表达式>）=>（<项>）
=>（<因子>）=>（i）
（3）<表达式>=><项>=><项>*<因子>=><因子>*<因子>=i*i
（4）<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>
=><因子>*<因子>+<项>=><因子>*<因子>+<因子>=i*i+i
（5）<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=i+<项>
=>i+<因子>=>i+（<表达式>）=>i+（<表达式>+<项>）
=>i+（<因子>+<因子>）
=>i+（i+i）
（6）<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>
=>i+<项>*<因子>=>i+<因子>*<因子>=i+i*i
第7题
第9题
语法树
推导:
S=>SS*=>SS+S*=>aa+a*
11.推导:
E=>E+T=>E+T*F
语法树:
短语:
T*FE+T*F
直接短语:
T*F
句柄:
T*F
12．
短语：
直接短语：
句柄：
13.
（1）最左推导：
S=>ABS=>aBS=>aSBBS=>aBBS
=>abBS=>abbS=>abbAa=>abbaa
最右推导：
S=>ABS=>ABAa=>ABaa=>ASBBaa
=>ASBbaa=>ASbbaa=>Abbaa=>a1b1b2a2a3
（2）文法：
SABS
SAa
Sε
Aa
Bb
（3）短语：
a1,b1,b2,a2,,bb,aa,abbaa,
直接短语：
a1,b1,b2,a2,,
句柄：
a1
14
（1）
SAB
AaAb|ε
BaBb|ε
（2）
S1S0
SA
A0A1|ε
第四章
1.1.构造下列正规式相应的DFA
（1）1（0|1）*101
NFA
（2）1（1010*|1（010）*1）*0
NFA
（3）NFA
（4）NFA
2.解：
构造DFA矩阵表示
0
1
{X}0
{z}
{x}
{Z}*
{X,z}
{y}
{X,z}*
{X,z}
{X,y}
{y}
{X,y}
{X,y}
{X,y,z}
{x}
{X,y,z}*
{X,y,z}
{X,y}
其中0表示初态，*表示终态
用0，1，2，3，4，5分别代替{X}{Z}{X,z}{y}{X,y}{X,y,z}
得DFA状态图为：
3．解：
构造DFA矩阵表示
构造DFA的矩阵表示
0
1
{S}0
{V,Q}
{Q,U}
{V,Q}
{Z,V}
{Q,U}
{Q,U}
{V}
{Q,U,Z}
{Z,V}*
{Z}
{Z}
{V}
{Z}
{Q,U,Z}*
{V,Z}
{Q,U,Z}
{Z}
{Z}
{Z}
其中0表示初态，*表示终态
替换后的矩阵
0
1
00
1
2
1
3
2
2
4
5
3*
6
6
4
6
5*
3
5
6
6
6
构造DFA状态转换图（略）
4．
（1）解
构造状态转换矩阵：
a
b
{0}0*
{0,1}
{1}
{0,1}*
{0,1}
{1}
{1}
{0}
转换为
a
b
0*
1
2
1*
1
2
2
0
{2，3}{0，1}
{2，3}a={0,3}
{2},{3},{0,1}
{0,1}a={1,1}{0,1}b={2,2}
（2）解：
首先把M的状态分为两组：
终态组{0}，和非终态组{1，2，3，4,5}此时
G=（{0},{1,2,3,4,5}）
{1,2,3,4,5}a={1,3,0,5}
{1,2,3,4,5}b={4,3,2,5}
由于{4}a={0}{1,2,3,5}a={1,3,5}
因此应将{1,2,3,4,5}划分为{4},{1,2,3,5}
G=（{0}{4}{1,2,3,5}）
{1,2,3,5}a={1,3,5}
{1,2,3,5}b={4,3,2}
因为{1,5}b={4}{23}b={2,3}
所以应将{1,2,3,5}划分为{1,5}{2,3}
G=（{0}{1,5}{2,3}{4}）
{1,5}a={1,5}{1,5}b={4}所以{1,5}不用再划分
{2,3}a={1,3}{2,3}b={3,2}
因为{2}a={1}{3}a={3}所以{2,3}应划分为{2}{3}
所以化简后为G＝（{0},{2},{3},{4},{1,5}）
7.去除多余产生式后，构造NFA如下
确定化，构造DFA矩阵
a
b
S
A
Q
A
A
B,Z
B,Z
Q
D
Q
Q
D,Z
D
A
B
D,Z
A
D
B
Q
D
变换为
a
b
00
1
3
1
1
2
2*
3
4
3
3
5
4
1
6
5*
1
4
6
3
4
化简：
G={（0,1,3,4,6）,（2,5）}
{0,1,3,4,6}a={1,3}
{0,1,3,4,6}b={2,3,4,5,6}
所以将{0,1,3,4,6}划分为{0,4,6}{1,3}
G={（0,4,6）,（1,3）,（2,5）}
{0,4,6}b={3,6,4}所以划分为{0},{4,6}
G={（0）,（4,6）,（1,3）,（2,5）}
不能再划分，分别用0，4，1，2代表各状态，构造DFA状态转换图如下；
8．代入得
S=0（1S|1）|1（0S|0）
=01（S|ε）|10（S|ε）
=（01|10）（S|ε）
=（01|10）S|（01|10）
=（01|10）*（01|10）
构造NFA
由NFA可得正规式为（01|10）*（01|10）=（01|10）+
9.状态转换函数不是全函数,增加死状态8,
G={（1,2,3,4,5,8）,（6,7）}
（1,2,3,4,5,8）a=（3,4,8）（3,4）应分出
（1,2,3,4,5,8）b=（2,6,7,8）
（1,2,3,4,5,8）c=（3,8）
（1,2,3,4,5,8）d=（3,8）
所以应将（1,2,3,4,5,8）分为（1,2,5,8）,（3,4）
G={（1,2,5,8）,（3,4）,（6,7）}
（1,2,5,8）a=（3,4,8）8应分出
（1,2,5,8）b=（2,8）
（1,2,5,8）c=（8）
（1,2,5,8）d=（8）
G={（1,2,5）,（8）,（3,4）,（6,7）}
（1,2,5）a=（3,4,8）5应分出
G={（1,2）,（3,4）,5,（6,7）,（8）}
去掉死状态8,
最终结果为（1,2）（3,4）5,（6,7）以1,3,5,6代替,最简DFA为
正规式:
b*a（da|c）*bb*
第五章
1.
S->a|^|（T）
T->T,S|S
（a,（a,a））
S=>（T）=>（T,S）=>（S,S）=>（a,S）=>（a,（T））=>（a,（T,S））=>（a,（S,S））=>（a,（a,a））
S=>（T）=>（T,S）=>（S,S）=>（（T）,S）=>（（T,S）,S）=>（（T,S,S）,S）=>（（S,S,S）,S）
=>（（（T）,S,S）,S）=>（（（T,S）,S,S）,S）=>（（（S,S）,S,S）,S）=>（（（a,S）,S,S）,S）
=>（（（a,a）,S,S）,S）=>（（（a,a）,^,S）,S）=>（（（a,a）,^,（T））,S）
=>（（（a,a）,^,（S））,S）=>（（（a,a）,^,（a））,S）=>（（（a,a）,^,（a））,a）
S->a|^|（T）
T->T,S
T->S
消除直接左递归：
S->a|^|（T）
T->ST’
T’->,ST’|ξ
SELECT（S->a）={a}
SELECT（S->^）={^}
SELECT（S->（T））={（}
SELECT（T->ST’）={a,^,（}
SELECT（T’->,ST’）={,}
SELECT（T’->ξ）=FOLLOW（T’）=FOLLOW（T）={）}
构造预测分析表
a
^
（
）
#
S
->a
->^
->（T）
T
->ST’
->ST’
->ST’
T’
->ξ
->,ST’
分析符号串（a,a）#
分析栈剩余输入串所用产生式
#S（a,a）#S->（T）
#）T（（a,a）#（匹配
#）Ta,a）#T->ST’
#）T’Sa,a）#S->a
#）T’aa,a）#a匹配
#）T’，a）#T’->,ST’
#）T’S,,a）#,匹配
#）T’Sa）#S->a
#）T’aa）#a匹配
#）T’）#T’->ξ
#））#）匹配
##接受
2.
E->TE’E’->+EE’->ξT->FT’T’->TT’->ξF->PF’F’->*F’F’->ξ
P->（E）P->aP->bP->∧
非终结符名
是否＝>ε
FIRST集
FOLLOW集
E
否
{（，a，b，^}
{#，）}
E’
是
{+,ε}
{#，）}
T
否
{（，a，b，^}
{＋，#，）}
T’
是
{ε,（，a，b，^}
{＋，#，）}
F
否
{（，a，b，^}
{（，a，b，^，＋，#，）}
F’
是
{*,ε}
{（，a，b，^，＋，#，）}
P
否
{（，a，b，^}
{*，（，a，b，^，#，）}
SELECT（E－>TE’）=FIRST（TE’）=FIRST（T）={（，a，b，^）
SELECT（E’－>+E）={+}
SELECT（E’－>ε）=FOLLOW（E’）={#，）}
SELECT（T－>FT’）=FIRST（F）={（，a，b，^}
SELECT（T’—>T）=FIRST（T）={（，a，b，^）
SELECT（T’－>ε）=FOLLOW（T’）={＋，#，）}
SELECT（F－>PF’）=FIRST（F）={（，a，b，^}
SELECT（F’－>*F’）={*}
SELECT（F’－>ε）=FOLLOW（F’）={（，a，b，^，＋，#，）}
3.S->MHS->aH->LsoH->ξK->dMLK->ξL->eHfM->KM->bLM
FIRST（S）=FIRST（MH）=FIRST（M）∪FIRST（H）∪{ξ}∪{a}={a,d,b,e,ξ}
FIRST（H）=FIRST（L）∪{ξ}={e,ξ}
FIRST（K）={d,ξ}
FIRST（M）=FIRST（K）∪{b}={d,b,ξ}
FOLLOW（S）={#,o}
FOLLOW（H）=FOLLOW（S）∪{f}={f,#,o}
FOLLOW（K）=FOLLOW（M）={e,#,o}
FOLLOW（L）={FIRST（S）–{ξ}}∪{o}∪FOLLOW（K）
∪{FIRST（M）–{ξ}}∪FOLLOW（M）
={a,d,b,e,#,o}
FOLLOW（M）={FIRST（H）–{ξ}}∪FOLLOW（S）
∪{FIRST（L）–{ξ}}={e,#,o}
SELECT（S->MH）=（FIRST（MH）–{ξ}）∪FOLLOW（S）
=（FIRST（M）∪FIRST（H）–{ξ}）∪FOLLOW（S）
={d,b,e,#,o}
SELECT（S->a）={a}
SELECT（H->LSo）=FIRST（LSo）={e}
SELECT（H->ξ）=FOLLOW（H）={f,#,o}
SELECT（K->dML）={d}
SELECT（K->ξ）=FOLLOW（K）={e,#,o}
SELECT（L->eHf）={e}
SELECT（M->K）=（FIRST（K）–{ξ}）∪FOLLOW（M）={d，e,#,o}
SELECT（M->bLM）={b}
构造LL
（1）分析表
a
b
e
d
f
o
#
S
->a
->MH
->MH
->MH
->MH
->MH
H
->LSo
->ξ
->ξ
->ξ
K
->ξ
->dML
->ξ
->ξ
L
->eHf
M
->bLM
->K
->K
->K
->K
4.文法含有左公因式，变为
S->C${b,a}
C->bA{b}
C->aB{a}
A->bAA{b}
A->aA’{a}
A’->ξ{$,a,b}
A’->C{a,b}
B->aBB{a}
B->bB’{b}
B’->ξ{$,a,b}
B’->C{a,b}
5.<程序>---S<语句表>――A<语句>――B<无条件语句>――C<条件语句>――D<如果语句>――E
<如果子句>--F
S->beginAendS->beginAend{begin}
A->BA->BA’{a,if}
A->A;BA’->;BA’{;}
A’->ξ{end}
B->CB->C{a}
B->DB->D{if}
C->aC->a{a}
D->ED->ED’{if}
D->EelseBD’->elseB{else}
D’->ξ{;,end}
E->FCE->FC{if}
F->ifbthenF->ifbthen{if}
非终结符是否为空
S－否A－否A’－是B－否C－否D－否D’－是E－否F－否
FIRST（S）={begin}
FIRST（A）=FIRST（B）∪FIRST（A’）∪{ξ}={a,if,;,ξ}
FIRST（A’）={;,ξ}
FIRST（B）=FIRST（C）∪FIRST（D）={a,if}
FIRST（C）={a}
FIRST（D）=FIRST（E）={if}
FIRSR（D’）={else,ξ}
FIRST（E）=FIRST（F）={if}
FIRST（F）={if}
FOLLOW（S）={#}
FOLLOW（A）={end}
FOLLOW（A’）={end}
FOLLOW（B）={;,end}
FOLLOW（C）={;,end,else}
FOLLOW（D）={;,end}
FOLLOW（D’）={;,end}
FOLLOW（E）={else,;end}
FOLLOW（F）={a}
SAA’BCDD’EFifthenelsebeginendab;
if
then
else
begin
end
a
b
;
#
S
->beginAend
A
->BA’
->BA’
A’
->ξ
->;BA’
B
->D
->C
C
->a
D
->ED’
D’
->elseBD’
->ξ
->ξ
E
->FC
F
->ifbthen
6.1.
（1）S->A|B
（2）A->aA|a
（3）B->bB|b
提取
（2），（3）左公因子
（1）S->A|B
（2）A->aA’
（3）A’->A|ξ
（4）B->bB’
（5）B’->B|ξ
2.
（1）S->AB
（2）A->Ba|ξ
（3）B->Db|D
（4）D->d|ξ
提取（3）左公因子
（1）S->AB
（2）A->Ba|ξ
（3）B->DB’
（4）B’->b|ξ
（5）D->d|ξ
3.
（1）S->aAaB|bAbB
（2）A->S|db
（3）B->bB|a
4
（1）S->i|（E）
（2）E->E+S|E-S|S
提取
（2）左公因子
（1）S->i|（E）
（2）E->SE’
（3）E’->+SE’|-SE’|ξ
5
（1）S->SaA|bB
（2）A->aB|c
（3）B->Bb|d
消除
（1）（3）直接左递归
（1）S->bBS’
（2）S’->aAS’|ξ
（3）A->aB|c
（4）B->dB’
（5）B’->bB’|ξ
6.
（1）M->MaH|H
（2）H->b（M）|（M）|b
消除
（1）直接左递归，提取
（2）左公因子
（1）M->HM’
（2）M’->aHM’|ξ
（3）H->bH’|（M）
（4）H’->（M）|ξ
7.
（1）
1）A->baB
2）A->ξ
3）B->Abb
4）B->a
将1）、2）式代入3）式
1）A->baB
2）A->ξ
3）B->baBbb
4）B->bb
5）B->a
提取3）、4）式左公因子
1）A->baB
2）A->ξ
3）B->bB’
4）B’->aBbb|b
5）B->a
（3）
1）S->Aa
2）S->b
3）A->SB
4）B->ab
将3）式代入1）式
1）S->SBa
2）S->b
3）A->SB
4）B->ab
消除1）式直接左递归
1）S->bS’
2）S’->BaS’|ξ
3）S->b
4）A->SB
5）B->ab
删除多余产生式4）
1）S->bS’
2）S’->BaS’|ξ
3）S->b
4）B->ab
（5）
1）S->Ab
2）S->Ba
3）A->aA
4）A->a
5）B->a
提取3）4）左公因子
1）S->Ab
2）S->Ba
3）A->aA’
4）A’->A|ξ
5）B->a
将3）代入1）5）代入2
1）S->aA’b
2）S->aa
3）A->aA’
4）A’->A|ξ
5）B->a
提取1）2）左公因子
1）S->aS’
2）S’->A’b|a
3）A->aA’
4）A’->A|ξ
5）B->a
删除多余产生式5）
1）S->aS’
2）S’->A’b|a
3）A->aA’
4）A’->A|ξ
AA’S’S
将3）代入4）
1）S->aS’
2）S’->A’b|a
3）A->aA’
4）A’->aA’|ξ
将4）代入2）
1）S->aS’
2）S’->aA’b
3）S’->a
4）S’->b
5）A->aA’
6）A’->aA’|ξ
对2）3）提取左公因子
1）S->aS’
2）S’->aS’’
3）S’’->A’b|ξ
4）S’->b
5）A->aA’
6）A’->aA’|ξ
删除多余产生式5）
1）S->
升级会员 