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

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

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

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

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

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

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

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

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

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

譯”。

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

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

第二章形式語言的基本知識

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

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

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

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

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

第三章詞法分析

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

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

第四章語法分析

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

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

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

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

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

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

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

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

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

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

第七章運(yùn)行時(shí)的存儲組織與分配

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

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

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

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

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

DL動態(tài)鏈，指向調(diào)用該過程前正在運(yùn)行的那個(gè)過程的活動記錄的基地址，以確保能返回到調(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)化，復(fù)雜）基本塊優(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)自動機(jī)和詞法分

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

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

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

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

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

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)翻譯基本思想和實(shí)現(xiàn)方法。

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

9、正確理解目標(biāo)程序運(yùn)行進(jìn)存儲空間的使用和組織管理方式；理解靜態(tài)分配和動態(tài)存儲分配基本思想；掌握FORTRAN存儲分配的處理方式；掌握棧式動態(tài)分配中活動記錄的作用、組織、內(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、《編譯原理》徐國定編著，高等教育出版社。參考資料：

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

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

三、教學(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)，高級高級語言的一般特性，程序結(jié)構(gòu)，語句與控制結(jié)構(gòu)，上下文無關(guān)文法，語法分析樹與二義性。重點(diǎn)：上下文無關(guān)文法，程序語言定義參數(shù)傳遞。第三章有限狀態(tài)自動機(jī)和詞法分析

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

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

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

重點(diǎn)：遞歸下降子程序，預(yù)測分析表構(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ò)誤診察，語法分析器自動產(chǎn)生工具YACC。重點(diǎn)：歸約，算符優(yōu)先表構(gòu)造，LR分析法。第六章中間代碼生成和符號表

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

主要內(nèi)容：目標(biāo)程序運(yùn)行時(shí)的活動，運(yùn)行時(shí)存儲器的劃分，靜態(tài)存儲管理，簡單的棧式存儲分配的實(shí)現(xiàn)，嵌套過程語言的棧式實(shí)現(xiàn)，堆式動態(tài)存儲分配。重點(diǎn)：靜態(tài)分配策略和動態(tài)分配策略基本思想，嵌套過程語言棧式分配，活動記錄、運(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ù)方法。

四、考核方式說明

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

平時(shí)作業(yè)考核：要求學(xué)生認(rèn)真完成平時(shí)作業(yè)，各辦學(xué)點(diǎn)應(yīng)組織作業(yè)的批改和成績的核定。平時(shí)作業(yè)的成績評定標(biāo)準(zhǔn)和要求按省電大有關(guān)文件執(zhí)行。上機(jī)實(shí)驗(yàn)考核：學(xué)員必須完成規(guī)定的上機(jī)實(shí)驗(yàn)，并撰寫實(shí)驗(yàn)報(bào)告，由輔導(dǎo)實(shí)驗(yàn)的老師批改并評定成績，學(xué)員實(shí)驗(yàn)成績評定單必須加蓋承擔(dān)實(shí)驗(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．高級語言編譯程序常用的語法分析方法中，遞歸下降分析法屬于______分析方法。

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

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

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

A．1，2B．1，2，3C．1，2，3，4D．1，2，45．動態(tài)存儲分配時(shí)，可以采用的分配方法是1)以過程為單位的棧式動態(tài)存儲分配2)堆存儲分配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ù)�！�………（）2．每個(gè)文法都能改寫為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)計(jì)算每個(gè)非終結(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)的短語、素短語。參考答案

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

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

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

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

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

四、名詞解釋

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

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

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

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

五、綜合應(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ò)整理 免責(zé)聲明：本文僅限學(xué)習(xí)分享，如產(chǎn)生版權(quán)問題，請聯(lián)系我們及時(shí)刪除。

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

• 上一篇：關(guān)于通信原理的一點(diǎn)總結(jié)
• 下一篇：編譯原理和操作系統(tǒng)總結(jié)報(bào)告筆記