1、考試題型：填空24%簡答4*4=16%+解答4*15=6Chapter 1重要概念1什么編譯程序？ P3答：編譯程序的主要功能是把用高級語言編寫的源程序翻譯為等價的目標程序。2. 編譯程序的工作過程？（6個階段）P41、詞法分析程序 2、語法分析程序 3、語義分析程序 4、中間代碼生成5、代碼優化程序6、目標代碼生成（不做優化是4個階段，5、6不要）3. 編譯程序的邏輯結構？ P4圖1-2編譯程序的邏輯結構信息表管憂程序錯濱栓查和攤理程序4. 執行高級語言編寫的程序：（編譯執行、解釋執行）1）按編譯方式在計算機上執行用高級語言編寫的程序，一般須經過兩個階段。第一個階段 稱為編譯階段，其任務是由

2、編譯程序將源程序編譯為目標程序，若目標程序不是機器代碼， 而是匯編語言程序，則尚需匯編程序再行匯編為機器代碼程序；第二階段稱為運行階段， 其任務是在目標計算機上執行編譯階段所得到的目標程序。2）用高級語言編寫的程序也可以通過解釋程序來執行。解釋程序也以源程序作為它的輸 入，它與編譯程序的主要區別是在解釋程序的執行過程中不產生目標程序，而是解釋執行 源程序本身。缺點：這種邊翻譯邊執行的方式工作效率很低，但由于解釋程序的結構比編譯程序簡單， 且占用內存較少，在執行過程中也易于在源程序一級對程序進行修改，因此一些規模較小 的語言，如BASIC,也常米用此種方式。5. P 11第一段編譯程序的各部分之

3、間的關系，是指他們之間的邏輯關系，而不一定是執行時間上的先后 順序，事實上，可按不同的執行流程來組織上述各部分的工作，這在很大程度上依賴與編 譯過程中對源程序掃描的遍數，以及如何劃分各遍掃描所進行的工作。此處所說的“遍”，是指對源程序或其內部表示從頭到尾掃視一次，并進行有關的加工處理工作。（執行過程：單遍掃描、多遍掃描（大多數）Chapter 2前后文無關文法和語言1. 文法和語言的形式定義產生語言就是制定出有限個規則（文法），借助于它們，就能產生出此語言的全部句子。2. 文法規則四要素：文法：四要素（VN, VT，S，P）。1）產生語言的規則中的一系列需定義的語法范疇的名字稱為非終結符 號（

4、大寫字母）,其集合記為VN2）規則中不需進一步定義的基本符號稱為終結符號,其集合記為VT3）非終結符中最終需定義的那個為推導句子開始的語法范疇，稱其為開始符號或識別符號，記作S4）每一規則是用：:= 或-> 連接起來的有序對，也稱為產生式，用P表示3. 句型的分析 是指構造一種算法，用以判斷所給符號串是否為某一文法的句型（或句子）。分兩類方法：自頂向下 分析：從開始符 推導出句子或句型自底向上 分析：從句子或句型 歸約出開始符4. 短語和句柄語法樹的應用語法分析（自頂向下分析，自底向上分析）用語法樹進行句型分析：用語法樹自頂向下進行推導 ，-最右推導用語法樹自底向上進行歸約。-最左規約5

5、. 文法和語言的 Chomsky分類1）0型文法或短語結構文法（PSG）2）1型文法或前后文有關文法 （CSG）3）2型文法或前后文無關文法 （CFG）.4） 3型文法或正規文法。（左線性文法+右線性文法）編譯過程的詞法分析使用正規文法（3型文法）描述單詞結構；語法分析采用前后文無關文法（2型文法）描述語句結構 課堂練習1） Chomsky定義的四種形式語言文法分別為0型文法，1型文法，2型文法,3型文法, 其中3型文法用于描述詞法，2型文法用于描述語法。2）遞歸文法產生的語言語句集合是無限集合。3）規范推導是最 右推導，規范歸約是最 左歸約。 定義每種語言的文法都是 不（不| ）唯一的。文法

6、的化簡與改造主要包括無用符號和無用產生式的刪除，£產生式的消除，單產生式的消除幾項內容。大題：1）畫出句子的語法樹，找出所有的短語，直接短語和句柄（運算符最低原則）Chapter3詞法分析及詞法分析程序1）了解6種定義，特點正規文法、狀態轉換圖、有限自動機FA（NFA DFA）、狀態轉換矩陣、正規表達式、正規集大題：正規式狀態圖（ NFA 確定化最小化順序：或，連接，閉包（1）狀態轉換圖的五要素1 ）有限非空狀態集 K2 ）有限輸入字母表刀3 ）狀態之間的映射關系 f4 ）初態S0 K5 ）終態集Z K（2）1.確定的有限自動機（DFA若FA在每個狀態，對輸入符號的下一狀態是唯一的，

7、稱此種FA為確定的有限自動機 DFA2. 非確定的有限自動機（NFA若FA在某個狀態，對輸入符號的下一狀態不是唯一的，而是狀態集的一個子集，稱此種FA為非確定的有限自動機 NFA（3）正規式中用到符號：閉包連接（不引起混亂可略去）最優（優先順序可用括號加以改變） 次之最后正規式：將文法的終結符號用以上三種運算符連接起來組成的正規文法的表達式，是另一種用于描述正規文法的直觀表示。正規集：正規式所描述的字符串的集合。（4）詞法分析方法（正規文法、狀態轉換圖、狀態轉換矩陣）（5） 單詞描述（正規文法、狀態轉換圖、有限自動機FA（NFA DFA、狀態轉換矩陣、正 規表達式、正規集）課堂練習：1. 單詞

8、的編譯器內部表示為二元式（class , value ）2. 單詞的描述形式有許多種，包括文法形式正規文法，圖示方式狀態轉換圖，便于計算機存儲的 狀態轉換矩陣，自動機又分為NFAQFA兩種，正規表達式和 正規集最便于體現單詞的結構3. Bell實驗室M.Lesk等人用C語言研制的一個詞法分析程序的自動生成工具叫LEX4. 判斷（對）所有帶有£的自動機都是非確定的自動機Chapter 4語法分析和語法分析程序1.語法分析方法：自頂向下分析法：如遞歸下降法，LL （1 ）等（最左推導）自底向上分析法：如算符優先法（分析表達式常用），LR等（最右規約）大題 LR、SLR1（1）LL （1）

9、-預測分析法（LL （1）分析法一最左推導一 LL （1）分析表）1）編寫文法，消除二義性；2）消除左遞歸、提取左因子；3）求 FIRST 集和 FOLLOW集FIRST（ 丫 ）: 丫可以推出的開頭的終結符號 （或& ）FOLLOW（A）在所有句型中可能直接跟在A之后的終結符號4）檢查是不是LL（1） 文法（若不是LL（1），說明文法的復雜性超過自頂向下方法的分析能力）5）按照LL（1）文法構造預測分析表6）實現預測分析器（2）算符優先分析法（構造算符優先矩陣一分析句子）廣義運算符：文法的終結符號廣義運算對象：非終結符（3）LR （ 0）分析法A. 引入S' ->S拓廣

10、文法B. 構造識別所有規范句型全部的活前綴的DFAC. 構造LR （0 ）分析表 r產生式編號D. 分析句子（4）SLR（1）分析表將文法拓廣（2）構造識別文法全部規范句型活前綴的DFA求非終結符號Follow（）集合（4）對每個項目集按以下四條規則填表： 若項目集L中有S,->S 置if#=Me 若項目集Ii中有a的項目，A” 口為第j個產生式，則Follow（A）元素所在列置歸約動作為町 若項目集I沖形如A> a 的項目若二口/為終結符，置i以】為Sj”x為非終結符,置【i“為j - ©分析表中無定義的元素均表示"出錯課堂練習1、LL （1）分析器由_緩沖區

11、 _ ,分析棧_，分析表 _,控制程序四部分組成。2、 語法分析的方法主要分為自頂向下_和 自底向上_兩大類，前者又包括 LL（1）分析法 和遞歸下降法 兩種具體方法，后者又包括 LR分析法和算符優先分析法 兩種具體方法3、判斷（錯）1、自頂向下語法分析采用規范推導。（最左）（對）2、所有左遞歸文法均無法直接用LL（ 1）分析方法進行語法分析。（錯）3、所有的自底向上語法分析，每步分析都是找出當前句型的句柄進行歸約。（算符優先矩陣t最左素短語 ）（對）4、一個文法如果是 LR （ 0）文法，則必定是 LR （1）文法。（更多的文法適應SL R（l）Chapter 5語法制導翻譯及中間代碼生成1）語法制導翻譯： 在一遍掃描中，由語法分析引導 ，既完成語法分析任務，又完成語義分析 和中間代碼生成方面的工作。實現方法：對文法中的每一產生式，都附加一“語義動作”或“語義子程序”，且在語法分析過程中，每當用一產生式進行推導或歸約時，語法分