《編譯原理》第1章 緒論

編譯原理編輯ppt自我介紹姓名：劉善梅QQ：30683530辦公室：逸夫樓C427

郵箱：

lsmei@2編輯ppt課程介紹兩門獨(dú)立的課程：理論（48學(xué)時(shí)）

實(shí)驗(yàn)（16學(xué)時(shí)）考試成績組成

理論：平時(shí)作業(yè)和考勤占20%，期末結(jié)業(yè)考試占80%；

實(shí)驗(yàn)：根據(jù)實(shí)驗(yàn)報(bào)告和程序源代碼評(píng)分，實(shí)驗(yàn)報(bào)告占40%,程序源代碼占60%。課程特點(diǎn)：難！3編輯ppt開課目的：

介紹設(shè)計(jì)與構(gòu)造程序設(shè)計(jì)語言編譯程序的原理與方法源程序編譯程序目標(biāo)程序連接可執(zhí)行程序預(yù)備知識(shí)：形式語言與自動(dòng)機(jī)、兩門以上的高級(jí)程序設(shè)計(jì)語言匯編語言數(shù)據(jù)結(jié)構(gòu)等How?4編輯ppt教學(xué)要求通過課程的學(xué)習(xí)和實(shí)驗(yàn)的完成，

應(yīng)該清楚的理解一個(gè)編譯程序是如何工作的；

如果在以后遇到了任何一個(gè)程序設(shè)計(jì)語言，應(yīng)該知道如何實(shí)現(xiàn)這個(gè)語言的多數(shù)機(jī)制；

應(yīng)具有一定的使用編譯構(gòu)造工具開發(fā)編譯程序的經(jīng)驗(yàn)；

會(huì)將所學(xué)的常用技術(shù)和算法應(yīng)用于類似的軟件的設(shè)計(jì)和實(shí)現(xiàn)中。5編輯ppt理論課內(nèi)容簡介：第一章：緒論第二章：編譯基礎(chǔ)(形式語言

、有窮自動(dòng)機(jī)等）第三章：詞法分析第四章：語法分析第五章：語法制導(dǎo)翻譯和中間代碼生成第七章：程序運(yùn)行時(shí)的存貯分配問題第八章：代碼優(yōu)化第九章：目標(biāo)代碼生成第六章：符號(hào)表6編輯ppt實(shí)驗(yàn)課內(nèi)容簡介：第一次課：詞法分析（4學(xué)時(shí)）第二次課：語法分析（4學(xué)時(shí)）第三次課：詞義分析、代碼生成（4學(xué)時(shí)）第四次課：小型C語言編譯器設(shè)計(jì)（4學(xué)時(shí)）詳細(xì)實(shí)驗(yàn)內(nèi)容請(qǐng)見實(shí)驗(yàn)要求和實(shí)驗(yàn)指導(dǎo)書7編輯ppt教材：《編譯原理》（第2版），張素琴、呂映芝、蔣維杜、戴桂蘭，清華大學(xué)出版社2004參考書：教材及主要參考書Compilers:Principles,Technigues,andToolsAlfredV.Aho,RaviSethi,JeffreyD.Ullman,Addison-Wesley,1986.譯著版：機(jī)械工業(yè)出版社，2003，李建中，姜守旭譯。(龍書）

中文名：編譯原理技術(shù)和工具M(jìn)odernCompilerImplementationinJava

ModernCompilerImplementationinCAndrewW.Appel，人民郵電出版社影印，2005（虎書）中文名：現(xiàn)代編譯原理

AdvancedCompilerDesignandImplementation

StevenS.Muchnick,1997.機(jī)械工業(yè)出版社影印，2003（鯨書）

中文名：高級(jí)編譯器設(shè)計(jì)與實(shí)現(xiàn)8編輯ppt內(nèi)地陳火旺（國防科大版）

陳意云（中國科技大學(xué)版）

王生原等（人民郵電版）

王生原等（清華大學(xué)第三版）主要參考書編輯ppt第一章緒論編譯器就是一個(gè)程序，它讀入用某種語言編寫的源程序，并翻譯成一個(gè)與之等價(jià)的另一種語言編寫的源程序。編譯器源程序目標(biāo)程序錯(cuò)誤信息Fortran、Pascal、Java、C…..另一種程序設(shè)計(jì)語言、匯編語言、機(jī)器語言1.1什么是編譯程序10編輯ppt什么是編譯程序

編譯程序通常是從較高級(jí)語言的程序翻譯至較低級(jí)語言的程序，如C代碼匯編代碼aCcompilerC++代碼匯編代碼aC++compilerC++代碼C代碼anotherC++compilerJava代碼Bytecode代碼aJavacompiler編輯ppt1.2編譯過程概述編譯程序的工作，從輸入源程序開始，到輸出目標(biāo)程序結(jié)束，與自然語言之間的翻譯有很多相似之處。一段英文翻譯成中文，需經(jīng)下列步驟：識(shí)別出句子中的單詞分析句子的語法結(jié)構(gòu)根據(jù)句子的含義進(jìn)行初步分析對(duì)譯文進(jìn)行修飾寫出最后的譯文編譯程序詞法分析代碼優(yōu)化語法分析語義分析及中間代碼生成目標(biāo)代碼生成構(gòu)成編譯程序各個(gè)階段Iamateacher.12編輯ppt編譯器的各個(gè)階段：編譯器是分階段執(zhí)行的。每個(gè)階段將源程序從一種表示轉(zhuǎn)換成另一種表示源程序詞法分析器錯(cuò)誤處理器符號(hào)管理表語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器編譯的各個(gè)階段13編輯ppt各分析階段隨著編譯器各個(gè)階段的進(jìn)展，源程序的內(nèi)部表示不斷地發(fā)生變化。以a=b+c*d為例1。詞法分析讀入源程序完成的任務(wù)：識(shí)別出單詞：a、=、b、+、c、*、d并用記號(hào)方式表示識(shí)別出的單詞關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、算符和界符例：25表示a、b、c、d；36：＝；３2：＋；31：*記號(hào)表示邏輯上相關(guān)的字符序列，常用整數(shù)來表示上述單詞表示為：(25,a),(36,=),(25,b),(32,+),(25,c),(31,*),(25,d)14編輯ppt程序文本Ifx=ythenz:=1elsez:=2;經(jīng)詞法分析，變成一個(gè)個(gè)單詞if,x,=,y,then,z,:=,1,else,z,:=,2,;語言的單詞符號(hào)是由詞法規(guī)則所確定的。詞法規(guī)則規(guī)定了字母表中哪樣的字符串是一個(gè)單詞符號(hào)。又例，

編輯ppt從左至右掃描字符流的源程序、分解構(gòu)成源程序的字符串，識(shí)別出(拼)一個(gè)個(gè)的單詞（符號(hào)）單詞符號(hào)是語言中具有獨(dú)立意義的最基本結(jié)構(gòu)。多數(shù)程序語言中，單詞符號(hào)一般包括—各類型的常數(shù)、保留字、標(biāo)識(shí)符、運(yùn)算符、界符等等。

詞法分析—第一步識(shí)別單詞編輯ppt

position:=initial+rate*60;

單詞類型 單詞值標(biāo)識(shí)符1(id1) position算符(賦值) :=標(biāo)識(shí)符2(id2) initial算符(加) +標(biāo)識(shí)符3(id3) rate算符(乘) *整數(shù) 60分號(hào) ；詞法分析編輯ppt語法分析在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號(hào)串組成各類語法單位.具體的說，語法分析是在單詞流的基礎(chǔ)上建立一個(gè)層次結(jié)構(gòu)-----建立語法樹賦值語句標(biāo)識(shí)符=表達(dá)式id1表達(dá)式標(biāo)識(shí)符id2+表達(dá)式表達(dá)式*標(biāo)識(shí)符id3表達(dá)式

整數(shù)6018編輯ppt語法分析舉例id1:=id2+id3*60;（Pascal）語法規(guī)則<賦值語句>::=<標(biāo)識(shí)符>“:=”<表達(dá)式><表達(dá)式>::=<表達(dá)式>“+”<表達(dá)式><表達(dá)式>::=<表達(dá)式>“*”<表達(dá)式><表達(dá)式>::=“(”<表達(dá)式>“)”<表達(dá)式>::=<標(biāo)識(shí)符><表達(dá)式>::=<整數(shù)><表達(dá)式>::=<實(shí)數(shù)>編輯ppt

賦值語句標(biāo)識(shí)符表達(dá)式表達(dá)式+表達(dá)式表達(dá)式標(biāo)識(shí)符整數(shù)標(biāo)識(shí)符:=表達(dá)式*編輯pptid1:=id2+id3*60 :=+60*id1id2id3編輯ppt語義分析階段語義分析利用語法分析階段確定的層次結(jié)構(gòu)來識(shí)別表達(dá)式和語句中的操作信息及類型信息=+ab*cdtemp1=c*dtemp2=b+temp1temp1temp2a=temp222編輯ppt語義分析

句子的結(jié)構(gòu)理解了，撲捉它的“含義”如：杰克說杰瑞把他的作業(yè)落在了家里?！八摹笔钦l的？又：杰克說杰克把他的作業(yè)落在了家里。幾個(gè)杰克？編輯ppt杰克把她的作業(yè)落在了家里。（杰克是男生）“杰克”和“她的”不一致?！敖芸恕焙汀八摹辈牌ヅ湔Z義分析編輯ppt中間代碼生成階段本階段將產(chǎn)生源程序的一個(gè)顯式中間表示這種中間表示可以看成是某種抽象的程序，通常是與平臺(tái)無關(guān)的其重要性質(zhì)：1.易于產(chǎn)生

2.易于翻譯成目標(biāo)程序下面是用三地址碼（四元式）表示的例子：temp1=c*dtemp2=b+temp1a=temp2（*,c,d,tempt1)(+,b,tempt1,tempt2)(=,tempt2,,a)25編輯ppt

id1:=id2+id3*60(1) (inttoreal, 60, ,t1 )(2) (* , id3, t1, t2 )(3) (+ , id2, t2, t3 )(4) (:= , t3, ,id1 )編輯ppt代碼優(yōu)化階段對(duì)代碼進(jìn)行變換以使得編譯產(chǎn)生的目標(biāo)代碼更高效（執(zhí)行速度更快）。對(duì)上面中間代碼進(jìn)行優(yōu)化處理后，產(chǎn)生如下的代碼：temp1=c*da=b+temp1temp1=c*dtemp2=b+temp1a=temp227編輯ppt如下程序

語法分析結(jié)果j=2*i+1;

if(j>=n)

j=2*i+3;

returna[j];

t1=2*i

t2=t1+1

j=t2

t3=j<n

ift3gotoL0

t4=2*i

t5=t4+3

j=t5

L0: t6=a[j]

returnt6編輯ppt

t1=2*i

t2=t1+1

j=t2

t3=j<n

ift3gotoL0

t4=2*i

t5=t4+3

j=t5

L0: t6=a[j]

returnt6 t1=2*i

j=t1+1

t3=j<n

ift3gotoL0

j=t1+3

L0: t6=a[j]

returnt6代碼優(yōu)化編輯ppt代碼優(yōu)化

id1:=id2+id3*60(1) (inttoreal 60 - t1 )(2) (* id3 t1 t2 )(3) (+ id2 t2 t3 )(4) (:= t3 - id1 )

變換（1）(* id3 60.0 t1 )(2）（+ id2 t1 id1 )編輯ppt代碼生成階段生成目標(biāo)機(jī)機(jī)器代碼或匯編代碼(* , id3 60.0 t1 )(+ , id2 t1 id1 )movf id3,R2mulf #60.0,R2movf id2,R1addf R2,R1movf R1,id131編輯pptExample:ainR0,iinR1,ninR2t1=2*i

j=t1+1

t3=j<n

ift3gotoL0

j=t1+3

L0: t6=a[j]

returnt6 sllR1,1,R1

addR1,1,J

cmpJ,R2

blt.LL3

addR1,3,J

.LL3:ld[R0+J],

Rt

retr代碼生成編輯ppt記錄源程序中使用的標(biāo)識(shí)符收集每個(gè)標(biāo)識(shí)符的各種屬性信息普通變量：類型、作用域、分配存儲(chǔ)信息函數(shù)或過程：參數(shù)個(gè)數(shù)、類型、傳遞方法

返回值類型符號(hào)表管理(登錄，查找）1.3符號(hào)表編輯ppt符號(hào)表管理inta,b;floate,fcharch1,ch2;為什么要先說明?

定義了變量的類型，也就規(guī)定了變量在內(nèi)存中的存放形式，在其上所能進(jìn)行的運(yùn)算解決符號(hào)地址到存貯地址上的映射34編輯ppt

編譯器的一個(gè)基本功能是記錄源程序中使用的標(biāo)識(shí)符并將它們記載到符號(hào)表中。符號(hào)表是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每個(gè)標(biāo)識(shí)符在符號(hào)表中都有一條記錄名字記號(hào)類型種屬……addrid1(25)id2(25)ba例：inta,b;int簡變04

并收集與每個(gè)標(biāo)識(shí)符相關(guān)的各種屬性信息，int簡變35編輯ppt在編譯的各個(gè)階段都會(huì)發(fā)現(xiàn)源程序中的錯(cuò)誤，1.4錯(cuò)誤檢測(cè)與報(bào)告為了使編譯器能繼續(xù)運(yùn)行，以檢測(cè)出源程序中更多的錯(cuò)誤，在檢測(cè)到錯(cuò)誤后，必須以合適的方式進(jìn)行錯(cuò)誤處理。error36編輯ppt小結(jié)：編譯器的各個(gè)階段源程序詞法分析器錯(cuò)誤處理器符號(hào)管理表語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器37編輯ppt編譯的前端和后端

前端包括詞法分析、語法分析、語義分析，以及相關(guān)的錯(cuò)誤處理和符號(hào)表的建立

前端依賴于源程序并在很大程度上獨(dú)立于目標(biāo)機(jī)器。38編輯ppt

后端主要包括代碼優(yōu)化、代碼生成和相關(guān)錯(cuò)誤處理。

后端依賴于目標(biāo)機(jī)器。

后端處理對(duì)象是由前端產(chǎn)生的結(jié)果，即中間代碼

前端生成與平臺(tái)無關(guān)的字節(jié)碼

后端是由與平臺(tái)有關(guān)的解釋器對(duì)所生成的字節(jié)碼文件進(jìn)行解釋執(zhí)行Java語言的編譯采用的是前端后端方式。39編輯ppt編譯程序的組織

編譯程序的遍（Passes/Phases）

對(duì)一種代碼形式從頭到尾掃描一遍將一個(gè)代碼空間變換到另一個(gè)代碼空間

代碼空間=代碼+符號(hào)表+其他有用信息

編譯程序的組織取決于各遍的組織

單遍編譯程序，多遍編譯程序多個(gè)遍之間有邏輯上的先后關(guān)系多個(gè)遍的實(shí)現(xiàn)可采用順序結(jié)構(gòu)或并發(fā)結(jié)構(gòu)（后者不常用）編輯ppt編譯程序的組織

例：一個(gè)以語法、語義分析程序?yàn)橹行牡膯伪榫幾g程序組織sourceprogramtargetprogram語法、語義分析程序詞法分析程序代碼生成程序編輯ppt編譯程序的伙伴程序

解釋程序（Interpreter）

不產(chǎn)生目標(biāo)程序文件不區(qū)別翻譯階段和執(zhí)行階段翻譯源程序的每條語句后直接執(zhí)行

程序執(zhí)行期間一直有解釋程序守候常用于實(shí)現(xiàn)虛擬機(jī)

比較編譯程序和解釋程序源程序編譯程序目標(biāo)程序輸入目標(biāo)程序輸出解釋程序輸出輸入源程序編輯ppt