《編譯原理》第1章 緒論

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

郵箱：

lsmei@2編輯ppt課程介紹兩門獨立的課程：理論（48學時）

實驗（16學時）考試成績組成

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

實驗：根據(jù)實驗報告和程序源代碼評分，實驗報告占40%,程序源代碼占60%。課程特點：難！3編輯ppt開課目的：

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

應該清楚的理解一個編譯程序是如何工作的；

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

應具有一定的使用編譯構造工具開發(fā)編譯程序的經驗；

會將所學的常用技術和算法應用于類似的軟件的設計和實現(xiàn)中。5編輯ppt理論課內容簡介：第一章：緒論第二章：編譯基礎(形式語言

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

中文名：編譯原理技術和工具ModernCompilerImplementationinJava

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

AdvancedCompilerDesignandImplementation

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

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

陳意云（中國科技大學版）

王生原等（人民郵電版）

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

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

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

詞法分析—第一步識別單詞編輯ppt

position:=initial+rate*60;

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

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

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

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

2.易于翻譯成目標程序下面是用三地址碼（四元式）表示的例子：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)化階段對代碼進行變換以使得編譯產生的目標代碼更高效（執(zhí)行速度更快）。對上面中間代碼進行優(yōu)化處理后，產生如下的代碼：temp1=c*da=b+temp1temp1=c*dtemp2=b+temp1a=temp227編輯ppt如下程序

語法分析結果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代碼生成階段生成目標機機器代碼或匯編代碼(* , 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記錄源程序中使用的標識符收集每個標識符的各種屬性信息普通變量：類型、作用域、分配存儲信息函數(shù)或過程：參數(shù)個數(shù)、類型、傳遞方法

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

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

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

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

前端包括詞法分析、語法分析、語義分析，以及相關的錯誤處理和符號表的建立

前端依賴于源程序并在很大程度上獨立于目標機器。38編輯ppt

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

后端依賴于目標機器。

后端處理對象是由前端產生的結果，即中間代碼

前端生成與平臺無關的字節(jié)碼

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

編譯程序的遍（Passes/Phases）

對一種代碼形式從頭到尾掃描一遍將一個代碼空間變換到另一個代碼空間

代碼空間=代碼+符號表+其他有用信息

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

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

例：一個以語法、語義分析程序為中心的單遍編譯程序組織sourceprogramtargetprogram語法、語義分析程序詞法分析程序代碼生成程序編輯ppt編譯程序的伙伴程序

解釋程序（Interpreter）

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

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

比較編譯程序和解釋程序源程序編譯程序目標程序輸入目標程序輸出解釋程序輸出輸入源程序編輯ppt