第1章 緒論new (編譯原理 陳火旺)

編譯原理

主講：周雁Email：yanzi0910@課程的性質(zhì)計算機專業(yè)的專業(yè)基礎(chǔ)課是軟件技術(shù)基礎(chǔ)是計算機專業(yè)的學生必修的一門主干課學習編譯原理的目的通過本課程主要學習編譯程序構(gòu)造的基本原理和技術(shù)加深對程序研發(fā)過程的理解加深對程序執(zhí)行過程的認識進一步編好程序為將來從事系統(tǒng)軟件和軟件工具研究與開發(fā)打下基礎(chǔ)提高計算機專業(yè)素養(yǎng)（計算機專業(yè)的“詩經(jīng)”）學習任務(wù)掌握編譯的理論基礎(chǔ)和形式化系統(tǒng)了解編譯的全過程及其具體的實現(xiàn)方法成績考核方法成績考核方法平時成績占20％ 實踐成績占30%期末考試成績占50％平時成績?yōu)檎n堂點名+作業(yè)學習方法及要求認真聽課，認真理解書中的基本概念、基本原理與基本算法弄懂書中的例題與習題在看書時或理解例題時，一定要劃出相應(yīng)的細節(jié)變化過程，通過畫圖來加深理解在理解的基礎(chǔ)上記憶理論結(jié)合實踐上課、上機紀律！編譯原理課程學習方法之我見：

(1)編譯原理與離散數(shù)學的關(guān)系

(2)“游戲”與“游戲規(guī)則”*例如，有一個文法:

(0)EE+E|E*E|(E)|i

請采用最右推導產(chǎn)生句子i+i*i:解：EE+EE+E*EE+E*iE+i*ii+i*i“變形金剛”游戲規(guī)則：1.從開始符號開始變形；2.每次按照“變形規(guī)則”將一個式子的左部變形為右部；3.每次變形串中最右邊的大寫字母，一直變形到目標串(不含大寫字母)為止。*試采用最右推導產(chǎn)生句子:(1)i*(i+i)(2)i*(i+i*i)C語言的復習：

編寫程序要求：讓用戶輸入一個字符，然后判斷(如果用戶輸入多個字符，只判斷第一個)：1.若是字母，在屏幕上輸出該字母ASCⅡ值；2.若是數(shù)字，在屏幕上輸出該數(shù)字的二進制值；3.若是＋－*/，在屏幕上輸出“輸入為算符”；4.若是其它字符，在屏幕上輸出“非法輸入！”。第1章引論內(nèi)容簡介程序的翻譯編譯程序的工作過程編譯程序的結(jié)構(gòu)編譯程序的組織方式編譯程序的構(gòu)造第1章引論教學要求掌握：編譯的概念，編譯的過程理解：編譯的各個階段了解：編譯的結(jié)構(gòu)和組合1.0程序設(shè)計語言程序設(shè)計語言

在計算機上如何執(zhí)行一個高級語言程序？把高級語言程序翻譯成機器語言程序運行所得的機器語言程序求得計算結(jié)果機器語言001110010010匯編語言ADD高級語言

beginx:=9+2end

各種程序設(shè)計語言都有自己的語法和語義體系，其編譯程序根據(jù)這種語言的語法和語義將其翻譯成機器能夠接受的機器語言。程序設(shè)計語言是按一定規(guī)則排列的符號集合，而編譯程序就是把這些符號集合變成機器指令的轉(zhuǎn)換器，編譯程序又稱為編譯器。軟件分類軟件計算機系統(tǒng)中的程序及其文檔系統(tǒng)軟件

居于計算機系統(tǒng)中最靠近硬件的一層，其他軟件一般都通過系統(tǒng)軟件發(fā)揮作用，如編譯系統(tǒng)和操作系統(tǒng)。

應(yīng)用軟件把軟件語言編寫的各種程序處理成可在計算機上執(zhí)行的程序。操作系統(tǒng)編譯系統(tǒng)裸機編譯程序的重要性使得計算機用戶不必考慮與機器有關(guān)的繁瑣細節(jié)使程序員和程序設(shè)計人員獨立于機器一、翻譯程序的定義

程序的翻譯通常有兩種方式：1.編譯2.解釋翻譯：是指能將用甲語言（源語言）編寫的程序，在不改變語義的條件下轉(zhuǎn)換成用乙語言（目標語言）書寫的程序。高級語言程序翻譯機器語言程序1.1什么是編譯程序(compiler)二、什么是編譯程序(compiler)編譯程序

是一個語言翻譯程序,是將用高級語言書寫的源程序翻譯成等價的低級語言的目標程序。C、PASCLE、JAVA等機器語言、匯編語言編譯程序的功能一個編譯程序就是一個語言翻譯程序，它把一種語言(稱作源語言)編寫的程序翻譯成另一種語言(稱作目標語言)的等價的程序.世界上第一個編譯程序——FORTRAN編譯程序是20世紀50年代中期研制成功。高級語言書寫的程序編譯程序低級語言程序1.編譯方式是一種分階段進行的方式。兩個階段的轉(zhuǎn)換：編譯階段

運行階段

三、編譯方式源程序編譯程序目標程序編譯時初始數(shù)據(jù)計算結(jié)果運行時目標代碼運行子程序三個階段的轉(zhuǎn)換：編譯階段匯編階段運行階段

源程序匯編語言編譯時編譯程序匯編程序目標代碼匯編時初始數(shù)據(jù)計算結(jié)果運行時目標代碼運行字程序2.編譯方式的特點

⑵編譯方式下，生成了目標代碼，且可多次執(zhí)行。⑴在編譯方式下，源程序的執(zhí)行需要分階段。如果編譯后的目標程序是機器語言程序，則源程序的執(zhí)行分為兩大階段：編譯階段和運行階段。如果編譯后的目標程序是匯編語言程序，則源程序的執(zhí)行分為三大階段：編譯階段、匯編階段和運行階段。完成解釋工作的解釋程序?qū)丛闯绦蛑姓Z句的動態(tài)順序，逐句地進行分析解釋，并立即予以執(zhí)行。優(yōu)點：直觀易懂，結(jié)構(gòu)簡單，易于實現(xiàn)人機對話缺點：效率低四、解釋方式

源程序解釋執(zhí)行的歷程

在解釋方式下，并不生成目標代碼，而是直接執(zhí)行源程序本身。這是編譯方式與解釋方式的根本區(qū)別。

?先看自然語言的翻譯1.識別出句子中的一個個單字2.分析句子的語法結(jié)構(gòu)3.初步翻譯句子的含意4.譯文修飾5.寫出最后譯文1.2編譯過程概述

?編譯的五個階段1.詞法分析2.語法分析3.語義分析中間代碼生成4.優(yōu)化5.目標代碼生成1.2編譯過程概述

目標代碼源程序出錯處理語法分析程序語義分析程序目標代碼生成程序詞法分析程序中間代碼生成程序代碼優(yōu)化程序表格管理1.2編譯過程概述舉例說明：有一個C語言程序，對它進行編譯voidjisuan(){inty,c,b;floatx,a,b;x=a+b-50;y=c+(d+x)+b;}1.2編譯過程概述

一、詞法分析

voidjisuan(){inty,c,b;floatx,a,b;x=a+b-50;y=c+(d+x)+b;}識別右邊程序中的單詞基本字：標識符：整常數(shù)：運算符：界限符：任務(wù)：輸入源程序，對構(gòu)成源程序的字符串進行掃描和分析，識別出一個個的單詞。單詞：

是高級語言中有實在意義的最小語法單位，它由字符構(gòu)成。void、int、floata、b、c、d、x、y、

jisuan50＋、—、=（），{}；一、詞法分析

轉(zhuǎn)換：對基本字、運算符、界限符的轉(zhuǎn)換；標識符的轉(zhuǎn)換；常數(shù)的轉(zhuǎn)換；轉(zhuǎn)換完成后的格式：（單詞種別單詞值）

詞法分析依照詞法規(guī)則，識別出正確地單詞，轉(zhuǎn)換成統(tǒng)一規(guī)格，備用。描述詞法規(guī)則：有效工具是正規(guī)式和有限自動機二、語法分析

語法規(guī)則：語言的規(guī)則，又稱為文法；規(guī)定單詞如何構(gòu)成短語、語句、過程和程序。

任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號組成各類的語法單位：短語、子句、語句、過程、程序。語法規(guī)則的表示：（Backus范式）

BNF:A::=B|C

讀做“A定義為B或C”語法分析方法：推導和歸納。三、語義分析與中間代碼產(chǎn)生

中間代碼的形式：

四元式、三元式、逆波蘭式任務(wù)：對語法分析識別出的各類語法范疇，分析其含義，進行和初步翻譯，產(chǎn)生介于源代碼和目標代碼之間的一種代碼。分為兩個階段：

&對每種語法范疇進行靜態(tài)語義檢查

&若語義正確，就進行中間代碼的翻譯四、代碼優(yōu)化任務(wù)：對前面產(chǎn)生的中間代碼進行加工變換，使變換后的代碼更為高效（時間，空間上）。原則：等價變換

主要方面：

公共子表達式的提取，合并已知量，刪除無用語句，循環(huán)優(yōu)化等五、目標代碼生成

任務(wù)：把經(jīng)過優(yōu)化的中間代碼轉(zhuǎn)換成特定機器上的低級語言代碼。目標代碼的形式：

&絕對指令代碼：（可直接運行）

&

匯編指令代碼：（要經(jīng)過匯編才能運行）

&可重新定位的指令代碼：（要經(jīng)過link才能運行）

說明：上述編譯過程的階段劃分是一種典型的處理模式，事實上并非所有的編譯程序都包括這樣幾個階段。有些編譯程序并不要中間代碼，即不存在中間代碼生成階段；有些編譯程序不進行優(yōu)化，優(yōu)化階段即可省去;有些最簡單的編譯程序只有詞法分析，語法分析；語義分析和目標代碼生成。1.3編譯程序的結(jié)構(gòu)編譯程序總框詞法分析器語法分析器中間代碼生成中間代碼優(yōu)化目標代碼生成源程序單詞符號語法單位四元式四元式目標程序

出錯處理

表格管理一、表格與表格管理

與編譯前三個階段有關(guān)的表格有：

&***符號表:登記源程序中出現(xiàn)的每個名字（常量名、變量名、數(shù)組名等）以及名字的各種屬性；

&常數(shù)表:登記源程序中出現(xiàn)的各種類型的常數(shù)值；

&標號表:登記源程序中出現(xiàn)的標號的定義和引用情況；

&分程序入口表:登記過程的層次、分程序符號表的入口等；

&中間代碼表:記錄四元式序列的表。表格的作用：登記源程序的各類信息和編譯各階段的進展狀況。編譯各階段均須維持表格并進行表格管理。二、出錯處理

任務(wù)：如果源程序有錯誤，編譯程序應(yīng)該設(shè)法發(fā)現(xiàn)錯誤，并報告給用戶。完成：由專門的出錯處理程序來完成。源程序中的錯誤通常分為：

&語法錯誤不符合語法（或詞法）規(guī)則的錯誤單詞拼寫錯誤、括號不匹配...

&

語義錯誤不符合語義規(guī)則的錯誤說明錯誤、作用域錯誤、類型不匹配...三、遍(趟，趟程)

遍:對源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間結(jié)果或目標程序。

&注：遍與階段的含義毫無關(guān)系。根據(jù)對編譯程序在完成翻譯任務(wù)的過程中需要對源程序或其中間等價物掃描的遍數(shù)，可以把編譯程序分為單遍掃描的編譯程序(只需掃描一遍)和多遍掃描的編譯程序(需掃描多遍)。

前端主要由與源語言有關(guān)但與目標機器無關(guān)的那些部分組成，如詞法分析、語法分析、語義分析與中間代碼生成及部分代碼優(yōu)化工作。

后端主要包括編譯中與目標機器有關(guān)的那些部分，如與目標機有關(guān)的代碼優(yōu)化和目標代碼生成等。后端不依賴于源語言而僅依賴于中間語言。

可以通過改變編譯程序的后端來實現(xiàn)編譯程序的移植。四、編譯的前端和后端1.4編譯程序的生成構(gòu)造編譯程序的語言： 1.直接用機器語言編寫的編譯程序 2.用匯編語言編寫的編譯程序 3.用高級語言編寫的編譯程序（普遍采用的方法）構(gòu)造編譯程序的方法：1.自編譯：“滾雪球”2.移植：同種語言的編譯程序在不同類型的機器之間移植編譯工具

LEX（詞法分析）YACC（用于自動產(chǎn)生LALR分析表）1.5編譯程序與程序設(shè)計環(huán)境編譯程序

&

無疑是實現(xiàn)高級語言的一個最重要的工具

&

支持程序設(shè)計人員進行程序設(shè)計開發(fā)通常還需要其它一些工具：如編輯程序、連接程序、調(diào)試程序等

&

編譯程序與這些程序設(shè)計工具