[1]蔣立源、康慕寧.《編譯原理》.西北工業(yè)大學(xué)出版社。[2]（美）KennethC.Louden著，馮博琴，馮嵐等譯。《編譯原理及實(shí)踐》.機(jī)械工業(yè)出版社[3]金成植.《編譯程序構(gòu)造原理和實(shí)現(xiàn)技術(shù)》.高等教育出版社，2000.[4]張幸兒.《編譯原理編譯程序構(gòu)造與實(shí)踐》.機(jī)械工業(yè)出版社，2008.[5]陳火旺等.《程序設(shè)計(jì)語(yǔ)言編譯原理》.國(guó)防工業(yè)出版社，2000.編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章網(wǎng)站資源：[1]清華同方編譯原理在線學(xué)習(xí)網(wǎng)站[2]編譯原理百度貼吧[3]

西北工業(yè)大學(xué)編譯原理網(wǎng)絡(luò)課程[4]

國(guó)防科技大學(xué)編譯原理網(wǎng)絡(luò)課程編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章第一章 緒論1.1編譯過(guò)程概述1.2編譯程序的邏輯結(jié)構(gòu)1.3編譯程序的組織編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章第一章 緒論程序設(shè)計(jì)語(yǔ)言分低級(jí)語(yǔ)言和高級(jí)語(yǔ)言兩類。低級(jí)語(yǔ)言:機(jī)器語(yǔ)言、匯編語(yǔ)言及其它面向機(jī)器的程序設(shè)計(jì)語(yǔ)言；其特點(diǎn)為對(duì)計(jì)算機(jī)的依賴性強(qiáng)、直觀性差、編寫程序的工作量大，對(duì)程序設(shè)計(jì)人員要求較高。高級(jí)語(yǔ)言：有幾百種之多，常用的有BASIC、FORTRAN、PASCAL、C、JAVA等，高級(jí)語(yǔ)言在算法描述能力、編寫和調(diào)試效率上均比低級(jí)語(yǔ)言優(yōu)越。編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章但高級(jí)語(yǔ)言與機(jī)器之間有一“鴻溝”：機(jī)器不能理解高級(jí)語(yǔ)言！因此，要在計(jì)算機(jī)上實(shí)現(xiàn)高級(jí)語(yǔ)言，需使該語(yǔ)言能讓計(jì)算機(jī)所理解。方法：對(duì)程序進(jìn)行翻譯或進(jìn)行解釋。翻譯：在計(jì)算機(jī)中放置一能由計(jì)算機(jī)直接執(zhí)行的翻譯程序，它將某程序設(shè)計(jì)語(yǔ)言（源語(yǔ)言）所編寫的程序（源程序）作為加工對(duì)象，將其翻譯成為與之等價(jià)的另一種語(yǔ)言（目標(biāo)語(yǔ)言）的程序（目標(biāo)程序）。編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章源程序P目標(biāo)程序P’編譯程序C計(jì)算機(jī)A編譯階段運(yùn)行結(jié)果S原始數(shù)據(jù)D運(yùn)行程序計(jì)算機(jī)B運(yùn)行階段按編譯方式執(zhí)行一個(gè)高級(jí)語(yǔ)言程序的主要步驟

編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章可見(jiàn)，計(jì)算機(jī)執(zhí)行某高級(jí)語(yǔ)言程序，需經(jīng)兩個(gè)階段，即編譯階段和運(yùn)行階段。在執(zhí)行時(shí)，一般應(yīng)有一些輔助子程序配合。如：數(shù)據(jù)格式轉(zhuǎn)換子程序、標(biāo)準(zhǔn)函數(shù)、動(dòng)態(tài)存儲(chǔ)分配子程序等等，由它們構(gòu)成的子程序庫(kù)稱為運(yùn)行系統(tǒng)。編譯系統(tǒng)=編譯程序+運(yùn)行系統(tǒng)編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章編譯程序與解釋程序高級(jí)語(yǔ)言程序也可通過(guò)解釋程序來(lái)執(zhí)行。解釋程序：以源程序?yàn)檩斎耄趫?zhí)行過(guò)程中不再產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行。解釋程序運(yùn)行效率不高。目前，純粹的解釋程序已不多見(jiàn)，通常是將編譯和解釋作某種程度的結(jié)合。編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章本課程的目的編譯程序是現(xiàn)今任何計(jì)算機(jī)系統(tǒng)的最重要的系統(tǒng)程序。本課程的目的，在于向大家介紹設(shè)計(jì)和構(gòu)造編譯程序的基本原理和基本方法，其中許多方法也適用于構(gòu)造解釋程序或匯編程序。編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章1.1編譯過(guò)程概述翻譯外文書刊與編譯工作比較編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章編譯程序的構(gòu)成編譯程序主要由八個(gè)部分構(gòu)成：1.詞法分析程序（掃描器scanner）2.語(yǔ)法分析程序（分析器parser）3.語(yǔ)義分析程序4.中間代碼生成程序5.代碼優(yōu)化程序6.目標(biāo)代碼生成程序7.錯(cuò)誤檢查和處理程序8.各種信息表格的管理程序編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章1.2編譯程序的邏輯結(jié)構(gòu)詞法分析程序語(yǔ)法分析程序語(yǔ)義分析程序中間代碼生成代碼優(yōu)化程序目標(biāo)代碼生成信息表管理程序錯(cuò)誤檢查和處理程序源程序目標(biāo)代碼編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章一個(gè)微型PASCAL語(yǔ)言的定義為了便于說(shuō)明，引入一個(gè)微型PASCAL語(yǔ)言（PASCAL/M）的定義。它只有如下四種語(yǔ)句：1）PROGRAM語(yǔ)句；2）說(shuō)明語(yǔ)句；3）BEGIN-END語(yǔ)句；4）賦值語(yǔ)句；每個(gè)PASCAL/M語(yǔ)句都以PROGRAM語(yǔ)句開頭，后跟說(shuō)明語(yǔ)句，再跟以一個(gè)BEGIN-END語(yǔ)句，在其內(nèi)部可以有若干賦值語(yǔ)句。編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章程序1-1一個(gè)PASCAL源程序sourcePROGRAMsource;

{Thislittlesourceprogramisusedtoillustratecompilingprocedure}VAR

x,y,z:integer;

a:integer;BEGIN

{Thisprogramhasonly4statement}x:=23+5;z:=xDIV-3;y:=z+18*3;a:=x+(y-2)DIV4END.編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章1.2.1詞法分析程序（掃描器）詞法分析程序的任務(wù)是：1）識(shí)別出源程序的各個(gè)基本語(yǔ)法單位（單詞或語(yǔ)法符號(hào)）；2）刪除無(wú)用的空白字符及其它與輸入介質(zhì)相關(guān)的非實(shí)質(zhì)性字符（空格、回車等）；3）刪除注釋；4）進(jìn)行詞法檢查，報(bào)告所發(fā)現(xiàn)的錯(cuò)誤。編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章掃描器輸出以單詞為單位的單詞流。例如，以特殊符號(hào)“#”分隔的單詞流：

#

PROGRAM#source#;#VAR#x#,#y#,#z#:#integer#;#a#:#integer#;#BEGIN#x#:=#23#+#5#;#z#:=#x#DIV#-#3#;#y#:=#z#+#18#*#3#;#a#:=#x#+#(#y#-#2#)#DIV#4#;#END#.#編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章單詞流的內(nèi)部表示注意，前面的單詞流形式只是我們?yōu)檎f(shuō)明原理便于閱讀而假定的形式。為了讓計(jì)算機(jī)能夠方便地識(shí)別和使用，在實(shí)際中的常用方法是將單詞計(jì)算機(jī)內(nèi)部表示為一個(gè)有序?qū)?Class,Value)。Class為一整型數(shù)，用于標(biāo)識(shí)該單詞的類別；Value用于存放單詞的值。編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章單詞流的內(nèi)部表示例如對(duì)于source程序，可將其單詞分為四類：

(1)保留字

(2)專用符號(hào)

(3)標(biāo)識(shí)符

(4)整數(shù)

這樣，source程序相應(yīng)的單詞流為：

(1,’PAROGRAM’)(3,’source’)(2,’;’)(1,’VAR’)(...)……(2,’;’)(1,’END’)(2,’.’)編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章圖3-1文法G[<無(wú)符號(hào)數(shù)>]的狀態(tài)轉(zhuǎn)換圖

045326ddddd.E+|－Edd.1編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章b|a123abb(a)M＇的狀態(tài)矩陣(b)M＇的狀態(tài)轉(zhuǎn)換圖

f＇ab

[S0][S0S1][S1][S1][][S0S1][S0S1][S0S1][S0S1]

編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章1.2.2語(yǔ)法分析程序（分析器）語(yǔ)法分析程序以詞法分析程序輸出的單詞流為輸入，分析源程序的結(jié)構(gòu)，判斷它是否為相應(yīng)程序設(shè)計(jì)語(yǔ)言的合法程序。方法：試圖為源程序構(gòu)造一個(gè)語(yǔ)法樹。分析工作是在相應(yīng)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法規(guī)則指導(dǎo)下進(jìn)行的。語(yǔ)法規(guī)則描述了該語(yǔ)言的各種語(yǔ)法成份的組成結(jié)構(gòu)。所謂語(yǔ)法樹只是邏輯概念上的，并不是在機(jī)器內(nèi)真要存儲(chǔ)一個(gè)樹形結(jié)構(gòu)。編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章CB1thenCifB2thenCS1ifelseCS2CB1thenCifB2thenCS1ifelseCS2圖2-3復(fù)合if語(yǔ)句的兩棵不同的語(yǔ)法樹

編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章(a)句子i+i*i的語(yǔ)法樹(b)句型F+i*i

的語(yǔ)法樹E

E+TT*FiFiTFiE

E+TT*FiFiTF編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章(c)句子F+F*F的語(yǔ)法樹(d)句型F+T的語(yǔ)法樹E

E+TT*FFTFE

E+TTF編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章I0:S’→·SS→·CbBAC→·aI1:S’→S·SI3:C→a·aI2:S→C·bBACI4:S→Cb·BAB→·CB→·DbC→·aD→·abI5:S→CbB·AA→·AabA→·abI6:B→C·BCI8:C→a·D→a·aI7:B→D·bI9:B→Db·DbI11:A→a·bI12:A→ab·abI10:S→CbBA·A→A·abAI13:A→Aa·bI14:A→Aab·ab圖5-13識(shí)別G[S]全部可歸前綴的DFA編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章1.2.3語(yǔ)義分析程序程序設(shè)計(jì)語(yǔ)言具有語(yǔ)法和語(yǔ)義兩個(gè)特征。語(yǔ)法特征描述各成份的形式或結(jié)構(gòu)；語(yǔ)義特征描述各語(yǔ)法成份的含義與功能，即規(guī)定它們的屬性或在執(zhí)行時(shí)應(yīng)進(jìn)行的運(yùn)算或操作。因此，只有進(jìn)行了語(yǔ)義分析，才能讓計(jì)算機(jī)知道，應(yīng)進(jìn)行何操作或運(yùn)算。編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章1.2.4

中間代碼生成常見(jiàn)的中間代碼有：逆波蘭式、三元式、四元式及樹形結(jié)構(gòu)等。例如，與source程序中的第四條賦值語(yǔ)句相應(yīng)的逆波蘭式可寫成：

axy2-div+:=與source程序相應(yīng)的四元式表示為：(prologue,’source’)(add,’23’,’5’,T)(store,T,,’x’)(div,’x’,’-3’,T)(store,T,,’z’)(mult,‘18’,’3’,T)(add,’z’,T,T)(store,T,,’y’)(sub,’y’,’2’,T)(div,T,’4’,T)(add,’x’,T,T)(store,T,,’a’)(epilogue)編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章賦值語(yǔ)句x:=a+b*c的語(yǔ)法制導(dǎo)翻譯過(guò)程

+EE.PLACE=T1

EE.PLACE=aEE.PLACE=T2*EE.PLACE=cEE.PLACE=bii.PLACE=bii.PLACE=aii.PLACE=cVV.PLACE=xii.PLACE=x:=AS(1)(*,b,c,T1)(2)(+,a,T1,T2)(3)(:=,T2,,x)編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章1.2.5代碼優(yōu)化程序代碼優(yōu)化的目的是生成質(zhì)量較高的目標(biāo)代碼。衡量質(zhì)量的標(biāo)準(zhǔn)：空間指標(biāo)和時(shí)間指標(biāo)。優(yōu)化方法分類：與機(jī)器有關(guān)和無(wú)關(guān)兩類。優(yōu)化指標(biāo)有時(shí)是相互矛盾的，應(yīng)根據(jù)具體情況進(jìn)行取舍和側(cè)重。source程序優(yōu)化后結(jié)果：編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章(prologue,’source’)(store,28,,’x’)(div,’x’,’-3’,T)(store,T,,’z’)(add,’z’,54,T)(store,T,,’y’)(sub,’y’,’2’,T)(div,T,’4’,T)(add,’x’,T,T)(store,T,,’a’)(epilogue)(prologue,’source’)(add,’23’,’5’,T)(store,T,,’x’)(div,’x’,’-3’,T)(store,T,,’z’)(mult,‘18’,’3’,T)(add,’z’,T,T)(store,T,,’y’)(sub,’y’,’2’,T)(div,T,’4’,T)(add,’x’,T,T)(store,T,,’a’)(epilogue)編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章1.2.6目標(biāo)代碼生成程序任務(wù)：將中間代碼翻譯成為目標(biāo)程序。首先確定源語(yǔ)言各種語(yǔ)法成份的目標(biāo)代碼結(jié)構(gòu)；再根據(jù)需要制定中間代碼到目標(biāo)代碼的翻譯策略。這部分程序?qū)唧w機(jī)器的依賴性很強(qiáng)，需具體情況具體分析。編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章1.2.6目標(biāo)代碼生成程序通常，目標(biāo)代碼的三種形式：（1）具有絕對(duì)地址的機(jī)器指令代碼；（2）匯編語(yǔ)言形式的目標(biāo)程序；（3）模塊結(jié)構(gòu)的機(jī)器指令（浮動(dòng)地址）。Source對(duì)應(yīng)的80386匯編程序見(jiàn)書中P9編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章1.2.7錯(cuò)誤檢查和處理程序程序中出現(xiàn)錯(cuò)誤是難免的。一完善的編譯程序應(yīng)具有很強(qiáng)的查錯(cuò)能力，并能準(zhǔn)確地報(bào)告源程序中錯(cuò)誤的種類及位置。除報(bào)錯(cuò)外，編譯程序還可生成一些另外的注釋信息，它有助于程序設(shè)計(jì)人員調(diào)試程序。常見(jiàn)的輔助手段根據(jù)請(qǐng)求輸出“對(duì)照?qǐng)D”和各變量的值。Source程序的對(duì)照?qǐng)D，見(jiàn)P10表1-2編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章1.2.8信息表管理程序編譯過(guò)程中，需經(jīng)常收集、記錄或查詢程序中所出現(xiàn)的各種量的有關(guān)屬性（信息）。為此，編譯程序需要建立一批不同用途的表格（常數(shù)表、變量表、關(guān)鍵字表等）。除此之外，根據(jù)不同的分析方法，編譯程序還保持一些專用的表格（LL分析表、LR分析表、狀態(tài)矩陣等）。合理地組織各種表格，恰當(dāng)?shù)剡x用相應(yīng)的造表和查表算法是提高編譯程序工作效率的有效途徑。編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章狀態(tài)轉(zhuǎn)換矩陣

B11B12…B1mB21B22…B2m::::::Bn1Bn2…Bnm

a1a2…amS1S2::SnB=編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章產(chǎn)生式FIRSTFOLLOWE→TE′{(,i}{),#}E′→+TE′E′→ε{+}{ε}{),#}T→FT′{(,i}{+,),#}T′→*FT′T′→ε{*}{ε}{+,),#}F→(E)F→i{(}{i}{+,*,),#}FIRST集和FOLLOW集

編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章LL(1)分析表

i+*()#EE→TE

E→TE

E

E

→+TE

E

→εE

→εTT→FT

T→FT

T

T

→εT

→*FT

T

→εT

→εFF→iF→(E)編譯原理-西北工業(yè)大學(xué)第1節(jié)課第一章LR(1)分析表

狀態(tài)ACTIONGOTOab#SABCD0123456789101