河北工業(yè)大學編譯原理期末復習

1、考試題型：填空考試題型：填空24%24%簡答簡答44=16%44=16%解答解答415=6415=6ChapterChapter1重要概念重要概念1.1.什么編譯程序？什么編譯程序？P3P3答：編譯程序的主要功能是把用高級語言編寫的源程序翻譯為等價的目標程序。答：編譯程序的主要功能是把用高級語言編寫的源程序翻譯為等價的目標程序。2.2.編譯程序的工作過程？（編譯程序的工作過程？（6個階段）個階段）P4P41、詞法分析程序詞法分析程序2、

2、語法分析程序、語法分析程序3、語義分析程序、語義分析程序4、中間代碼生成、中間代碼生成5、代碼優(yōu)化程序代碼優(yōu)化程序6、目標代碼生成、目標代碼生成（不做優(yōu)化是（不做優(yōu)化是4個階段，個階段，5、6不要）不要）3.3.編譯程序的邏輯結構？編譯程序的邏輯結構？P4P4圖1212編譯程序的邏輯結構編譯程序的邏輯結構4.4.執(zhí)行高級語言編寫的程序：（執(zhí)行高級語言編寫的程序：（編譯執(zhí)行、解釋執(zhí)行編譯執(zhí)行、解釋執(zhí)行）1）按編譯方式編譯方式在計算機上執(zhí)行

3、用高級語言編寫的程序，一般須經過兩個階段。第一個階段在計算機上執(zhí)行用高級語言編寫的程序，一般須經過兩個階段。第一個階段稱為編譯階段，其任務是由編譯程序將源程序編譯為目標程序，若目標程序不是機器代碼，稱為編譯階段，其任務是由編譯程序將源程序編譯為目標程序，若目標程序不是機器代碼，而是匯編語言程序，則尚需匯編程序再行匯編為機器代碼程序；第二階段稱為運行階段，而是匯編語言程序，則尚需匯編程序再行匯編為機器代碼程序；第二階段稱為運行階段，其任務

4、是在目標計算機上執(zhí)行編譯階段所得到的目標程序。其任務是在目標計算機上執(zhí)行編譯階段所得到的目標程序。2）用高級語言編寫的程序也可以通過用高級語言編寫的程序也可以通過解釋程序解釋程序來執(zhí)行。解釋程序也以源程序作為它的輸入，來執(zhí)行。解釋程序也以源程序作為它的輸入，它與編譯程序的主要區(qū)別是在解釋程序的執(zhí)行過程中不產生目標程序，而是解釋執(zhí)行源程它與編譯程序的主要區(qū)別是在解釋程序的執(zhí)行過程中不產生目標程序，而是解釋執(zhí)行源程序本身。序本身。缺點：這種

5、邊翻譯邊執(zhí)行的方式工作效率很低，但由于解釋程序的結構比編譯程序簡單，缺點：這種邊翻譯邊執(zhí)行的方式工作效率很低，但由于解釋程序的結構比編譯程序簡單，且占用內存較少，在執(zhí)行過程中也易于在源程序一級對程序進行修改，因此一些規(guī)模較小且占用內存較少，在執(zhí)行過程中也易于在源程序一級對程序進行修改，因此一些規(guī)模較小的語言，如的語言，如BASICBASIC，也常采用此種方式。，也常采用此種方式。5.5.P11P11第一段第一段編譯程序的各部分之間的關系

6、，是指他們之間的邏輯關系，而不一定是執(zhí)行時間上的先后編譯程序的各部分之間的關系，是指他們之間的邏輯關系，而不一定是執(zhí)行時間上的先后順序，事實上，可按不同的執(zhí)行流程來組織上述各部分的工作，這在很大程度上依賴與編順序，事實上，可按不同的執(zhí)行流程來組織上述各部分的工作，這在很大程度上依賴與編譯過程中對源程序掃描的遍數，以及如何劃分各遍掃描所進行的工作。此處所說的譯過程中對源程序掃描的遍數，以及如何劃分各遍掃描所進行的工作。此處所說的“遍”，是

7、指對源程序或其內部表示從頭到尾掃視一次，并進行有關的加工處理工作。是指對源程序或其內部表示從頭到尾掃視一次，并進行有關的加工處理工作。（執(zhí)行過程：（執(zhí)行過程：單遍掃描、多遍掃描（大多數）單遍掃描、多遍掃描（大多數））ChapterChapter2前后文無關文法和語言前后文無關文法和語言1.1.文法和語言的形式定義文法和語言的形式定義產生語言就是制定出有限個規(guī)則（文法）產生語言就是制定出有限個規(guī)則（文法），借助于它們，就能產生出此語言的全

8、部句子。，借助于它們，就能產生出此語言的全部句子。2.2.文法規(guī)則四要素文法規(guī)則四要素:文法文法:四要素（四要素（VNVN，VTVT，S，P）。1)1)產生語言的規(guī)則中的一系列需定義的語法范疇的名字稱為產生語言的規(guī)則中的一系列需定義的語法范疇的名字稱為非終結符非終結符號(大寫字母大寫字母))其集合其集合記為記為VNVN若FAFA在某個狀態(tài)，對輸入符號的下一狀態(tài)不是唯一的，而是狀態(tài)集的一個子集，稱此種在某個狀態(tài)，對輸入符號的下一狀態(tài)不是唯

9、一的，而是狀態(tài)集的一個子集，稱此種FAFA為非確定的有限自動機為非確定的有限自動機NFANFA。（3）正規(guī)式中用到符號：）正規(guī)式中用到符號：閉包閉包最優(yōu)最優(yōu)（優(yōu)先順序可用括號加以改變）（優(yōu)先順序可用括號加以改變）連接（不引起混亂可略去）連接（不引起混亂可略去）次之次之|或最后最后正規(guī)式正規(guī)式：將文法的終結符號用以上三種運算符連接起來組成的正規(guī)文法的表達式，是另一：將文法的終結符號用以上三種運算符連接起來組成的正規(guī)文法的表達式，是另一種用

10、于描述正規(guī)文法的直觀表示。種用于描述正規(guī)文法的直觀表示。正規(guī)集正規(guī)集：正規(guī)式所描述的字符串的集合。：正規(guī)式所描述的字符串的集合。（4）詞法分析方法詞法分析方法（正規(guī)文法、狀態(tài)轉換圖、狀態(tài)轉換矩陣）（正規(guī)文法、狀態(tài)轉換圖、狀態(tài)轉換矩陣）（5）單詞描述單詞描述（正規(guī)文法、狀態(tài)轉換圖、有限自動機（正規(guī)文法、狀態(tài)轉換圖、有限自動機FAFA（NFANFA、DFADFA）、狀態(tài)轉換矩陣、正、狀態(tài)轉換矩陣、正規(guī)表達式、正規(guī)集）規(guī)表達式、正規(guī)集）課堂練

11、習：課堂練習：1.1.單詞的編譯器內部表示為二元式（單詞的編譯器內部表示為二元式（classclassvaluevalue）2.2.單詞的描述形式有許多種，包括文法形式單詞的描述形式有許多種，包括文法形式正規(guī)文法正規(guī)文法，圖示方式，圖示方式狀態(tài)轉換圖狀態(tài)轉換圖，便于計算機存儲的便于計算機存儲的狀態(tài)轉換矩陣狀態(tài)轉換矩陣，自動機又分為，自動機又分為NFADFANFADFA兩種，兩種，正規(guī)表達式正規(guī)表達式和正規(guī)集正規(guī)集最便于體現單詞的結構最便

12、于體現單詞的結構3.Bell3.Bell實驗室實驗室M.LeskM.Lesk等人用等人用C語言研制的一個詞法分析程序的自動生成工具叫語言研制的一個詞法分析程序的自動生成工具叫LEXLEX4.4.判斷（判斷（對）所有帶有）所有帶有ε的自動機都是非確定的自動機的自動機都是非確定的自動機ChapterChapter4語法分析和語法分析程序語法分析和語法分析程序1.1.語法分析方法語法分析方法:自頂向下分析法：如遞歸下降法，自頂向下分析法：如遞

13、歸下降法，LLLL（1）等（）等（最左推導最左推導）自底向上分析法：如算符優(yōu)先法（分析表達式常用）自底向上分析法：如算符優(yōu)先法（分析表達式常用），LRLR等（等（最右規(guī)約最右規(guī)約）大題大題LRLR、SLR1SLR1（1）LLLL（1）預測分析法（預測分析法（LLLL（1）分析法）分析法→最左推導最左推導→LL→LL（1）分析表）分析表）1)1)編寫文法，消除二義性；編寫文法，消除二義性；2)2)消除左遞歸、提取左因子；消除左遞歸、提取左

14、因子；3)3)求FIRSTFIRST集和集和FOLLOWFOLLOW集FIRST(γ)FIRST(γ):γ:γ可以推出的開頭的終結符號可以推出的開頭的終結符號(或ε)ε)FOLLOW(A)FOLLOW(A):在所有句型中可能直接跟在在所有句型中可能直接跟在A之后的終結符號之后的終結符號4）檢查是不是）檢查是不是LL(1)LL(1)文法文法（若不是（若不是LL(1)LL(1)，說明文法的復雜性超過自頂向下方法的分析能力，說明文法的復雜性超

15、過自頂向下方法的分析能力）5）按照按照LL(1)LL(1)文法構造預測分析表文法構造預測分析表6）實現預測分析器實現預測分析器（2）算符優(yōu)先分析法）算符優(yōu)先分析法(構造算符優(yōu)先矩陣構造算符優(yōu)先矩陣→分析句子分析句子)廣義運算符廣義運算符:文法的終結符號文法的終結符號廣義運算對象廣義運算對象:非終結符非終結符（3）LRLR（0）分析法）分析法A.A.引入引入S’SS’S拓廣文法拓廣文法B.B.構造識別所有規(guī)范句型全部的活前綴的構造識別所有