編譯原理答案(主編張晶)

1、標準文檔1.1翻譯程序:臥某一種程序設計語言所編寫的程序作為翻譯或力0J的對象， 將它翻譯成與之等價的另一種語言的程序0高級語言雖然優(yōu)越，但計算機硬件卻只懂得自己的指令系統(tǒng)，即只能直接 瓠行相應機器語言格式的代碼程序而不能直接執(zhí)行用高級語言或匯編語言 編寫的程序*因此高級程瘵設計語言需要翻鋒程序將苴翻譯成為計算機能 理解與執(zhí)行的機器語言的程序。1.2編譯程序解釋程序：從高級語言到機器語言或匯編語言的翻譯程序* 編譯程序；產(chǎn)生目標程序然后再執(zhí)行目標程序，可以反復執(zhí)彳亍。解釋程序：不產(chǎn)生目標程序，逐句翻譯執(zhí)行，只能執(zhí)行一次，若需重新 執(zhí)行，則必須重新解釋程序。1.3實用文案(1) 通常一個編譯程序

2、由詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化、目標代碼生成出錯管理和符號表管理八部分組成。(2) 各部分的任務：i司法井析：從左到右逐個字符的讀入源程序按照源語言規(guī)定的詞法規(guī)貼對構成源程序的字符流進行扌瑚和分解，從而識別出一個個單詞，并把 他們表示成機內(nèi)單詞形式紡語法分析：根採源語言的語法規(guī)則扌詞序列分解成各類語法單位，并指出其中的語法錯吳語義分析：分析各語法成分的含義和力能，即它1門的屬性或在執(zhí)行時應曲亍的運算或操作。中間代碼生成：在語法分析和語義分析的基礎上，根扌居語法成分的語義對其翻譯，翻譯成在語義上等怕的中間代碼的語言。代碼優(yōu)化：對代碼進行改造變換，目的是使生成的目標代碼更為

3、高效，目皓時間和省空間。目標代碼生成：轉換為等價的目標代碼。出錯管理：員貴發(fā)現(xiàn)源程序中可能出現(xiàn)的錯誤，并把錯誤報告給用戶，指出錯誤的tJ廝竣生錯誤能墨符理：記錄源程序中使用的標識符和毎個標識符的答種屬性，臥便后續(xù)的工作中Bffft用。1.4編譯程序的組織方式有3種：(1邏輯組織方式，即將編譯過程劃分為六個階段，貫穿始終的是符號 表管理和出錯管理*(2編譯過程分為前端和后端兩個部分，前端主要依輟于源語言，它由 幾乎獨豈于目標機器的階段或階段的一部分組成后端是編譯器中依賴于目 標機器的部分，它一般獨立于源語言而與中間語言有關。(3采用“吩遍”的形式，即編譯過程可以由一遍或多遍來完成。(遍： 在編譯

4、過程中，對源程序或其等價的內(nèi)部表示從頭到屋掃視，幷進行相應的 加工處理進而完成規(guī)定任務的過程稱為編譯的一遍)2.1標準文檔最左推導： E3T=F=i E =T = F =舊=(T) =(F) =(i) E=T z=T*F=F*F= 產(chǎn)F = 產(chǎn)i E =E+T=T+T =F+T =i+T =i+T*F =i+F*F =i+產(chǎn)F ni+產(chǎn)i E =E+T =T+T =F+T =i+T =l+F = k(E) =i+(T) = l+fT*F)=i+(F*F) =i+(F*F) =i+F) =i+(門) E =E+T =T+T =T/F+T =F/F+T =i/F+T =i/i+T =i/i+T*F

5、 =i/i+F*F=i/i+i*F =i/i+i/i最右推導：E=T=F=i E=T=F=(E) =(T) n (F) =(i) E 二E+TdE+I/F =E+T/i 二 E+M =E+i/i =T+i/i F+i/i qi+i/i E =E+T=E+F = E+(E) = E+(E+T) = E+(E+F) =E+|E+i) =E+(T+i)二* E+(F+i) E+(i+i) =T+(i+i) F+i+i)二 i+(i+i) E =E+T=E+T*F=E+T*i=E+F*i=E+i*i=T+i*l=T/F+l*i=T/i+i/i =F/i+i/i =i/i+i/i實用文案標準文檔語法樹：

6、AE 4-I /K 【T /實用文案EE/NI +I AF f E I /Ni E2.2標準文檔此西答案不唯一，正確即可4 XOS I 1AA-OA | EaS | bA | fA- bA | cC | ECCC I s-a5 | eS-OA | IBADS | 1C |0B-1S | 0C| 1C-OB | 1A2.3實用文案標準文檔此題答案不唯一，正確即可。 S-aAbCAaAb | eC-cC | ESISO I 1A0A-OA1 | 01SOIAAlAl | 0SDiAIDjA-D5A|D：D1-1|2|3|4|5|6|7|S|9Dr2|4|6|8D3-0|l|2|3|4|5|6|7|

7、8|92.4(1)終結符；0* 、 非終結符：S. L 幵皓符號:S實用文案2.5(3) CD(L)二 (LPS)二 (SfS)二 (aFS)二 (ara)$ = (L) = (LfS) = (S-S) = (L).S = (S)fS) = (a)5)=(aML = (aK(S) = a)4a(4) S= (L) = (LS) = La) = (Sa) = (ara)5= L) = (LS) = L(L = (L(S =仏剛= (SJa)= I(L)4a = (SMa)= (卻)(1) S=aSbS =aSb =abSaSb=abSab =abab 5 =a5bS =aSba5bS =a5ba

8、Sb aSbab =abab由于句子abab在兩種不同的最右推導，所以該文法為一個二義性文 法(2) SaSbS abSabaSbSababSabab 5 =aSbS =abSaSbS = abaSbS=aba bS =4abab由于句子abab在兩種不同的最左推導，所汰該文法為一個二義性文J eZ 1由于句子mbab存在兩棵不同的語法樹所臥該文法為一個二義性文法。2.6根據(jù)1型文法的是義可知該文法為1型文法。2.7(1) Liabtd-1 0=1, j=0(2) L2=baa | i=0)=l2.8(1) P=SABS | Aa | G A-a?B-bAB5 =aBS=aSBBS =aBBS

9、 =abBS =abbS =abbAa =4abbaa最右推導：S =ABS =ABAa = ABaa ASBBaa =ASBbaa = ASbbaaAbba a=abbaa2.9生成該語言的文法為G:S-ABA-aAd | DD-bDc | beB-Be | e2.10例如對于句子abc： 5 =AB =aB =abc 5 =DC abC = a be由于句子日be存在兩種不同的最左推導，所I汰該文法為一個二義性文法3.1(1)正規(guī)式為:s=o+|onr有窮自動機為:(2)正規(guī)式為：S=aa+(bc)+有窮自動機為：3.2（1）狀態(tài)轉換團為:(2)右線性文法為:| 0AARIA | OBBW

10、B | IB(b)SlB | OAA-1A | OCB-HJB | 1C90C | 1C3）同以,1幵頭.由g 1組成的數(shù)字串,或以D開頭，至少包含兩個0 的由譏丄組成的數(shù)字串*（b）臥o開頭，至少含有2個0的由0、1組成繼字串，或以1開頭, 至少含有2個1的由0、1組成的數(shù)字串。3.3 bmb、bbbv ba bbc（2）以maa* aat aba.占bb結尾的由a% b組咸的符號串;列舉四個較短的句子為：aaa aab aba abb（打含有2個。的宙0、1組成的符號串；列舉四個較桓的句子為：00、100, 010 001.（4）以0或1結尾的前面由若干個01組成的符號串；列舉四個較短的旬

11、子為：o. r 010, 011c3.4使用子集法進行確定化，并對狀態(tài)重新進行命名（0. 1. 2. 3:01二 *SrArB0AAC1APB2ArBFC1A.BPC1ArBrT3傀B2A,Bfq1AfB23A.BX1APB2確走化的有窮自動機為:3.5使用子集法進行確定化，并對狀態(tài)重新進行命名（久B、： D、E）:01n *1A2,4B2,4B(5,61D(3)C3 C1A*A6)D6*6E何 E確定化的有窮自動機為:3.634(D*423使用最小化算注后四個狀態(tài)可以凜少為三個狀態(tài)：1,4,2,3 畫出的最小化的DFA為：3.7與正規(guī)式蒔價的有窮自動機為:3.8正規(guī)式：1(0|1)*00NF

12、A如下團所示；101n閔 10BX-D 2CrD 2憶 D*E3QD4CAE： 3MEtF 5QD4C-D)4比D同 3IGD4*CrD,E,F5t,D.E,F) 5CD4DFA如下團所示;使用最小化聖去后，5個狀態(tài)可以凜少為心個狀態(tài)：也冊劇冏，以2 作為狀態(tài)代表，最小化后的DFA為：3.9文法G對應的自動機為:該自動機是不確定的。使用子集法進行確定化，并對狀態(tài)重新進行命名（As B、C）:101=RAABABA,S C0*A,S CA,S CA B則DFA如下團所示:標準文檔3.10實用文案標準文檔使用子集法進行確定化，并對狀態(tài)重新進行命名（X、3. 4、5.靈7）:101=S1VB2BX3

13、A.B2 JA,BfQD 4B5BfC3AFBfC 6BfD7* 仏 BCD4A.BD 4B.D1B5gB6B5A7BrC 6AzBrQD 4B,D7* D 7A.B.GD 4 1DFA如下團所示;000200030使用最小化算法后7個狀態(tài)可決減少為6個狀態(tài)；2”創(chuàng)5閥他7,以4作為狀態(tài)代表，最小化后的D啟為：3.11(1) (a | b廠的 NFA為:梗用子集法進行確定化，并對狀態(tài)重新進行命名（A、B）:1abm2.3 B(2,3 B* (2.3)2.3 B2,3) BDFA如下團所示:使用最小化算法后,2個狀態(tài)可以減少為1個狀態(tài):A（Bb決A作為狀態(tài)代表，最小化后的DF自為:(2a|bra

14、(a |b)的 nfa為:使用子集法迸行確定化，并對狀態(tài)重新進行命名（茲氛3. 4, 5）:1ab=1,Z32,3,42.3323323A5 423,55乙3(2342.33*23 A 52,3t4fS 42,3,55*2.3,52,3r42.33DFA如下團所示:使用最小化算法后，5個狀態(tài)可以減少為幼個狀態(tài)：lr3J2r4r5J 以.1作為狀態(tài)代表：最小化后的DFA為：(3H0 I tO I 11W 1 的 NFA為:使用子集法進行確走化，并對狀態(tài)重新進行命名（K 2.沢4：101nu 132.432閭 241X4 3432*540DFA如下圖所示:該團已為最1毗的DFA。（4 （0| 1）

15、 ） 101 可簡化為（0 | 1） 101,它的 NFA為:使用子集法進行確定化，并對狀態(tài)重新進行命名(A, B. C. D. E):101= 1.232,32,3,4 C2J2,3234 C2,3,42,3P5 D23A C23Q2.3B23A623.5 D234 CDFA如TF圖所示:使用最小化算法后，5個狀態(tài)可以;咸少為山個狀態(tài)： 以A作為狀態(tài)代表，最小化后的DFA為:3. 12(a | b)a白的NF血為:使用子集法進行確定化并對狀態(tài)重新進行命名5、馭0 )：1ab=1,23 a(2t3r4Jc2331 B23-4503c2.3 C2341c*2,3AS23 綣 5231cDFA如下

16、圖所示:使用最小化M法后，4個狀態(tài)可咲減少為2個狀態(tài)：A.Cj/BLfDhA作為狀態(tài)代表，最小化后的DFA為：實用文案2)(b a | a)NFA為:使用子集法進行確走化，并對狀態(tài)重新進行命名（A,氛C”1abn *1,2,4233 C*2.43C c2r4DFA如下團所示:態(tài)代表，最小化后的DF血為:儀旺u2.寸 一A屈扯 XBVTA丘 gp 尿屁地”點期不八丘轡 pum 屈班芝冠aq個八住理7X4-aspga-v3BTE 個詁5呆55*!*削-旱LdLO個山二LU)個 52qsT8JBW-U5J、5aSTca的T-Tb | b: bbfc根據(jù)產(chǎn)生式，可求得該文法中各非終結符的FIRST集和

17、FOLLOW集如下所示:產(chǎn)生式FIRST 集FOLLOW 集SAB(a, Uc#A-aAb | Eab,cBbB | cb(c#根揚產(chǎn)生式，可求得該文；去中各非終結符的FIRST集和FOLLOW集如下所示:產(chǎn)生式FIRST 集FOLLOW 集2 aAbDe | dgd #, af e A- BsD | ea, cfd, e,sbB- Sac | cD | eardtcsD 今 Se | Eard bF e,s4.4根據(jù)文法的各個產(chǎn)生式 可求得FIRST ft. FOLLOW集和SELECT集如下所示:產(chǎn)生式FIRST 集FOLLOW 集SELECTS-eTe#eS-RTd, aP bf s如b

18、T-DRWb#afbT-e#RdRddR-Ela.b,#DWaId,#aHbdbb由于每一非終結符的各個候選式的SELECT集互不相交，所以該文法為LL(1)文法.4.5根據(jù)文法的各個產(chǎn)生式，可求得FIRST集、FOLLOW集和SELECTajOTS所示：嚴生式FIRST 集FOLLOW 隼SELECT 集aFbr #他a,bR #a-bca,b,#a,bP #6-a2g#aikSC-bbttbC-#該文法的同一非絡結符的各個產(chǎn)生式的可選集的交集如下；SELCnB-a)n5ELECT(B)=SELECT(Cb)nSELECT(C 根擔LL文建的定義可知，該文法杲一個L1文法亠(2)構造的LL分

19、析表対:ab#sS-A#S-A#AA-BCA-BCABCBB-aB-Cc-bSe4.6消除左遞歸后的文法為：5F | (T)TsrTTsr | 對消去左遞歸后的文法求FIRST集s FOLLOW集和SELECT集:產(chǎn)應FIRST 集FOLLOW 集SELECT 集S-aa骷)a5)(t-star()1()T%sr-0)TW)根據(jù)SELECT可得到消去左遞歸后文法的L中吩析表知a(rSTT-STFT-STrTTTwTyr由于同一非終結符的各個候選式的可選集互不相交所以該文法為LL文法標準文檔4.7由于該文法存在公共左因子，所次該文法不是LL文法改寫文法為:S-NSr今 |EE9SEETe I +

20、E改寫后文法與原文法等價且是山1文法。(2)由干該文法存在直接左遞歸，所以該文法不是LL文法。 改寫文法為：A今BNaUba, | eBnC0F | E| DD-(A) | i改寫后文法與原文法等價且是LL文法。4.8(1)與GA等協(xié)的文法甲偽:A-aArATAbe | 0-IBr實用文案:銖昨i鮑陰加(323e,92q島q啟pp用pzp-#M23e,v盯eaflVVe(PJ#)eev13313S蕭 MCmCHiglSHH:土昂丄呼毒丄RUS血零MOllOd赴來巨f竿玉睪心號劭因*BX1W標準文檔aedbAA-aAfXA?-ABe心eA%BB1Bf-eBTbB諭入串日3d餅的分析過程為:步驟分

21、析棧余留輸入串所用產(chǎn)生式1#AaadettA-aA*2#Araaade#3#Arade#AABe4ffeBAa de#A-aA55tteBAaade#6ffeBAde#Af-7#eBde#8#eBrddetf9#eBr曲B510#e11分析成功4.9各個產(chǎn)生式的Fl RST集、FOLLOW集和SELECT集如下:產(chǎn)生式FIRST 集FOLLOW 集SELECT 集SaBc(a)#aS-bABbbA-aAbaW#aA-bbbBbb訂b)B今EC,#根g SELECT可得到LL分析表為:abc#sS-aBcSABAA-aAbA今bBB-b符號串bab的分析過程為:分析桟余留輸入串所用產(chǎn)生式1#Sb

22、abbbttS-bAB2#BAbbabbb#3#BAabbb#A-aAb4#8bAaabbbff5ffBbAbbb#A-b6#Bbbbbb#7帕bbbti8b#B-b9#b10分折成功由上述分析過程可知符號串babbb為該文進的句子,4.10各個產(chǎn)生式的FIRST集、FOLLOW集和SELECT集女嚇:產(chǎn)生式FIRST 集FOLLOW 集SELECT 集S-TPa,c a(c P-aSa代bap*優(yōu)bT-QRa,c(aA#Ja-cR-Taca, b, #(a,cR今E町a(chǎn)f bF #QaSbaaQ云cc根據(jù)各個產(chǎn)生式及其SELECT集可寫出遞歸下降分析程序如下:實用文案王朗數(shù)：scan;cal

23、ls；if tokens then accept; else error;MS:if token in ayc then call T;call P;else error;ffl&T:if token in a.c then call Q;call R;else error;MP：If token = 8then match(a); call S;else if token in b# the n return;標準文檔函數(shù)Q：if token = 8then match(a); call S; match(b);else if token = V then matchc);else erro

24、r;函數(shù)R：if token In afcthen call T;else if token in a,bR# then return;else error;4.11各個產(chǎn)生式的FIRST集、FOLLOW集和SELECT集浚嚇:產(chǎn)生式FIRST 集FOLLOW 集select集S-AaB(aftg#a.f,gS-Bb:d,已 bd,eFbA-aDaaaA-Dtgf,gB今dMb,#JdB去eBEE際 JD今fDfafMgg根據(jù)各個產(chǎn)生式及其SELECT集可寫出遞歸下降分析程序如下:標準文檔王國數(shù)：scan：call s;rf token = then acceptelse error;購數(shù)S:

25、rf token in a, frgthen call A;matchf a); call B;else rf token fin d,巳 b then call B;match) b);else error;函數(shù)A：if token = *afthen match(a);call D;else rf token in fPg then call D;else error;標準文檔的數(shù)B：if token 二 7Tthen match(d);else rf token 二 JeJthen match(e);else tf token in b,#then return;else error;函

26、數(shù)D:if token = Tthen match(f); call D;else if token -創(chuàng)then match(g);else error：4.12S-aAbA-aAb | eS-OA11AOAll | SaAbA-bAb | a實用文案標準文檔實用文案5.1句子嚴i的分析過程為:步驟分析棧內(nèi)容余留諭入串動作1#-i+i*i#移進2i+i*i#移進3#d+i*i#用Li歸約4# F+i*i#用F-F歸約5#F+i*i#用Tf F U醪6#T+i*i#用Ef T朋7#E+i*i#移進8#E+產(chǎn)i#移進9#E+I*i#用F-i歸約10#E+F用TF歸約11#E+T*itt移進12#

27、E+T*i#移進13#E+T*I#用F-i歸約14#E+T*F用Tf T芥歸約15#E+T用Ef “T歸約16#E#接受5.2TFJ5語：F, Ft, FFtS 無 FFt*a* 直接短語：F, Ft , a 句柄：F最左素短語：F t5.3ETF 11TFFPfPpIII(1) 句子 i f (i+i)的短語為：il, D(R)1)R-R;P | Pd i, (i）P-S | 1b G(b )1D今iii（2）該文法的算符優(yōu)先關系表為:ff()Ji(-5.5根據(jù)各個產(chǎn)生式，可以得到FIRSTVT集 LASTVT集如下表所示：電式FIRSTVT 集LASTVT 集s-bAbbbA-B 1 aI

28、 aa, (, 0-Aa)(, a)該文法的算符優(yōu)先關系表為:b(aIb=(二)#=. SaP 1 P4 b, 5 d4 b, J dP- PbQ | Qb，s dc, d| d仙d d該文法的算符優(yōu)先關系表為:abcd#abcd步驟符號棧輸入串優(yōu)先關系動作1dacbd#d移進2#tacbdff# a用Q今d歸約3ffQacbd#na移進斗#03cbdtta c移進5畀Qacbd#a b用Q譏歸約6ffQaQbd#a b移進7#QaQbd#b dP移進8ffQaQbd#bd 9菸119#QaQbQ#a #用PPbQ歸約ID用SSaP歸約11#5#接受5.7豐艮據(jù)旨個產(chǎn)主式,可以得到Fl RST

29、VT集和LAS1VT集如下表所示;產(chǎn)生式Fl RSTVT 集LASTVT 集5 1 (T)4(他）T-SJ | Sa. (=J#由算符優(yōu)先關系表可見，丈去中f壬訶一對終結符之間至務只滿足一種關系, 所以該文法為算符優(yōu)先文法。(2)句子(仙叭可的算符優(yōu)先分析過程為:符號棧輸入串優(yōu)先關系動作1(fa； a), a#(移進2(3/ ab a#(移進3a#(a移進4#(a；a), a#(.用5-a朋5(S、a)7日胯c移進5ah atfr8移進7ab酈,)用 Sa Jl3g5砒()用T*T歸約3(Tb確(=)移進10#(mj a)#(,用(T)歸約11#(S,a)#(，移進12#(S,a#,a移進13

30、#(S, a憐r)用宀I喲14#(S, 5(|用TSJ歸約15#(T(=)移進16#(T)#fr用5今歸約17ffS接受句子阿亦可的規(guī)范歸約過程為:步驟分析棧內(nèi)容余留輸入符號串動作1#(a ? 3)，a)#移進2ff(歸ah耶移進3#(4 ab a)#移進4、ab用5歸約5*l(s7 ab訓移進6帕a) a)#移進7#(S, a),a#用宀歸約8#(S, sb砂用丁冬歸約9帕T),a J#用WT歸約10制Th a J#移迸11如用S-T）歸約12#(S,at#移進13訓移進14#(S aJ#用Sa歸約15#( S艸用T*歸約16#(S TJ#用T-SJ歸約17#(T-移進18fl(T)用“歸約

31、19#S接受5.8(1)vi, i： r的規(guī)范推導為(為了區(qū)分，特將I進行編號為k、h)：S =vl: T =v I: r =vlj b: r =v ii, b: rR)句子vi, i： r的崽語為：h, i八、vi1? i2： r句子vij i： r的句柄為:ii句子vl, I: r的素短語為；k、r(3)根據(jù)各個產(chǎn)生式，可以得到FIRSTS集和LASTVT集如下表所示:產(chǎn)生式FIRSTVT 集LASTVT 集VI: Ty：，b Cl-b i | ih iT-r | c. cfrj c該文5去的算符優(yōu)先關系表為:Vrrc#VA =irc#二(4)句子心的算符優(yōu)先分析過程為:步驟符號棧輸入串優(yōu)

32、先關系動作1vij 1： r# V移進2#vG i：井v i移進3Wi,i： 甲v f用1今i歸約4#vl,1: r#移進5#vbi： r#,=i移進6#vl, i:Zv:用19歸約7#vli r#V -:移進3#vl :#:用“ r歸約10#vh T用Wvl: T歸約11#s接受5.9(1)根據(jù)各個產(chǎn)生式,可嘆得到FIR5TVT集#口 LA5TVT集如下表所示:產(chǎn)生式FIRSTVT 集LASJVT 集5今CAic仙bA- a Ab | c(flj c4 C(2)該文法的算符優(yōu)先關系表為:cabcab-(3)由算符優(yōu)先關系表可見，文法中任何一對終結符之間至多只滿定一 種關系，所以該文法為算符優(yōu)

33、先文法。儀旺u靜靜UV ttH3VOmVCDVraq A u V mq1003q A q11 ru Veq II p站A o V冊4t 霄 o年_g看qq*o|r#U0 um (Do心toit e Q 并nittcA5 A-d6 B-c01 B-d$-.Eb：A今匚上E-.aAA-xAbeMS-*EkAd.lliE-a.AbiE-*bB.A-.CAh：日去EA-.dh：EbJB-.dB今上Bn；B-d.B-.dha：A-cA.h；EaA 0-HBbLR(O!(分析表為:MSATORACTIONGOTO9cE4e0軌寂1Iacc25sSfi43知烏74r2r2r2r2r25$sS106r5r5r5r5r57r3r3r3t3S知務ii9r7r7r7r7r710r4r4r4r4r411r6rfirflf66acccd的井折過程；歩議n編入卑動隹下一嚇狀態(tài)10$12012S53Qa2cSccd#S540b2c55cd#S5$0)c5c5cS撫6(JiZc5c5e5d&*rsGOT0(5,A)=1O7Od2tSt5tSA10#GOT