河北工業(yè)大學(xué)編譯原理期末復(fù)習(xí)

1、考試題型：填空考試題型：填空24%24%簡(jiǎn)答簡(jiǎn)答44=16%44=16%解答解答415=6415=6ChapterChapter1重要概念重要概念1.1.什么編譯程序？什么編譯程序？P3P3答：編譯程序的主要功能是把用高級(jí)語(yǔ)言編寫(xiě)的源程序翻譯為等價(jià)的目標(biāo)程序。答：編譯程序的主要功能是把用高級(jí)語(yǔ)言編寫(xiě)的源程序翻譯為等價(jià)的目標(biāo)程序。2.2.編譯程序的工作過(guò)程？（編譯程序的工作過(guò)程？（6個(gè)階段）個(gè)階段）P4P41、詞法分析程序詞法分析程序2、

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

3、用高級(jí)語(yǔ)言編寫(xiě)的程序，一般須經(jīng)過(guò)兩個(gè)階段。第一個(gè)階段在計(jì)算機(jī)上執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序，一般須經(jīng)過(guò)兩個(gè)階段。第一個(gè)階段稱為編譯階段，其任務(wù)是由編譯程序?qū)⒃闯绦蚓幾g為目標(biāo)程序，若目標(biāo)程序不是機(jī)器代碼，稱為編譯階段，其任務(wù)是由編譯程序?qū)⒃闯绦蚓幾g為目標(biāo)程序，若目標(biāo)程序不是機(jī)器代碼，而是匯編語(yǔ)言程序，則尚需匯編程序再行匯編為機(jī)器代碼程序；第二階段稱為運(yùn)行階段，而是匯編語(yǔ)言程序，則尚需匯編程序再行匯編為機(jī)器代碼程序；第二階段稱為運(yùn)行階段，其任務(wù)

4、是在目標(biāo)計(jì)算機(jī)上執(zhí)行編譯階段所得到的目標(biāo)程序。其任務(wù)是在目標(biāo)計(jì)算機(jī)上執(zhí)行編譯階段所得到的目標(biāo)程序。2）用高級(jí)語(yǔ)言編寫(xiě)的程序也可以通過(guò)用高級(jí)語(yǔ)言編寫(xiě)的程序也可以通過(guò)解釋程序解釋程序來(lái)執(zhí)行。解釋程序也以源程序作為它的輸入，來(lái)執(zhí)行。解釋程序也以源程序作為它的輸入，它與編譯程序的主要區(qū)別是在解釋程序的執(zhí)行過(guò)程中不產(chǎn)生目標(biāo)程序，而是解釋執(zhí)行源程它與編譯程序的主要區(qū)別是在解釋程序的執(zhí)行過(guò)程中不產(chǎn)生目標(biāo)程序，而是解釋執(zhí)行源程序本身。序本身。缺點(diǎn)：這種

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

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

7、指對(duì)源程序或其內(nèi)部表示從頭到尾掃視一次，并進(jìn)行有關(guān)的加工處理工作。是指對(duì)源程序或其內(nèi)部表示從頭到尾掃視一次，并進(jìn)行有關(guān)的加工處理工作。（執(zhí)行過(guò)程：（執(zhí)行過(guò)程：?jiǎn)伪閽呙?、多遍掃描（大多?shù)）單遍掃描、多遍掃描（大多數(shù)））ChapterChapter2前后文無(wú)關(guān)文法和語(yǔ)言前后文無(wú)關(guān)文法和語(yǔ)言1.1.文法和語(yǔ)言的形式定義文法和語(yǔ)言的形式定義產(chǎn)生語(yǔ)言就是制定出有限個(gè)規(guī)則（文法）產(chǎn)生語(yǔ)言就是制定出有限個(gè)規(guī)則（文法），借助于它們，就能產(chǎn)生出此語(yǔ)言的全

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

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

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

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

12、于體現(xiàn)單詞的結(jié)構(gòu)3.Bell3.Bell實(shí)驗(yàn)室實(shí)驗(yàn)室M.LeskM.Lesk等人用等人用C語(yǔ)言研制的一個(gè)詞法分析程序的自動(dòng)生成工具叫語(yǔ)言研制的一個(gè)詞法分析程序的自動(dòng)生成工具叫LEXLEX4.4.判斷（判斷（對(duì)）所有帶有）所有帶有ε的自動(dòng)機(jī)都是非確定的自動(dòng)機(jī)的自動(dòng)機(jī)都是非確定的自動(dòng)機(jī)ChapterChapter4語(yǔ)法分析和語(yǔ)法分析程序語(yǔ)法分析和語(yǔ)法分析程序1.1.語(yǔ)法分析方法語(yǔ)法分析方法:自頂向下分析法：如遞歸下降法，自頂向下分析法：如遞

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

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

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