編譯原理在線考試考前輔導資料新

1、編譯原理在線考試考前輔導資料（新）考試復習所用教材：程序設計語言編譯原理，陳火旺、劉春林，國防工業(yè)出版社?？荚囶}型及分值介紹： 單項選擇題（每題4分，共10題，總分40分）、判斷題（每題2分，共10題，總 分20分）、綜合題（每題20分，共1題，總分20分）、簡答題題（每題10分，共2題，總分20分），滿 分100分。考試相關概念、知識點、復習題、例題歸納：編譯程序和高級語言。用匯編語言或高級語言編寫的程序，必須先送入計算機，經(jīng)過轉(zhuǎn)換成用機器語言表示的目標程序（這個過程即編譯），才能由計算機執(zhí)行。執(zhí)行轉(zhuǎn)換過程的程序叫編譯程序。匯編程序是指沒有編譯過 的匯編語言源文件。編譯程序轉(zhuǎn)換過的叫目標程序

2、，也就是機器語言。編譯程序的工作情況有三種：匯編型、解釋型和編譯型。匯編型編譯程序用來將匯編語言編寫的程 序，轉(zhuǎn)換成用機器語言表示的程序。解釋型編譯程序?qū)⒏呒壵Z言程序的一個語句，先解釋成為一組機器 語言的指令，然后立即執(zhí)行，執(zhí)行完了，取下一組語句解釋和執(zhí)行，如此繼續(xù)到完成一個程序為止。用 解釋型編譯程序，執(zhí)行速度很慢，但可以進行人和計算機的"對話"，隨時可以修改高級語言的程序。編譯型編譯程序?qū)⒓壵Z言編寫的程序，一次就會部翻譯成機器語言表示的程序，而且過程進行很快，在過 程中，不能進行人機對話修改。編譯方式:先將源程序翻譯成匯編語言程序或機器語言程序，然后在執(zhí)行它。在編譯方式

3、中 ，如果目標程序是匯編語言，。那么還需要由另一個稱為匯編程序的翻譯程序?qū)⑺M一步翻譯成機器語言程序。解釋方式：解釋方式不是先產(chǎn)生目標程序然后再執(zhí)行，而且對源程序邊翻譯邊執(zhí)行。優(yōu)點是 ：便于對源程序進行調(diào)試和修改，但其加工處理過程的速度較慢。例題：運行階段的存儲組織與管理的目的是（ D）。 提高編譯程序的運行速度 節(jié)省編譯程序的存儲空間提高目標程序的運行速度為運行階段的存儲分配做準備A.B. C. D.二義性理解二義性，并判斷文法是否為二義性的。如果文法G中的某個句子存在不只一棵語法樹，則稱該句子是二義性的。如果文法含有二義性的句子，則稱該文法是二義性的。例已知文法G1:P->PaP|P

4、bP|cP|Pe|f 是二義文法。編譯程序包含的步驟：一個典型的編譯程序不僅包括詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、目標代碼生成等五個部分，還應包括表格處理和出錯處理。 例題：在編譯程序中，語法分析分為自頂向下分析和自底向上分析兩類：算符優(yōu)先分析法和LR分析法屬于自底向上分析。中間代碼：也叫中間語言：是源程序的一種內(nèi)部表示，不依賴目標機的結(jié)構(gòu)，易于機械生成目標代碼的中間表 示。常見的幾種形式：后綴式，圖表示法和三地址代碼（三元式，四元式，間接三元式）。中間代碼 不可能是目標代碼。一個可執(zhí)行程序所使用的存儲空間被分為四個區(qū)：代碼區(qū)、數(shù)據(jù)區(qū)、棧區(qū)、堆區(qū)。LR分析法：“L”是指從左至右掃描輸

5、入符號串“R”是指構(gòu)造一個最右推導的逆過程三元式和四元式的比較 ：相同點： 無論在一個三元式序列還是四元式序列中，各個三元式或四元式都是按相應表達式的實際運算順序出現(xiàn)的。對同一表達式而言，所需的三元式或四元式的個數(shù)一般都是相同的。不同點：由于三元式?jīng)]有result字段，且不需要臨時變量，故三元式比四元式占用的存儲空間少；在進行代碼優(yōu)化處理時，需要從現(xiàn)有的運算序列中刪去某些運算或挪動一些運算的位置這對三元 式來說是很困難的，但四元式之間的相互聯(lián)系是通過臨時變量來實現(xiàn)的，所以影響就比較小。三元式與間接三元式之間的區(qū)別： 由于間接三元式在執(zhí)行表中已經(jīng)依次列出每次要執(zhí)行的那個三元式，若其中有相同的三元

6、式，則僅需在三元式表中保存其中之一，即就是說三元式的項數(shù)一般比執(zhí)行表的項數(shù)少；當進行代碼優(yōu)化需要挪動運算順序時，則只需對執(zhí)行表進行相應地調(diào)整，而不必再改動三元式本身，這樣，就避免了 前面講到的因改變?nèi)降捻樞蛩鸬穆闊?。符號表：編譯過程中編譯程序需要不斷匯集和反復查證出現(xiàn)在源程序中各種名字的屬性和特征等有關信息， 這些信息通常記錄在一張或幾張符號表中。符號表的每一項包含兩部分：名字（標識符），和此名字的 有關信息。作用：這些信息將用于語義檢查，產(chǎn)生中間代碼以及最終生成目標代碼等不同階段。編譯程序概念及其基本過程？將源程序為高級語言（如 Fortran、Pascal、C等），翻譯成目標語言是

7、諸如匯編語言或機器語言之 類的“低級語言”的一個翻譯程序成為編譯程序。基本過程：詞法分析、語法分析、語義分析與中間代碼生成、優(yōu)化、目標代碼生成。詞法分析器的功能和輸出形式。輸出的單詞符號包括哪幾種？功能：輸入源程序，輸出單詞符號。詞法分析遵循構(gòu)詞規(guī)則種類：關鍵字、標識符、常數(shù)、運算符、界符。例題：詞法分析器的輸出結(jié)果是（單詞的種別編碼和屬性值 ）（初始狀態(tài)集合）不是DFA的成分。在屬性文法中，終結(jié)符只具有 綜合屬性。編譯程序絕大多數(shù)時間花在表格管理上語法分析器。語法分析是編譯過程的核心部分。它的任務是在詞法分析識別出單詞符號串的基礎上，分析并判定 程序的語法結(jié)構(gòu)是否符合語法規(guī)則。兩種分析方法：

8、自上而下分析法、自下而上分析法。例題：編譯過程中，語法分析器的任務是（A ）1 .分析單詞的構(gòu)成2 .分析單詞串如何構(gòu)成語句3 .分析語句是如何構(gòu)成程序4 .分析程序的結(jié)構(gòu)A.B.C.D.理解自頂向下的語法分析方法和自底向上的語法分析方法的區(qū)別。它是編譯過程中哪個階段用到的?自頂向下語法分析方法的基本思想是從文法的開始符號開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生 式一步一步的向下進行直接推導，試圖推導出文法的句子，使之與給定的輸入串匹。自底向上的語法分析方法的基本思想是從給定的輸入串（終結(jié)符串）開始，根據(jù)文法的規(guī)則一步一 步的向上進行直接歸約，試圖歸約到文法的開始符號。理解什么是動態(tài)存儲分配。動

9、態(tài)存儲分配是指在程序執(zhí)行的過程中動態(tài)地分配或者回收存儲空回空也蟲存的方法。動態(tài)內(nèi)存 分配不像 數(shù)組等靜態(tài)內(nèi)存分配方法那樣需要預先分配存儲空間，而是由系統(tǒng)根據(jù)程序的需要即時分配,且 分配的大小就是程序要求的大小。掌握LL（1）文法，給出一個文法，判斷是否為LL（1）文法，能夠計算出非終結(jié)符的FIRST集和FOLLOW集，證明它是LL（1）文法，并能夠構(gòu)造它的預測分析表。例題：判斷下列文法是否是LL（1）文法？G: Sf aASfdZ bASAr £解： select（S 一 aA）=aselect（S 一d）=dselect（S 一 aA） n select（S 一d）=?select

10、（A 一 bAS）=bselect（A 一 e ）=First（ £ ） - £ U Follow（A）=Follow（A）=a,d,#select（A 一 bAS）C select（A 一 e ）=?所以，該文法是 LL（1）文法。如果文法G是無二義的，則它的任何句子 最左推導和最右推導對應的語法樹必定相同。一個LR （1）文法合并同心集后，如果不是LALR（1）文法必定存在 歸約-歸約沖突。一個 LL（l）文法一定是無二義的。（錯誤）有窮自動機只有一個初態(tài)（錯誤）包含左遞歸的文法肯定不能直接用LL分析法來分析。（正確）若文法G定義的語言是無限集，則文法必然是（遞歸文法）

11、掌握短語、句柄和直接短語短語：就是某個子樹的葉子節(jié)點的序列。直接短語：就是二級子樹的葉子節(jié)點的序列句柄：就是最左直接短語。對編譯程序而言，輸入數(shù)據(jù)是源程序，輸出結(jié)果是目標程序。作為編譯程序的源語言不能是低級語言。規(guī)范歸約和規(guī)范推導是互逆的兩個過程。（ 錯誤）逆波蘭式。逆波蘭式（Reverse Polish notation , RPN或逆波蘭記法），也叫后綴表達式（將運算符寫在操 作數(shù)之后）。例如：3* （2- （5+1）,用逆波蘭式來表示是：3 2 5 1 + - *,也就是把操作運算符往操作數(shù)后面放。DFA與NFA的基本概念及其區(qū)別？DFA與NFA定義見課本，區(qū)別：DFA與NFA的區(qū)別表現(xiàn)

12、為兩個方面：一是NFA可以若干個開始狀態(tài)， 而DFA僅只一個開始狀態(tài)。另一方面，DFA的映象M是從KX匯到K,而NFA的映象M是從KX匯到K的子集，即映象M將產(chǎn)生一個狀態(tài)集合（可能為空集），而不是單個狀態(tài)。代碼優(yōu)化代碼優(yōu)化是盡量生成“好”的代碼的編譯階段。也就是要對程序代碼進行一種等價變換，在保證變 換前后代碼執(zhí)行結(jié)果相同的前提下，盡量使目標程序運行時所需要的時間短，同時所占用的存儲空間 少。常用的代碼優(yōu)化技術也需要了解一下。例題：含有代碼優(yōu)化功能的編譯器的執(zhí)行效率通常較高。（ 錯誤）兩個正規(guī)集相等的必要條件是他們對應的正規(guī)式等價。（ 錯誤 ）綜合題：將下面的文法改寫為 LL（1）文法。布爾表

13、達式一布爾表達式V布爾因子布爾表達式一布爾因子布爾因子一布爾因子A布爾二次量布爾因子一布爾二次量布爾二次量一布爾初等量布爾二次量一布爾初等量布爾初等量一（布爾表達式）布爾初等量一 true | false答案：為方便書寫，記：布爾表達式 > 為A,<布爾因子 > 為B,布爾二次量 > 為C,布爾初等量 > 為D,原文法可以簡化為：Z AV B | B B-BAC | C8 n D | DA （A）| true | false,顯然，文法含有左遞歸，消去后等價LL（1）文法為：Z BA'A'一 VBA' | 3 B一 CB ,B'一A

14、 CB | coCHn D|DA （A）| true|false證明下述文法不是 LL(1)文法。 S->C$ C-> bA|aB A->a|aC|bAA B->b|bC| aBB 你能否構(gòu)造一等價的文法，使其是 LL (1) ?并給出判斷過程。答案：因為 SELECT(A->a)nSELECT(A->aC)w，根據(jù)LL (1)文法的判定條件： (1)文法不含左遞歸(2)對于文法U的任意兩個不同的規(guī)則有：Select(U - a ) n Select(U -b尸一個文法若滿足以上條件，稱該文法G為LL(1)文法。得出該文法不是LL (1)文法。該文法含公共因

15、子，消除后的文法為： S->C$ C-> bA|aB A->aA'|bAA A' ->C| £ B->bB'| aBB B' ->C| £【證明】因為 SELECT(C-> bA) n SELECT(C->aB)= SELECT(A->Aa) n SELECT(A->bAA)=SELECT(A ->C) ASELECT(A -> e )=(FIRST(C)-£ ) n FOLLOW(A ) w 因此消除公共因子后得到文法也不是LL (1)文法。對于如下的文法 G

16、 S:5- SbS- Ab6- bA- AaZ a(1) 構(gòu)造一個與 G等價的LL(1)文法G ;(2) 對于G',構(gòu)造相應的LL(1)分析表。答案：解：(1)消除左遞歸性，得：Sf bZ11|aZ21A f bZ121az22Z11 -bZ11| £ Z12fbz12Z21fbz111az21Z22 fbz121az22| £消除無用產(chǎn)生式得：SfbZ111az21Z11-bZ11| e Z21fbz111az21此文法已滿足LL(1)文法的三個條件，所以G' S:SfbZ111az21Z11-bZ11| e Z21fbz111az21(2) G'

17、文法的各非終結(jié)符的FIRST集和FOLLOW:產(chǎn)生式FIRST 集FOLLOWSf bZ11faZ21ba#Z11fbZ11b & #Z21fbz11faZ21ba#LL(1)分析表為:ab#SaZ21bZ11Z11bZ11Z21aZ21bZ11說明屬性文法與屬性番S譯文法有何異同？答案：解：屬性文法是文法符號帶有語義屬性的前后文無關文法；屬性翻譯文法首先是對文法的屬性依賴關系作出限制，不允許出現(xiàn)屬性的直接或間接的循環(huán)定義，即 要求屬性文法是良定義的；其次還應將屬性定義規(guī)則改造為計算屬性值的語義程序，即將靜態(tài)的定義 規(guī)則改寫為可動態(tài)執(zhí)行的語義動作；屬性文法是靜態(tài)描述，而屬性翻譯文法是動

18、態(tài)描述，有語義動作。寫出一個LEX正規(guī)式，它能匹配 C語言的所有無符號整數(shù)(例如：OX89ab 0123, 45, ' Z't ' , ' xab' , ' 012',等等)。答案：'(a-zA-Z|Xx0-70-7a-fA-F|0010-70-，)Whilea>0Vbv0 doBeginX： = X+ 1;if a> 0 then a： = a 1else b： = b + 1End;翻譯成四元式序列。答案：解：(1) (j >, a, 0, 5)(2) (j ,3)(5) ( + , x, 1, T1)(6)

19、 (: =, T1, , X )(7) (j >, a, 0, 9)(8) (j ,12)(9) (-, a, 1, T2)(10) (: =, T2,a)(11) (J,-,-, 1)(12) (+, b, 1,T3)(13) (: =, T3,b)(14) (J ,1)(15)試證明： 文法Sf ABSH> DCA aAA a8- bBcBf bcg cC8 cA aDbA ab為二義性文法。答案：證明：因為存在句子：abc,它對應有兩個最右推導:STABTAbcTabcSTDCTDcTabc所以，本文法具有二義性。一個C語言程序如下:func(i1,i2,i3)long i1

20、,i2,i3;=%o,%o,%on”,&i1,&i2,&i3);=%o,%o,%on”,&J1,&J2,&J3);long j1,j2,j3;printf("Addressesofi1,i2,i3printf("Addressesof J1,J2,J3main()long i1,i2,i3;func(i1,i2,i3);該程序在某種機器的Linux上的運行結(jié)果如下:Addressesofi1,i2,i3AddressesofJ1,J2,J3=27777775460,27777775464,27777775470=2777777

21、5444,27777775440,277777754343個局部變量的地址依次降從上面的結(jié)果可以看出，func 函數(shù)的3個形式參數(shù)的地址依次升高，而 低。試說明為什么會有這個區(qū)別。答案：由于實參表達式是反序進入活動記錄，而局部變量是順序在活動記錄中分配。設已給文法 G=(VN,VT,P,S),其中：VN=SVT=a1,a2,an, V , A , 1 P=Sfai|i=1,2,n USfS,S- SV S ,Sf SA S ,試指出此文法所產(chǎn)生的語言。答案：此文法產(chǎn)生的語言是：以終結(jié)符al 、a2 - an為運算對象，以A、V、為運算符，以、為分隔符的布爾表達式串一個C語言程序如下:int f

22、act(i) int i;if(i=0) return1;else returni*fact(i-1);main() printf("%dn",fact(5);printf("%dn", fact(5,10,15);printf("%dn",fact(5.0);printf("%dn",fact(); 該程序在X86/Linux機器上的運行結(jié)果如下： 120 120Segmentation fault請解釋下面問題：(core dumped)? 第二個fact? 第三個fact? 第四個fact調(diào)用調(diào)用調(diào)用結(jié)果為什

23、么沒有受參數(shù)過多的影響？為什么用浮點數(shù) 5.0作為參數(shù)時結(jié)果變成1?為什么沒有提供參數(shù)時會出現(xiàn)Segmentation fault ?答案：(1)參數(shù)表達式逆序計算并進棧，fact能夠取到第一個參數(shù)。(2)參數(shù)5.0轉(zhuǎn)換成雙精度數(shù)進棧，占 8個字節(jié)。它低地址的 4個字節(jié)看成整數(shù)時正好是 0。(3)由于沒有提供參數(shù)，fact把老ebp (控制鏈)(main的活動記錄中保存的 ebp)當成參數(shù), 它一定是一個很大的整數(shù)，使得活動記錄棧溢出。設有某程序語言的循環(huán)語句的產(chǎn)生式- for i:= downto do其語義是：T1:=;T2:=;i:=T1;L1:if i-T2<0 nbsp="" then="" goto="&