编译原理课后习题答案1.pdf

文档介绍：该【编译原理课后习题答案1 】是由【cby201601】上传分享，文档一共【27】页，该文档可以免费在线阅读，需要了解更多关于【编译原理课后习题答案1 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:.
Chapter1
i.



“”Computing!"#$%&'()*+,-
./-012%,- 345678 +9
5:;756<=>? ,-
%/- ***@AB5CD“EF”78GHIJK2LM.NOPQ7RSFORTRANPascalC_
_`abc /-%
defJgh7mnopqrsFtu_vk
lwxyz{!|}~+5jHkl#$7y€‚ƒ„+“de”%8&'*+…
.†‡012%
†‡†‡Translator! ‰de78sŠ‹Ftu„+Œ!}~
+_vFŽ‰tu„+g!%Œ >?7g 567„‰†‡+>?
%Œ /-7g ,-7„‰†‡+?‡%
……Interpreter! ‰de78“Œ”r•|–l*—7˜™šr•›œk
l•<
j%
2.

?‡¡¢£¤£%¦§¨©*—67ª„«678H¬Š‹Œ7“Œ–l¨©*—7­®¯
rr°¨±²7¦Š¯³x °¨±²%
´µŽ´-,
iBHWfc
4sm
©*—67“°¨±²¸–l©*—˜™©¹–lº»¼½¾!7­®¯§¿2©°À7ÁÂÃÄ
Š‹¸ Åƀ©ÇÈÉ“”%
œ*—ʧËÌÍÎÏ67ÐÑœ¹“©*—6½¾¯¼º»¯!©°À–lœ*—ÒÓ8a†‡€

#$§ËÌÍ%?‡'(˜™ÔÕÖ×ØÙÔÕ§ËÌÍ#$7q?‡ÚÛÜq§ËÌÍ#$7Ý
HπgÌÍ%
Þß6“§ËÌ͖lÞßde%i&Áàπ§ËÌÍklwáâãä,7mn×å§ËÌÍÞß7¦"æç
è. “§ËÌ͖l_vé~7êëklìjGí7ÒîFGïðË%
gÌÍπ6Ó§ËÌ͆‡€g%§ËÌÍ& ‰56CDPQ#$7iqÓ8ñ†‡€***@56òó
HôD56j­®7õg7öjë56Ç÷l%
PøùeúûüýŽ:þPø7ÿ





!"#$%&'()
*+,- ./0
1234516
278349
:27
;<=>627?:***@27AB:.
DEF

:GH>6271234"5>627834IJKLDEF
Chapter2
={0,1}XYZ[\]^_`a
b:c1de fghi
jkl:31:ghno[\
(3)[\{01,1}
r:c111fghi
sta(1)1(0|1)*1|1
j0*10*10*10*
w01|1
(4)(0|1)*111
{)|[]^_`jOP1cz5|~€:z{)|[]^_`
sta(1)0|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)'
j0|(1|2|3|4|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*
†‡:ˆ‰Š‹ŒMŽ
‘’a“H5”•:ˆ‰Š‹Œ8Ž–—Š‹Œ˜™š”•
Ž›E‰‘œ=žŸ=9Ya
 80¡¢£‘aQ£‘Qr¦Q-Q,
¨©˜8ªk¡¢£‘¬Q˜­£‘o(Q“Q”-Q,,),°8k+1£‘5Q²(i=lµn),©qIq'eQ²,¹º
5»¼aeV“8(q,a)eQ, 5(q',a)GQ„j^lÂ3(q,a)ÃÄ3(q',a)+ÃÂKÅ^†Q,£‘Æ
Ç[Qu,Qi2)¹qeQi”q'eQi2É
ÊĘ̈ÍÎÏ=¼Ð£‘Ñ5ŽÒ£‘ºÓ‰Ç[Ô¼Ç[ÕÖ×Ç[ØÙ¼‰Ú׉Ç
[ÛÜÒÝÞßà:ˆ‰Š‹Œ‰áâã|3,äbÚEYá滉Ç[ØÙç‰çèÞoáæ
׉Ç[Û©¼‰Ç[»¼‰šßàde‰^׉Ç[Ûéšê:ˆ‰Š‹Œde
‰ë4©¼‰Ç[‰ìšŽí‰^׉Ç[Ûéšê:ˆ‰Š‹ŒŽí‰
îïðGHÃÏE‰¦+Gñ‰
staò:ˆ‰Š‹Œ‰áâ9‡a
䇉
ab1
ABC
BDC
CBE
1)1)FAccept
EGEAccept
FGEAccept
GI)FAccept
óòô1aò:ˆ‰Š‹Œš”•
Ža
õe£‘ó2Ç[no¬:({A,},{D,E,F,G}):.
[\{D,E,F,G}+!"¼Ð£‘ýþÇ[{A,B,C}óÿ
8(B,a)=De{D,E,F,G),B(A,a)=8(C,a)=Be{A,BC},
Q:((A,C},{B},(D,E,F,G})
5(A,b)=CG{A,C},5(C,b)=Ee{D,E,F,G}0
Q#({A},{C},{B},{D,E,F,G})$
%&'()*+,-./:>?:
:
a#)1
BC
CBE
BDC
DDDAccept
(GH)IJKLMNOPGQ:RSRU:?:
(D*E|D+.D+E|E|.D*E)((+|-)D|D)D*|D+|D*.D+
Z[\]^_`abc2345678$
d\ef2345678/01$
ghef2345678ijklm7n+opF(GH)IJKL$
q#rGQ:RSst2345678Muv$
wxyrz{X-z{~+2~e€MGQ:RSR$z{X€M“”.ƒ„45+z{Y€M“+”.
/…45$r%†2~‡pˆ‰ŠmN‡>?.‹ŒQ+Ž>22~‘€’“”$
121
CP->©*CQOw
‡‹ŒQ
•–—mNw>,-.˜™‡i.“+Mu#š›–—“œ+žŸ–—ž “$
a)“œ.–—¡¢#
i.¤“œ.¥¦§¨©ª{$
ii.«¬­©l®.2~$
iii.¯“œiA45°/…(‘ƒ„)45+Q±ª{°/…(‘ƒ„)45$
b)ž]e.–—2u²¡¢#
1)´µ¢#¶·¸8Closure(T),ž:?r45µTi¿ÀÁ45“M-ÃÄ$
žÅ{°#rƒ„=“-Closure(q0)DŽ+È9O¡¢st45µ#
i.ÉSet={X}Ì
ii.¯SetiÍ2ÎÏÐÑ.45´µXj,QÓÔÕÖIJaeVØÙT=“-Closure(move(X^a)),Set=SetU{T}(ži
move(XM={q|qe6(p,a),peXi})$áŠâv(2),Ž'ãh%ä.X,$%ä,-.Set¶–—“å.
(DFA)oDFA.ƒ„45æ°$Closure(q0),/…45çèéê2©/…´µë`$
2)ì–—¢#
žÅ{°í-îï‡>?+ðrB)F“ñp.“$
‡ì–—¢
ò—45A-45B.“+ÓÔÁyr45B-45C€’a,.+ók1yr45A-45C€’aj.$¯B:.
°/…45+QôA/…45$áŠefÑBŽ–—Ãõ.“+%ä,-.ö°'÷NFA$
øù#Z‡úpØrGQ:RSRst2345678M.ÑB$
‡‹ŒÑB
mN´µ¢–—?:
e-ClosureÉAl={x,2},·¸:
#-Closure(move(Al,D))=#-Closure({7,10,2,1})={7,10,2,l,y!
e-Closure(move(Al,+))=e-Closure({5,3})={5,3}
#-Closure(move(Al,E))=e-Closure({4})={4}
ÉA2={7,10,2,l,y},A3={5,3}+A4={4},·¸:
#-Closure(move(A2,D))={7,10,2,1,y}
#-Closuremove(A2,+))={8,3}
E-Closure(move(A2,E))={4}
e-Closure(move(A3,D))={5,6,3,y}
e-Closure(move(A4,D))={12,y}
e-Closure(move(A4,+))={11}
#-Closure(move(A4,-))={11}
ÉA5={8,3},A6={5,6,3,y},A7={12,y},A8={11},·¸:
e-Closure(move(A5,D)={8,9,3,y}
e-Closure(move(A6,D)={5,6,3,y}
#-Closurc(move(A6,E)={4}
#-Closure(move(A7,D)={12,y}
#-Closurc(move(A8,D)={12,y}
ÉA9={8,9,3,y},·¸:
e-Closure(move(A9,D)={8,9,3,y}:.
#-Closure(move(A9,E)={4}
,-.DFAM+.ƒ„45°Al,/…45µA2,A6,A7,A9ë`$
‡°M+.45^_‡+M+.45^_:9:>?$
:+.45^_:
D!'*+-1
A1A2A4A3
A2A2A4A5Accept
A3A6
A4A7A8A8
A5A9
A6A6A4Accept
A7A7Accept
A8A7
A9A9A4Accept
‡+.45^_‡
dÿ

 
2
({A1,A3,A4,A5,A8},{A2,A6,A7,A9})

{A2,A6,A7,A9},
({A6,A9},{A2},{A7})

{A1,A3,A4,A5,A8},
({A4},{A1},{A8},{A3A5})
!"#$%"&'
()*+,-.
/012""*7&89:;<=>?***@AB(CD)FGH2"IJ2K4L2KMNO2QR
STUVWXYQRST
AH2"ZJ2Knumber
AH2"L2Kexp
$2cd2n
AH2L2KCDGexpsign
=4QRSTO&'
()*"ijkl m%n0U
p2qkgetchar,wxyzOX{F!QRSTchar|U:.
p2qkvalue,wxy}~N:QRSTchar|2{{F"€U
q‚Qƒ"
„…+-.
‚Qƒ"
„…
D+-±
A1#1,A2#2,A3#2,A4
A2#3,A2#2,A3#2,A4#10,Accept
A3#4,A6
A4#5,A7#6,A8#7,A8
A6#4,A6#2,A4#11,Accept
A7#8,A7#12,Accept
A8#9,A7
„…|T‡Al,A2,A73.ˆ‰Š‹"X
U#1,#2,#123.ˆ‰Œ"Ž
klUŽ
k
l"‘’“”+X
#1numbei*:=value(char);getchar;
#2getchar;
#3number:=nuiTiber*10+value(char);getchar;
#4n:=n+1;number:=number*10+value(char);getchar;
#5expsign:=l;exp:=value(char);getchar;
#6expsign:=1;getchar;
#7expsign="l;getchar;
#8exp:=exp*10+value(char);getchar;
#9exp:=value(char);getchar;
#10•–—˜}™šB(CD)FG2›
#11exp:=-n;•–—˜}™šB(CD)FG2›
#12ifexpsign=-lthenexp:=-exp;exp=exp-n;•–—˜}™šB(CD)FG2›
˜M"Sž&'y{STEP,SWITCH,STRING},ŸˆC 3¡¢ySTEP|SWITCH|STRING,£¤Š‹
¥¦§&'

()*U
¨©
={a,b},£™šXYC 3¡¢"¥¦§&'
()*
(1)a(a|b)*baa
(2)(a|b)*bbb*
¨©(D0AC 3¡¢™š"&'
()*Ml"
Š‹,+,-.:
,&'
()*Ml"Š‹,
¥¦%()
"¥¦%:.
Q'6a'3b1
JJ°
[2]³³3]
[2,3][2,4][2,3]
[2,4][2,5][2,3]
[2,5]2.[2,3]A
¶ˆ"
Š‹,+,-.:
,"
Š‹,
(2)0C 3¡¢™š"&'
()*M2"
Š‹,+,-.
,"
,
¥¦%()
"¥¦%
Q'3¼3b1
[1][1][1,2]
[1,2][1][1,2,3]
[1,2,3][1][1,2,3]
,"
Š‹,
9.¶1X½"
Š‹„…:
ab1
SAS
AAB
BBBZ
ab1
sAS
ABAZ
BBB
¾M¿~Ÿˆ"
Š‹,U
³(ÀŽÁMÂYÃ-M"ÄOÅ"ÆÇU
¨©¾31-¶ˆ"
Š‹,+,-.:.
,¶ˆ"
Š‹,
32-¶ˆ"
Š‹,+,-.:
,¶ˆ"
Š‹,
³31-M"ÄOÅyÈb*aa*bÉÊ"ƒËÌÍÎaÏb" a,bI"{FÅU
32-M"ÄOÅy?Ð&a" a,bI"{FÅU
10.@ÑÒ,-."Ó¥¦"&'
()*¥¦%4#$%U
ÑÒ,Ó¥¦"&'
()*M
¨©¥¦%Ô
"¥¦%
ab1
[S][A]
[A][][A]
[B,C][Alz
ÕB=[B,C]¶ˆ"
Š‹,+,-.:
,"
Š‹,
¥¦%"MÖy#$%"U
11.×ØÙÚ,TÔÑÒ,|"eÛU
ÑÒ,ÙÚ,T
¨©iÜ×ØÝÞßàá
243,!"ÙÚ,T+,-.
,×Ø?Þß"ÙÚ,T
iiãä×ØåØwæÝÛ#ç!"ÙÚ,T”+,-.:.
,×Ø-&ÝÛ"ÙÚ,
Chapter3
&èG1[<S>]
<S>-<N>
<N>-<D>|<NXD>
<D-0|l|2|-|9
£é~02844321"#êëì4#íëìqkU
î:ï"ëì|ðy¶#ê"ñÓç”FŸˆ"òó¢"íKôõ‹=ö"ëì÷n#êëìUøùú
+ûï"ëì|ðy¶#í"ñÓç”FŸˆ"òó¢"íKôõ‹=ö"ëì÷n#íëì#íëìü÷ý
þëìU
¨©028"#êëì
<S>^><N>=><N><D>=><N><D><D>=XD><D><D>=>0<D><D>=>02<D>^>028
028"#íëì
<S>=><N>^><N><D>=><N>8=><N><D>8=><N>28=><D>28=>028
4321"#êëì
<S>=><N>^><N><D>=><N><D><D>=><N><D><D><D>=><D><D><D><D>=>4<D><D><D>=>43<D><D>=>432<D>=>4321
4321"#íëì
<S>=><N>^xN><D>=><N>1=><N><D>1=><N>21=><N><D>21=><N>321=><D>321=>4321
3.ÿ
G[S

<S>^if<E>then<S>else<S>|if<E>then<S>|s
<E>r0|l
 


 if0thenif1thenselses!"#$%&
if<E>thoi<s>rfgg<S>
I.1I
0,>s
if<E>bea<S>
II
Is
'if0thenif1thenselses$%&)1
'if0thenif1thenselses$%&(2)
4.+,
G[<E
<E>^<E>><T>|<T>
<T>J><T>/<F>|<F>
<F>->i|(<E>)
-./i/(i0i)$%&
1./(<F>-i)/VF>234562378
 
9:()$%&<=>?234562378
 -i/(i-i-i)$%& :.
<E>
'i/(i-i-i)$%&
1EF>-i)HF>$%&:
V-e
-
T
6<F—>
i
'(<F>-i)/<F>$%&
23 <F>,i,<F>-i,(<F>-i),(<F>-i)/<F>
5623:<F>,i
8 <F>
5.NOPQ
10014
1010to
010001
000000
100100
^000001J
?B+o
 UVWarshall]?^_:.
min
*mm
--oooooo
milt
jOOOOOl7
7.a^b3cG[<S>]
<S>->a|A|(<T>)
<T>k><T>,<S>|<S>
-.9(a,(a,a))lm7ln$%
1o(((a,a),p,(a)),a)ln$%qrstuvw8
x9(((a,a)y(a)),a)$%&z{|b}~
 €
‚ƒ„…qz{|b}$%&~ln$%(t†$%)‡~qˆ~‰zŠ‹|

~qŒ
84Žu
 -(a,(a,a))lm$%
<S>=>(<T>)=>(<T>,<S>)=>(<S>,<S>)=>(a,<S>)=>(a,(<T>))=>(a,(<T>,<S>))=>(a,(<S>,<S>)=>(a,(a,<S>)=>(a,(a,a))
ln$%
<S>=>(<T>)=>(<T>,<S>)=>(<T>,(<T>))=>(<T>,(<T>,<S>))=>(<T>,(<T>,a))=>(<T>,(<S>,a))=>(<T>,(a,a))=>(<S>,(a,a))=>(a,(a,a))
1(((a,a)y(a)),a)ln$%sŽuvw8’“
(((a,a),y,(a))xln$%~
ln$%vwŽu”8
<s>(ET•ET•
(ET>,<S•<T>,<S>
(ET>,a)a
(ES>,a)<S>
((ET•,a)ET•
((ET>,<S•,a)<T>,<S>
((ET>,ET•),a)ET•
((ET>,ES•),a)<s>
((ET>,(a)),a)a
((ET>,<S>,(a)),a)<T>,<S>
((ET>,A,(a)),a)A
((ES>,A,(a)),a)<S>
(((ET•,A,(a)),a)(<T•
(((ET>,<S•,A,(a)),a)<T>,<S>
(((ET>,a),A,(a)),a)a
(((ES>,a),A,(a)),a)<S>
((((a,a),A,(a)),a)a
x(((a,a)y(a)),a)$%&'’“::.
'(((a,a),A,(a)),a)$%&
b}~'’“:
'(((a,a),A,(a)),a)$%&z{|b}~
Chapter4(–)
Chapter5
1.—˜]™aš›œ
Tl
T1=({+,*,G),C},{<E>,<T>,<P>},{C,ADD,MUL},R,<E>)
ŒžRŸ t¡¢£
<E>^<E>+<T>,<E><T>ADD:.
<E><T>,<T>
<T>-*<T>*<P>,<T><P>MUL
<P>T<E>),<E>
<P>C,C
Œ¤¥¦
LR(1).¥¦
$z§¨©ªa«¬­®§qb}œ$z§¨©ªaq¯œ
$z§¨°±²ŸC,+,*¢£ž³aš›œ£´³aš›
 +œ
žœt¡µ vA>-x,y
°zŠ‹|$z§¨®}£¤$œz§¨¶·56 ¸t¹q­$z§¨Vº»›i¼½tu#
”q¥yž¥¾¿
 ¥¦
LR(1)ÀÁÂ
¥¦
LR(1)ÀÁÂ

¾¿
ÀÁTÃÄÂGOTO(T,B)
B
*[!Eq>-Ç<E>1,A]<E>1
[<E>fÇ<E>+<T>,±/+]<E>1
[<E>-Ç<T>,1/+]<T>2
0[<T>-Ç<T>*<P>,_L/+/*]<T>2
[<T>-Ç<P>,1/+/*]<P>3
[<P>fÇEE•,1/+/*](4
[<P>fÇC,±/+/*]c5
*[<E>>-<E>DZ]1Accept
1
*[<E>-<E>Ç+<T>,1/-+6
*[<E>-<T>Ç,1/+]±/+42
2
*[<T>-<T>Ç*<P>,!_/+/*]#7
3*[<T>-*<P>Ç,1/+/*]1/+/*#4
*[<P>-(Ç<E•,1/+/*]<E>8
[<E>-Ç<E>+<T>,)/+]<E>8
[<E>-Ç<T>,)/+]<T>9
4[<T>--<T>*<P>,)/+/*]<T>9
[<T>f.<P>,)/+/*]<P>10
[<P>fÇEE•,)/+/*](11
[<P>--c,)/+/*]c12
5*[<P>-C-,1/+/*]1/+/*#6
*[<E>-<E>+Ç<T>,±/+<T>13
[<T>-Ç<T>*<P>,1/+/*]<T>13
6[!TAÇ<P>,±/+/*]<P>3
[<P>$ÇEE•,±/+/*](4
[<P%fÇC,±/+/*]c5
*[<T>-<T>*Ç<P>,!_/+/*]<p>14
7[!PAÇEE•,±/+/*](1
[<P>fÇC,±/+/*]c5
*[<P>-EE>Ç),1/+/*])15
8
*[<E>-<E>Ç+<T>,)/+]+16
*[<E>-<T>Ç,)/+])/+#2
9
*[<T>-<T>Ç*<P>,)/+/*]*17
10*[<T>-*<P>Ç,)/+/*])/+/*#4:.
*[<P>-*(+<EN,)/+/*]<E>18
[<E>-+<E>+<T>,)/+]<E>18
[<E>--<T>,)/+]<T>9
11[<T>-+<T>*<P>,)/+/*]<T>9
[<T>-+<P>,)/+/*]<P>10
[<P>f+OEN,)/+/*](11
[<P>--C,)/+/*]c12
12*[<P>-C+,)/+/*])/+/*#6
*[<E>-><E>+<T>+,1/-1/+#1
13
*[<T>-*<T>+*<P>,I/+/*]*7
14*[<T>-<T>*<P>+,±/+/*]_!_/+/*#3
15*[<P>-OEN+,1/+/*]_!_/+/*#5
*[<E>-*<E>++<T>,)/+]<T>19
[<T>-+<T>*<P>,)/+/*]<T>19
16[<T>J+<P>,)/+/*]<P>10
[<P>-+OEN,)/+/*](11
[<P>--C,)/+/*]c12
*[<T>-<T>*+<P>,)/+/*]<p>20
17[<P>-+OEN,)/+/*](11
[<P>--c,)/+/*]c12
*[P>f(EØÇ),)/+/*])21
18
*[<E>^<E>++<T>,)/+]+16
*[<E>-<E>+<T>+,)/+])/+#1
19
*[<T>-*<T>+*<P>,)/+/*]*17
20*[<T>-<T>*<P>+,)/+/*])1,*#3
21*[<P>-NOE>)+,)/+/*])/+/*#5
œ$z§¨©ªa’“:
œ$z§¨©ªa
§«a(Action)ۋa(Goto)
ÀÁT
+*()c1<E><T><P>
0Sis5123
1SBAcc
2R#2S;R#2
3R#4R#1R44
4S.)S128910
5R#6,GEN(C)R#6,GEN(C)R#6,GEN(C)
6S5133
7s”S514
8Sl6Sl5
9R#2s-R#2
10RH4Iá4R#4
11SuS1218910
12R#6,GEN(C)R#6,GEN(C)R#6,GEN(C)
13R#1,GEN(ADD)sãR#1,GEN(ADD)
14R#3,GEN(MUL)R#3,GEN(MUL)R#3,GEN(MUL)
15R45R45R45:.
16SnS121910
17S]220
18S16
19R#1,GEN(ADD)S17R#1,GEN(ADD)
20R#3,GEN(MUL)R#3,GEN(MUL)R#3,GEN(MUL)
21R#5R#5R#5
2.—˜æ
G[vS>]
<S>J>i:=<E>
<E>-*<E'>+<E2>
<E>J*<E