編譯原理課件

編譯方法第一章引論江西財(cái)經(jīng)大學(xué)信息管理學(xué)院介紹程序設(shè)計(jì)語(yǔ)言編譯程序構(gòu)造的基本原理和基本實(shí)現(xiàn)技術(shù)領(lǐng)悟計(jì)算機(jī)理論的精髓，從實(shí)現(xiàn)的角度重新審視軟件的開(kāi)發(fā)江西財(cái)經(jīng)大學(xué)信息管理學(xué)院編譯理論與方法計(jì)算機(jī)科學(xué)與技術(shù)中理論和實(shí)踐相結(jié)合的最好典范

ACM圖靈獎(jiǎng)，授予在計(jì)算機(jī)技術(shù)領(lǐng)域作出突出貢獻(xiàn)的科學(xué)家自1966年以來(lái)（截止2014年）的所有圖靈獎(jiǎng)獲得者中，有近1/3的科學(xué)家是因?yàn)樵诔绦蛟O(shè)計(jì)語(yǔ)言和編譯方面的成就而獲得該項(xiàng)獎(jiǎng)勵(lì)程序設(shè)計(jì)語(yǔ)言和編譯的發(fā)展集中體現(xiàn)了計(jì)算機(jī)科學(xué)發(fā)展的重要成果與精華計(jì)算機(jī)應(yīng)用能發(fā)展到今天，編譯技術(shù)的發(fā)展有著極其重要的、不可替代的作用江西財(cái)經(jīng)大學(xué)信息管理學(xué)院整個(gè)20世紀(jì)50年代，編譯程序的編寫一直被認(rèn)為是一個(gè)難題，第一個(gè)FORTRAN語(yǔ)言(1954年)編譯程序整整花了18年才得以實(shí)現(xiàn)。江西財(cái)經(jīng)大學(xué)信息管理學(xué)院源語(yǔ)言程序目標(biāo)語(yǔ)言程序翻譯程序翻譯一、什么是編譯程序翻譯程序把某一種語(yǔ)言程序(稱為源語(yǔ)言程序)等價(jià)地轉(zhuǎn)換成另一種語(yǔ)言程序(稱為目標(biāo)語(yǔ)言程序)的程序江西財(cái)經(jīng)大學(xué)信息管理學(xué)院高級(jí)語(yǔ)言程序機(jī)器語(yǔ)言程序結(jié)果編譯程序翻譯運(yùn)行一、什么是編譯程序編譯程序(compiler)

把某一種高級(jí)語(yǔ)言程序等價(jià)地轉(zhuǎn)換成另一種低級(jí)語(yǔ)言程序(如匯編語(yǔ)言或機(jī)器語(yǔ)言程序)的程序診斷編譯程序 優(yōu)化編譯程序交叉編譯程序 可變目標(biāo)編譯程序江西財(cái)經(jīng)大學(xué)信息管理學(xué)院一、什么是編譯程序解釋程序把源語(yǔ)言寫的源程序作為輸入，但不產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行源程序本身源程序結(jié)果解釋程序解釋執(zhí)行江西財(cái)經(jīng)大學(xué)信息管理學(xué)院編譯程序vs.解釋程序編譯解釋江西財(cái)經(jīng)大學(xué)信息管理學(xué)院兩種翻譯方式的比較解釋方式和編譯方式的主要區(qū)別是：目標(biāo)代碼的執(zhí)行方式不同，基本原理和方法沒(méi)有本質(zhì)上的區(qū)別。1）解釋方式的優(yōu)點(diǎn)（編譯方式的缺點(diǎn)）提供一種直接的交互調(diào)試功能，易獲得較好的動(dòng)態(tài)調(diào)試效果。使用變量可不預(yù)先定義。變量性質(zhì)可動(dòng)態(tài)修改。2）解釋方式的缺點(diǎn)（編譯方式的優(yōu)點(diǎn)）在執(zhí)行時(shí)需動(dòng)態(tài)地對(duì)程序進(jìn)行分析翻譯，開(kāi)銷大，其執(zhí)行速度相當(dāng)于編譯方式的1/10至1/100。解釋方式占用內(nèi)存大。對(duì)任何一種高級(jí)語(yǔ)言，既可采用編譯方式，也可采用解釋方式，包括匯編語(yǔ)言在內(nèi)（MASM方式和DEBUG方式）。江西財(cái)經(jīng)大學(xué)信息管理學(xué)院在編譯的每個(gè)階段都有可能發(fā)現(xiàn)錯(cuò)誤，最簡(jiǎn)單的處理是：終止編譯程序工作，指出錯(cuò)誤的地點(diǎn)和類型。目前有些高級(jí)語(yǔ)言的翻譯程序同時(shí)具有解釋和編譯兩種功能，在調(diào)試時(shí)采用解釋方式，調(diào)試過(guò)程中若發(fā)現(xiàn)錯(cuò)誤，翻譯程序立即暫停工作，并用特殊記號(hào)指示當(dāng)前錯(cuò)誤的位置；當(dāng)調(diào)試完成后，可利用翻譯程序的編譯功能，將源程序翻譯成機(jī)器碼程序。機(jī)器碼程序通常存放在擴(kuò)展名為.exe的文件中，它可在操作系統(tǒng)環(huán)境下脫離翻譯程序直接運(yùn)行。江西財(cái)經(jīng)大學(xué)信息管理學(xué)院二、編譯過(guò)程把英文翻譯為中文

識(shí)別出句子中的一個(gè)個(gè)單詞；分析句子的語(yǔ)法結(jié)構(gòu)；根據(jù)句子的含義進(jìn)行初步翻譯；對(duì)譯文進(jìn)行修飾；寫出最后的譯文。詞法分析語(yǔ)法分析中間代碼產(chǎn)生優(yōu)化目標(biāo)代碼產(chǎn)生江西財(cái)經(jīng)大學(xué)信息管理學(xué)院二、編譯過(guò)程編譯程序的工作一般分為五個(gè)階段:詞法分析語(yǔ)法分析中間代碼產(chǎn)生（語(yǔ)義分析）優(yōu)化目標(biāo)代碼產(chǎn)生江西財(cái)經(jīng)大學(xué)信息管理學(xué)院1.詞法分析任務(wù):輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)別出一個(gè)個(gè)單詞符號(hào)。依循的原則：構(gòu)詞規(guī)則描述工具：有限自動(dòng)機(jī)FORi:=1TO100DO

保留字標(biāo)識(shí)符等符整常數(shù)保留字整常數(shù)保留字江西財(cái)經(jīng)大學(xué)信息管理學(xué)院2.語(yǔ)法分析任務(wù):在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則把單詞符號(hào)串分解成各類語(yǔ)法單位。依循的原則：語(yǔ)法規(guī)則描述工具：上下文無(wú)關(guān)文法Z:=X+0.618*Y

算術(shù)表達(dá)式，賦值語(yǔ)句江西財(cái)經(jīng)大學(xué)信息管理學(xué)院3.中間代碼產(chǎn)生（語(yǔ)義分析）任務(wù):對(duì)各類不同語(yǔ)法范疇按語(yǔ)言的語(yǔ)義進(jìn)行初步翻譯。依循的原則：語(yǔ)義規(guī)則中間代碼:三元式、四元式、語(yǔ)法樹(shù)、后綴式等Z:=X+0.618*Y翻譯成四元式為

(1)*0.618YT1 (2)+XT1T2 (3):=T2_Z江西財(cái)經(jīng)大學(xué)信息管理學(xué)院4.優(yōu)化任務(wù)：對(duì)于前階段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段產(chǎn)生更高效的目標(biāo)代碼。依循的原則：程序的等價(jià)變換規(guī)則FORK:=1TO100DOBEGINX:=I+1;M:=I+10*K;N:=J+10*K;END江西財(cái)經(jīng)大學(xué)信息管理學(xué)院中間代碼（一）序號(hào) OPR OPN1 OPN2RESULT注釋 (1) := 1 KK:=1 (2) j< 100 K (10)if(100<K)goto(10)(3) + I 1 X X:=I+1 (4) * 10 K T1 T1:=10*K(5) + I T1 M M:=I+T1 (6) * 10 K T2 T2:=10*K(7) + J T2 N N:=J+T2 (8) + K 1 K K:=K+1 (9) j (2) goto(2)(10) 400次加法200次乘法江西財(cái)經(jīng)大學(xué)信息管理學(xué)院轉(zhuǎn)換后的等價(jià)代碼（二）序號(hào) OPR OPN1 OPN2 RESULT 注釋 (1) + I 1 X X:=I+1 (2) := I M M:=I (3) := J N N:=J (4) := 1 K K:=1 (5) j< 100 K (10) if(100<K)goto(10)(6) + M 10 M M:=M+10 (7) + N 10 N N:=N+10 (8) + K 1 K K:=K+1 (9) j (5) goto(5) (10) 301次加法江西財(cái)經(jīng)大學(xué)信息管理學(xué)院5.目標(biāo)代碼產(chǎn)生任務(wù):把中間代碼變換成特定機(jī)器上的目標(biāo)代碼。依賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令的含義目標(biāo)代碼三種形式:絕對(duì)指令代碼:可直接運(yùn)行可重新定位指令代碼:需要連接裝配匯編指令代碼:需要進(jìn)行匯編江西財(cái)經(jīng)大學(xué)信息管理學(xué)院模塊A…a模塊B…b模塊C…c模塊A…a模塊B…b模塊C…c模塊A…a模塊B…b模塊C…c江西財(cái)經(jīng)大學(xué)信息管理學(xué)院

例，表達(dá)式3*16+2值的實(shí)現(xiàn)（機(jī)器語(yǔ)言程序、匯編語(yǔ)言程序和C++語(yǔ)言程序表示）。22038210260261011000f000LoadR0,#3MulR0,#10LoadR1,#2AddR0,R1WriteR0Haltvoidmain(void){cout<<3*16+2;}注：十六進(jìn)制，10H表示16D

5.目標(biāo)代碼產(chǎn)生江西財(cái)經(jīng)大學(xué)信息管理學(xué)院三、編譯程序結(jié)構(gòu)1.編譯程序總框江西財(cái)經(jīng)大學(xué)信息管理學(xué)院四元式單詞符號(hào)語(yǔ)法單位四元式目標(biāo)代碼詞法分析器語(yǔ)法分析器語(yǔ)義分析與中間代碼生成器優(yōu)化段源程序表格管理出錯(cuò)處理目標(biāo)代碼生成器江西財(cái)經(jīng)大學(xué)信息管理學(xué)院2.表格和表格管理常見(jiàn)的表格:符號(hào)名表，常數(shù)表，標(biāo)號(hào)表，過(guò)程引用表。格式:名字信息江西財(cái)經(jīng)大學(xué)信息管理學(xué)院例:PASCAL程序段：PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.江西財(cái)經(jīng)大學(xué)信息管理學(xué)院PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.江西財(cái)經(jīng)大學(xué)信息管理學(xué)院PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.江西財(cái)經(jīng)大學(xué)信息管理學(xué)院PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.江西財(cái)經(jīng)大學(xué)信息管理學(xué)院PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.江西財(cái)經(jīng)大學(xué)信息管理學(xué)院江西財(cái)經(jīng)大學(xué)信息管理學(xué)院PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.江西財(cái)經(jīng)大學(xué)信息管理學(xué)院3.出錯(cuò)處理出錯(cuò)處理程序：發(fā)現(xiàn)源程序中的錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)告給用戶語(yǔ)法錯(cuò)誤語(yǔ)義錯(cuò)誤江西財(cái)經(jīng)大學(xué)信息管理學(xué)院4.遍(pass)所謂"遍"，就是對(duì)源程序或源程序的中間表示從頭到尾掃描一次。階段與遍是不同的概念。一遍可以由若干段組成，一個(gè)階段也可以分若干遍來(lái)完成。江西財(cái)經(jīng)大學(xué)信息管理學(xué)院5.

編譯前端與后端編譯前端：與源語(yǔ)言有關(guān)，如詞法分析，語(yǔ)法分析，語(yǔ)義分析與中間代碼產(chǎn)生，與機(jī)器無(wú)關(guān)的優(yōu)化編譯后端：與目標(biāo)機(jī)有關(guān)，與目標(biāo)機(jī)有關(guān)的優(yōu)化，目標(biāo)代碼產(chǎn)生優(yōu)點(diǎn)：減少對(duì)內(nèi)存容量的要求，程序邏輯結(jié)構(gòu)清晰;優(yōu)化更充分，有利于移植。不足:編譯程序運(yùn)行的效率低源語(yǔ)言中間語(yǔ)言目標(biāo)語(yǔ)言前端后端江西財(cái)經(jīng)大學(xué)信息管理學(xué)院四、編譯程序與程序設(shè)計(jì)環(huán)境

程序設(shè)計(jì)環(huán)境編輯程序編譯程序連接程序調(diào)試工具集成化的程序設(shè)計(jì)環(huán)境江西財(cái)經(jīng)大學(xué)信息管理學(xué)院五、編譯程序生成以匯編語(yǔ)言和機(jī)器語(yǔ)言為工具優(yōu)點(diǎn):可以針對(duì)具體的機(jī)器，充分發(fā)揮計(jì)算機(jī)的系統(tǒng)功能。生成的程序效率高。缺點(diǎn):程序難讀、難寫、易出錯(cuò)、難維護(hù)、生產(chǎn)的效率低。江西財(cái)經(jīng)大學(xué)信息管理學(xué)院五、編譯程序生成高級(jí)語(yǔ)言書寫優(yōu)點(diǎn):程序易讀、易理解、容易維護(hù)、生產(chǎn)的效率高。缺點(diǎn):難以充分發(fā)揮計(jì)算機(jī)的系統(tǒng)功能，生成的程序效率低。江西財(cái)經(jīng)大學(xué)信息管理學(xué)院五、編譯程序生成高級(jí)語(yǔ)言書寫利用已有的某種語(yǔ)言的編譯程序?qū)崿F(xiàn)另一語(yǔ)言的編譯程序。L1語(yǔ)言A代碼P1:A代碼L2語(yǔ)言A代碼P2:L1語(yǔ)言L2語(yǔ)言A代碼P2:A代碼同一臺(tái)機(jī)器不同的語(yǔ)言江西財(cái)經(jīng)大學(xué)信息管理學(xué)院五、編譯程序生成

移植方法把一種機(jī)器上的編譯程序移植到另一種機(jī)器上。L語(yǔ)言A代碼P1:A代碼L語(yǔ)言B代碼P2:L語(yǔ)言L語(yǔ)言B代碼P2:A代碼L語(yǔ)言B代碼P2:L語(yǔ)言L語(yǔ)言B代碼P2:B代碼同一種語(yǔ)言不同的機(jī)器江西財(cái)經(jīng)大學(xué)信息管理學(xué)院L1+L2+...+Ln…L1+L2五、編譯程序生成自展技術(shù)L1江西財(cái)經(jīng)大學(xué)信息管理學(xué)院五、編譯程序生成編譯程序自動(dòng)產(chǎn)生編譯程序-編譯程序，編譯程序書寫系統(tǒng)LEX詞法分析程序產(chǎn)生器YACC語(yǔ)法分析程序產(chǎn)生器編譯程序自動(dòng)產(chǎn)生器L語(yǔ)言的語(yǔ)法描述語(yǔ)義描述目標(biāo)語(yǔ)言或機(jī)器描述L語(yǔ)言的編譯程序江西財(cái)經(jīng)大學(xué)信息管理學(xué)院六、關(guān)于學(xué)習(xí)編譯原理

構(gòu)造編譯程序的前提掌握源語(yǔ)言掌握目標(biāo)語(yǔ)言掌握編譯方法江西財(cái)經(jīng)大學(xué)信息管理學(xué)院六、關(guān)于學(xué)習(xí)編譯原理意義學(xué)習(xí)編譯程序構(gòu)造的原理、方法、技術(shù)更好地理解高級(jí)語(yǔ)言編譯的原理和方法有助于構(gòu)造一些實(shí)用的工具培養(yǎng)計(jì)算思維，提