編譯原理考點最新

1、編譯程序涉及的三個語言 答：源語言 目標(biāo)語言 實現(xiàn)語言編譯程序的概念及其結(jié)構(gòu)(五個)答：編譯程序(compiler)是一種翻譯程序，它特指把某種高級程序設(shè)計語言翻譯成具體計算機(jī)上的低級程序設(shè)計語言。源程序 詞法分析 語法分析 語義分析 優(yōu)化處理 目標(biāo)代碼生成 目標(biāo)程序什么是二義性文法。答：若文法中存在這樣的句型，它具有兩棵不同的語法樹，則稱該文法是二義性文法。超前搜索技術(shù)答：詞法分析程序在讀取單詞時，為了判斷是否已讀入整個單詞的全部字符，常采取向前多讀取字符并通過讀取的字符來判別，即所謂超前搜索技術(shù)。5、“遍”的概念答：編譯程序?qū)υ闯绦蚧虻葍r程序從頭至尾掃描的次數(shù)。6、上下文無關(guān)文法的定義答：

2、文法是規(guī)則的有限集,其中的上下文無關(guān)文法可定義為四元組： G(Z)=(VN, VT, Z, P)每個元素：VN : 非終結(jié)符集（定義的對象集，如：語法成分等)，它的每個元素是非終結(jié)符號。VT : 終結(jié)符集（字母表），它的每個元素是終結(jié)符號。Z : 開始符號（研究范疇中，最大的定義對象）；P : 規(guī)則集（又稱產(chǎn)生式集）；每個規(guī)則：A - 或者 A - | 其中： 描述符號 ： -(定義為)，|(或者是)文法符號 ： Z,AVN，(VN+VT)*7、詞法分析，自上而下以及自下而上語法分析的基本概念，輸入，輸出，分析方法。答：詞法分析是編譯過程中的一個階段，在語法分析前進(jìn)行，也可以和語法分析結(jié)合在一

3、起作為一遍。輸入：源程序字符串輸出：等價的屬性字序列（內(nèi)部表示形式）詞法分析器又稱掃描器，是執(zhí)行詞法分析的程序。任務(wù)有二： (1) 識別單詞 從用戶的源程序中把單詞分離出來; (2) 翻譯單詞 把單詞轉(zhuǎn)換成機(jī)內(nèi)表示，便于后續(xù)處理。自上而下語法分析是從文法的開始符號出發(fā)，反復(fù)使用不同產(chǎn)生式向下推導(dǎo)以謀求與輸入符號串相匹配。對任何輸入串，試圖用一切可能的辦法，從文法開始符號(根結(jié))出發(fā)，自上而下地為輸入串建立一棵語法樹。輸入符號串指的是由單詞符號(文法的終結(jié)符)組成的有限序列自下而上分析法就是從輸入串開始，逐步進(jìn)行“歸約”，直至歸約到文法的開始符號；或者說從語法樹的末端開始，步步向上“歸約”，直到

4、根結(jié)。輸入串在這里是指從詞法分析器送來的單詞符號組成的二元式的有限序列(單詞種別，單詞符號的屬性值)。8、LL(k)的含義，以及LL(1)文法的判定。P73答：判斷某給定文法是否為LL(1)文法其條件為： (1)文法不含左遞歸。 (2)對于文法中每個非終結(jié)符A的各個產(chǎn)生式的候選首符集兩兩不相交。即，若 A 1 | 2 |。| n 則： FIRST(i) FIRST(j) = （i j ) (3) 對文法中每一個終結(jié)符A，若它存在某個候選首符集包含，則 FIRST(A) FLLOW(A)= 一個文法若滿足以上條件，則稱該文法G為LL(1)文法.9、LR分析法答：LR(0)分析法SLR(1) 分析

5、法LR分析法 LR(1)分析法LALR(1)分析法10、中間代碼生成的依據(jù)，形式，目的。P166答：中間代碼的生成方法：屬性文法制導(dǎo)翻譯語義制導(dǎo)翻譯中間代碼的形式：逆波蘭式圖表示法三元式四元式：最常用的形式中間代碼：不是機(jī)器語言，便于生成機(jī)器語言，便于代碼優(yōu)化11、四元式p172答：一個四元式是一個帶有四個域(field)的記錄結(jié)構(gòu)，這四個域分別稱為op、arg1、arg2及result。域op包含一個代表運算符的內(nèi)部碼。三地址語句x:=y op z可表示為：將y置于arg1域，z置于arg2域，x置于result域，:=為算符。帶有一元運算符的語句如x:= -y或x:= y的表示中不使用ar

6、g2。而像param(過程調(diào)用)這樣的運算符僅適用arg1。條件和無條件轉(zhuǎn)移語句將目標(biāo)標(biāo)號置于result域中。通常，四元式中的arg1、arg2和result的內(nèi)容都是一個指針，此指針指向有關(guān)名字的符號表入口。12、棧式存儲分配p255 p245答：動態(tài)存儲分配（1）棧式存儲分配運行時，每進(jìn)入一個過程，就在棧頂為該過程分配一塊數(shù)據(jù)區(qū)，一旦退出該過程，它所占的空間也退還給系統(tǒng)。（2）堆式存儲分配 棧式存儲分配 使用棧式存儲分配法意味著把存儲組成一個棧，運行時，每當(dāng)進(jìn)入一個過程（一個新的活動開始）時， 就把它的活動記錄壓入棧（累筑于棧頂），從而形成過程工作時的數(shù)據(jù)區(qū)，一個過程的活動記錄的體積在編

7、譯時是可靜態(tài)確定的。當(dāng)該過程結(jié)束（過程退出）時，再把它的活動過程彈出棧。這樣在棧頂?shù)臄?shù)據(jù)區(qū)也隨即不復(fù)存在。允許過程(函數(shù))遞歸調(diào)用的數(shù)據(jù)存儲管理 1)語言特點：允許過程(函數(shù))的遞歸調(diào)用，但不允許定義嵌套的過程(函數(shù))，也不許使用可變數(shù)組。如C語言。2)棧式存儲分配：每進(jìn)入一個過程，就有相應(yīng)的數(shù)據(jù)區(qū)建立在棧頂。當(dāng)程序開始運行前，用于建造數(shù)據(jù)區(qū)的棧是空棧。當(dāng)開始進(jìn)入主程序執(zhí)行語句前，便在棧中建立全局變量和主程序數(shù)據(jù)區(qū)。在主程序中若有調(diào)用過程的語句時，便在棧頂累筑該過程的活動記錄。在進(jìn)入過程后執(zhí)行過程的可執(zhí)行語句前再把局部數(shù)組累筑于棧頂，若還有調(diào)用過程的語句就重復(fù)上述過程。唉，太多了，還是看書吧1

8、3、循環(huán)優(yōu)化的具體措施。P287答：主要方法循環(huán)不變運算外提（代碼外提）降低運算強(qiáng)度（強(qiáng)度削弱）刪除歸納變量找出程序中的循環(huán)循環(huán)語句條件轉(zhuǎn)移和無條件轉(zhuǎn)移構(gòu)成循環(huán)找程序中的循環(huán)的方法程序數(shù)據(jù)流程分析程序控制流程分析是數(shù)據(jù)流程分析的基礎(chǔ)14、翻譯程序，編譯程序的異同。答： 翻譯程序：將一種語言程序轉(zhuǎn)換為另一種語言程序的程序, 按照對象不同分別有： 轉(zhuǎn)換程序 - 把一種高級語言轉(zhuǎn)換成另一種高級語言； 編譯程序 - 把某種高級語言轉(zhuǎn)換成某種低級語言; 解釋程序 - 把某種高級語言轉(zhuǎn)換成某種低級語言; 匯編程序 - 把匯編語言轉(zhuǎn)換為機(jī)器語言的翻譯程序。 編譯程序(compiler)是一種翻譯程序，它特指

9、把某種高級程序設(shè)計語言翻譯成具體計算機(jī)上的低級程序設(shè)計語言。解釋程序(interpreter)也是一種翻譯程序，將某高級語翻譯成具體計算機(jī)上的低級程序設(shè)計語言。 編譯程序與解釋程序的主要區(qū)別: 前者有目標(biāo)程序而后者無目標(biāo)程序； 前者運行效率高而后者便于人機(jī)對話。15、NFA、DFA的定義，區(qū)別，以及轉(zhuǎn)換。DFA的最小化。答：DFA定義：一個確定的有窮自動機(jī)（DFA）M是一個五元組： M=（S，s0，F(xiàn)）其中1.S是一個有窮集，它的每個元素稱為一個狀態(tài)；2.是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱為輸入符號表；3. 是轉(zhuǎn)換函數(shù)，是在SS上的映射，即，如 （s，a）=s，（sS，s

10、S）就意味著，當(dāng)前狀態(tài)為s，輸入符為a時，將轉(zhuǎn)換為下一個狀態(tài)s，我們把s稱作s的一個后繼狀態(tài)；4. s0S是唯一的一個初態(tài)；5.F S是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。NFA定義：一個不確定的有窮自動機(jī)（NFA）M是一個五元組： M=（S，S0，F(xiàn)）其中1.S是一個有窮集，它的每個元素稱為一個狀態(tài)；2.是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱為輸入符號表；3. 是轉(zhuǎn)換函數(shù)，是在S*S上的映射，有: S 2S ；4. S0 S是一個非空初態(tài)集；5.F S是一個終態(tài)集(可空)。區(qū)別：DFANFA開始狀態(tài)唯一一個或多個映像單個狀態(tài)狀態(tài)集合DFA的最小化算法的核心把一個DFA

11、的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的.算法假定每個狀態(tài)射出的弧都是完全的,否則,引入一個新狀態(tài),叫死狀態(tài),該狀態(tài)是非狀態(tài)，將不完全的輸入弧都射向該狀態(tài)，對所有輸入，該狀態(tài)射出的弧還回到自己.DFA的最小化算法（參看P56）構(gòu)造DFA M的最小狀態(tài)DFA M，以書上例子來說明該過程。16、逆波蘭表達(dá)式的求得。答：后綴式(逆波蘭式) 后綴式表示法有稱逆波蘭表示法。這種方法是，把運算量(操作數(shù))寫在前面，把算符寫在后面(后綴)。 一個表達(dá)式的后綴式可以如下定義： (1)如果E是一個變量或常量，則E的后綴式是E自身。 (2)如果E是E

12、1 op E2形式的表達(dá)式，這里op是任何二元操作符，則E的后綴式為 E1 E2op,這里E1 和E2分別為E1和E2的后綴式。 (3)如果E是(E1)形式的表達(dá)式，則E1的后綴式就是E的后綴式。后綴式把表達(dá)式翻譯為后綴式的語義規(guī)則： 產(chǎn)生式 語義規(guī)則 EE1 op E2 E.code:=E1.code|E2.code|op E (E1) E.code:=E1.code Eid E.code:=id其他語法成分翻譯為后綴式： 產(chǎn)生式 語義規(guī)則單目運算“-”： -E E.code|-賦值語句“=”： E=T E.code|T.code|=17、DISPLAY表的概念。P257-259答：18、提

13、高程序運行效率的途徑 p273答：對于源程序級，程序員可安排適當(dāng)?shù)膶崿F(xiàn)語言和選擇適當(dāng)?shù)乃惴壠浯?，在設(shè)計語義動作時，可以考慮產(chǎn)生更加高效的中間代碼，還可以為后面的優(yōu)化階段做一些預(yù)備工作。對編譯產(chǎn)生的中間代碼，安排專門的優(yōu)化階段，進(jìn)行各種等價變換，以改進(jìn)代碼的效率。主要優(yōu)化內(nèi)容，與計算機(jī)硬件無關(guān)。對于目標(biāo)代碼級，應(yīng)該考慮如何有效地利用寄存器，如何選擇指令，以及進(jìn)行窺孔優(yōu)化等等。19、根據(jù)正規(guī)式畫出轉(zhuǎn)換圖（NFA），通過狀態(tài)轉(zhuǎn)移矩陣把NFA確定化后變成DFA，把DFA最小化。答：NFA到相應(yīng)的DFA的構(gòu)造的基本思路 DFA的每一個狀態(tài)對應(yīng)NFA的一組狀態(tài). DFA使用它的狀態(tài)去記錄在NFA讀入一個

14、輸入符號后可能達(dá)到的所有狀態(tài)NFA確定化算法(1)假設(shè)NFA M=(S,S0,F)按如下辦法構(gòu)造一個DFA M，使得L(M)=L(N)：引進(jìn)新的初態(tài)結(jié)點X和終態(tài)結(jié)點Y，X,Y不屬于S，從X到S0中任意狀態(tài)結(jié)點連一條弧，從F中任意狀態(tài)結(jié)點連一條弧到Y(jié)。對M的狀態(tài)轉(zhuǎn)換圖進(jìn)一步施行下圖所示的替換，直至狀態(tài)轉(zhuǎn)換圖中每條弧上標(biāo)記為，或為中的單個字母。 (2)將M進(jìn)一步變換為DFA，方法如下：假定I是M的狀態(tài)集的子集，定義I的-閉包_closure(I)為 (a)若qI，則q_closure(I); (b)若qI，那么從q出發(fā)經(jīng)任意條弧而能到達(dá)的任何狀態(tài)q都屬于_closure(I)。假定I是M的狀態(tài)集的

15、子集，a，定義Ia=_closure(J)，其中，J是那些可從I中的某一狀態(tài)結(jié)點出發(fā)經(jīng)過一條a弧而能到達(dá)的狀態(tài)結(jié)點的全體。假定=a1,ak。構(gòu)造一張表，此表的每一行含有k+1列，置表的首行首列為_closure(X)。DFA的最小化算法的核心把一個DFA的狀態(tài)分成一些不相交的子集，使得任何不同的兩子集的狀態(tài)都是可區(qū)別的，而同一子集中的任何兩個狀態(tài)都是等價的.算法假定每個狀態(tài)射出的弧都是完全的,否則,引入一個新狀態(tài),叫死狀態(tài),該狀態(tài)是非狀態(tài)，將不完全的輸入弧都射向該狀態(tài)，對所有輸入，該狀態(tài)射出的弧還回到自己.唉，太復(fù)雜了，還是看書吧20、根據(jù)文法推導(dǎo)給定的句型，并會畫分析樹。答：語法樹句型(句子

16、)產(chǎn)生過程的一種樹結(jié)構(gòu)表示；樹根-開始符號；樹葉給定的句型(句子)【語法樹的構(gòu)造算法】 置樹根為開始符號； 若采用了推導(dǎo)產(chǎn)生式： A - x1x2xn，則有子樹： 重復(fù)步驟，直到再沒有推導(dǎo)產(chǎn)生式為止 如此構(gòu)造的語法樹，其全體樹葉（自左至右）恰好是給定的句型。21、給定文法，學(xué)會消除左遞歸，并提取左公因子從而產(chǎn)生新文法，然后從新文法中構(gòu)造相應(yīng)的FIRST集和FOLLOW集。最后學(xué)會構(gòu)造新文法的預(yù)測分析表。答：沒法寫，孩子還是看書把22、對某一語法樹找出其短語，直接短語，句柄和素短語。答：關(guān)于語法樹：子樹 ：以任何具有分支的結(jié)點為根所形成的樹，稱為原樹的子樹。簡單子樹 ：僅具有單層分支的子樹。任一

17、子樹的樹葉全體(具有共同祖先的葉節(jié)點符號串)皆為短語；任一簡單子樹的樹葉全體(具有共同父親的葉節(jié)點符號串)皆為簡單短語；一個句型的最左簡單短語稱為該句型的句柄23、對給定文法，計算其FIRSTVT集和LASTVT集，并學(xué)會構(gòu)造該文法的優(yōu)先關(guān)系矩陣。答：沒法寫，孩子還是看書把24、畫出給定基本塊的DAG圖，并學(xué)會優(yōu)化。答：太多了，我們還是看書吧25、給定控制語句，翻譯成四元式序列。答：對于產(chǎn)生式Swhile E do S1，標(biāo)號S.begin和E.true分別標(biāo)記整個語句S的代碼的頭一條指令和其中的循環(huán)體S1的代碼的頭一條指令。因此，在下面產(chǎn)生式中引入了標(biāo)記非終結(jié)符M，以記錄這些位置的四元式標(biāo)號

18、： Swhile M1 E do M2 S1其中M,其語義動作是把下一條四元式的標(biāo)號賦給屬性M.quad。當(dāng)while語句中S1的代碼執(zhí)行完畢，控制流轉(zhuǎn)向S的開始處。因此，當(dāng)歸約while M1 E do M2 S1為S時，我們回填表S1.nextlist中所有相應(yīng)的轉(zhuǎn)移指令的目標(biāo)標(biāo)號為M.quad。對于if E then S1 else S2的代碼生成，執(zhí)行完S1的代碼后，應(yīng)跳過S2的代碼。因此，在S1的代碼之后應(yīng)有一條無條件轉(zhuǎn)移指令。我們用一個標(biāo)記非終結(jié)符N來生成這條跳轉(zhuǎn)指令，N的產(chǎn)生式為N，它具有屬性N.nextlist，鏈中包含由N的語義動作所產(chǎn)生的跳轉(zhuǎn)指令的標(biāo)號。修改后文法的翻譯模式：(1) Sif E then M1 S1 N else M2 S2 backpatch(E.truelist, M1.quad); backpatch(E.falselist, M2.quad); S.nextlist:=merge(S1.nextlist, N.nextlist, S2.nextlist)對E為真的四元式(E.truelist所鏈的四元式)需回填為M1.quad，即S1的第一條四元式的標(biāo)號。同樣，對E為假的四元式需回填S2的第一條語句的標(biāo)號。鏈表S.nextlist中包含跳出S