編譯原理文字總結(jié)

1.高級(jí)程序設(shè)計(jì)語(yǔ)言的翻譯主要有兩種方式：編譯和解釋。2.編譯過(guò)程概述：

(1)詞法分析：輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)的

單詞（亦稱(chēng)單詞符號(hào)或符號(hào)）如基本字，標(biāo)識(shí)符，常數(shù)，算符和界符。

(2)語(yǔ)法分析：在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)串分解成各類(lèi)

語(yǔ)法單位（語(yǔ)法范疇），如短語(yǔ)，子句，句子，程序段和程序等

(3)語(yǔ)義分析與中間代碼產(chǎn)生：對(duì)語(yǔ)法分析所識(shí)別出的各類(lèi)語(yǔ)法范疇，分析其含義，并

進(jìn)行初步翻譯（產(chǎn)生中間代碼）。包括靜態(tài)語(yǔ)義檢查和中間代碼的翻譯。(4)優(yōu)化：對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段能產(chǎn)生出更為高效（省

時(shí)間和空間）的目標(biāo)代碼。

(5)目標(biāo)代碼生成：把中間代碼（或經(jīng)優(yōu)化處理之后）變換成特定機(jī)器上的低級(jí)語(yǔ)言代

碼。

編譯程序結(jié)構(gòu)框圖

3．文法是表述語(yǔ)言的語(yǔ)法結(jié)構(gòu)的形式規(guī)則。

4.所謂上下文無(wú)關(guān)文法是這樣一種文法，它所定義的語(yǔ)法范疇（或語(yǔ)法單位）是完全獨(dú)立于這種范疇可能出現(xiàn)的環(huán)境的。一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分：一組終結(jié)符號(hào)，一組非終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組產(chǎn)生式。

5.形式上說(shuō)，一個(gè)上下文無(wú)關(guān)文法G是一個(gè)四元式（VT,VN,S,＆）其中VT是一個(gè)非空有

限集，它的每個(gè)元素稱(chēng)為終結(jié)符號(hào)；VN是一個(gè)非空有限集，它的每個(gè)元素稱(chēng)為非終結(jié)符號(hào)，VT∩VN=；S是一個(gè)非終結(jié)符號(hào)，稱(chēng)為開(kāi)始符號(hào)；&是一個(gè)產(chǎn)生式集合，每個(gè)產(chǎn)生式的形式是P→a，其中P屬于VN，a屬于（VT∪VN）*。開(kāi)始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。

6.推導(dǎo)每前進(jìn)一步總是引用一條規(guī)則（產(chǎn)生式）。7.假定G是一個(gè)文法，S是它的開(kāi)始符號(hào)。如果Sa，則稱(chēng)a是一個(gè)句型（0步或若干步）。

僅含終結(jié)符號(hào)的句型是一個(gè)句子。文法G所產(chǎn)生的句子的全體是一個(gè)語(yǔ)言，將它記為L(zhǎng)(G)。L(G)=｛a|Sa&a∈VT*｝例如終結(jié)符號(hào)串（i*i+i）是文法（2.1）的一個(gè)句子。8.從一個(gè)句型到另一個(gè)句型的推導(dǎo)過(guò)程往往不是唯一的。所謂最左推導(dǎo)是指任何一步ab都是對(duì)a中最左非終結(jié)符進(jìn)行替換的。同樣可定義最右推導(dǎo)。9.一顆語(yǔ)法樹(shù)表示了一個(gè)句型種種可能的（但未必是所有的）不同推導(dǎo)過(guò)程，包括最左（最

右）推導(dǎo)。這樣的一顆語(yǔ)法樹(shù)是這些不同推導(dǎo)過(guò)程的共性抽象，是它們的代表。一個(gè)句型不一定只對(duì)應(yīng)唯一的一棵語(yǔ)法樹(shù)，也就是不一定只有唯一的一個(gè)最左（最右）推導(dǎo)。

+

10.某文法如果存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)（證明一個(gè)文法是二義的），則說(shuō)這個(gè)

文法是二義性文法�；蛘哒f(shuō)，若一個(gè)文法中存在某個(gè)句子，有兩個(gè)不同的最左推導(dǎo)或最右推導(dǎo)，則該文法是二義的。

11.文法的二義性和語(yǔ)言的二義性是兩個(gè)不同的概念。

12.二義性問(wèn)題是不可判定的，即不存在一個(gè)算法，它能在有限步驟內(nèi)，確切的判定一個(gè)文

法是否為二義的。

13.形式語(yǔ)言鳥(niǎo)瞰：文法分為4種：0型，1型，2性和3型

（1）0型文法也稱(chēng)短語(yǔ)文法，0型文法的能力相當(dāng)于圖靈機(jī)，任何0型語(yǔ)言就是遞歸可枚舉的

（2）1型文法也成為上下文有關(guān)文法。對(duì)非終結(jié)符進(jìn)行替換的時(shí)務(wù)必考慮上下文，并且一般不允許替換成空串e

（3）2型文法也稱(chēng)上下文無(wú)關(guān)文法，非終結(jié)符的替換可以不必考慮上下文。

（4）3型文法也稱(chēng)正規(guī)文法，包括右線性文法（非終結(jié)符在右邊）和左線性文法。14．一個(gè)確定有限自動(dòng)機(jī)（DFA）M是一個(gè)五元式，M=(S,,,S0,F)，

S：有限狀態(tài)集，它的每個(gè)元素稱(chēng)為一個(gè)狀態(tài)。

：有窮字母表，它的每個(gè)元素稱(chēng)為一個(gè)輸入字符。

：狀態(tài)轉(zhuǎn)換函數(shù)，SS{}是單值全映射函數(shù)；S0：唯一的初態(tài)，S0SF：終態(tài)集（可空），F(xiàn)S

15.一個(gè)DFA可以用一個(gè)矩陣表示，行表示狀態(tài)，列表示輸入字符，矩陣元素表示（s,a）

的值。這個(gè)矩陣稱(chēng)為狀態(tài)轉(zhuǎn)換矩陣。

16.一個(gè)DFA也可表示成一張確定的狀態(tài)轉(zhuǎn)換圖。對(duì)于*中的任何字a，若存在一條從

初態(tài)結(jié)點(diǎn)到某一終態(tài)結(jié)點(diǎn)的通路，且這條通路上所有弧的標(biāo)記符連接成的字等于a，則稱(chēng)a可為DFAM所識(shí)別（讀出或接受）。若M的初態(tài)結(jié)點(diǎn)同時(shí)又是終態(tài)結(jié)點(diǎn)，則空字e可為M所識(shí)別。DFAM所能識(shí)別的字的全體記為L(zhǎng)(M)。17.一個(gè)非確定有限自動(dòng)機(jī)（NFA）M是一個(gè)五元式，M=(S,,,S0,F)，

S：有限狀態(tài)集，它的每個(gè)元素稱(chēng)為一個(gè)狀態(tài)。

：有窮字母表，它的每個(gè)元素稱(chēng)為一個(gè)輸入字符。：一個(gè)從S到S的子集的映照，SS0：非空初態(tài)集，S0SF：終態(tài)集（可空），F(xiàn)S

18.有限自動(dòng)機(jī)中若有e則為NFA。狀態(tài)圖中若某一狀態(tài)輸入某字符轉(zhuǎn)換至多個(gè)狀態(tài)

則為NFA。DFA是NFA的特例。對(duì)于每個(gè)NFAM存在一個(gè)DFAM”，使L（M）=L(M”)。NFA確定化為DFA的方法：子集法（P49-50）（必定在有限步內(nèi)完成）19.所謂自上而下語(yǔ)法分析，是從文法的開(kāi)始符號(hào)出發(fā)，反復(fù)使用各產(chǎn)生式，尋找“匹配”

于輸入符號(hào)串的推導(dǎo)。從語(yǔ)法樹(shù)的角度來(lái)看，自上而下方法是從文法符號(hào)開(kāi)始，將它作為語(yǔ)法樹(shù)的根，向下逐步建立語(yǔ)法樹(shù)，使語(yǔ)法樹(shù)的末端結(jié)點(diǎn)符號(hào)串正好是輸入符號(hào)串。這種方法是帶回溯的，是一個(gè)推導(dǎo)+匹配的過(guò)程。面臨的問(wèn)題：

1.文法的左遞歸問(wèn)題2.回溯

3.匹配成功可能是暫時(shí)的(虛假匹配)4.當(dāng)匹配不成功時(shí)不知道出錯(cuò)位置5.效率太低,代價(jià)極高20.直接左遞歸的消除：將P->Pa|b改寫(xiě)為P->bP’P’->aP’|e

21.如果文法G不含以e為右部的產(chǎn)生式并且不存在P=+>P，下述算法消除左遞歸

1）對(duì)文法G中所有狀態(tài)進(jìn)行排序，任意順序均可，得P1P2P3...Pn2)fori=1tonbegin

forj=1toi-1beginif存在Pi-->PjY

將之改寫(xiě)為Pi-->a1Y|a2Y|a3Y...PmY//其中，Pj-->a1|a2...|am是關(guān)于Pj的所有規(guī)則endend采用算法一消除Ai產(chǎn)生式的左遞歸end

22.為了消除回溯就必須保證：對(duì)文法的任何非終結(jié)符，當(dāng)要它去匹配輸入串時(shí)，能夠根據(jù)它所面臨的輸入符號(hào)準(zhǔn)確地指派它的一個(gè)候選去執(zhí)行任務(wù)，并且此候選的工作結(jié)果應(yīng)是確信無(wú)疑的。（不能是虛假匹配）要求是非終結(jié)符A的所有候選首符集兩兩不相交，即A的任何兩個(gè)不同候選ai和ajFIRST(ai)∩FIRST(aj)=空。

23.為達(dá)到上述目的，辦法是提取公共左因子：假定關(guān)于A的規(guī)則是A->b1|b2||bn|r1|r2|r3|…|rm其中每個(gè)r不以開(kāi)頭，那么將之改寫(xiě)成A->A’|r1|r2|r3||rmA’->b1|b2|b3||bn。

24.LL(1)文法：第一個(gè)L表示從左導(dǎo)游掃描輸入串,第二個(gè)L表示最左推導(dǎo),1表示分析時(shí)每一步只需向前查看一個(gè)符號(hào)文法滿足以下條件

（1）文法不含左遞歸

（2）對(duì)于文法中每一個(gè)非終結(jié)符A的各個(gè)產(chǎn)生式的候選首符集兩兩不相交。即若A->a1|a2||an則FIRST(ai)∩FIRST(aj)=空（i!=j）

（3）對(duì)文法中的每個(gè)非終結(jié)符A，若它存在某個(gè)候選首符集包括e，則FIRST(A)∩FOLLOW（A）=空25.實(shí)現(xiàn)LL（1）的一種有效方法是使用一張分析表和一個(gè)棧進(jìn)行聯(lián)合控制：預(yù)測(cè)分析程序。26.對(duì)每個(gè)文法符號(hào)XVT∪VN，構(gòu)造FIRST(X)的方法：（1）若XVT，則FIRST（X）=｛X｝。（2）若XVN，且有產(chǎn)生式X->a…，則把a(bǔ)加入到FIRST（X）中，若X->e也是一條產(chǎn)生式，則把e也加到FIRST（X）中。（3）若X->Y…是一個(gè)產(chǎn)生式，且YVN，則把FIRST（Y）中的所有非e-元素都加入到FIRST（X）中；若X->Y1Y2…Yk是一個(gè)產(chǎn)生式，Y1，…，Yi-1都是非終結(jié)符，而且FIRST（Yj）（1aB是一個(gè)產(chǎn)生式，或A->aBb是一個(gè)產(chǎn)生式且B=>e,則把FOLLOW（A）加至FOLLOW（B）中。

28.構(gòu)造預(yù)測(cè)分析表M的算法是：以文法G的終結(jié)符為表頭，以產(chǎn)生式左部為列頭（1）對(duì)文法G的每個(gè)產(chǎn)生式A->E執(zhí)行第二步和第三步（2）對(duì)每個(gè)終結(jié)符aFIRST(E),把A->E加至M[A,a]中；（3）若eFIRST（E），則對(duì)任何bFOLLOW（A）把A->E加至M[A,b]中（4）把所有無(wú)定義的M[A,a]標(biāo)上“出錯(cuò)標(biāo)志”。29.我們所討論的自下而上分析法是一種移進(jìn)-歸法法。這種方法的大意是用一個(gè)寄存符號(hào)的先進(jìn)后出棧，把輸入符號(hào)一個(gè)一個(gè)地移進(jìn)到棧里，當(dāng)棧頂形成某個(gè)產(chǎn)生式的一個(gè)候選式時(shí)，即把棧頂?shù)倪@一部分替換成（歸約為）該產(chǎn)生式的左部符號(hào)。

30.在算符優(yōu)先分析中，規(guī)范對(duì)象（可歸約串）：最左素短語(yǔ)，在“規(guī)范歸約”分析中，規(guī)范對(duì)象（可歸約串）：句柄（最左直接短語(yǔ)）。

31．短語(yǔ)，直接短語(yǔ)，一個(gè)句型的最左直接短語(yǔ)稱(chēng)為該句型的句柄。32.最右推導(dǎo)通常成為規(guī)范推導(dǎo),由規(guī)范推導(dǎo)所得的句型成為規(guī)范句型如果文法G是無(wú)二義的,則規(guī)范推導(dǎo)(最右推導(dǎo))的逆過(guò)程必須是規(guī)范規(guī)約。

規(guī)范歸約步驟表：表頭：1.步驟（標(biāo)號(hào)，從0開(kāi)始）2.符號(hào)棧（步驟0時(shí)為#）3.輸入串（步驟0時(shí)為輸入串+#）4.動(dòng)作（步驟0時(shí)為預(yù)備，分為進(jìn)和歸，歸包括所用產(chǎn)生式）

最后一行4列值分別為步驟號(hào)#和文法開(kāi)始符號(hào)#接受33.算符優(yōu)先分析法1.不是一種規(guī)范規(guī)約法2.算符優(yōu)先就是尋早可能相繼出現(xiàn)的終結(jié)符a和b的優(yōu)先關(guān)系3.任意產(chǎn)生式右部不能都不含有2個(gè)相繼的非終結(jié)符4.終結(jié)符優(yōu)先級(jí)只有一種5.特別有利于表達(dá)式分析，宜于手工實(shí)現(xiàn)。

34.算符優(yōu)先分析比規(guī)范歸約要快得多，因?yàn)樗惴麅?yōu)先分析跳過(guò)了所有單非產(chǎn)生式所對(duì)應(yīng)的歸約步驟，這既是它的優(yōu)點(diǎn)，同時(shí)也是它的缺點(diǎn)。因?yàn)楹雎苑墙K結(jié)符在歸約過(guò)程中的作用，存在某種危險(xiǎn)性，可能導(dǎo)致把原本不成句子的輸入串誤認(rèn)為是句子。這種缺陷容易從技術(shù)上彌補(bǔ)。

35.一個(gè)文法，若它的任一產(chǎn)生式的右部都不含2個(gè)相繼（并列）的非終結(jié)符，則為算符文法。

36.算符優(yōu)先表：表頭和列均為終結(jié)符號(hào)，表元素為終結(jié)符的優(yōu)先關(guān)系<>=

37.屬性文法(屬性翻譯文法)在上下文無(wú)關(guān)文法的基礎(chǔ)上,為每個(gè)文法符號(hào)配備若干相關(guān)的’值’（稱(chēng)為屬性）.這些屬性代表與文法相關(guān)的信息。屬性的分類(lèi):綜合屬性(自下而上)和繼承屬性(自上而下)

38.語(yǔ)法制導(dǎo)翻譯：給文法每個(gè)產(chǎn)生式制造一個(gè)相應(yīng)的語(yǔ)義子程序,完成對(duì)應(yīng)的翻譯工作,分析過(guò)程中每當(dāng)語(yǔ)法用一個(gè)產(chǎn)生式進(jìn)行規(guī)約或推導(dǎo),驅(qū)動(dòng)對(duì)應(yīng)的語(yǔ)義子程序工作。

39.中間語(yǔ)言的形式:后綴式（又稱(chēng)逆波蘭表示法）三地址代碼(三元式,四元式)DAG圖表示后綴式舉例：（a+b）*(c+d)ab+cd+*后綴式不使用括號(hào)，不論從哪一端進(jìn)行掃描，都能對(duì)它正確進(jìn)行唯一分解。40.賦值語(yǔ)句的翻譯：未完成

41.參數(shù)傳遞:形參實(shí)參途徑:傳地址傳值傳名

42.存儲(chǔ)分配策略：靜態(tài)分配策略在編譯時(shí)對(duì)所有數(shù)據(jù)對(duì)象分配固定的存儲(chǔ)單元，且在運(yùn)行時(shí)始終保持不變。棧式動(dòng)態(tài)分配策略在運(yùn)行時(shí)把存儲(chǔ)器作為一個(gè)棧進(jìn)行管理，運(yùn)行時(shí)，每當(dāng)調(diào)用一個(gè)過(guò)程，它所需要的存儲(chǔ)空間就動(dòng)態(tài)地分配于棧頂，一旦退出，它所占空間就予以釋放。堆式動(dòng)態(tài)分配策略在運(yùn)行時(shí)把存儲(chǔ)器組織成堆結(jié)構(gòu)，以便用戶關(guān)于存儲(chǔ)空間的申請(qǐng)與歸還（回收），凡申請(qǐng)者從堆中分給一塊，反釋放者退回給堆。

43.活動(dòng)記錄:是一個(gè)連續(xù)存儲(chǔ)塊,存儲(chǔ)了管理過(guò)程在一次執(zhí)行中所需要的信息,使用一個(gè)連續(xù)的存儲(chǔ)塊。C的過(guò)程包括：過(guò)程調(diào)用，過(guò)程進(jìn)入，數(shù)組空間分配和過(guò)程返回。44.優(yōu)化:對(duì)程序進(jìn)行等價(jià)變換,使得從變換后的程序出發(fā),能生成更有效的目標(biāo)代碼原則:1.等價(jià)原則:經(jīng)過(guò)優(yōu)化后不應(yīng)改變程序的運(yùn)行結(jié)果2.有效原則:使優(yōu)化后的目標(biāo)代碼運(yùn)行時(shí)間較短,占用的存儲(chǔ)空間較少3.合算原則:應(yīng)盡可能以較低的代價(jià)取得叫好的優(yōu)化效果分類(lèi):局部?jī)?yōu)化:刪除公共子表達(dá)式刪除無(wú)用代碼合并已知量循環(huán)優(yōu)化:代碼外提強(qiáng)度削弱刪除歸納變量全局優(yōu)化:常用優(yōu)化技術(shù)：刪除公共子表達(dá)式強(qiáng)度削弱復(fù)寫(xiě)傳播刪除歸納變量刪除無(wú)用代碼合并已知量代碼外提部分概念：基本塊:程序中順序執(zhí)行的語(yǔ)句序列,其中只有一個(gè)入口和出口,入口就是其中的第一個(gè)語(yǔ)句,出口就是最后一個(gè)語(yǔ)句

流圖:將控制流的信息增加到基本塊的集合上來(lái)表示某個(gè)程序45.目標(biāo)代碼形式:3種1.能夠立即執(zhí)行的機(jī)器語(yǔ)言代碼,所有地址已定位2.待裝配的機(jī)器語(yǔ)言模塊,當(dāng)需要執(zhí)行時(shí),由連接裝入程序把他們和某些運(yùn)行程序連接起來(lái)轉(zhuǎn)換成能執(zhí)行的機(jī)器語(yǔ)言代碼3.匯編語(yǔ)言代碼:尚需經(jīng)過(guò)匯編程序匯編,轉(zhuǎn)換成機(jī)器語(yǔ)言可執(zhí)行的機(jī)器語(yǔ)言代碼

擴(kuò)展閱讀：編譯原理大總結(jié)

《編譯原理》期末復(fù)習(xí)指導(dǎo)

本課程是計(jì)算機(jī)專(zhuān)業(yè)的重要專(zhuān)業(yè)課之一，主要介紹程序設(shè)計(jì)語(yǔ)言編譯構(gòu)造的基本原理和基本實(shí)現(xiàn)方法。本課程主要講授形式語(yǔ)言、有限狀態(tài)自動(dòng)機(jī)和詞法分

析、自頂而下和自底而上的語(yǔ)法分析、中間代碼生成、存儲(chǔ)器的動(dòng)態(tài)分配與管理、符號(hào)表的組織與管理、代碼生成、出錯(cuò)恢復(fù)等內(nèi)容。通過(guò)本課程學(xué)習(xí)，使學(xué)生對(duì)編譯的基本概念、原理和方法有完整的和清楚的理解，并能正確地、熟練地運(yùn)用。

一、通過(guò)本課程的學(xué)習(xí)，應(yīng)使學(xué)生達(dá)到以下基本要求：

1、正確理解什么是編譯程序；了解編譯程序工作的基本過(guò)程及其各階段的基本任務(wù)；熟悉編譯程序總框；了解編譯程序的生成過(guò)程和構(gòu)造工具。

2、理解程序語(yǔ)言詞法、語(yǔ)法和語(yǔ)義等概念；熟悉高級(jí)程序語(yǔ)言一般結(jié)構(gòu)和主要共同特征。正確理解上下文無(wú)關(guān)文法基本概念，包括：文法的定義、編寫(xiě)、句型、句子、語(yǔ)言、語(yǔ)法樹(shù)、二義性等；理解三種參數(shù)傳遞方式：傳值、傳地址、傳名的含義。

3、理解詞法分析器功能及形式；熟練掌握詞法分析器設(shè)計(jì)的原理，掌握運(yùn)用狀態(tài)轉(zhuǎn)換圖進(jìn)行詞法分析器設(shè)計(jì)。

4、正確理解自頂而下分析的基本思想；熟練掌握遞歸下降分析基本方法：消除左遞歸，消除回溯，構(gòu)造遞歸下降子程序；掌握預(yù)測(cè)分析程序的基本原理和預(yù)測(cè)分析表構(gòu)造；理解LL(1)方法的定義。

5、正確理解自下而上語(yǔ)法分析的基本思想，以及歸約、短語(yǔ)、句柄、分析樹(shù)等概念；掌握算符優(yōu)先分析基本方法：算符優(yōu)先表和和算符優(yōu)先函數(shù)構(gòu)造技術(shù)。6、正確理解語(yǔ)法制導(dǎo)翻譯基本原理；掌握基于屬性文法的處理方法，了解自上而下分析制導(dǎo)翻譯基本思想和實(shí)現(xiàn)方法。

7、熟悉常見(jiàn)的幾種中間語(yǔ)言：四元式、三元式、逆波蘭表示；掌握各種語(yǔ)句到四元式的翻譯方法，包括：簡(jiǎn)單算術(shù)表達(dá)式，布爾表達(dá)式，控制語(yǔ)句，數(shù)組引用，過(guò)程調(diào)用等。8、理解符號(hào)表的作用及符號(hào)表組織和使用方法，了解名字的作用范圍，了解符號(hào)表中一般應(yīng)包含的內(nèi)容。

9、正確理解目標(biāo)程序運(yùn)行進(jìn)存儲(chǔ)空間的使用和組織管理方式；理解靜態(tài)分配和動(dòng)態(tài)存儲(chǔ)分配基本思想；掌握FORTRAN存儲(chǔ)分配的處理方式；掌握棧式動(dòng)態(tài)分配中活動(dòng)記錄的作用、組織、內(nèi)容及使用；了解嵌套過(guò)程語(yǔ)言程序運(yùn)行時(shí)整個(gè)運(yùn)行棧的內(nèi)容的組織。

10、正確理解代碼優(yōu)化的定義和各種可能的優(yōu)化概念；掌握用DAG表示進(jìn)行局部?jī)?yōu)化的方法。

11、正確理解代碼生成過(guò)程的基本問(wèn)題，理解待用信息、寄存器描述和地址描述等概念；掌握簡(jiǎn)單代碼生成算法、寄存器分配策略。二、文字教材

文字教材是教學(xué)媒體的核心，是傳遞教學(xué)信息及學(xué)生進(jìn)行自主學(xué)習(xí)的基本依據(jù)，是整個(gè)教學(xué)媒體體系的基礎(chǔ)。包括主教材、學(xué)習(xí)指導(dǎo)書(shū)和參考資料匯編、教學(xué)大綱、課程教學(xué)設(shè)計(jì)方案、復(fù)習(xí)提要等。1、《編譯原理》徐國(guó)定編著，高等教育出版社。參考資料：

1、《程序設(shè)計(jì)語(yǔ)言編譯原理（第3版）》陳火旺、劉春林等編著，國(guó)防工業(yè)出版社。

2、《程序設(shè)計(jì)語(yǔ)言與編譯》龔天富、侯文永編，電子工業(yè)出版社。3、《編譯原理習(xí)題與解析》伍春香編著，清華大學(xué)出版社。4、《編譯原理》呂映芝張素琴蔣維杜，清華大學(xué)版社。

三、教學(xué)內(nèi)容和教學(xué)要求第一章概論

主要內(nèi)容：編譯程序，編譯過(guò)程概述，編譯程序的結(jié)構(gòu)，編譯程序與程序設(shè)計(jì)環(huán)境，編譯程序生成，學(xué)習(xí)構(gòu)造編譯程序。

重點(diǎn)：編譯程序工作的基本過(guò)程及其各階段的基本任務(wù)，編譯程序總框。第二章形式語(yǔ)言基礎(chǔ)主要內(nèi)容：程序語(yǔ)言定義，初等數(shù)據(jù)類(lèi)型，數(shù)據(jù)結(jié)構(gòu)，高級(jí)高級(jí)語(yǔ)言的一般特性，程序結(jié)構(gòu)，語(yǔ)句與控制結(jié)構(gòu)，上下文無(wú)關(guān)文法，語(yǔ)法分析樹(shù)與二義性。重點(diǎn)：上下文無(wú)關(guān)文法，程序語(yǔ)言定義參數(shù)傳遞。第三章有限狀態(tài)自動(dòng)機(jī)和詞法分析

主要內(nèi)容：詞法分析器任務(wù)，詞法分析器設(shè)計(jì)，正規(guī)表達(dá)式與有限自動(dòng)機(jī)，詞法分析器自動(dòng)生成。

重點(diǎn)：詞法分析器的任務(wù)與設(shè)計(jì)，狀態(tài)轉(zhuǎn)換圖。第四章自頂向下句法分析

主要內(nèi)容：語(yǔ)法分析器的功能，自上而下語(yǔ)法分析（遞歸下降分析法，預(yù)測(cè)分析程序），LL（1）分析法，遞歸下降分析程序構(gòu)造，預(yù)測(cè)分析程序，自上而下分析的錯(cuò)誤診察，語(yǔ)義錯(cuò)誤診察。

重點(diǎn)：遞歸下降子程序，預(yù)測(cè)分析表構(gòu)造，LL(1)文法。第五章自底向上句法分析

主要內(nèi)容：自下而上語(yǔ)法分析（算符優(yōu)先分析法），算符優(yōu)先分析，LR分析器，LR(0)項(xiàng)目集族和LR(0)分析表的構(gòu)造，SLR分析表的構(gòu)造，規(guī)范LR分析表的構(gòu)造，出錯(cuò)處理概述，詞法分析階段的錯(cuò)誤診察，語(yǔ)法分析（自下而上）階段的錯(cuò)誤診察，語(yǔ)法分析器自動(dòng)產(chǎn)生工具YACC。重點(diǎn)：歸約，算符優(yōu)先表構(gòu)造，LR分析法。第六章中間代碼生成和符號(hào)表

主要內(nèi)容：中間語(yǔ)言，說(shuō)明語(yǔ)句，賦值語(yǔ)句的翻譯，布爾表達(dá)式的翻譯，控制語(yǔ)句的翻譯，過(guò)程調(diào)用的處理各種常見(jiàn)中間語(yǔ)言形式，各種語(yǔ)句到四元式的翻譯。符號(hào)表的組織與作用，整理與查找，名字的作用范圍，符號(hào)表的內(nèi)容。重點(diǎn)：三種中間語(yǔ)言：四元式、三元式、逆波蘭表示；算術(shù)表達(dá)式的翻譯，布爾表達(dá)式的翻譯，控制語(yǔ)句的翻譯。符號(hào)表的作用與內(nèi)容。第七章運(yùn)行時(shí)刻存儲(chǔ)和環(huán)境管理

主要內(nèi)容：目標(biāo)程序運(yùn)行時(shí)的活動(dòng)，運(yùn)行時(shí)存儲(chǔ)器的劃分，靜態(tài)存儲(chǔ)管理，簡(jiǎn)單的棧式存儲(chǔ)分配的實(shí)現(xiàn)，嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)，堆式動(dòng)態(tài)存儲(chǔ)分配。重點(diǎn)：靜態(tài)分配策略和動(dòng)態(tài)分配策略基本思想，嵌套過(guò)程語(yǔ)言棧式分配，活動(dòng)記錄、運(yùn)行時(shí)棧的組織。第八章代碼生成

主要內(nèi)容：目標(biāo)機(jī)器模型，一個(gè)簡(jiǎn)單代碼生成器，寄存器分配，DAG目標(biāo)代碼，窺孔優(yōu)化。

重點(diǎn)：簡(jiǎn)單代碼生成器，寄存器分配策略。第九章出錯(cuò)恢復(fù)

主要內(nèi)容：詞法分析的出錯(cuò)恢復(fù)，LR和LL句法分析的出錯(cuò)恢復(fù)重點(diǎn)：錯(cuò)誤的恢復(fù)方法。

四、考核方式說(shuō)明

該課程的考核由形成性考核和期末課程考核兩部分組成。其中形成性考核成績(jī)由平時(shí)作業(yè)和上機(jī)實(shí)驗(yàn)兩部分成績(jī)組成,各占總成績(jī)的10%，期末課程考核占總成績(jī)的80%。

平時(shí)作業(yè)考核：要求學(xué)生認(rèn)真完成平時(shí)作業(yè)，各辦學(xué)點(diǎn)應(yīng)組織作業(yè)的批改和成績(jī)的核定。平時(shí)作業(yè)的成績(jī)?cè)u(píng)定標(biāo)準(zhǔn)和要求按省電大有關(guān)文件執(zhí)行。上機(jī)實(shí)驗(yàn)考核：學(xué)員必須完成規(guī)定的上機(jī)實(shí)驗(yàn)，并撰寫(xiě)實(shí)驗(yàn)報(bào)告，由輔導(dǎo)實(shí)驗(yàn)的老師批改并評(píng)定成績(jī)，學(xué)員實(shí)驗(yàn)成績(jī)?cè)u(píng)定單必須加蓋承擔(dān)實(shí)驗(yàn)單位的公章方能生效。

課程結(jié)業(yè)考核：該課程的結(jié)業(yè)考核在期末進(jìn)行，采用筆試、閉卷，由省電大統(tǒng)一組織命題，試卷采用百分制，卷面成績(jī)按80%的比例折算計(jì)入總成績(jī)。四、考試題型

試題類(lèi)型包括：選擇題，判斷題，填空題，簡(jiǎn)答題，應(yīng)用題。模擬試題

一、單項(xiàng)選擇題

1．把匯編語(yǔ)言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由______完成的。A．編譯器B．解釋器C．匯編器D．預(yù)處理器2．編譯過(guò)程中，語(yǔ)法分析器的任務(wù)是______。1)分析單詞是怎樣構(gòu)成的

2)分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的3)分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的4)分析程序的結(jié)構(gòu)

A．2和3B．3和4C．2，3和4D．1，2，3和4

3．高級(jí)語(yǔ)言編譯程序常用的語(yǔ)法分析方法中，遞歸下降分析法屬于______分析方法。

A．自左至右B．自頂向下C．自底向上D．自右向左4．算符優(yōu)先文法是指_______的文法。

1)沒(méi)有形如U->…VW…的規(guī)則（U，V，W∈Vn）

2)終結(jié)符號(hào)集Vt中任意兩個(gè)符號(hào)對(duì)之間至多有一種優(yōu)先關(guān)系成立。3)沒(méi)有相同的規(guī)則右部。4)沒(méi)有形如U->ε的規(guī)則

A．1，2B．1，2，3C．1，2，3，4D．1，2，45．動(dòng)態(tài)存儲(chǔ)分配時(shí)，可以采用的分配方法是1)以過(guò)程為單位的棧式動(dòng)態(tài)存儲(chǔ)分配2)堆存儲(chǔ)分配3)最佳分配方法

A．1B．2C．1，2D．1，2，3

二、填空題

1．編譯方式和解釋方式的根本區(qū)別在于__________________。

2．LL（1）分析法中，第一個(gè)L的含義是_________________，第二個(gè)L的含義是___________________，“1”的含義是____________________。

3．過(guò)程調(diào)用時(shí)，參數(shù)的傳遞方法通常有__________、__________、__________和傳名。

4．一個(gè)上下文無(wú)關(guān)文法所含四個(gè)組成部分是____________集、______________集、_____________集和______________集。

三、判斷題

1．算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。…………（）2．每個(gè)文法都能改寫(xiě)為L(zhǎng)L(1)文法�！�……………………（）3．符號(hào)表由詞法分析程序建立，由語(yǔ)法分析程序使用……（）4．上下文無(wú)關(guān)文法規(guī)則的左部一定是非終結(jié)符號(hào)…………（）5．LL（1）文法有可能是二義性的。…………………………（）

四、簡(jiǎn)述題

1．簡(jiǎn)述詞法分析階段的任務(wù)。

2．什么是語(yǔ)法制導(dǎo)翻譯？

3．什么是素短語(yǔ)？

4．什么是靜態(tài)存儲(chǔ)分配？

5．畫(huà)圖說(shuō)明編譯程序的組成結(jié)構(gòu)。

五、綜合應(yīng)用題1．設(shè)文法G(S)：S→(L)|aS|aL→L，S|S

(1)消除左遞歸和回溯；

(2)計(jì)算每個(gè)非終結(jié)符的FIRST和FOLLOW；(3)構(gòu)造預(yù)測(cè)分析表。

2．已知文法G(E)E→T|E＋TT→F|T*FF→(E)|i

(1)給出句型(T*F＋i)的最右推導(dǎo)及畫(huà)出語(yǔ)法樹(shù)；(2)給出句型(T*F＋i)的短語(yǔ)、素短語(yǔ)。參考答案

一、單項(xiàng)選擇題題號(hào)1答案C二、填空題

1．是否生成目標(biāo)代碼

2．從左向右進(jìn)行分析，每次進(jìn)行最左推導(dǎo)，向輸入串中查看一個(gè)輸入符號(hào)3．傳值，傳地址，傳結(jié)果（順序可互換）

2C3B4D5C4．終結(jié)符、非終結(jié)符、開(kāi)始符號(hào)、產(chǎn)生式（順序可互換）

三、判斷題1．√2．×3．×4．√5．×

四、名詞解釋

1、答:詞法分析的基本任務(wù)是從左向右掃描每行源程序的符號(hào)，識(shí)別出單詞及其屬性，把單詞換成統(tǒng)一的內(nèi)部表示送給語(yǔ)法分析程序。同時(shí)還要完成在語(yǔ)法分析之前需要做的工作，如刪除注解、空格、換行符等非必要信息，把標(biāo)識(shí)符登錄到符號(hào)表及某些預(yù)加工處理等。

2、答:語(yǔ)法制導(dǎo)翻譯就是在進(jìn)行語(yǔ)法分析的同時(shí)，完成語(yǔ)義的分析，即在語(yǔ)法分析的過(guò)程中，根據(jù)語(yǔ)言的語(yǔ)義定義隨時(shí)翻譯已識(shí)別的那部分語(yǔ)法成分的全部含義。

答:有以下特征的短語(yǔ)稱(chēng)為素短語(yǔ)：1)它首先是一個(gè)短語(yǔ)。2)它至少含一個(gè)終結(jié)符號(hào)。3)除自身外，不再包含其它素短語(yǔ)。

3、答:如果在編譯時(shí)就能確定一個(gè)程序在運(yùn)行時(shí)所需要的存儲(chǔ)空間的大小，則在編譯時(shí)就能夠安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，并確定每個(gè)數(shù)據(jù)項(xiàng)的存儲(chǔ)單元地址，而這些數(shù)據(jù)項(xiàng)的存儲(chǔ)地址在運(yùn)行時(shí)始終不變，這就是靜態(tài)存儲(chǔ)分配。4、答：表格管理詞法分析語(yǔ)法分析語(yǔ)義分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成錯(cuò)誤處理

五、綜合應(yīng)用題1．解：(1)

S→(L)|aS’S’→S|εL→SL’L’→SL’|ε(2)

FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)}FIRST(S’)＝{，a,ε}FOLLOW(S’)＝{#，，，)}FIRST(L)＝{(，a}FOLLOW(L)＝{)}FIRST(L’)＝{，，ε}FOLLOW(L’〕＝{)}(3)SS’La，()＃S→aS’S→(L)S’→SS’→εS’→SS’→εS’→εL→SL’L→SL’L’L’→εL’→ε2．答：(1)最右推導(dǎo)：

E→T→F→(E)→(E＋T)→(E＋F)→(E＋i)→(T＋i)→(T*F＋i)語(yǔ)法樹(shù)：ETF(E)E+TTFT*Fi

(2)短語(yǔ)：(T*F＋i)，T*F＋i，T*F，素短語(yǔ)：T*F,i

i

友情提示：本文中關(guān)于《編譯原理文字總結(jié)》給出的范例僅供您參考拓展思維使用，編譯原理文字總結(jié)：該篇文章建議您自主創(chuàng)作。

來(lái)源：網(wǎng)絡(luò)整理 免責(zé)聲明：本文僅限學(xué)習(xí)分享，如產(chǎn)生版權(quán)問(wèn)題，請(qǐng)聯(lián)系我們及時(shí)刪除。

《編譯原理文字總結(jié)》由互聯(lián)網(wǎng)用戶整理提供,轉(zhuǎn)載分享請(qǐng)保留原作者信息,謝謝!
鏈接地址：http://m.seogis.com/gongwen/747429.html

• 上一篇：通信原理總結(jié)
• 下一篇：化工原理重要知識(shí)點(diǎn)總結(jié)