編譯原理期末總結(jié)

編譯原理期末總結(jié)編譯原理期末總結(jié)

編譯原理期末總結(jié)

編譯原理期末總結(jié)第一章編譯概述

程序的翻譯：源程序：用匯編語言或高級(jí)語言編寫的程序。

目標(biāo)程序：用目標(biāo)語言所表示的程序。（目標(biāo)語言：可以是介于源語言和機(jī)器語言

之間的中間語言，可以是某種機(jī)器的機(jī)器語言，也可以是某機(jī)器的匯編語言）

翻譯程序：將源程序轉(zhuǎn)換為目標(biāo)程序的程序稱為翻譯程序。它是指各種語言的翻譯

器，包括匯編程序和編譯程序，是匯編程序、編譯程序以及各種變換程序的總稱。

匯編程序：若源程序用匯編語言書寫，經(jīng)過翻譯程序得到用機(jī)器語言表示的程序，這是

的翻譯程序就稱之為匯編程序。

編譯程序：若源程序是用高級(jí)語言書寫，經(jīng)加工后得到目標(biāo)程序，上述翻譯過程稱為“編

譯”。

編譯過程：詞法分析（程序）、語法分析（程序）、語義分析及生成中間代碼、代碼優(yōu)化、

目標(biāo)代碼生成（生成目標(biāo)程序）。符號(hào)表管理錯(cuò)誤處理每個(gè)階段都要有

其次章形式語言的基本學(xué)問

符號(hào)串：由字母表中的符號(hào)組成的任何有窮序列。符號(hào)串的連接運(yùn)算，符號(hào)串的冪運(yùn)算符號(hào)串集合的運(yùn)算：若集合A中的一切元素都是某字母表上的符號(hào)串，則稱A為該字母表上的符號(hào)串集合。符號(hào)串集合的乘積，符號(hào)串集合的冪運(yùn)算，符號(hào)串集合的閉包運(yùn)算

文法和語義的定義：文法是對語言結(jié)構(gòu)的定義與描述。

規(guī)范推導(dǎo)：最右推導(dǎo)，對于一個(gè)推導(dǎo)序列中的每始終接推導(dǎo)，被替換的總是當(dāng)前符號(hào)串中的最右非終結(jié)符號(hào)。

規(guī)范歸約：規(guī)范推導(dǎo)的逆過程，最左歸約。規(guī)范歸約遞歸文法：含有遞歸規(guī)章的文法。文法的BNF，EBNF表示

文法的二義性：若一個(gè)文法的某句子存在兩個(gè)不同的最右（最左）推導(dǎo)，則該文法是二義性的，否則是無二義性的。

第三章詞法分析

詞法分析程序的任務(wù)：編譯第一階段的工作，它讀入字符流的源程序，根據(jù)詞法規(guī)章識(shí)別單詞，再由語法分析程序接下去處理。

詞法分析程序的手工實(shí)現(xiàn)：單詞的文法----狀態(tài)圖---流程圖---偽碼詞法分析程序的自動(dòng)構(gòu)造：正規(guī)式：正規(guī)集的描述機(jī)制有窮自動(dòng)機(jī)（NFADFA）：正規(guī)集的識(shí)別機(jī)制LEX的實(shí)現(xiàn)原理和源程序的基本組成

第四章語法分析

第五章語義分析和中間代碼生成

語義分析的任務(wù)：依據(jù)語義規(guī)章對識(shí)別出的各種語法成分分析其含義，進(jìn)行初步翻譯，生成相應(yīng)的中間代碼或直接生成目標(biāo)代碼。1.確定數(shù)據(jù)類型；2.語義檢查：動(dòng)態(tài)語義檢查（在運(yùn)行時(shí)刻進(jìn)行），靜態(tài)語義檢查（在編譯完成時(shí)）；3.識(shí)別含義，進(jìn)行真正的翻譯。

屬性文法：附加了一組屬性和運(yùn)算（語義）規(guī)章的文法。語法制導(dǎo)翻譯的過程：將語義規(guī)章與語法規(guī)章相結(jié)合，在語法分析的過程中通過執(zhí)行語義動(dòng)作，計(jì)算語義屬性值，從而完成預(yù)定的翻譯工作。

自低向上（語法制導(dǎo)定義）：在產(chǎn)生式規(guī)約的同時(shí)調(diào)用相應(yīng)的語義子程序自頂向下（翻譯方案）：將語義子程序嵌入到每個(gè)遞歸過程中中間代碼的目的：便于優(yōu)化便于移植

中間代碼的幾種形式：后綴式四元式三元式間接三元式

第六章符號(hào)表管理和錯(cuò)誤處理

表：編譯程序在其工作過程中使用最多的數(shù)據(jù)結(jié)構(gòu)是表，在這些表中，符號(hào)表最為重要，它的生存周期最長，使用最頻繁。

作用：1.收集符號(hào)的各種信息；2.語義檢查的依據(jù)；3.目標(biāo)代碼生成階段地址安排的依據(jù)

內(nèi)容：名字欄+信息欄

符號(hào)表的總體組織：多張一張前兩種折中符號(hào)表項(xiàng)的組織：線性組織排序組織散列組織明確錯(cuò)誤處理的兩種方法：錯(cuò)誤校正和局部化處理

第七章運(yùn)行時(shí)的存儲(chǔ)組織與安排

靜態(tài)存儲(chǔ)安排：在編譯階段由編譯程序?qū)崿F(xiàn)對存儲(chǔ)空間的管理，為源程序中的變量安排存儲(chǔ)單元。在編譯時(shí)能夠確定變量在運(yùn)行時(shí)的數(shù)據(jù)空間大小，運(yùn)行時(shí)不轉(zhuǎn)變。

動(dòng)態(tài)存儲(chǔ)安排：在目標(biāo)程序運(yùn)行階段由目標(biāo)程序?qū)崿F(xiàn)對存儲(chǔ)空間的組織與管理，為源程序中的變量安排存儲(chǔ)單元。在目標(biāo)程序運(yùn)行時(shí)進(jìn)行安排，編譯時(shí)為運(yùn)行階段升級(jí)好存儲(chǔ)組織形式，即每個(gè)數(shù)據(jù)項(xiàng)支配好它在數(shù)據(jù)區(qū)中的相對位置。

活動(dòng)記錄：連接數(shù)據(jù)單元（聯(lián)系單元）：靜態(tài)鏈，動(dòng)態(tài)鏈，返回地址；+局部數(shù)據(jù)區(qū)PL0存儲(chǔ)安排策略：程序存儲(chǔ)器code，數(shù)據(jù)存儲(chǔ)器s，程序地址存儲(chǔ)器p，地址寄存器t，指令寄存器i，基本地址寄存器b。

三個(gè)聯(lián)系單元：

SL靜態(tài)鏈，指向定義該過程的直接外層過程的活動(dòng)記錄的基地址，以確保變量的正確存取

DL動(dòng)態(tài)鏈，指向調(diào)用該過程前正在運(yùn)行的那個(gè)過程的活動(dòng)記錄的基地址，以確保能返回到調(diào)用過程段。

RA返回地址，保存該被調(diào)過程返回后的地址，即當(dāng)時(shí)程序的地址寄存器p的值，也就是調(diào)用過程指令的下一條指令的地址，用來確保返回到正確的指令地址。

第八章代碼優(yōu)化

代碼優(yōu)化的目的：提高目標(biāo)代碼運(yùn)行效率時(shí)間效率（削減運(yùn)行時(shí)間）空間效率（削減內(nèi)容容量）

代碼優(yōu)化的分類：局部優(yōu)化（在基本塊內(nèi)進(jìn)行優(yōu)化）循環(huán)優(yōu)化（對循環(huán)語句所生成的中間代碼進(jìn)行優(yōu)化）全局優(yōu)化（跨越多個(gè)基本塊的全局范圍內(nèi)的優(yōu)化，簡單）基本塊優(yōu)化方法：合并常量，刪除公共子表達(dá)式，刪除無用賦值循環(huán)優(yōu)化方法：代碼外提，強(qiáng)度減弱，刪除歸納變量

第九章目標(biāo)代碼生成

實(shí)現(xiàn)一個(gè)代碼生成器應(yīng)考慮2個(gè)問題如何使生成的目標(biāo)代碼盡可能的短如何充分利用計(jì)算機(jī)的寄存器，削減目標(biāo)代碼中訪問內(nèi)存的次數(shù)明確目標(biāo)代碼的三種不同形式的優(yōu)缺點(diǎn)可馬上執(zhí)行的機(jī)器語言代碼待裝配的機(jī)器語言代碼，又稱相對目標(biāo)代碼匯編語言代碼

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

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

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

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

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

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

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

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

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

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

7、熟識(shí)常見的幾種中間語言：四元式、三元式、逆波蘭表示；把握各種語句到四元式的翻譯方法，包括：簡潔算術(shù)表達(dá)式，布爾表達(dá)式，掌握語句，數(shù)組引用，過程調(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)容及使用；了解嵌套過程語言程序運(yùn)行時(shí)整個(gè)運(yùn)行棧的內(nèi)容的組織。

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

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

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

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

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

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

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

重點(diǎn)：編譯程序工作的基本過程及其各階段的基本任務(wù)，編譯程序總框。其次章形式語言基礎(chǔ)主要內(nèi)容：程序語言定義，初等數(shù)據(jù)類型，數(shù)據(jù)結(jié)構(gòu)，高級(jí)高級(jí)語言的一般特性，程序結(jié)構(gòu)，語句與掌握結(jié)構(gòu)，上下文無關(guān)文法，語法分析樹與二義性。重點(diǎn)：上下文無關(guān)文法，程序語言定義參數(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)容：語法分析器的功能，自上而下語法分析（遞歸下降分析法，猜測分析程序），LL（1）分析法，遞歸下降分析程序構(gòu)造，猜測分析程序，自上而下分析的錯(cuò)誤診察，語義錯(cuò)誤診察。

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

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

主要內(nèi)容：中間語言，說明語句，賦值語句的翻譯，布爾表達(dá)式的翻譯，掌握語句的翻譯，過程調(diào)用的處理各種常見中間語言形式，各種語句到四元式的翻譯。符號(hào)表的組織與作用，整理與查找，名字的作用范圍，符號(hào)表的內(nèi)容。重點(diǎn)：三種中間語言：四元式、三元式、逆波蘭表示；算術(shù)表達(dá)式的翻譯，布爾表達(dá)式的翻譯，掌握語句的翻譯。符號(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ǔ)管理，簡潔的棧式存儲(chǔ)安排的實(shí)現(xiàn)，嵌套過程語言的棧式實(shí)現(xiàn)，堆式動(dòng)態(tài)存儲(chǔ)安排。重點(diǎn)：靜態(tài)安排策略和動(dòng)態(tài)安排策略基本思想，嵌套過程語言棧式安排，活動(dòng)記錄、運(yùn)行時(shí)棧的組織。第八章代碼生成

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

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

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

四、考核方式說明

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

平常作業(yè)考核：要求同學(xué)仔細(xì)完成平常作業(yè)，各辦學(xué)點(diǎn)應(yīng)組織作業(yè)的批改和成果的核定。平常作業(yè)的成果評定標(biāo)準(zhǔn)和要求按省電大有關(guān)文件執(zhí)行。上機(jī)試驗(yàn)考核：學(xué)員必需完成規(guī)定的上機(jī)試驗(yàn)，并撰寫試驗(yàn)報(bào)告，由輔導(dǎo)試驗(yàn)的老師批改并評定成果，學(xué)員試驗(yàn)成果評定單必需加蓋擔(dān)當(dāng)試驗(yàn)單位的公章方能生效。

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

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

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

1．把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由______完成的。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．高級(jí)語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于______分析方法。

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

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

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

A．1，2B．1，2，3C．1，2，3，4D．1，2，45．動(dòng)態(tài)存儲(chǔ)安排時(shí)，可以采納的安排方法是1)以過程為單位的棧式動(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．過程調(diào)用時(shí)，參數(shù)的傳遞方法通常有__________、__________、__________和傳名。

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

三、推斷題

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

四、簡述題

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

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

3．什么是素短語？

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

5．畫圖說明編譯程序的組成結(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)造猜測分析表。

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

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

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

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

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

2C3B4D5C4．終結(jié)符、非終結(jié)符、開頭符號(hào)、產(chǎn)生式（挨次可互換）

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

四、名詞解釋

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