編譯原理基礎(chǔ)精品課件

1、編譯原理基礎(chǔ)第1頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二第6章 編譯原理基礎(chǔ)Principles of Compilation中原工學(xué)院軟件學(xué)院韓玉民第2頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二編譯程序是高級語言的支撐基礎(chǔ)，是計(jì)算機(jī)系統(tǒng)中重要的系統(tǒng)軟件之一。第6章 編譯原理第3頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.1 程序設(shè)計(jì)語言的編譯與解釋6.2 形式語言6.3 第一階段 詞法分析6.4 第二階段 語法分析6.5 第三階段 語義分析與中間代碼生成6.6 第四階段 代碼優(yōu)化6.7 符號表管理和錯(cuò)誤處理6.8 第五階段 目標(biāo)代碼生成 第

2、6章 編譯原理第4頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二程序設(shè)計(jì)語言分成兩大類:低級語言: 包括機(jī)器語言和匯編語言，主要是面向機(jī)器的。高級語言: 高級語言則是面向應(yīng)用的，分成很多種，如FORTRAN、Pascal、C、C#、VB、Java等。 6.1 程序設(shè)計(jì)語言的編譯與解釋6.1.1 程序設(shè)計(jì)語言第5頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二機(jī)器語言本身是有由0和1組成的，符合計(jì)算機(jī)的硬件特性，因此能夠直接執(zhí)行。但用機(jī)器語言編寫程序很不方便且容易出錯(cuò)，因此就用助記符代替機(jī)器語言，產(chǎn)生了匯編語言。匯編語言比機(jī)器語言在可讀性方面有了進(jìn)步，但是其依賴具體機(jī)器的特

3、性無法改變，給程序設(shè)計(jì)語言增添了難度。6.1.2 程序的編譯與解釋6.1 程序設(shè)計(jì)語言的編譯與解釋第6頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二高級語言不能直接在機(jī)器上運(yùn)行，它不是面向機(jī)器，而是面向應(yīng)用的，因此，要想讓高級語言運(yùn)行必須有編譯程序。編譯程序就是這樣的一種程序，它能將高級語言編寫的源程序轉(zhuǎn)換成與之在邏輯上等價(jià)的低級語言形式的目標(biāo)程序。 1.編譯方式 6.1 程序設(shè)計(jì)語言的編譯與解釋第7頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二高級語言程序的執(zhí)行通常分為兩個(gè)階段，即編譯階段和運(yùn)行階段，源程序的運(yùn)行過程如圖1-1所示。#includeMain() For

4、 (; ; ) Printf (“Hello World!n”); 源程序編譯程序01101001100101011001001110101010101011000011111001011111110010101010001010001111101101目標(biāo)程序編譯初始數(shù)據(jù)目標(biāo)程序、運(yùn)行系統(tǒng)計(jì)算結(jié)果輸入處理輸出程序的編譯 程序的執(zhí)行 6.1 程序設(shè)計(jì)語言的編譯與解釋第8頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二編譯階段將源程序變換成目標(biāo)程序；運(yùn)行階段則由所生成的目標(biāo)程序連同運(yùn)行系統(tǒng)（數(shù)據(jù)空間分配子程序、標(biāo)準(zhǔn)函數(shù)程序等）接受程序的初始數(shù)據(jù)作為輸入，運(yùn)行后輸出計(jì)算結(jié)果。如果目標(biāo)程序

5、是匯編語言的形式，則需要在編譯階段和運(yùn)行階段之間加一個(gè)匯編階段。#includeMain() For (; ; ) Printf (“Hello World!n”); 源程序匯編程序011010011001010010101011000011111011機(jī)器語言程序ADD A,BMOV B,C編譯程序匯編語言程序 編譯匯編6.1 程序設(shè)計(jì)語言的編譯與解釋第9頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二高級語言編寫的程序除了可以通過編譯方式外，還可以通過解釋程序執(zhí)行。所謂解釋程序是一種語言翻譯程序，按動(dòng)態(tài)順序，讀入一條語句，解釋一條語句，執(zhí)行一條語句，即邊翻譯邊執(zhí)行。源程序解釋程序

6、計(jì)算結(jié)果源程序、輸入解釋執(zhí)行輸出數(shù) 據(jù) 2.解釋方式 6.1 程序設(shè)計(jì)語言的編譯與解釋第10頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二高級語言源程序經(jīng)編譯程序編譯的經(jīng)過目標(biāo)代碼還可以是待裝配的目標(biāo)代碼（相對目標(biāo)代碼），這種形式的目標(biāo)程序通常由多個(gè)目標(biāo)模塊組成，各目標(biāo)模塊由相應(yīng)的源程序模塊經(jīng)編譯生成，必須將相關(guān)的多個(gè)目標(biāo)模塊組裝成到一個(gè)可執(zhí)行目標(biāo)程序中，才能運(yùn)行。完成集成工作的程序稱為連接程序。連接程序還連接目標(biāo)程序和用于標(biāo)準(zhǔn)庫函數(shù)的代碼，以及連接目標(biāo)程序和由計(jì)算機(jī)的操作系統(tǒng)提供的資源（例如，存儲(chǔ)分配程序及輸入與輸出設(shè)備）。 3. 連接程序（linker） 6.1 程序設(shè)計(jì)語言的

7、編譯與解釋第11頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二解釋程序與編譯程序的主要區(qū)別是：編譯程序?qū)⒃闯绦蚍g成目標(biāo)程序后再執(zhí)行目標(biāo)程序.解釋程序是逐條讀出源程序中的語句并執(zhí)行，即在解釋程序的執(zhí)行過程中并不產(chǎn)生目標(biāo)程序。6.1 程序設(shè)計(jì)語言的編譯與解釋第12頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.1.3 編譯程序的編譯過程和編譯程序的結(jié)構(gòu) 編譯程序的功能是將用高級語言編寫的源程序翻譯成等價(jià)的低級語言（匯編語言或機(jī)器語言）目標(biāo)程序。編譯的過程就是一個(gè)不同語言翻譯的過程，所以其過程類似于自然語言的翻譯。 第13頁，共50頁，2022年，5月20日，20點(diǎn)31分

8、，星期二6.1.3 編譯程序的編譯過程和編譯程序的結(jié)構(gòu) 步驟完 成 的 工 作自然語言翻譯（英語翻譯成漢語）編譯程序（源程序翻譯成機(jī)器目標(biāo)代碼）1根據(jù)英文單詞拼寫規(guī)則，識(shí)別出各個(gè)單詞和標(biāo)點(diǎn)符號等，并檢查單詞是否有拼寫錯(cuò)誤。這就是詞法分析對源程序進(jìn)行詞法分析，檢查有無拼寫錯(cuò)誤，識(shí)別出其中的單詞（關(guān)鍵字、標(biāo)識(shí)符等）2根據(jù)英文語法規(guī)則，對詞法分析中得到的各個(gè)單詞和標(biāo)點(diǎn)符號等進(jìn)行分析、檢查，看是否能組成一個(gè)符合語法規(guī)則的句子。因此，該步驟稱為語法分析進(jìn)行語法分析，檢查單詞串是否組成符合語法的正確的程序語句，如表達(dá)式是否正確等3對語法分析后得到的符合英文語法規(guī)則的句子進(jìn)行分析，理解句子的含義，初步翻譯成

9、中文。該步驟稱為語義分析分析翻譯語句要完成的操作，是將源程序初步翻譯成目標(biāo)程序（一種中間代碼）。這是為了方便編譯過程的實(shí)現(xiàn)，同時(shí)也便于進(jìn)行代碼優(yōu)化4對初步翻譯的中文進(jìn)行修飾、潤色等代碼優(yōu)化5將英文翻譯成最終的中文將優(yōu)化后的中間代碼轉(zhuǎn)換成特定機(jī)器上的機(jī)器語言程序或匯編語言程序自然語言的翻譯第14頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.1.3 編譯程序的編譯過程和編譯程序的結(jié)構(gòu) 源程序詞法分析語法分析語義分析和中間代碼生成代碼優(yōu)化生成目標(biāo)代碼出錯(cuò)處理表格管理目標(biāo)程序編譯過程編譯程序結(jié)構(gòu)詞法分析程序語法分析程序語義分析和中間代碼生成程序代碼優(yōu)化程序生成目標(biāo)代碼編譯過程可以劃分成

10、五個(gè)階段1.編譯過程第15頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二編譯程序的功能是把高級語言源程序翻譯成等價(jià)的低級語言目標(biāo)程序。源程序是由一些基本符號構(gòu)成的，我們在運(yùn)行這個(gè)程序時(shí)，先編譯，若某處有錯(cuò)誤，就報(bào)錯(cuò)，無錯(cuò)誤就運(yùn)行。編譯程序在編譯時(shí)，先將程序中的單詞一個(gè)個(gè)分離出來，登記在一個(gè)表中，這叫詞法分析，然后檢查語句格式，叫做語法分析。然后檢查類型是否一致，計(jì)算表達(dá)式的值叫語義分析。這些功能都是由編譯程序相應(yīng)的程序完成的。6.1.3 編譯程序的編譯過程和編譯程序的結(jié)構(gòu) 第16頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二一般來說，整個(gè)編譯過程可以劃分成五個(gè)階段：詞法

11、分析階段語法分析階段語義分析和中間代碼生成階段中間代碼的優(yōu)化目標(biāo)代碼的生成。6.1.3 編譯程序的編譯過程和編譯程序的結(jié)構(gòu) 1.編譯過程第17頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.1.3 編譯程序的編譯過程和編譯程序的結(jié)構(gòu) 2.一遍與多遍編譯 編譯程序還采用“分遍”的形式，即編譯過程可通過一遍或多遍編譯來完成。所謂編譯的“一遍”（pass）是指下述過程：對于源程序或中間代碼，從頭到尾掃描一遍，并完成規(guī)定的處理任務(wù)，生成新的源程序的中間代碼代碼或目標(biāo)代碼。在單遍編譯中，編譯程序包括了編譯程序的各個(gè)階段的任務(wù)，所有的階段由一遍完成，其結(jié)果是編譯得很好，但通常代碼效率差。 第

12、18頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.1.3 編譯程序的編譯過程和編譯程序的結(jié)構(gòu) 2.一遍與多遍編譯 在多遍掃描的編譯程序中，每一遍完成一個(gè)或幾個(gè)相關(guān)邏輯的工作，一個(gè)階段的工作也可以分多遍來完成。例如，將詞法分析作為第一編，語法分析和語義分析作為第二遍等。 第19頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.2 形式語言 程序設(shè)計(jì)語言的語法描述 程序和自然語言一樣，也有其語法規(guī)則，要對程序進(jìn)行語法分析，就要先了解程序的語法規(guī)則。程序的語法規(guī)則稱為文法，即文法是描述語言的形式規(guī)則（語法規(guī)則）。用一組數(shù)學(xué)符號和規(guī)則來描述的語言稱為形式語言。 目前程序設(shè)計(jì)

13、語言都是用形式語言來描述，形式語言是編譯原理的理論基礎(chǔ)。 1. 什么是形式語言?第20頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.2 形式語言 程序設(shè)計(jì)語言的語法描述程序和自然語言一樣，也有其語法規(guī)則，要對程序進(jìn)行語法分析，就要先了解程序的語法規(guī)則。程序的語法規(guī)則稱為文法，即文法是描述語言的形式規(guī)則（語法規(guī)則）。這種規(guī)則要能夠描述程序語言各種不同的結(jié)構(gòu)，同時(shí)還要使程序能夠易于分析和翻譯，最好能夠根據(jù)其語法規(guī)則自動(dòng)生成有效的語法分析程序。 目前程序設(shè)計(jì)語言都是用形式語言來描述，形式語言是編譯原理的理論基礎(chǔ)。 第21頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.2

14、 形式語言 程序設(shè)計(jì)語言的語法描述 2. 字母表和符號串 任何一種語言，都是由該語言的基本符號所組成的符號串的集合。例如，英語文章是由句子和標(biāo)點(diǎn)符號構(gòu)成的，句子是由單詞構(gòu)成的，而單詞則是由字母構(gòu)成的。 第22頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.2 形式語言 程序設(shè)計(jì)語言的語法描述 2. 字母表和符號串 （1）字母表 字母表是符號的非空有窮集合，字母表中的元素稱為符號。因此字母表也稱為符號表。 不同的語言有不同的字母表，例如英語的字母表是26個(gè)英文字母、數(shù)字和一些特殊符號。漢語的字母表是漢字、數(shù)字和專用符號等。而C語言的字母表包括關(guān)鍵字、字母、數(shù)字和一些專用符號。 （2

15、）符號串 字母表中的符號所組成的任何有窮序列稱為該字母表上的符號串。 例如語句 “if (x=8) then a=5 else a=9”可以看作是定義在C語言字母表上的一個(gè)符號串。 第23頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.2 形式語言 程序設(shè)計(jì)語言的語法描述3.什么是文法?文法是描述語言語法結(jié)構(gòu)的形式規(guī)則。我們以自然語言為例來說明。在描述一種語言時(shí)，就是要說明這種語言包含哪些句子。例如漢語，但漢語的句子有無窮多個(gè)，無法全部寫出來。這就要制定有限條語法規(guī)則，用這些語法規(guī)則來產(chǎn)生漢語的全部句子。這些規(guī)則就是所謂的文法。 第24頁，共50頁，2022年，5月20日，20點(diǎn)

16、31分，星期二6.2 形式語言 程序設(shè)計(jì)語言的語法描述3.什么是文法?語法規(guī)則 例如，定義如下語法規(guī)則： 語法規(guī)則 例如，定義如下語法規(guī)則： = = | = 我|你|他|她 = 李翔|韓方|計(jì)算機(jī)|大學(xué)生|教師|C語言 = = 是|學(xué)習(xí) = 由語法規(guī)則推導(dǎo)句子第25頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.2 形式語言 程序設(shè)計(jì)語言的語法描述如用EBNF來描述文法的定義： =+|- =0|1|2|3|4|5|5|6|7|8|9第26頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.2 形式語言 程序設(shè)計(jì)語言的語法描述 = | = | = _ | | = a|b|

17、c|d|e|f|g|h|i|j|z = A|B|C|D|E|F|G|H|I|J|Z = |8|9 = 0|1|2|3|4|5|6|7C語言的“標(biāo)識(shí)符”用BNF描述為： 第27頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二詞法分析是編譯過程的基礎(chǔ)，其任務(wù)是掃描源程序，根據(jù)語言的詞法規(guī)則，分解和識(shí)別出每個(gè)單詞，并把單詞翻譯成相應(yīng)的機(jī)內(nèi)表示。當(dāng)然，詞法分析在識(shí)別單詞的過程中，同時(shí)也做了詞法檢查。6.3 第一階段-詞法分析第28頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二在高級語言中，所謂單詞，就是指邏輯上緊密相連的一組字符，這些字符具有集體含義。單詞是語言中最小的語義單位，

18、如語言中的關(guān)鍵字、標(biāo)識(shí)符、運(yùn)算符和界限符。詞法分析的依據(jù)是詞的構(gòu)造。單詞的構(gòu)造規(guī)則在高級語言中有明確的規(guī)定，比如哪些為保留字、變量如何定義、常量如何構(gòu)造、分界符有哪些等。 6.3 第一階段-詞法分析第29頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二詞法分析的主要內(nèi)容包括：（1）分析并識(shí)別單詞及其屬性；（2）跳過空格、回車、制表符等分隔符；（3）濾掉注釋；（4）進(jìn)行詞法檢查，報(bào)告發(fā)現(xiàn)的錯(cuò)誤；（5）還要根據(jù)需要?jiǎng)?chuàng)建符號表、常量表等。 6.3 第一階段-詞法分析第30頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二main( )float x=2,y=3,s;s=x+y*5;

19、例如，用C 語言編寫的程序段如下：識(shí)別出的單詞序列為表所示6.3 第一階段-詞法分析第31頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二表1 詞法分析程序類型名單詞類型名單詞保留字main左括號(右括號)花括號保留字float標(biāo)識(shí)符x等號=常量2逗號,標(biāo)識(shí)符y等號=常量3逗號,標(biāo)識(shí)符s分號;標(biāo)識(shí)符s等號=標(biāo)識(shí)符x運(yùn)算符+標(biāo)識(shí)符y運(yùn)算符*常量5分號;花括號6.3 第一階段-詞法分析作為第二階段的輸入第32頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二語法分析是在詞法分析的 基礎(chǔ)上進(jìn)行的，是編譯過程的第二個(gè)階段。語法分析的任務(wù)是根據(jù)語言的語法規(guī)則，把單詞符號串分解成各類語法

20、單位，如表達(dá)式、語句等。并在分析過程中，對單詞串組成的源程序進(jìn)行語法正確性檢查。 通過語法分析，可以確定整個(gè)輸入符號串是否構(gòu)成一個(gè)正確的程序。6.4 第二階段-語法分析第33頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.4 第二階段-語法分析語法分析的結(jié)果是無語法錯(cuò)誤的語法成分，有多種輸出形式。 第34頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.5 第三階段-語義分析和中間代碼的生成一個(gè)源程序通過詞法分析和語法分析后，可以確定該源程序在單詞拼寫和語法上是正確的，但并沒有分析其語句的邏輯含義，即要執(zhí)行什么操作？詞法和語法的正確并不能保證語義的正確正如一篇單詞拼寫

21、正確、語法正確的文章，人們在閱讀時(shí)首先是要能讀通，然后是要理解每句話及整篇文章的含義或思想。這就是對文章的語義分析。第35頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二語義分析的任務(wù)是對各種不同語句進(jìn)行翻譯，包括兩方面的工作：一是對每種語法范疇進(jìn)行語義檢查，如變量是否定義、類型是否正確等；二是在語義檢查正確的情況下，進(jìn)行中間代碼的翻譯。程序的語義分析就是對程序的邏輯含義進(jìn)行分析，是編譯過程中最實(shí)質(zhì)性的工作。 Why?6.5 第三階段-語義分析和中間代碼的生成1.語義分析第36頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二中間代碼是介于高級語言語句和低級語言語句之間的一種

22、獨(dú)立于具體硬件的記號系統(tǒng)，它即有一定程度的抽象，又和低級語言十分接近，因此，轉(zhuǎn)換成目標(biāo)代碼很容易。Why?6.5 第三階段-語義分析和中間代碼的生成2.中間代碼的生成第37頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二中間代碼的表示形式有很多種，常見的有:四元式三元式間接三元式逆波蘭式等。其中四元式的形式為:（運(yùn)算符，運(yùn)算對象1，運(yùn)算對象2，結(jié)果） 6.5 第三階段-語義分析和中間代碼的生成第38頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.6 第四階段中間代碼優(yōu)化代碼優(yōu)化就是為提高目標(biāo)代碼質(zhì)量而進(jìn)行的加工和處理工作，使得目標(biāo)代碼在執(zhí)行時(shí)效率更高，即執(zhí)行時(shí)間更短，同

23、時(shí)占用內(nèi)存空間更小。一般優(yōu)化工作階段是在中間代碼生成之后或目標(biāo)代碼生成之后，實(shí)際上，編譯程序通常包括許多代碼改進(jìn)或優(yōu)化步驟。 第39頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二中間代碼優(yōu)化通過調(diào)整和改變中間代碼中某些操作次序，以最終產(chǎn)生更加高效的目標(biāo)代碼。優(yōu)化的主要手段有:刪除冗余運(yùn)算刪除無用賦值合并已知量循環(huán)優(yōu)化等。 6.6 第四階段中間代碼優(yōu)化第40頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.6 第四階段中間代碼優(yōu)化第41頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二這一階段的任務(wù)是對前一階段的中間代碼變換成特定機(jī)器上的機(jī)器語言或匯編語言程序，實(shí)

24、現(xiàn)機(jī)器的最終翻譯。最后階段的工作因?yàn)槟繕?biāo)語言的關(guān)系而十分依賴機(jī)器的硬件系統(tǒng)，即如何充分利用機(jī)器現(xiàn)存的寄存器，合理的選擇指令，生成盡可能短的目標(biāo)代碼，這與機(jī)器的硬件有關(guān)。 6.7 第五階段目標(biāo)代碼的生成第42頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二目標(biāo)代碼生成程序生成的目標(biāo)代碼有不同的形式，一般有以下三種形式。（1）能夠立即執(zhí)行的機(jī)器語言代碼 這種代碼所有地址已定位，編譯后可以立即執(zhí)行。（2）待裝配的機(jī)器語言代碼模塊 需要執(zhí)行時(shí)，必須經(jīng)由連接裝配程序?qū)⑺鼈兣c另外一些運(yùn)行子程序（如語言的系統(tǒng)函數(shù)庫）連接裝配起來，構(gòu)成可以執(zhí)行的機(jī)器代碼。（3）匯編語言代碼 必須經(jīng)過匯編程序?qū)⑵鋮R編成可執(zhí)行的機(jī)器語言代碼。6.7 第五階段目標(biāo)代碼的生成第43頁，共50頁，2022年，5月20日，20點(diǎn)31分，星期二6.7 第五階段目標(biāo)代碼的生成第44頁，共50頁，2022年，5月20日，2