資源描述：
《編譯原理及實現(xiàn)課后習題答案》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、編譯原理及實現(xiàn)課后習題解答2.1設(shè)字母表A={a}，符號串x=aaa，寫出下列符號串及其長度：x0,xx,x5以及A+和A*.x0=(aaa)0=ε
2、x0
3、=0xx=aaaaaa
4、xx
5、=6x5=aaaaaaaaaaaaaaa
6、x5
7、=15A+=A1∪A2∪….∪An∪…={a,aa,aaa,aaaa,aaaaa…}A*=A0∪A1∪A2∪….∪An∪…={ε,a,aa,aaa,aaaa,aaaaa…}2.2令∑={a，b，c}，又令x=abc，y=b，z=aab，寫出如下符號串及它們的長度：x
8、y，xyz，（xy）3xy=abcb
9、xy
10、=4xyz=abcbaab
11、xyz
12、=7(xy)3=(abcb)3=abcbabcbabcb
13、(xy)3
14、=122.3設(shè)有文法G[S]：S∷=SS*
15、SS+
16、a，寫出符號串a(chǎn)a+a*規(guī)范推導，并構(gòu)造語法樹。S=>SS*=>Sa*=>SS+a*=>Sa+a*=>aa+a*SSS*SS+aaa2.4已知文法G[Z]：Z∷=U0∣V1、U∷=Z1∣1、V∷=Z0∣0,請寫出全部由此文法描述的只含有四個符號的句子。Z=>U0=>Z10=>U010=>1010Z
17、=>U0=>Z10=>V110=>0110Z=>V1=>Z01=>U001=>1001Z=>V1=>Z01=>V101=>01012.5已知文法G[S]：S∷=ABA∷=aA︱εB∷=bBc︱bc,寫出該文法描述的語言。A∷=aA︱ε描述的語言:{an
18、n>=0}B∷=bBc︱bc描述的語言：{bncn
19、n>=1}L(G[S])={anbmcm
20、n>=0,m>=1}2.6已知文法E∷=T∣E+T∣E-T、T∷=F∣T*F∣T/F、F∷=(E)∣i，寫出該文法的開始符號、終結(jié)符號集合VT、非終結(jié)符
21、號集合VN。開始符號：EVt={+,-,*,/,（,）,i}Vn={E,F,T}ETE+FTE+iFT*T2.7對2.6題的文法，寫出句型T+T*F+i的短語、簡單短語以及句柄。短語：T+T*F+iT+T*FiiTT*F簡單短語：iT*FT句柄：T2.8設(shè)有文法G[S]：S∷=S*S
22、S+S
23、(S)
24、a，該文法是二義性文法嗎？SSS*S+SaaaSSS+S*Saaa根據(jù)所給文法推導出句子a+a*a，畫出了兩棵不同的語法樹，所以該文法是二義性文法。2.9寫一文法，使其語言是奇正整數(shù)集合。A::=1
25、
26、3
27、5
28、7
29、9
30、NAN::=0
31、1
32、2
33、3
34、4
35、5
36、6
37、7
38、8
39、92.10給出語言{anbm
40、n,m≥1}的文法。G[S]:S::=ABA::=aA
41、aB::=bB
42、b3.1有正則文法G[Z]：Z::=Ua
43、Vb，U::=Zb
44、b，V::=Za
45、a，畫出該文法的狀態(tài)圖，并檢查句子abba是否合法。解：該文法的狀態(tài)圖如下：SUVZaaabbb句子abba合法。3.2狀態(tài)圖如圖3.35所示，S為開始狀態(tài)，Z為終止狀態(tài)。寫出相應的正則文法以及V，Vn和Vt。SAZabab圖3-35狀態(tài)圖解：左線性文
46、法G[Z]:右線性文法G’[S]:Z::=Ab
47、bS::=aA
48、bA::=Aa
49、aA::=aA
50、bV={Z,A,a,b}V={S,A,a,b}Vn={Z,A}Vn={S,A}Vt={a,b}Vt={a,b}3.3構(gòu)造下列正則表達式相應的NFA：1(1
51、0)*
52、01(1010*
53、1(010)*1)*0解：正則表達式：1(1
54、0)*
55、01、SZ1(1
56、0)*
57、02、SZ1(1
58、0)*03、SAZ01ε014、q0q1010,1q2正則表達式：1(1010*
59、1(010)*1)*00135462101
60、0107801011ε01a,baa3.4將圖3.36的NFAM確定化圖3.36狀態(tài)圖解：abq0={0}{0,1}{1}q1={0,1}{0,1}{1}q2={1}{0}ΦDFA:q0q1q2ababa3.4將圖3.37的DFA化簡。014253aaaaaabbbbbb圖3.37DFA狀態(tài)圖解：劃分ab{0,1}{1}{2,4}{2,3,4,5}{1,3,0,5}{3,5,2,4}劃分ab{0,1}{1}{2,4}{2,4}{0,1}{3,5}{3,5}{3,5}{2,4}q0={0,1}q1
61、={2,4}q2={3,5}化簡后的DFA：q0q1q2baaabb4.1對下面文法，設(shè)計遞歸下降分析程序。S→aAS
62、(A),A→Ab
63、c解：首先將左遞歸去掉，將規(guī)則A→Ab
64、c改成A→c非終結(jié)符號S的分析程序如下：過程SINPUTSYM=’a’INPUTSYM=下一個符號YNINPUTSYM=’(’INPUTSYM=下一個符號YINPUTSYM=’)’INPUTSYM=下一個符號YNN出口錯誤錯誤過程A過程S過程A非終結(jié)符號A的分析程序如下：過程AINPUTSYM=’c’INPUTSY
