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

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

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

單詞（亦稱單詞符號或符號）如基本字，標識符，常數(shù)，算符和界符。

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

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

(3)語義分析與中間代碼產(chǎn)生：對語法分析所識別出的各類語法范疇，分析其含義，并

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

時間和空間）的目標代碼。

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

碼。

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

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

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

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

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

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

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

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

+

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

文法是二義性文法。或者說，若一個文法中存在某個句子，有兩個不同的最左推導(dǎo)或最右推導(dǎo)，則該文法是二義的。

11.文法的二義性和語言的二義性是兩個不同的概念。

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

法是否為二義的。

13.形式語言鳥瞰：文法分為4種：0型，1型，2性和3型

（1）0型文法也稱短語文法，0型文法的能力相當于圖靈機，任何0型語言就是遞歸可枚舉的

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

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

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

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

：有窮字母表，它的每個元素稱為一個輸入字符。

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

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

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

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

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

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

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

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

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

于輸入符號串的推導(dǎo)。從語法樹的角度來看，自上而下方法是從文法符號開始，將它作為語法樹的根，向下逐步建立語法樹，使語法樹的末端結(jié)點符號串正好是輸入符號串。這種方法是帶回溯的，是一個推導(dǎo)+匹配的過程。面臨的問題：

1.文法的左遞歸問題2.回溯

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

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

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

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

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

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

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

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

（1）文法不含左遞歸

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

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

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

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

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

規(guī)范歸約步驟表：表頭：1.步驟（標號，從0開始）2.符號棧（步驟0時為#）3.輸入串（步驟0時為輸入串+#）4.動作（步驟0時為預(yù)備，分為進和歸，歸包括所用產(chǎn)生式）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一、通過本課程的學習，應(yīng)使學生達到以下基本要求：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

四、考核方式說明

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

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

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

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

一、單項選擇題

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

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

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

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

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

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

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

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

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

二、填空題

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

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

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

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

三、判斷題

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

四、簡述題

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

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

3．什么是素短語？

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

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

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

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

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

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

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

一、單項選擇題題號1答案C二、填空題

1．是否生成目標代碼

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

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

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

四、名詞解釋

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

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

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

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

五、綜合應(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)語法樹：ETF(E)E+TTFT*Fi

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

i

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

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

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

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