編譯原理基礎正規(guī)版資料

編譯原理(yuánlǐ)基礎第一頁，共50頁。第6章編譯原理(yuánlǐ)基礎

PrinciplesofCompilation中原工學院軟件(ruǎnjiàn)學院

韓玉民第二頁，共50頁。編譯程序(biānyìchénɡxù)是高級語言的支撐基礎，是計算機系統(tǒng)中重要的系統(tǒng)軟件之一。第6章編譯(biānyì)原理第三頁，共50頁。6.1程序設計語言(yǔyán)的編譯與解釋6.2形式語言(yǔyán)6.3第一階段—詞法分析6.4第二階段—語法分析6.5第三階段—語義分析與中間代碼生成6.6第四階段—代碼優(yōu)化6.7符號表管理和錯誤處理6.8第五階段—目標代碼生成第6章編譯(biānyì)原理第四頁，共50頁。程序設計語言分成兩大類:低級語言:包括機器語言和匯編語言，主要(zhǔyào)是面向機器的。高級語言:高級語言則是面向應用的，分成很多種，如FORTRAN、Pascal、C、C#、VB、Java等。6.1程序設計語言(yǔyán)的編譯與解釋6.1.1程序設計(chénɡxùshèjì)語言第五頁，共50頁。機器語言本身是有由0和1組成的，符合計算機的硬件特性，因此能夠直接執(zhí)行。但用機器語言編寫程序很不方便且容易出錯，因此就用助記符代替機器語言，產生了匯編語言。匯編語言比機器語言在可讀性方面有了進步，但是其依賴(yīlài)具體機器的特性無法改變，給程序設計語言增添了難度。6.1.2程序的編譯(biānyì)與解釋6.1程序設計(chénɡxùshèjì)語言的編譯與解釋第六頁，共50頁。高級語言程序的執(zhí)行通常分為(fēnwéi)兩個階段，即編譯階段和運行階段，源程序的運行過程如圖1-1所示。語法分析是在詞法分析的基礎上進行的，是編譯過程的第二個階段。第三十一頁，共50頁。中間代碼優(yōu)化通過調整和改變中間代碼中某些操作次序，以最終(zuìzhōnɡ)產生更加高效的目標代碼。1程序設計語言的編譯(biānyì)與解釋<整數>∷=[+|-]<數字>{<數字>}2程序的編譯(biānyì)與解釋第二十八頁，共50頁。（4）進行詞法檢查，報告發(fā)現的錯誤；詞法分析的主要內容包括：查錯是指在編譯過程中應該能夠準確、及時地檢查出錯誤，并以簡明的形式報告錯誤的性質和出錯位置，使程序員能夠方便地修改源程序。<字母(zìmǔ)數字串>∷=<字母(zìmǔ)>|<十進制數字>|<字母(zìmǔ)數字串><字母(zìmǔ)>|<字母(zìmǔ)數字串><十進制數字>第二十八頁，共50頁。單詞是語言中最小的語義單位，如語言中的關鍵字、標識符、運算符和界限符。01101001100101011001001110101010101011000011111001011111110010101010001010001111101101……對語法分析后得到的符合英文語法規(guī)則的句子進行分析，理解句子的含義，初步翻譯成中文。高級語言不能直接在機器上運行，它不是面向機器，而是面向應用的，因此，要想讓高級語言運行必須(bìxū)有編譯程序。編譯程序就是這樣的一種程序，它能將高級語言編寫的源程序轉換成與之在邏輯上等價的低級語言形式的目標程序。1.編譯(biānyì)方式6.1程序設計語言(yǔyán)的編譯與解釋第七頁，共50頁。高級語言程序的執(zhí)行通常分為(fēnwéi)兩個階段，即編譯階段和運行階段，源程序的運行過程如圖1-1所示。#includeMain(){For(;;){Printf(“HelloWorld!\n”);}}源程序編譯程序01101001100101011001001110101010101011000011111001011111110010101010001010001111101101……目標程序編譯初始數據目標程序、運行系統(tǒng)計算結果輸入處理輸出程序(chéngxù)的編譯程序(chéngxù)的執(zhí)行6.1程序設計語言的編譯與解釋第八頁，共50頁。編譯階段將源程序變換成目標程序；運行階段則由所生成的目標程序連同運行系統(tǒng)（數據空間分配子程序、標準函數(hánshù)程序等）接受程序的初始數據作為輸入，運行后輸出計算結果。如果目標程序是匯編語言的形式，則需要在編譯階段和運行階段之間加一個匯編階段。#includeMain(){For(;;){Printf(“HelloWorld!\n”);}}源程序匯編程序011010011001010010101011000011111011……機器語言程序ADDA,BMOVB,C……編譯程序匯編語言程序編譯匯編6.1程序設計語言(yǔyán)的編譯與解釋第九頁，共50頁。2形式語言(yǔyán)1程序設計語言(yǔyán)的編譯與解釋例如，將詞法分析作為第一編，語法分析和語義分析作為第二遍等。在編譯(biānyì)的各個階段常常要收集和使用源程序的各種信息，為了方便，通常把這些信息保存在一些表中，如關鍵字表、常量表、數組信息表、標識符表等等，這些表稱為符號表。3第一階段--詞法(cífǎ)分析<字母(zìmǔ)>∷=_|<大寫字母(zìmǔ)>|<小寫字母(zìmǔ)>④<名詞>∷=李翔|韓方|計算機|大學生|教師|C語言（1）分析并識別單詞及其屬性；第四十四頁，共50頁。編譯(biānyì)過程第二十九頁，共50頁。高級語言:高級語言則是面向應用的，分成很多種，如FORTRAN、Pascal、C、C#、VB、Java等。編譯程序的功能是將用高級語言編寫的源程序翻譯成等價的低級語言（匯編語言(huìbiānyǔyán)或機器語言）目標程序。⑥<動詞>∷=是|學習連接程序還連接目標程序和用于標準庫函數的代碼，以及連接目標程序和由計算機的操作系統(tǒng)提供的資源（例如，存儲分配程序及輸入(shūrù)與輸出設備）。8符號表管理(guǎnlǐ)和錯誤處理高級語言編寫的程序除了可以通過編譯方式外，還可以通過解釋程序執(zhí)行。所謂解釋程序是一種語言翻譯程序，按動態(tài)順序(shùnxù)，讀入一條語句，解釋一條語句，執(zhí)行一條語句，即邊翻譯邊執(zhí)行。源程序解釋程序計算結果源程序、輸入解釋執(zhí)行輸出數據2.解釋(jiěshì)方式6.1程序設計(chénɡxùshèjì)語言的編譯與解釋第十頁，共50頁。高級語言源程序經編譯程序編譯的經過目標代碼還可以是待裝配的目標代碼（相對目標代碼），這種形式的目標程序通常由多個目標模塊組成，各目標模塊由相應的源程序模塊經編譯生成，必須將相關的多個目標模塊組裝成到一個可執(zhí)行目標程序中，才能運行。完成集成工作的程序稱為連接程序。連接程序還連接目標程序和用于標準庫函數的代碼，以及連接目標程序和由計算機的操作系統(tǒng)提供的資源（例如，存儲分配程序及輸入(shūrù)與輸出設備）。3.連接(liánjiē)程序（linker）6.1程序設計(chénɡxùshèjì)語言的編譯與解釋第十一頁，共50頁。解釋程序與編譯程序的主要區(qū)別是：編譯程序將源程序翻譯成目標程序后再執(zhí)行(zhíxíng)目標程序.解釋程序是逐條讀出源程序中的語句并執(zhí)行(zhíxíng)，即在解釋程序的執(zhí)行(zhíxíng)過程中并不產生目標程序。6.1程序設計語言的編譯(biānyì)與解釋第十二頁，共50頁。6.1.3編譯程序的編譯過程(guòchéng)和編譯程序的結構編譯程序的功能是將用高級語言編寫的源程序翻譯成等價的低級語言（匯編語言(huìbiānyǔyán)或機器語言）目標程序。編譯的過程就是一個不同語言翻譯的過程，所以其過程類似于自然語言的翻譯。第十三頁，共50頁。6.1.3編譯(biānyì)程序的編譯(biānyì)過程和編譯(biānyì)程序的結構步驟完成的工作自然語言翻譯（英語翻譯成漢語）編譯程序（源程序翻譯成機器目標代碼）1根據英文單詞拼寫規(guī)則，識別出各個單詞和標點符號等，并檢查單詞是否有拼寫錯誤。這就是詞法分析對源程序進行詞法分析，檢查有無拼寫錯誤，識別出其中的單詞（關鍵字、標識符等）2根據英文語法規(guī)則，對詞法分析中得到的各個單詞和標點符號等進行分析、檢查，看是否能組成一個符合語法規(guī)則的句子。因此，該步驟稱為語法分析進行語法分析，檢查單詞串是否組成符合語法的正確的程序語句，如表達式是否正確等3對語法分析后得到的符合英文語法規(guī)則的句子進行分析，理解句子的含義，初步翻譯成中文。該步驟稱為語義分析分析翻譯語句要完成的操作，是將源程序初步翻譯成目標程序（一種中間代碼）。這是為了方便編譯過程的實現，同時也便于進行代碼優(yōu)化4對初步翻譯的中文進行修飾、潤色等代碼優(yōu)化5將英文翻譯成最終的中文將優(yōu)化后的中間代碼轉換成特定機器上的機器語言程序或匯編語言程序自然語言的翻譯(fānyì)第十四頁，共50頁。6.1.3編譯程序的編譯過程(guòchéng)和編譯程序的結構源程序詞法分析語法分析語義分析和中間代碼生成代碼優(yōu)化生成目標代碼出錯處理表格管理目標程序編譯過程編譯程序結構詞法分析程序語法分析程序語義分析和中間代碼生成程序代碼優(yōu)化程序生成目標代碼編譯(biānyì)過程可以劃分成五個階段1.編譯(biānyì)過程第十五頁，共50頁。編譯程序的功能是把高級語言源程序翻譯成等價的低級語言目標程序。源程序是由一些基本符號構成的，我們在運行這個程序時，先編譯，若某處有錯誤，就報錯，無錯誤就運行。編譯程序在編譯時，先將程序中的單詞一個個分離出來，登記在一個表中，這叫詞法(cífǎ)分析，然后檢查語句格式，叫做語法分析。然后檢查類型是否一致，計算表達式的值叫語義分析。這些功能都是由編譯程序相應的程序完成的。6.1.3編譯程序(biānyìchénɡxù)的編譯過程和編譯程序(biānyìchénɡxù)的結構第十六頁，共50頁。一般來說，整個(zhěnggè)編譯過程可以劃分成五個階段：詞法分析階段語法分析階段語義分析和中間代碼生成階段中間代碼的優(yōu)化目標代碼的生成。6.1.3編譯(biānyì)程序的編譯(biānyì)過程和編譯(biānyì)程序的結構1.編譯(biānyì)過程第十七頁，共50頁。6.1.3編譯程序的編譯過程(guòchéng)和編譯程序的結構2.一遍與多遍編譯(biānyì)編譯程序還采用“分遍”的形式，即編譯過程(guòchéng)可通過一遍或多遍編譯來完成。所謂編譯的“一遍”（pass）是指下述過程(guòchéng)：對于源程序或中間代碼，從頭到尾掃描一遍，并完成規(guī)定的處理任務，生成新的源程序的中間代碼代碼或目標代碼。在單遍編譯中，編譯程序包括了編譯程序的各個階段的任務，所有的階段由一遍完成，其結果是編譯得很好，但通常代碼效率差。第十八頁，共50頁。6.1.3編譯程序(biānyìchénɡxù)的編譯過程和編譯程序(biānyìchénɡxù)的結構2.一遍與多遍編譯(biānyì)在多遍掃描的編譯程序中，每一遍完成一個或幾個相關邏輯的工作，一個階段的工作也可以(kěyǐ)分多遍來完成。例如，將詞法分析作為第一編，語法分析和語義分析作為第二遍等。第十九頁，共50頁。6.2形式語言—程序設計(chénɡxùshèjì)語言的語法描述程序和自然語言一樣，也有其語法規(guī)則，要對程序進行語法分析，就要先了解程序的語法規(guī)則。程序的語法規(guī)則稱為(chēnɡwéi)文法，即文法是描述語言的形式規(guī)則（語法規(guī)則）。用一組數學符號和規(guī)則來描述的語言稱為(chēnɡwéi)形式語言。目前程序設計語言都是用形式語言來描述，形式語言是編譯原理的理論基礎。1.什么(shénme)是形式語言?第二十頁，共50頁。6.2形式語言(yǔyán)—程序設計語言(yǔyán)的語法描述程序和自然語言一樣，也有其語法規(guī)則，要對程序進行語法分析，就要先了解程序的語法規(guī)則。程序的語法規(guī)則稱為文法，即文法是描述語言的形式規(guī)則（語法規(guī)則）。這種規(guī)則要能夠描述程序語言各種不同的結構，同時還要使程序能夠易于分析和翻譯，最好能夠根據(gēnjù)其語法規(guī)則自動生成有效的語法分析程序。目前程序設計語言都是用形式語言來描述，形式語言是編譯原理的理論基礎。第二十一頁，共50頁。6.2形式語言(yǔyán)—程序設計語言(yǔyán)的語法描述

2.字母表和符號串

任何一種語言，都是由該語言的基本符號所組成(zǔchénɡ)的符號串的集合。例如，英語文章是由句子和標點符號構成的，句子是由單詞構成的，而單詞則是由字母構成的。第二十二頁，共50頁。6.2形式語言—程序設計語言的語法(yǔfǎ)描述

2.字母表和符號串

（1）字母表字母表是符號的非空有窮集合(jíhé)，字母表中的元素稱為符號。因此字母表也稱為符號表。不同的語言有不同的字母表，例如英語的字母表是26個英文字母、數字和一些特殊符號。漢語的字母表是漢字、數字和專用符號等。而C語言的字母表包括關鍵字、字母、數字和一些專用符號。（2）符號串字母表中的符號所組成的任何有窮序列稱為該字母表上的符號串。例如語句“if(x==8)thena=5elsea=9”可以看作是定義在C語言字母表上的一個符號串。第二十三頁，共50頁。6.2形式語言(yǔyán)—程序設計語言(yǔyán)的語法描述3.什么(shénme)是文法?文法是描述語言語法結構的形式(xíngshì)規(guī)則。我們以自然語言為例來說明。在描述一種語言時，就是要說明這種語言包含哪些句子。例如漢語，但漢語的句子有無窮多個，無法全部寫出來。這就要制定有限條語法規(guī)則，用這些語法規(guī)則來產生漢語的全部句子。這些規(guī)則就是所謂的文法。第二十四頁，共50頁。6.2形式語言(yǔyán)—程序設計語言(yǔyán)的語法描述3.什么(shénme)是文法?語法(yǔfǎ)規(guī)則例如，定義如下語法(yǔfǎ)規(guī)則：語法規(guī)則例如，定義如下語法規(guī)則：

①<句子>∷=<主語><謂語>②<主語>∷=<代詞>|<名詞>③<代詞>∷=我|你|他|她④<名詞>∷=李翔|韓方|計算機|大學生|教師|C語言⑤<謂語>∷=<動詞><賓語>⑥<動詞>∷=是|學習⑦<賓語>∷=<名詞>由語法規(guī)則推導句子第二十五頁，共50頁。6.2形式語言—程序設計語言的語法(yǔfǎ)描述如用EBNF來描述<整數>文法的定義(dìngyì)：<整數>∷=[+|-]<數字>{<數字>}<數字>∷=0|1|2|3|4|5|5|6|7|8|9第二十六頁，共50頁。6.2形式語言—程序設計(chénɡxùshèjì)語言的語法描述<標識符>∷=<字母(zìmǔ)>|<標識符><字母(zìmǔ)數字串><字母(zìmǔ)數字串>∷=<字母(zìmǔ)>|<十進制數字>|<字母(zìmǔ)數字串><字母(zìmǔ)>|<字母(zìmǔ)數字串><十進制數字><字母(zìmǔ)>∷=_|<大寫字母(zìmǔ)>|<小寫字母(zìmǔ)><小寫字母(zìmǔ)>∷=a|b|c|d|e|f|g|h|i|j|…|z<大寫字母(zìmǔ)>∷=A|B|C|D|E|F|G|H|I|J|…|Z<十進制數字>∷=<八進制數字>|8|9<八進制數字>∷=0|1|2|3|4|5|6|7C語言的“標識符”用BNF描述(miáoshù)為：第二十七頁，共50頁。詞法分析是編譯過程的基礎，其任務是掃描源程序，根據語言的詞法規(guī)則(guīzé)，分解和識別出每個單詞，并把單詞翻譯成相應的機內表示。當然，詞法分析在識別單詞的過程中，同時也做了詞法檢查。6.3第一階段--詞法(cífǎ)分析第二十八頁，共50頁。在高級語言中，所謂單詞，就是指邏輯上緊密相連的一組字符，這些字符具有(jùyǒu)集體含義。單詞是語言中最小的語義單位，如語言中的關鍵字、標識符、運算符和界限符。詞法分析的依據是詞的構造。單詞的構造規(guī)則在高級語言中有明確的規(guī)定，比如哪些為保留字、變量如何定義、常量如何構造、分界符有哪些等。6.3第一階段--詞法(cífǎ)分析第二十九頁，共50頁。詞法分析的主要內容包括：（1）分析并識別單詞及其屬性；（2）跳過空格(kōnɡɡé)、回車、制表符等分隔符；（3）濾掉注釋；（4）進行詞法檢查，報告發(fā)現的錯誤；（5）還要根據需要創(chuàng)建符號表、常量表等。6.3第一階段--詞法(cífǎ)分析第三十頁，共50頁。main(){ floatx=2,y=3,s; s=x+y*5;}例如，用C語言編寫(biānxiě)的程序段如下：識別出的單詞(dāncí)序列為表所示6.3第一階段--詞法(cífǎ)分析第三十一頁，共50頁。表1詞法(cífǎ)分析程序類型名單詞類型名單詞保留字main左括號(右括號)花括號{保留字float標識符x等號=常量2逗號,標識符y等號=常量3逗號,標識符s分號;標識符s等號=標識符x運算符+標識符y運算符*常量5分號;花括號}6.3第一階段--詞法(cífǎ)分析作為(zuòwéi)第二階段的輸入第三十二頁，共50頁。語法分析是在詞法分析的基礎上進行的，是編譯過程的第二個階段。語法分析的任務是根據語言的語法規(guī)則，把單詞符號串分解成各類語法單位，如表達式、語句等。并在分析過程中，對單詞串組成的源程序進行語法正確性檢查。通過語法分析，可以(kěyǐ)確定整個輸入符號串是否構成一個正確的程序。6.4第二階段--語法分析第三十三頁，共50頁。6.4第二階段--語法分析語法分析的結果是無語法錯誤的語法成分(chéngfèn)，有多種輸出形式。第三十四頁，共50頁。6.5第三階段--語義分析(fēnxī)和中間代碼的生成一個源程序通過詞法分析和語法分析后，可以(kěyǐ)確定該源程序在單詞拼寫和語法上是正確的，但并沒有分析其語句的邏輯含義，即要執(zhí)行什么操作？詞法和語法的正確并不能保證語義的正確正如一篇單詞拼寫正確、語法正確的文章，人們在閱讀時首先是要能讀通，然后是要理解每句話及整篇文章的含義或思想。這就是對文章的語義分析。第三十五頁，共50頁。語義分析的任務是對各種不同語句進行翻譯，包括兩方面的工作：一是對每種語法范疇進行語義檢查，如變量是否定義(dìngyì)、類型是否正確等；二是在語義檢查正確的情況下，進行中間代碼的翻譯。程序的語義分析就是(jiùshì)對程序的邏輯含義進行分析，是編譯過程中最實質性的工作。Why?6.5第三階段--語義分析(fēnxī)和中間代碼的生成1.語義分析第三十六頁，共50頁。中間代碼是介于(jièyú)高級語言語句和低級語言語句之間的一種獨立于具體硬件的記號系統(tǒng)，它即有一定程度的抽象，又和低級語言十分接近，因此，轉換成目標代碼很容易。Why?6.5第三階段--語義分析(fēnxī)和中間代碼的生成2.中間代碼的生成(shēnɡchénɡ)第三十七頁，共50頁。中間代碼的表示形式有很多種，常見的有:四元式三元式間接三元式逆波蘭式等。其中四元式的形式為:（運算符，運算對象(duìxiàng)1，運算對象(duìxiàng)2，結果）6.5第三階段--語義分析(fēnxī)和中間代碼的生成第三十八頁，共50頁。6.6第四階段—中間(zhōngjiān)代碼優(yōu)化代碼優(yōu)化就是為提高(tígāo)目標代碼質量而進行的加工和處理工作，使得目標代碼在執(zhí)行時效率更高，即執(zhí)行時間更短，同時占用內存空間更小。一般優(yōu)化工作階段是在中間代碼生成之后或目標代碼生成之后，實際上，編譯程序通常包括許多代碼改進或優(yōu)化步驟。第三十九頁，共50頁。中間代碼優(yōu)化通過調整和改變中間代碼中某些操作次序，以最終(zuìzhōnɡ)產生更加高效的目標代碼。優(yōu)化的主要手段有:刪除冗余運算刪除無用賦值合并已知量循環(huán)優(yōu)化等。6.6第四階段—中間(zhōngjiān)代碼優(yōu)化第四十頁，共50頁。6.6第四階段—中間(zhōngjiān)代碼優(yōu)化第四十一頁，共50頁。這一階段的任務是對前一階段的中間(zhōngjiān)代碼變換成特定機器上的機器語言或匯編語言程序，實現機器的最終翻譯。最后階段的工作因為目標語言的關系而十分依賴機器的硬件系統(tǒng)，即如何充分利用機器現存的寄存器，合理的選擇指令，生成盡可能短的目標代碼，這與機器的硬件有關。6.7第五階段(jiēduàn)—目標代碼的生成第四十二頁，共50頁。目標代碼生成程序生成的目標代碼有不同的形式，一般(yībān)有以下三