1、1.1翻譯程序以某一種程序設計語言所編寫的程序作為翻譯或加工的對象; 將它翻譯成與之等價的另一種語言的程序。高級語言雖然優越，但計算機硬件卻只懂得自己的指令系統，即只能直接 執行相應機器語言格式的代碼程序，而不能直接執行用高級語言或匯編語言 編寫的程序。因此高級程序設計語言需要翻連程序，將其翻程成為計算機能 理解與執行的機器語言的程序。1.2編譯程序解繇程序：從高級語言到機器語言或匯編語言的翻譯程序。編譯程序：產生目標程序，然后再執行目標程序，可以反復執行。解釋程序：不產生目標程序，逐句翻怪執行，只葭執行一次，若需重新 執行，則必須重新解釋程序。1.3(1)通常一個編譯程序由詞法分析、語法分析

2、、語義分析、中間代碼生 成、代碼優化、目標代碼生成出錯管理和符號表管理人音盼組成。( 2)各部分的任務：詞法分析：從左到右逐個字符的讀入源程序，按照源語言規定的詞法規 貝山對構成源程序的字符流進行掃描和分解，從而識別出一個個直詞，并把 他們表示成機內單詞形式。語法分析：根據'源語言的香法頰則把電運I序列分解成各類語法單位，井指出其中的語法錯誤。語義分析：分析各語法成分的含義和I力能，即它們的屬性或在執行時應 進行的運算或操作。中間代碼生成：在語法分析和語義分析的基礎上，木睡語法成分的語義 對其翻侄，翻徑成在語義上等價的中間代碼的語言。代是I優化：對代碼進行改造變換，目的是使生成的目標代

3、碼更為高效，即省時間和省空間。目標代碼生成：轉換為等價的目標代碼。出錯管理：負責發現源程序中可能出現睇音誤，并把錯誤報言給用尸， 指出錯誤的性質和發生錯誤的位差。符號表管理：記錄源程序中使用的標識符和每個標識符的各種屬性，以 便后續的工作中進行使用。1.#編考程序的組織方式有3種；（1）遺霜組織方式，即將編徑過程劃分為六個階段，貫穿始終的是符號表管理和出錯管理。（2）編譯過程分為前端和后端兩個部分：前端主要依賴于源語言，它由 幾乎獨立于目標機器的階段或階段的一部分組成。后端是編譯器中依賴于目 標機器的削分，它一般獨立于源語言而與中間語言有關。（3）采用“分遍”的形式，即編停過程可以由一遍或多遍

4、耒完成。（遍: 在編怪過程中，對源程序或其等價的內部表示從頭到尾掃視，并進行相應的 加工處理，進而完成規定任務的過程稱為編注的一遍）2.1<1>最左推導：(De=>T=>F=>i e nT=F=(E)n(T)n(F)n(i) E =>T=>T*F=> F*F => i*F>i*i E =>E+T =>T+T >F+T i+T =>i+T*F =>i+F*F =>i+i*F =>i+i*i E =>E+T=>T+T nF+T =>i+T ni+F =>i+(E) =>

5、;i+(T) n i+(T*F)=>i+(F*F)ni+(F*=F) =i+(產 F) =>i+(i*i)© E =E+T=T+T nT/F+TnF/F+Tni/F+T =>i/i+T ni/i+T/F =i/i+F*F=i/i+i*F<2>最右推導： E=T = F=iE=>T=>F =(E)=>(F) =(»® E>T>T*F>F*F>F*i=>i*i E 今 E+TnE+T/F 今 E+T/i 今 E+F/i =E+i/i 今 T+i/i =F+i/i 今 i+i/i E =E+T

6、nE+F = E+(E) = E+(E+T) = E+(E+F) = EHE+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*i =T/F+產i=>T/i+i/i =F/i+i/i => i/i+i/i<3>語法樹:FF2.2此題答案不唯一，正確即可。S40S | 1AA 0 0A | £S- aS I bA I £bA | cC | £CT cC

7、 | £S-aS | eS->OA | IBA50S | IC | 0BT1S | OC | 1SOB | 1A2.3此題答案不唯一，正確即可。S-aAbCAT a Ab | £«cC | £ST ISO I 1A0A->OA1 | 01SOIAA 玲 1A1 | 0S9D1A|D2a->d3a|d2D1|2|3|4|5|6|7|S|9D2->2|4|6|8D30|l|2|3|4|5|6|7|8|92.4(1)終結符：a、(、)非終結符：S、L開始符號；S(幻U (，)Ck(e) u (sis) <=(ele1s1,(-1

8、)/ s'、/(1/ s(忖 u -) <=U二(s)。)u (Ci)，)<= (sR u h) us可 u (ezs) <= El) aS，)<= (1) us(V) Re)忖 u (寸)<=Ki-e)u=S(i) u (s4) u (5，)u <1) US3)u (S,e) u (szs) u (s'l) u m us(£) e1Se1】)el/I/(1) /s(1) (Ds => aSbS => aSba bSaSba bSa ba ba bS=>aSbS =>aSbaSbSaSbaSb => a

9、Sbab => abab由于句子abab存在兩種不同的最右推導，所以該文法為一個二義性文 法。（2）SnaSbS =>abS =>abaSbS =>ababS =>abab S=aSb3 =>abSaSbS => a ba SbS => a ba bSa ba b由于句子abab存在兩種不同的最左推導，所以該文法為一個二義性文 法6 由于句子abab存在兩棵不同的語法樹,所以該文法為一個二義性文法.2.6根據1型文法的定義可知該文法為1型文法。2.7（1） U=a'b;cjdj | XL j>=0（2）L2=b'aa | i

10、>=0（3）由。-9組成的任意長度的數字串（4）U=arnbrn | m>=l#.8(1) P=S->ABS | Aa | E, A3a,B-b(2)最左推導：SnAB§ naBS =>aSBBS =>aBBS =>abBS =>abbS =>abbAa =>abbaa最右推導：SnABS =>ABAa z> ABaa ASBBaa ASBbaa ASbbaa =>Abbaa zz>abbaa2.9生成該語言的文法為GS：SABAaAd | DDbDc | beBBe | ee2.10例如對于句子a be

11、；OSnAB 今aBnabc S = DC =abC = a be由于句子abc存在兩種不同的最左推導,所以該文法為一個二義性文法。3.1(1)正規式為：3二0+|0口 有窮自動機為：(2)正規式為：S=aaqbc).有窮自動機為：3.2(1)狀態轉換圖為:(2)右線性文法為：(a)SlB | 0AAflA | OBB*OB | IB(b)SlB | CAA->1A | OCB今OB | ICC今 OC | IC(3)以1開頭，由0、1組成的教字串；或以。開頭，至少包含兩個。的由。、1組成緘字串。(b)以0開頭，至少含有2個。的由0、1組成的數字串；或以1開頭,至少含有2個1的由0、1組

12、成的數字串。3.3（1）以b開頭和結尾的由a、b組成的符號串，列舉四個較短的句子為：bbx babx bbbs babb©（2）以aa、aab、aba. abb結尾的由a、b組成的符號串j列舉四個較短的句子為；aaa、aabx abax abbo（3）含有2個。的由0、1蛆成的符號串；列舉四個較短的句子為;00、100、010、001。（4）以。或1結尾的前面由若干個。1組成的符號串j列舉四個較短的句子為:0、1、010、011.3.4使用子集法進行確定化，并對狀態重新進行命名（。、1、2、3）:01=> *S,A,B0A,B,C1A,B2(AEG1ABC13A,B2ABC1A

13、,B2*A,B2T)3ARC1A,B2確定化的有窮自動機為；3.7使用子集法進行確定化，并對狀態重新進行命名（以B、C、D、E）:-01=> *1A2,4 B2,4B5,6 D3C3 C1 A*5,6D0*6E E確定化的有窮自動機為：（1）將該狀態轉換圖用狀態轉換矩陣表示:字符01n 5AABDBCCBD*DBD使用最小化算法后，5個狀態可以減少為3個狀態:5,B,A,C,D*取£A作為狀態代表,畫出的最小化的DFA為：（2）將該狀態憑換圖用狀態轉換矩陣表示:符ab0*123*2234*423使用最小化算法后，四個狀態可以減少為三個狀態； 畫出的最小化的DFA為：與正規式2口

14、七十名也：1）等價的有窮自動機為：3.8正卻式：1（0|1）*00NFA如下圖所示:使用子集法進行確定化，并對狀態重新進行命名（1、2、3、4、5）:1010同1BCD)22(C,D,E)3%,D)4C,D,E)3C,D,E,F 5CD4CD4C,D,E3CD4*C,D,E,F)5C,D,E,F 5C,D4DFA如下圖所示:使用最小化算法后,5個狀態可以減少為4個狀態：1,億4,3,5,以2 作為狀態代表，最小化后的DFA為：3.11文法G對應的自動機為:該自動機是不確定的6使用子集法進行確定化,并對狀杰重新進行命名（A、B、C）:101=RAABG汝B2C*A,S )CA,SCA B則DFA

15、如下圖所示:使用子集法進行確定化,并對狀態重新進行命名(1、2、3、4、5、6、7”101=S1AfB2B,C3A,B2A,B,C,D4B5B,C3A,B,C6B,D7* ABQD4A,B,C,D4B,D7間5A,B,C6B5ABC6A,B,C,D4B,D7*BrD )7A, BCD4B,D7DFA如下圖所示:使用最小化算法后,7個狀態可以減少為6個狀態:口,包,，,14,7), 以4作為狀態代表，最小化后的DFA為：(1) (a | b) .的 NFA為:使用子集法進行確定化并對狀態重新進行命名6、B）:1ab=L2,32,3 B2,3 B*2,32,3 B2,3 BDFA如下圖所示:使用最

16、小化算法后，2個狀態可以服少為1個狀態；以A作為狀 態代表,最小化后的DFA為:(2) (a |b)Ma(a | b)的 NFA 為:使用子集法進行確定化，并對狀態重哥進行命名（1、2、3、4、5）:1ab=1232342,3312,3,42,3,41542,3,552,32,3,42,33*234 5234,5 42,3,55*2,3,5)2,3,42,33（4）0門）廣101可簡化為（0 | 1） <101,它的NFA為:DFA如下圖所示:使用最小化算法后：5個狀態可以減少為4個狀態：1國2/,;以1作為狀態代表，最小化后的DFA為:(3)10 I (0 I llltTl 的 NFA

17、 為:使用子集法進行確定化,并對狀態重新進行命名（1、2、3、4）:101*1324332岱 2542,435432*540DFA如下圖所示:該圖已為最小化的DFA。使用子集法進行確定化，并對狀態重新進行命名（Ax B、C、D、E）:1011,2,3)2,32,3,4 C2,32,32,3,4 C234(2,3,5 D234 C2352,3 B2346)12,3,5 D億3,處 CDFA如下圖所示二使用最小化算法后，5個狀態可以減少為4個狀態：4見C,D,E, 以A作為狀態代表,最小化后的DM為：(2)(ba | a) NFA為:(a | b)D 的 NFA 為;使用子集法進行確定化，并對狀態

18、重藥進行命名（以B、C、D>:1ab=123 A2,3,42,3c234 B234,52,3c2,3 C23,42.3c*(234,5234,52,3cD FA如下圖所示:使用最小化算法后，4個狀態可以減少為3個狀態；A,C,B,D,以A作為狀態代表，最小化后的DFA為；使用子集法進行確定化并對狀態重新進行命名（A、B. C）:1ab=*1242,4 C*2,4億4 C3 C2140DFA如下圖所示:使用最小化算法后, 3個狀態可以減少為2個狀態：ArBHC,以A作為狀態代表,最小化后的DFA為:4.1(1)SlaAS'SbAS'leA少BeBSb(2)S3(E)|iEW

19、E3+SESElw(3)S 今 AS'SaASjbSjEAABcA|BBdSe|f(4)程序begin語句表end語句表玲語句 語句表 (語句表沙玲;(語句x語句表小語句4.2步騷推導過卷所用產生式號翰人串1Stfafbf#2SaA(1)tfafbf#3AaA(1)cfafbf#4QaA(2)tfafbf#5cRaAcfafbf#6cfaA(4)cfafbf#7cfaAbQ(2)cfafbf#8cfaQbQ(2)cfafbf#9cfaRbQcfafbfi#10cfafbQcfafbftf11cfafbR(3)cfafbft112cfafbfcfafbft根據產生式，可求得該文法中含非終

20、結符的FIRST集和FOLLOW集如下所示:FIRST 集FOLLOW 集SaSTca#,bT玲Tb | b3bfc根據產生式，可求得該文法中各非終結符的FIRST集和FOLLOW集如下所示:產生式FIRST 集FOLLOW 集SABa,b,c#AT a Ab | £3b,cBTbB | cb,c#(3)根據產生式，可求得該文法中各非終結符的FIRST集和FOLLOW集如下所示:產生式FIRST 集FOLLOW 集ST aAbDe | da,dAT BsD | ea, c, d,巳 sbB玲 Sac | cD| ea, d, csDTSq 1 £a,d b, e,s)4.#

21、根據文法的各個產生式，可求得FIRST集、FOLLOW集和SELECT集如下所示;產生式FIRST 集FOLLOW 集SELECT 集SeTe(«eS->RTdF a, b, £)d, a,bT9DRa,b【#】a,b£#)R->dRda, b, #dRe£a, b, # D-a(a)於aDfbdbb由于每一非終結符的各個候選式的SELECT集互不相交所以該文法為LL(1) 文法。4.5(1)根據文法的各個產生式，可求得FIRST集、F0110W集和SELECT集如下表 所示：產生式FIRST 集FOLLOW 集SELECT集S3A#a, b

22、, #a, b, #A3BCa, b, w#a, b, #B3aab,#aB3w£b,#CTbb#bC3w£#該文法的同一非終結符的各個產生式的可選集的交集如下;SELECTa)cSELECT(BTw)=SELECT(Cb)nSELECT(C£)=根據LL文法的定義可知，該文法是一個LL文法。構造的LL分析表為：ab#sSTA#STA#STA#AABCA3BCAf BCBBaB->eBTwCCTbC-»E4.6消除左遞歸后的文法為，Sa | (T)T9ST'Tf ST | E(2)對消去左遞歸后的文法求FIRST集、FOLLOW集和SELE

23、CT集;產生式FIRST 集FOLLOW 集SELECT 集S玲aa他，)aS(T)(11(】T玲ST卬)a,()r),sr-I) Jr£(£0根據SELECT集，可得到消去左遞歸后文法的山1)分析表為:a)j#sST aSTTTTSVTTST'TT'T£fST由于同一非終結符的各個候選式的可選集互不相交，所以該文法為LL文法。4.7(11由于該文法存在公共左因子，所以該文法不是LL(1)文法。改寫文法為：SNSZS8 |舊ETSE'E | +ENTi改寫后文法與原文法等價且是LL(1)文法。由于該文法存在直接左遞歸，所以該文法不是LL文法

24、。改寫文法為:A 玲 BA'AUBAr |£3 玲 CB'BfcCB' | ED | DD訓I i改寫后文法與原文法等價且是LL(1)文法。4.8(1)與GA等價的LL文法G卬為：A玲WAAbe | £BdBrB'TbB' | £根據各個產生式,可求得FIRST集、FOLLOW集和SELECT集如下所示:產鈣FIRST 集FO山DW集SELECT集ATMa#,daAf->ABea牝dA8任禮dBdB1d«dBbB7bebB8£e(2)GW的預測分析表為二aedb#AA-A'A，A'A

25、BrA8A”BB9dBB"B-bB'輸入串aade#的分析過程為：步驟分析棧余留愉入串所用產生式1aade#A-A'2#Azaaad&#3*AradeffA-ABe4件eBAadeffA->aAr5ffeBA'aadeff6#eBA'de#A-7#eBde#B9dB'8#eBrdde#9#eBrNtB810#ee*11#分析成功4.11各個產生式的FIRST集、FOLLOW集和SELECT集如下:產生式FIRST 集FOLLOW 集SELECT集S->aBca#aSbABbbA3aAbaaAb(bbB 9bbfc,#bBe&

26、#163;C, #根據SELECT集,可得到山1）分析表為:abc#sSaBcSTbABAA->aAbA)bBBfbBeB£符號串babj班的分析過程為；步驟分析棧余留輸入串所用產生式1#sbabbbffS->bAB2#BAbbabbbff3#BAabbb#A->aAb4#BbAaabbb#5#BbAbbb#Ab6#Bbbbbb#7#Bbbt>#8b#BTb9#bbit10#分析成功由上述分析過程可知符號串babbb為該文法的句子。各個產生式的FIRST集、FOLLOW集和SELECT集如下;產生式FIRST 集FOLLOW 集SELECT集3TTPa,c禮b

27、a,cPaSa#,baPH4用bT9QRai a, b, # 4cR玲Ta,ca, b, # a,cR£E孤 b, #Q 玲 a5b(ala, c,b,#aQTccc根據各個產生式及其select集可寫出遞歸下降分析程序如下:主函數：scan;calls；if token#' then accept; else error;函數s：if token in afc then call T;call P;else error;函數T;if token in a.c then call Q;call R;else error;函數P:if token = Hthen match(a

28、);call S;)else if token in b,# then return;函數Q：if token = Hthen match(a);call S;match(b);)else if token = Y then match(c);else error;函數R：if token in a,cthen call!;else if token in a.b,# then return;else error;4.11各個產生式的FIRST集、FOLLOW集和SELECT集如下:產燈FIRST 集FOLLOW 集SELECT集SAaBi a, f, g 5玲Bbd, e, bH e,bAa

29、DaaaATDtgtgBTddb,#dBe©B牝£b,#D->fD門a*DTggg根據各個產生式及其SELECT集可寫出遞歸下降分析程序如下:主函數；scan;call s;if token = #then acceptelse error;函教s：if token in a, ffgthen call A;match(a;call B;else if token in dr er b then call B;match (b);)else error;函數A：if token = Wthen match (a);call D;)else if token in f,

30、gthen call D;else error;函數B：if token =廿then match(d);else if token = /e/then match®elseif token in b,#then return;else error;函數D：if token = Tthenmatch(f);call D;else if token =then match(g);else error;4.12(1)S-aAbA->aAb | £ SOAllAOAll | £ S->aAbA玲bAb | a5.1句子的分析過程為；步驟分析棧內容余留輸入串動

31、作1件i鏟仰移進2#-n-rw移進3樸i+產-用f歸約4.#-F+產褥用i-F歸約5件F用Tf F歸約6#T+i*W用ET歸約1柢鏟iff移進a抖E+移進9#E+i*i«用Li歸約10#E+F用F歸約ii*E+T力并移進12并E+T*iff移進13#E+T*i#用Ff i歸約14井E+T*Fft用T-*T*F歸約15#E+T#用Ef E+T歸約16杞件接受FF5.2趣語:艮 F3 FFt % a, FF1 直接短語；I, Ft, a句柄：F最左素短語：F t5.3EET I FI p I i2(1)句子 it TD 的短語為:0 S3, 62+i3, (i2+i3), iT 個(i2

32、33);素短語為:il, i2, i3o句子 i/i*(i+i)的短語為:il, i2, i3 , i% il/i2,臥 14, (i3+i4), il/i2*(i3+i4)； 素短語為：il, i2, i3, i4o(3)句子T+T*FRi 的短語為：T, T*F, F> i, T+T*F> F/i, T+T*F-F /i ;素短語為:素F, i。(1)根據各個產生式j可以得到FIRSTVT集和LAS1VT集如下表所示:產轉FIRSTVT 集LASTVT 集ST#S#)#S->D(R)心i)RTR;P | P;, b o1 i, )P玲 5 | ii, (缶)Dii(2)該

33、文法的算符優先關系表為;#().i并<<(<<<)>>><>><i>>5.5根據各個產生式，可以得到FIRSTVT集和LASTVT集如下表所示：產生式FIRSTVT 集LASTVT 集S3bAbbbAf(B | a(, aa, (, )BTAa)(； a)該文法的算符優先關系表為：bai#b<<>c><>a>>>)>>><<<二由算符優先關系表可見，文法中終結符（與a之間滿足兩種關系，所以該文 法不是算符優先文法。5.6C

34、l）根據各個產生式,可以得到FIRSTVT集和LASTVT集如下表所示:產生式FIRSTVT 集LASTVT 集Sf SaP 1 P缸 b, Cj d)缸 b, J d)P-> PbQ | Qb, c, db, c, dQfc | d匕叫匕d該文法的算符優先關系表為:abcd律a><<<>b>><<>c>>>d>>>#<<<<(2)步驟符號棧輸入串優先關系動作1存dacbdff#<d移進2tfdacbdff# < d > a用Qfd歸約3存Qacbd#

35、<a移進4#Qacbd#a<c移進5#Qacbd#a <c> b用Qfc歸約6#QaQbd#a <b移進7#QaQbd#b< d移進8#QaQbd#b< d >#用QTd歸約9SQaQbQa < b>#用PfPbQ歸約10#QaP#<a>#用STSaP歸約11#3#接受5.7(1)根據各個產生式，可以得到FIRSTVT集和LASTVT集如下表所示：產生式FIRSTVT 集LASTVT 集ST a |(T)a, (a, )T3S,T | S, a, (, a, )該文法的算符優先關系表為：a()#a>>>(

36、<<二<)>>>><<><>#<<<=由算符優先關系表可見，文法中任何一對終結符之間至多只滿足一種關系, 所以該文法為算符優先文法。（2）句子（a, a）, a）的算符優先分析過程為:步驟符號棧輸入串優先關系動作1#(a, a), a)#<(移進2#(a, a), a)#(<(移進3#(a； a）；那(<a移進4#(a,a), a)#(<a >,用ST a歸約5#(S,a), a)#c< ,移進6#(S,a), a)#><a移進7#(S> a)，a)#

37、,<a >)用ST a歸約8#(S, s)，a)#(<,>)用TTS,T歸約9#(T)，a)#(=)移進10#（仃）沖(<(=)>,用ST歸約11#(S,a)#(<,移進12a)#,<a移進13#(S,a掰z<a >)用ST a歸約14#(S, s琳(<,>)用TTS,T歸約15#(T琳(=)移進16#(T)#<(二)>#用ST歸約17#s#接受句子俏，可，部的規范歸約過程為:步驟分析棧內容余留輸入符號串動作1#( a), a)#移進2#(a, a), a)#移進3#(a, a), a)#移進4#(a>

38、a), a-用Sa歸約5#(S,a), a)并移進6明a) 3 a)#移進7#(6),a)#用Sa歸約8#(忤S卜a)#用T9S歸約9#(忤T匕a)#用TTS,T歸約10#(T),a#移進11視,a)#用ST(T)歸約12蚱,a)#移進13#(5,a)#移進14#島a肉用Sa歸約15#(5,S用用T9s歸約16電T沈用T3S,T歸約17制T移進18町)#用ST(T)歸約19#s#接受5.#(1)vi, i： r的規范推導為為了區分，特將i進行編號為ij、ij：S=>vl ： T =>v I： r =>vl; i2： r=vi” is： r(2)句子vi, i： r的短語為:八

39、j i2、r、vV h： r句子vb i： r的句柄為：ii句子vi, i： r的素短語為：限r(3)根據各個產生式，可以得到FIRSTVT集和LASTVT集如下表所示:產生式FIRSTVT 集LASTVT 集Svl: TM匕 r, c-1, i |i，iiTf| ckC)匕c該文法的算符優先關系表為；V9. 1rc#V=<<>. .<<>>>>>r>c>并<<<<<<句子vi, i； r的算符優先分析過程為;步驟符號棧輸入串優先關系動作1#v i, i: r # V V移進2#vi,

40、i： r#v< i移進3#vi> i: r#v< i用-i歸約4*vli:#v<.移進5熱i;存> =i移進6樸八,i:#v< 3 =i > :用H1, i歸約7#vl:r#v=:移進8#vl：r#:<r移進9#vl： r#:<r>#用”歸約10#vl: T#<v =:>#用ST VI; T歸約11#5接受5.9(1)根據各個產生式,可以得到FIRSTVT集和LASTVT集如下表所示:產生式FIRSTVT 集LASTVT 集ST CAC勖bA-> aAb | ca' cb, c(2)該文法的算符優先關系表為:

41、cab并c<>>a<<>b>>件<<<(3)由算符優先關系表可見,文法中任何一對終結符之間至多只滿足一 種關系,所以該文法為算符優先文法。(4)句子caacbb的分析過程如下：步驟符號棧輸人串優先關系動作1caacbb.#<c移進2#aacbb ttc< a移進3#caacbb#a< a移進4#c a aebb#a < c移進5# ca a cbb#a<c>b用A->c歸約6#caa Abb#a= b移進7#caaAbb#a <a = b >b用AT a Ab歸約8# ca

42、Ab#a= b移進9# ca A b杼c<a = b用Af a Ab歸約10#cA#<c>#用SfeA歸約11#S#接受6.1假定該文法是經過拓廣后的，直接對產生式進行編號為:1 SE2 £TaA3 ETbB4 ACA5 A9d6 B->cB7 BTdb：ST.E卜：A->CAE->,aAAfcAE->.bBA，dk：STE.k：A-»d.k-E->a.Ab：E->bB.A->.cAb:Af.db：E今bBB今,dB.cBfc:Bd.B->.dho：一 CA.U:E->aXhi：BcB.IN。分析表為:

43、9ACTIONGOTOabcdEAB0s2S311acc2SsSs43sa5974r2r2r2r2r25S»Sc106r5r5r5r5r57r3r3r3r3r38So%119r7r7r7r7r710r4r4r4r4r411r6r5r6r6r5符號率的酎析過程:步理找輸入率排下T、狀態10accedeS220a2cccd#S530a2cSccd#S54O32C5C5cd#S5SO32C5C5C5d不se6oazcscscsdosrsGOTO(5,AhW7O32C5C5CSA1Offr4G0T0(5,A > 1080d2c5c5A10林r46OT0(5,A)=1090a2c5A40KrdGOTO(2.AM10032AAr2GOTO(O,E)二 1110E1接受6.2(1)對文法進行拓廣并編怎為:0 S'今S1 S*$|S)a 12Sa識別文法知交句激活前設的0FA:S-SSS(S) S-* aS-S- Sf(S)S-S