1、精品文檔精品文檔第一章1 典型的編譯程序在邏輯功能上由哪幾部分組成？ 答：編譯程序主要由以下幾個(gè)部分組成：詞法分析、語法分析、語義分析、中間代碼生成、 中間代碼優(yōu)化、目標(biāo)代碼生成、錯(cuò)誤處理、表格管理。2. 實(shí)現(xiàn)編譯程序的主要方法有哪些？ 答：主要有：轉(zhuǎn)換法、移植法、自展法、自動(dòng)生成法。3. 將用戶使用高級(jí)語言編寫的程序翻譯為可直接執(zhí)行的機(jī)器語言程序有哪幾種主要的方 式？ 答：編譯法、解釋法。4. 編譯方式和解釋方式的根本區(qū)別是什么？ 答：編譯方式：是將源程序經(jīng)編譯得到可執(zhí)行文件后，就可脫離源程序和編譯程序單獨(dú)執(zhí) 行，所以編譯方式的效率高，執(zhí)行速度快； 解釋方式：在執(zhí)行時(shí)，必須源程序和解釋程序同

2、時(shí)參與才能運(yùn)行，其不產(chǎn)生可執(zhí)行程序文 件，效率低，執(zhí)行速度慢。精品文檔尺N zzfe 弟早1 .喬姆斯基文法體系中將文法分為哪幾類？文法的分類同程序設(shè)計(jì)語言的設(shè)計(jì)與實(shí)現(xiàn)關(guān) 系如何？答：1) 0型文法、1型文法、2型文法、3型文法。2)2 .寫一個(gè)文法，使其語言是偶整數(shù)的集合，每個(gè)偶整數(shù)不以0為前導(dǎo)。答：Z SME|BS 1|2|3|4|5|6|7|8|9M |D|MDD 0|SB 2|4|6|8E 0|B3 .設(shè)文法G為：N D|NDD 0|1|2|3|4|5|6|7|8|9請(qǐng)給出句子123、301和75431的最右推導(dǎo)和最左推導(dǎo)。答：N ND N3 ND3 N23 D23 123N ND N

3、DD DDD 1DD 12D 123N ND N1 ND1 N01D01 301N ND NDD DDD 3DD 30D 301N ND N1 ND1 N31 ND31 N431 ND431N5431D54317543175431N ND NDD NDDD NDDDD DDDDD 7DDDD 75DDD 754DD 7543D4 .證明文法 S iSeS|iS| i是二義性文法。答：對(duì)于句型iiSeS存在兩個(gè)不同的最左推導(dǎo):S iSeS iiSesS iS iiSeS所以該文法是二義性文法。5 .給出描述下面語言的上下文無關(guān)文法。(1) L1=anbnci |n=1,i=0 (2) L2=ai

4、bjj=i=1(3) L3=anbmcmdn |m,n=0答：(1) S ABA aAb | abB cB |(2) S ASb |ab精品文檔A a |(3) S aSd | A |A bAc |6 .設(shè)計(jì)一個(gè)最簡(jiǎn)的 DFA M,使其能夠識(shí)別所有的被 3整除的無符號(hào)十進(jìn)制整數(shù)。 答：2|5|80|3|6|90|3|6|91|4|71|4|72|5|80|3|6|91|4|77 .設(shè)計(jì)一個(gè)DFA使其能夠接受被4整除的二進(jìn)制數(shù)。8 .寫出表達(dá)下列各項(xiàng)的正則表達(dá)式。(1)二進(jìn)制數(shù)且為 5的倍數(shù)。(2) 2 =a,b,c,第一個(gè)a位于第一個(gè)b之前的字符串。(3) 2 =a,b,c,包含偶數(shù)個(gè)a的字符

5、串。(4) 2=0, 1,不包含11子用的字符串。(D可以先畫出相應(yīng)的有限自動(dòng)機(jī)：100101BDE1010添加新的開始狀態(tài)S和終止?fàn)顟B(tài)T:1根據(jù)以上自動(dòng)機(jī)，列出以下方程：S=A A=0A+1B+T B=0C+1D C=0E+1A D=0B+1C E=0D+1E解以上方程組： E=1*0D A=0*1B+6T代入C=01*0D+1A代入C=01*00B+01*01C+1AC=xB+yA其中 x=(01*01)*01*00 y=(01 *01)*1代入B=0C+10B+11CB=(0|11)C+10BB=(10) *(0|11)C將C=xB+yAf弋入上式B=uB+vAB=u vA其中 u=(1

6、0) *(0|11)x v=(10)*(0|11)y將 B=iivA 代入 A=0*1u*vA+dTA=(0 * 1u*v) *0*T將 A代入 S=(0*1u*v)*0*T申(0*1u*v) *0*即為所求。(2)該題目理解為：至少有一個(gè) a和一個(gè)b,且a出現(xiàn)在b的前面(可以有問 隔)，則答案為:c*a(a|c)*b(a|b|c)*(3) (b|c)*a(b|c)*a)*(b|c)*(a(b|c)*a | b | c)*(4) (0|10)*(1| )尺K*弟二早TOKEN同時(shí)檢查源程1 .詞法分析器的功能是什么?答：讀源程序的字符序列，逐個(gè)拼出單詞，并構(gòu)造相應(yīng)的內(nèi)部表示 序中的詞法錯(cuò)誤。2

7、 .試分析分隔符(空格、跳格及回車等)對(duì)詞法分析的影響。答：空格、跳格、回車等分隔符號(hào)對(duì)詞法分析不起作用，可以刪除。但是回車符號(hào)可以用 于錯(cuò)誤定位，所以在刪除回車符號(hào)前需要統(tǒng)計(jì)回車的個(gè)數(shù)。3 .給出識(shí)別C語言全部實(shí)型常數(shù)的自動(dòng)機(jī)。答：(+|-1 )(1-90-9*|0)(.0-90-9*|) (E(+|-| )0-90-9*)4 .寫出識(shí)別C語言中所有單詞的 LEX程序。答：L=A-Z | a-zD=0-9D1=1-9%(LL)(L|D|_)* return ;D1D*return (2);+return (3);精品文檔精品文檔第四章1.設(shè)有如下文法GS:S aABbcd |A ASd |B

8、 SAh|eC|C Sf | Cg |(1)求每個(gè)產(chǎn)生式的Predict集。(2)該文法是否為 LL(1)文法？為什么？答：Predict(S aABbcd尸aPredict(S)=#,d,f,a,h Predict(A ASd)=a,dPredict(A)=h,a,d,b,ePredict(B SAh)=a,d,hPredict(B eC)=ePredict(B )=bPredict(C Sf)=a,fPredict(C Cg尸a,f,gLL文法。Predict(C )=g,b(2)由于Predict(A ASd) Predict(A ),所以該文法不是2 .下列描述括號(hào)匹配的文法中，哪些是

9、LL文法？(1) S (SS |S ) |(2) S (S)S |(3) S S(S)S |(4) S (S | S S (S ) |答：(1)不是，(2)是，(3)不是，(4)不是3 .已知文法 GE:E E+T | TT T*F | FF i | (E)請(qǐng)按遞歸下降法構(gòu)造該文法的語法分析程序。答：求產(chǎn)生式的predict集合：predict(E E+T)=i,(predict(E T)=i,(predict T*F)=i,(predict(T F)=i,(由于文法中非終極符號(hào)E 和 T 對(duì)應(yīng)的產(chǎn)生式的predict 集合的交集都不為空，法不滿足自頂向下分析的條件，現(xiàn)對(duì)文法進(jìn)行等價(jià)變換得到如

10、下文法：E TEE +TE|T FTT *FT |FiF (E)求新文法的predict 集合：Predict(ETE )=(,iPredict(E+TE )=+Predict(E )=#,)Predict(TFT )=i,(Predict(T*FT )=*Predict(T )=+,),#Predict(F i)=iPredict(F (E)=(由于以上文法中任意非終極符號(hào)對(duì)應(yīng)的產(chǎn)生式的predict 集合的交集都為空，自頂向下分析的條件，所以可以寫出如下的遞歸下降語法分析偽代碼：所以該文所以滿足Void E() if(token (,i) T();E else Error();void E

11、 () if(token +) Match();+ );T();E ();else if(token #,) ;else Error();void T() if(token i,() F();T ();else Error();void T () if(token *) Matc h( * );F();T ();else if(token +,),#) ;else Error();void F() if(token i) Match( i );else if(token () Match( ( );E();Match( ) ); else Error();4 .構(gòu)造一個(gè)LL(1)文法G,它能識(shí)

12、別語言L:L= | 為字母表上不包括兩個(gè)相鄰的1 的非空串，其中=0， 1。并證明你所構(gòu)造的文法是LL(1)文法。答：A 0E | 1FB 0E | 1FC 0EE B IF C IPredict(A 0E)=0Predict(A 1F尸1Predict(B 0E)=0Predict(B 1F尸1Predict(E B尸0,1Predict(E )=#Predict(F C)=0Predict(F )=#對(duì)任意非終極符號(hào)對(duì)應(yīng)的產(chǎn)生式的predict集合的交集都為空，所以該文法是LL(1)文法。5 .已知文法 GA為:A aABe|aB Bb | d(1)試給出與GA等價(jià)的LL文法G A(2)構(gòu)

13、造G簡(jiǎn)LL(1汾析表并給出輸入串a(chǎn)ade#的分析過程。答：所求G A的:AaA(1)AABe(2)A(3)BdB(4)BbB(5)B(6)Predict(A aA )=aPredict(A ABe)=aPredict(A )=#,dPredict(B dB )=dPredict(B bB )=bPredict(B )=e對(duì)任意非終極符號(hào)對(duì)應(yīng)的產(chǎn)生式的predict集合的交集都為空，所以該文法是LL(1)文法。(3)分析表如下:abde#A(1)A(2)(3)(3)精品文檔B(4)B，(5)(6)aade#的分析過程如下分析棧輸入流動(dòng)作A#aade#替換aA #aade#匹配A #ade#替換(

14、2)ABe#ade#替換aABe#ade#匹配A Be#de#替換Be#de#替換(4)dB e#de#匹配B e#e#替換e#e#匹配#成功精品文檔第五章(這章答案是錯(cuò)的)1 .設(shè)有下列文法：(1) S aAA AbA b(2) S aSSbS aSSSS c(3) S ASS bA SAA a(4) S cAS ccBB ccBB bA cAA a構(gòu)造上述文法的LR(0)歸約活前綴狀態(tài)機(jī)，并給出LR(0)分析表。答：(1)Ch05-1-(1)有移入、規(guī)約沖突(2)Ch05-1-(2)Zf .S (1)S .aSSb (2)S .aSSS (3)S7 .c(4)actiongotoabc#S

15、S0s2s51S1AccS2s2s53S3s2s54S4s2s6s57S5R4R4R4R4S6R2R2R2R2S7R3R3R3R3有移入、規(guī)約沖突Ch05-1-(3)Zf S- cA (2)S- ccB (3)B- ccB (4)B- b (5) 2 cA (6)A a (7)actiongotoabc#ABSS0s12S1s3s54S21AccS3R7R7R7R7S4 R6R6R6R6S5s3s9s876S6R3R3R3R3S7 1R2R2R2R2S8s3s107S9R5R5R5R5S10：s3s9s87r iiS11R4R4R4R42.設(shè)有下列文法:(1) S SaS | b(2) S b

16、Sb | cSc | b | c(3) S bSb | bSc | d(4) S aSb | bSa | ab(5) S Sab | bR R S | a(6) S SAB | BA B bA aA | B S AaAb | BbBaBA(8) A aABe | BaB dB |說明上述文法是否為SLR(1反法。若是，請(qǐng)構(gòu)造SLR(1分析表；若不是，請(qǐng)說明理由。答：(1)Ch05-2-(1)不是 SLR (1)(2)Ch05-2-(2)不是 slr (1)Follow(S)=#,b,c-bZf.SS7 .bSbS7.cScSf.bSf.crS b.Sb Sf b.Sf .bSbS7 .cScS

17、f .bSf .cCh05-2-(3) 是 SLR (1)3_S 一 d.1d 2Sf b.SbSf b.ScS- .bSbS 一 .bScS 一 .d5 S- bSb.b4 Sf bS.b Sf bS.ccZf .S (1)S7 .bSb (2)S7 .bSc (3)S7 .d (4)actiongotobcd#SS0s2s31S1AccS2s2s3Ch05-2-7 4S3r R4R4R4S4s5s6S5R2R2R2S6R3R3R36 S- bSc.Ch05-2-(4)不是 SLR( 1)Follow(S)=#,a,b-b-4S- aSb.(5)Ch05-2-(5)不是slr(i)Follo

18、w(R)=#,a(6)0Zf.S S .SAB Sf .BA Bf .b|bCh05-2-(6) 是SLR (1)SJ卡1Zf S.S S.ABZ .aAZ .B3一 a3S B.AZ .aA-B-Z .BBf .ba-5Af B.Bf .b-A-S1189S SA.BS SAB.IBBf .b5一 Z 2B4S- BA.Af a.AAf .aAAf .BBf .bAT7 A-aA.Z-S A SAB (2) A BA (3) A- aA (4) A- B (5) B- b (6)actiongotoab#ABSS01s231S1s6s2Acc85S2R6R6R6Ch05-2-7S31s6s2

19、45S4R3R3R3S5R5R5R5S61s6s275S7R4R4R4S8s29S9R2R2R2Ch05-2- 不是 SLR ( 1)Follow(A)=a,b Follow(B)=a,b0- ZSSf .AaAb Sf .BbBa 2.1-SZ Zf s.4TSf A.aAb-a-3Sf Aa.Ab A一.68Sf AaA.bSf AaAb.ATBf.BTSf B.bBa-b-Sf Bb.Ba B 一.7-o9Sf BbB.aSf BbBa.BT(8)Ch05-2-(8)不是 SLR (1) Follow(B尸a,e3 .設(shè)有下列文法：S aAd | bBd | aBe | bAeA gB

20、g說明該文法是 LR(1)文法，1不是LALR(1)文法。答：Ch05-3是LR文法0 ZfS Sf.aAd SfbBd Sf.aBe SfbAe#-a-5Sfa.Ad Sfa.Be Afg BfgZfS.3 Sfb.Bd Sfb.Ae Afg Bfg# # e d4SfaA.d#-At5SfaB.e#-Bt6Ag.dbg.e9SfbA.e#一At10S-bB.d #-Bf11 g A-g.B-g.7S-aAd.#-d-i8S-aBe.#一g12| SfbAe.#-e-d-J13 S-bBd.#Ch05-3不是LALR文法4 .設(shè)有下列文法：(1) E E+T | TT TF | TF (E)

21、 | F* | a | b(2) S Aa | bAc | dc | bda A d說明上述文法是否為SLR(1區(qū)法？是否為L(zhǎng)ALR(1戌法？并構(gòu)造相應(yīng)的分析表。答：Ch05-4-(1)不是 SLR文法Follow(T)=#,(,a,b,+,)F-(E).卜)Zf.E ef.e+t ef.t TfTF TfTEt1 ZfE.efe.+tEfE+.T* T f .TFT f .TT+-T-j3E-E+T.TfT.F TfT.F f(E) F f .F* Ff.a Ff.b -rr 8T-TF. F-F.*-a F-a.7Ffb.1110F-(E.)Le-efe.+tf-(.e) ef.e+t e

22、f.t TfTF TfT-TEfT.TfT.F TfT. Ff(E) Ff.F* Ff.a Ff.b5- F f F*-FJ J-a.TF#+(abT一.T#+(ab+9F-(E.) efe.+t#+(ab*)#+(ab*),10F-(E).#+(ab*)E3ef e+t.#+TfT.F#+(abT f T.#+(abFf(E)#+(ab* -F fF*#+(ab*F f.a#+(ab* F fb#+(ab*工18f-(.e)#+(ab*)ef.e+t#+(ab*)Ef.T#+(ab*)T f .TF#+(ab*)T f .T#+(ab*)5F-F*.#+(ab*J,*4T-TF.F -F.*

23、#+(ab#+(ab*Ft6Fa.#+(ab*7F fb.#+(ab*11e f t.#+(ab*)TfT.F#+(ab*)T f T.#+(ab*)F-.(E)#+(ab*)Ff.F*#+(ab*)Ff .a#+(ab*)Ff.b#+(ab*)-Tt(2)Ch05-4-(2)不是 SLR(1)文法 Follow(A)=a,cCh05-4-(2) 是 LALR(1)文法ZSr#TSr0 zf .sr#SAa.r#-Ta4-At S-A.aSf.AaSf.bAcSf.dcSf.bdaA f.d# # # a6S-b.AcSfb.daAf.d9SfbA.cSfd.c Afd.7 S-bd.a A

24、fd.S- bAc. #S dc.S-bda.Z. .S(1)Sf .Aa (2)Sf .bAc (3)Sf .dc(4)Sf .bda (5)Af.d(6)actiongotoabcd#ASS0s6s241S1AccS2R6s3S3R4S4s5S5R2S6s79S7s8R6S8R5S9s10S10R35 .設(shè)有下列文法：L MLb | aM說明上述文法是否為 LR(1)文法，若不是，請(qǐng)說明理由。答：Ch05-5 是 LR(1)文法精品文檔精品文檔第六章1. 試寫出下列類型的內(nèi)部表示：egerb.ARRAY1.5 of RECORDi:integer; b:boolean ENDc.

25、ARRAY1.5 of RECORDa:ARRAY1.10; r: RECORDi,j:integer END ENDd. RECORDr: RECORDx,y:real END;a: ARRAY1.10 of integer END2 .設(shè)當(dāng)前層數(shù)為l,可用區(qū)距為101,且有下列程序段：CONST mm=333； nn=444；TYPE atype =ARRAY1.10 OF real;rtype = RECORDi,j:integer END;VAR a,b:atype;x,y:real試寫出各標(biāo)識(shí)符的內(nèi)部表示。3 .設(shè)當(dāng)前層數(shù)和區(qū)距分別為l和off,且有函數(shù)說明首部：FUNCTION f

26、（ A： atype； VAR B： atype； VAR X： real） ： integer其中 atype 的定義見題5，試寫出f 的內(nèi)部表示。4 . 要求在下面括號(hào)中寫上相應(yīng)?（層數(shù)）和區(qū)距（off） 。（）（）PROCEDURE （g A： atype； （）（）VAR B： atype； （）（）VAR X： real （）（） （）（）.5 .給出下面C程序掃描到語句 c=a+b+x時(shí)相應(yīng)的全局符號(hào)表（采用順序表結(jié)構(gòu)）。main（）int a=0;float c=1.0;float a=3.0;float x=1.3;float b=0.3;int b=10;c=a+b+x;）。

27、6 .給出題1中程序掃描到語句 c=a+b+x時(shí)相應(yīng)的全局符號(hào)表（采用外拉鏈的散列表結(jié)構(gòu)7 . 根據(jù)標(biāo)識(shí)符的作用域規(guī)則，分別給出圖6.5 的程序中，過程P、 Q、 R、 S 中有效的標(biāo)識(shí)符。精品文檔第七章1 .將算術(shù)表達(dá)式(a+b)*(c+d)-(a+b+c)翻譯成四元式序列。2 .將下列語句翻譯成四元式序列：a. IF x0 THEN x:=0 ELSE x:=1b. WHILE x0 DO x:=x-1c. IF x0 THEN x:=x+1 ELSEIF x 0 DOWHILE y 0 DOBEGIN y:=y-x; x:=x-1 END3 .給出如下程序段的四元式序列。(四元式的操作符可用自身代替)。其中A: Array of 1.10of integer。a:=1;while a=10 dobegin if ab thenAa:=Ab+2;else a:=a+1;b:=b+1; end4 .試將FOR語句翻譯成四元式序列。5 .試將UNTIL語句翻譯成四元式序列。6