第1章 編譯概述

CompilersPrinciples主講教師：陳大玲

課程要求熟練掌握C、Pascal語言的編程、語法結(jié)構(gòu)；會(huì)一種程序設(shè)計(jì)語言的編程；會(huì)一種數(shù)據(jù)庫開發(fā)語言，或熟悉文件的管理；按時(shí)完成作業(yè)；按課程的進(jìn)程，按時(shí)完成課程實(shí)驗(yàn)；認(rèn)真聽講，認(rèn)真作筆記，上課不得遲到早退上課不得喧嘩。2023/2/33第1章

編譯概述

什么是編譯程序

編譯原理這門課程主要介紹設(shè)計(jì)和構(gòu)造編譯程序的基本原理和常用的技術(shù)和方法。本章重點(diǎn)介紹編譯程序的基本概念。編譯的過程編譯程序的結(jié)構(gòu)什么是編譯程序

計(jì)算機(jī)只能識別機(jī)器語言，不能識別自然語言或高級語言，那么我們的高級語言程序是如何在計(jì)算機(jī)上執(zhí)行的呢？在計(jì)算機(jī)上執(zhí)行一個(gè)高級語言程序一般要分兩步：第一步：用一個(gè)翻譯程序把高級語言翻譯成機(jī)器語言程序；第二步：運(yùn)行所得的機(jī)器語言程序求得計(jì)算結(jié)果。第二步我們暫時(shí)不考慮，那么第一步“翻譯程序”是我們這門課討論的重點(diǎn)，什么樣的程序叫翻譯程序？翻譯程序是如何翻譯的？世界上第一個(gè)編譯程序—FORTRAN編譯程序是20世紀(jì)50年代中期研制成功的。2023/2/351.1翻譯程序與編譯程序

翻譯程序是指這樣一個(gè)程序,它把一種語言(稱作源語言)所寫的程序(源程序)翻譯成等價(jià)的另一種語言(稱作目標(biāo)語言)的程序(目標(biāo)程序)。

高級語言程序機(jī)器語言程序翻譯程序#include<stdio.h>intmain(void){ printf("hello,world\n"); return0;}00001010…..2023/2/361.1翻譯程序與編譯程序

編譯程序是一種翻譯程序，它將高級語言所寫的源程序翻譯成等價(jià)的機(jī)器語言或匯編語言的目標(biāo)程序。

源程序高級語言程序編譯程序目標(biāo)程序匯編語言或者機(jī)器語言程序

定義：假設(shè)，SL指源語言程序，TL指目標(biāo)語言程序，則：1.翻譯程序－－把SL變換為TL的程序，SL與TL邏輯上等價(jià)。2.編譯程序－－SL為高級語言、TL為低級語言的翻譯程序。3.匯編程序－－SL為匯編語言程序，TL為機(jī)器語言程序。4.解釋程序－－逐條翻譯，且立即執(zhí)行，不生成目標(biāo)程序。2023/2/38程序運(yùn)行階段

采用編譯方式在計(jì)算機(jī)上執(zhí)行用高級語言編寫的程序，需分階段進(jìn)行。第一種情況：源程序編譯程序機(jī)器語言目標(biāo)程序初始數(shù)據(jù)運(yùn)行系統(tǒng)結(jié)果編譯階段運(yùn)行階段高級語言程序2023/2/39第二種情況：源程序編譯程序機(jī)器語言目標(biāo)程序初始數(shù)據(jù)運(yùn)行系統(tǒng)結(jié)果編譯階段運(yùn)行階段匯編程序匯編語言目標(biāo)程序匯編階段高級語言程序程序運(yùn)行階段2023/2/3101.2編譯過程與編譯程序的基本結(jié)構(gòu)

將英文句子“Iwishyousuccess”翻譯成中文句子的大致過程是：

詞法分析

語法分析

語義分析

修飾工作

翻譯成文

2023/2/311

編譯過程

編譯程序是將一種語言形式翻譯成另一種語言形式，因此，其工作過程一般可劃分為如下五個(gè)階段：

詞法分析

語法分析

語義分析和中間代碼生成

代碼優(yōu)化

目標(biāo)代碼生成2023/2/312floatr，h，s；

s=2*3.1416*r*(r＋h);例如計(jì)算圓柱體表面積的程序片斷如下：

編譯過程

2023/2/313

詞法分析階段的任務(wù)：對構(gòu)成源程序的字符串從左到右進(jìn)行掃描和分解，根據(jù)語言的詞法規(guī)則，識別出一個(gè)一個(gè)具有獨(dú)立意義的單詞(也稱單詞符號,簡稱符號

)。

單詞分類：基本字（if、else、for、while等）、標(biāo)識符、常數(shù)、算符、界符（標(biāo)點(diǎn)和括號）。1.

詞法分析2023/2/314

詞法規(guī)則是單詞符號的形成規(guī)則,它規(guī)定了哪樣的字符串構(gòu)成一個(gè)單詞符號。詞法規(guī)則floatr，h，s；

s=2*3.1416*r*(h＋r)；例如2023/2/315

上述源程序通過詞法分析識別出如下單詞符號：基本字float 標(biāo)識符r、h、s

常數(shù)3.1416、2 算符*、＋界符（、）、；、，、=詞法規(guī)則2023/2/3162.語法分析

語法分析的任務(wù)是在詞法分析的基礎(chǔ)上,根據(jù)語言的語法規(guī)則從單詞符號串中識別出各種語法單位,并進(jìn)行語法檢查,即檢查各種語法單位在語法結(jié)構(gòu)上的正確性。 語法單位：程序、程序段、語句、短語、表達(dá)式。2023/2/317語法規(guī)則

語言的語法規(guī)則規(guī)定了如何從單詞符號形成語法單位，語法規(guī)則是語法單位的形成規(guī)則。floatr，h，s；

s=2*3.1416*r*(h＋r)；例如2023/2/318語法規(guī)則

單詞符號串s=2*3.1416*r*(h＋r)中，“s”是<變量>，單詞符號串

“2*3.1416*r*(h＋r)”組合成<表達(dá)式>這樣的語法單位,由<變量>=<表達(dá)式>構(gòu)成<賦值語句>這樣的語法單位。2023/2/3193.語義分析和中間代碼生成

語義分析的任務(wù)是首先對每種語法單位進(jìn)行靜態(tài)的語義審查，然后分析其含義，并用另一種語言形式(比源語言更接近于目標(biāo)語言的一種中間代碼或直接用目標(biāo)語言)來描述這種語義。中間代碼的特點(diǎn)：結(jié)構(gòu)簡單、語義明確、易于轉(zhuǎn)換、易于優(yōu)化。中間代碼的形式：

后綴式、三地址代碼、四元式等。三地址代碼：由指令序列組成，每條指令最多有三個(gè)操作數(shù)。四元式的形式是：

（算符，左操作數(shù)，右操作數(shù)，結(jié)果）2023/2/321

例如，前例中

將s

=2*3.1416*r*(h＋r)翻譯成如下形式的四元式中間代碼：(1)(*,2,3.1416,T1)(2)(*,T1, r,T2)(3)(+,h, r,T3)(4)(*,T2,T3,T4)(5)(=,T4,__,s)2023/2/3224.代碼優(yōu)化

代碼優(yōu)化的任務(wù)是對前階段產(chǎn)生的中間代碼進(jìn)行等價(jià)變換或改造，以期獲得更為高效(即省時(shí)間和空間)的目標(biāo)代碼。優(yōu)化主要包括局部優(yōu)化和循環(huán)優(yōu)化等，例如上述四元式經(jīng)局部優(yōu)化后得：(1)(*,6.28,

r,T2)(2)(+,h,r,T3)(3)(*,T2,T3,T4)(4)(=,T4,__,s)2023/2/3235.目標(biāo)代碼生成

目標(biāo)代碼生成的任務(wù)是將中間代碼變換成特定機(jī)器上的絕對指令代碼或可重定位的指令代碼或匯編指令代碼。

2023/2/324表格管理和錯(cuò)誤處理

編譯程序在工作過程中需要建立一些表格，以登記源程序中所提供的或在編譯過程中所產(chǎn)生的一些信息，編譯各個(gè)階段的工作都涉及到構(gòu)造、查找、修改或存取有關(guān)表格中的信息，因此，在編譯程序中必須有一組管理各種表格的程序。

在編譯程序的各個(gè)階段中，都要涉及表格管理和錯(cuò)誤處理。2023/2/325表格管理和錯(cuò)誤處理

一個(gè)好的編譯程序在編譯過程中，應(yīng)具有廣泛的程序查錯(cuò)能力，并能準(zhǔn)確地報(bào)告錯(cuò)誤的種類及出錯(cuò)位置，以便用戶查找和糾正，因此，在編譯程序中還必須有一個(gè)出錯(cuò)處理程序。

2023/2/326編譯程序的結(jié)構(gòu)

源程序語義分析和中間代碼生成程序語法分析程序詞法分析程序代碼優(yōu)化程序目標(biāo)代碼生成程序

目標(biāo)程序表格管理程序出錯(cuò)處理程序(字符串)編譯過程實(shí)例:Pascal語言的一條賦值語句：p:=i+r*60;

1.詞法分析結(jié)果是識別出下列單詞符號：標(biāo)識符p

賦值號:＝標(biāo)識符i標(biāo)識符r

乘號*整常數(shù)60

分號；2.語法分析可得到如下所示的層次結(jié)構(gòu)，稱為語法分析樹，簡稱語法樹（或分析樹）賦值語句表達(dá)式表達(dá)式標(biāo)識符p+表達(dá)式標(biāo)識符表達(dá)式標(biāo)識符表達(dá)式數(shù)ir60*=：緊縮形式表示的語法分析樹：:=p+i*r603.語義分析和中間代碼生成類型檢查是語義分析的一個(gè)重要部分，按照語言的類型規(guī)則檢查和每個(gè)運(yùn)算符相關(guān)的操作數(shù)。:=p+i*r60inttoreal語義分析插入整型到實(shí)型的轉(zhuǎn)換由語義分析得到的分析樹可得到表達(dá)式p:=i+r*60的三地址代碼表示的中間代碼：

t1:=inttoreal(60) t2:=r*t1 t3:=i+t2

p

:=t3:=p+i*r60inttoreal語義分析插入整型到實(shí)型的轉(zhuǎn)換由語義分析得到的分析樹可得到表達(dá)式p:=i+r*60的四元式表示的中間代碼：(inttoreal()，60，，T1）(*，r，T1，T2)(+，i，T2，T3)(=，T3，_，p)課堂練習(xí)題：寫出：Z:=Y*(X+0.418)/W的四元式和三地址代碼表示的中間代碼。4.代碼優(yōu)化p:=i+r*60的三地址代碼可優(yōu)化為用下面兩條指令表示：

t1:=r*60.0

p

:=i+t15.目標(biāo)代碼生成例如：使用寄存器R1和R2，代碼 t1:=r*60.0 p:=i+t1可以翻譯成如下的代碼：

MOVFr,R2MULF#60.0,R2MOVFi,R1ADDFR2,R1MOVFR1,p一個(gè)語句的翻譯過程示意圖Temp1:=id3*60.0id1:=id2+temp1中間代碼生成器Temp1:=inttoreal(60)Temp2:=id3*temp1Temp3:=id2+temp2id1:=temp3代碼優(yōu)化器代碼生成器MOVFid3,R2MULF#60.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id1從源程序到中間代碼生成產(chǎn)品編譯程序的結(jié)構(gòu)源程序詞法分析器語法分析器語義分析器中間代碼生成器代碼優(yōu)化器目標(biāo)代碼生成器目標(biāo)程序符號表管理器錯(cuò)誤處理器分析部分綜合部分

符號表管理符號表

是為每個(gè)標(biāo)識符保存一個(gè)記錄的數(shù)據(jù)結(jié)構(gòu)，記錄著每一個(gè)標(biāo)識符的屬性。符號表在各個(gè)階段收集的信息一般不同。例如：在C，Pascal語言中的變量定義語句C語言:floatposition,initial,rate;Pascal語言:varposition,initial,rate:real;C語言中在讀到變量名的時(shí)候，變量的屬性已經(jīng)知道，可以一起寫入符號表，而Pascal語言中，詞法分析器在程序掃描時(shí)，讀到變量名的時(shí)候，并不知道標(biāo)識符的屬性，所以，符號表并不一定就記載有標(biāo)識符的屬性。出錯(cuò)處理一個(gè)好的編譯程序不但能最大限度的發(fā)現(xiàn)錯(cuò)誤，準(zhǔn)確地指出錯(cuò)誤的性質(zhì)和發(fā)生錯(cuò)誤的地點(diǎn)，而且能夠把錯(cuò)誤的范圍縮小到盡可能小的范圍，使程序的其他部分能繼續(xù)編譯下去；如果不僅能發(fā)現(xiàn)錯(cuò)誤，而且能夠知道校正錯(cuò)誤就更好啦。源程序中的錯(cuò)誤分為語法錯(cuò)誤和語義錯(cuò)誤

語法錯(cuò)誤：源程序中不符合語法或詞法規(guī)則的錯(cuò)誤，可在語法或詞法分析中檢測出來。（非法字符、括號不配、缺少等）

語義錯(cuò)誤：源程序中不符合語義規(guī)則的錯(cuò)誤，一般在語義分析中檢測出來，但有的要在運(yùn)行時(shí)才能檢測出來。（說明錯(cuò)誤、作用域錯(cuò)誤、類型不一致等）遍 編譯程序具體實(shí)現(xiàn)時(shí)，受不同源語言、設(shè)計(jì)要求、使用對象和計(jì)算機(jī)條件的限制，往往將編譯程序組織為若干遍。遍：就是對源程序或源程序的中間結(jié)果從頭到位掃描一次，并作有關(guān)的加工，生成新的中間結(jié)果或目標(biāo)程序。通常，一遍的工作，從外存上讀取前一遍的中間結(jié)果開始，完成它的工作后，再將其產(chǎn)生的結(jié)果存到外存上去。例如：我們可以把詞法分析、語法分析及語義分析與中間代碼生成合為一遍。這時(shí)，語法分析處于核心位置，當(dāng)他在識別語法結(jié)構(gòu)時(shí)需要下一個(gè)單詞，他就調(diào)用詞法分析器，一旦識別出一個(gè)語法單位時(shí)，他就調(diào)用中間代碼生成器。編譯前端與后端編譯前端主要由與源語言有關(guān)，但與目標(biāo)機(jī)無關(guān)的部分組成。包括：詞法分析、語法分析、語義分析與中間代碼產(chǎn)生，有的代碼優(yōu)化工作也可以包括在前端。編譯后端主要由與目標(biāo)機(jī)有關(guān)的部分組成。包括：與目標(biāo)機(jī)有關(guān)的代碼優(yōu)化、目標(biāo)代碼生成等?？梢匀【幾g程序的前端，改寫其后端生成不同目標(biāo)機(jī)上的相同語言的編譯程序。也可以為幾種語言寫出生成相同中間代碼的前端，再配上相同的后端，形成同一臺機(jī)器上不同語言的編譯程序。編譯器的伙伴語言擴(kuò)充程序預(yù)處理器匯編器編譯器裝配器/連接編輯器源程序目標(biāo)匯編程序絕對機(jī)器代碼重定位機(jī)器代碼庫、重定位目標(biāo)文件圖1-5一個(gè)語言處理系統(tǒng)預(yù)處理器預(yù)處理器產(chǎn)生編譯器的輸入，負(fù)責(zé)收集源程序，他可以完成的任務(wù)：

（1）宏處理#define…

（2）文件包括例如：#include<math.h>

（3）語言擴(kuò)充用內(nèi)部宏定義增強(qiáng)老語言的功能（數(shù)據(jù)庫語言、沒有的語句結(jié)構(gòu)）。宏處理的幾個(gè)名詞：宏定義、宏引用、形式參數(shù)、實(shí)在參數(shù)預(yù)處理器舉例說明：

#definemin(a,b)

((a)>(b)?(b):(a))#include<stdio.h>main(){ intm,n,i;m=10;n=15;I=10*min(m,n);printf(“%d\n”,i);}匯編器源程序：b=a+2匯編語言程序：

mova,r1add#2,r1

movr1,b第一次掃描：結(jié)果：標(biāo)識符地址

a0b4第二次掃描：

（可重定位的機(jī)器代碼）

0001010000000000*0011011000000010

0010010000000100*裝配器和連接編輯器裝配器的兩個(gè)功能:裝入和連接編輯裝入：指的是把可重定位的機(jī)器代碼進(jìn)行地址變換，裝入內(nèi)存儲(chǔ)器指定的起始地址。連接編輯：指的是把幾個(gè)可重定位的機(jī)器代碼文件連接成一個(gè)可執(zhí)行的程序。這些文件可以有分別編譯或匯編產(chǎn)生的結(jié)果，也可以有從系統(tǒng)提供的庫文件中取出的內(nèi)容。2023/2/3461.3編譯程序的生成方法

對源語言和目標(biāo)語言認(rèn)真分析

設(shè)計(jì)編譯算法

選擇語言編制程序

調(diào)試編譯程序

提交相關(guān)文檔資料

編譯程序是一個(gè)復(fù)雜的系統(tǒng)程序，要生成一個(gè)編譯程序一般要考慮以下幾方面：2023/2/347編譯程序的自動(dòng)生成詞法分析程序的自動(dòng)生成系統(tǒng)LEX語法分析程序自動(dòng)生成系統(tǒng)YACC編譯程序產(chǎn)生器:可用來自動(dòng)產(chǎn)生整個(gè)編譯程序的軟件工具,它的功能是將任一語言的詞法規(guī)則、語法規(guī)則和語義解釋的描述作為輸入，自動(dòng)生成該語言的編譯程序。

隨著編譯技術(shù)和自動(dòng)機(jī)理論的發(fā)展,近年來已研制出了一些編譯程序的自動(dòng)生成系統(tǒng)。如:2023/2/348編譯程序的自動(dòng)生成

生成編譯程序的方