編譯原理第1章

《編譯原理第1章》由會(huì)員分享，可在線閱讀，更多相關(guān)《編譯原理第1章（38頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,編譯原理,程序設(shè)計(jì)語(yǔ)言,第一章 引論,1.1,什么叫編譯程序,1.2,編譯過(guò)程概述,1.3,編譯程序的結(jié)構(gòu),1.4,編譯程序與程序設(shè)計(jì)環(huán)境（略）,1.5,編譯程序的生成,1.,什么是編譯程序？,1.1,什么叫編譯程序,翻譯程序,：一種語(yǔ)言程序,-,-,另一種語(yǔ)言程序,源語(yǔ)言,目標(biāo)語(yǔ)言,編譯程序,：高級(jí)語(yǔ)言程序,-,-,低級(jí)語(yǔ)言程序,匯編程序,：匯編語(yǔ)言程序,-,-,機(jī)器語(yǔ)言程序,解釋程序,：源語(yǔ)言程序,-,-,邊解釋邊執(zhí)行,（,1,）編譯方式：先編譯后執(zhí)行。,（,2,）解釋方式：,以源程序作為輸入，但,不產(chǎn)

2、生目標(biāo)代碼,，而,是,邊解釋邊執(zhí)行,源程序本身。,2.,“,高級(jí)語(yǔ)言程序,”,的執(zhí)行方式,1.1,什么叫編譯程序,編譯和解釋的主要區(qū)別：,是否產(chǎn)生目標(biāo)代碼！,b:=3;,a:=b+3;,write a;,編譯程序,解釋程序,MOV#3.0 R1,MOV R1 b,MOV b R2,ADD R1 R2,MOV R1 a,直接將,6,輸出顯示,3.,“,編譯程序”在計(jì)算機(jī)系統(tǒng)中的位置較接近于“硬件”,1.1,什么叫編譯程序,4.,發(fā)展,20,世紀(jì),50,年代 第一個(gè)編譯程序,FORTRAN,編譯程序,目前：編譯原理與技術(shù)得到迅速發(fā)展，現(xiàn)已形成一套比較成熟的系統(tǒng)化的理論與方法，并開(kāi)發(fā)出了一些好的編譯

3、程序的實(shí)現(xiàn)語(yǔ)言、環(huán)境與工具。,當(dāng)時(shí)普遍認(rèn)為設(shè)計(jì)和實(shí)現(xiàn)編譯程序是一件十分困難、令人生畏的事情,1.1,什么叫編譯程序,編譯技術(shù)是計(jì)算機(jī)科學(xué)中發(fā)展最迅速、最成熟的一個(gè)重要分支，集中體現(xiàn)了計(jì)算機(jī)科學(xué)發(fā)展的重要成果與精華。,通過(guò)本課程的學(xué)習(xí)，一方面要理解、掌握編譯系統(tǒng)的結(jié)構(gòu)、工作流程以及編譯程序各組成部分的設(shè)計(jì)原理和實(shí)現(xiàn)技術(shù)，獲得分析、設(shè)計(jì)、實(shí)現(xiàn)和維護(hù)編譯系統(tǒng)的初步能力；另一面，通過(guò)學(xué)習(xí)編譯的理論和方法，提高對(duì)程序設(shè)計(jì)語(yǔ)言、操作系統(tǒng)、計(jì)算機(jī)原理和體系結(jié)構(gòu)等課程知識(shí)的綜合理解。,1.2,編譯過(guò)程概述,The elephant ate an banana.,什么是語(yǔ)言？,for K:=1 to 100 d

4、o,begin,M:=I+10*K;,N:=J+10*K,end,一,.,類比自然語(yǔ)言翻譯和編譯過(guò)程,英漢 編譯的工作過(guò)程,1),識(shí)別單詞,詞法分析,2),分析句子語(yǔ)法結(jié)構(gòu),語(yǔ)法分析,3),根據(jù)句子含義初步翻譯,語(yǔ)義分析與中間代碼產(chǎn)生,4),修飾譯文,優(yōu)化,5),寫(xiě)出最后譯文,目標(biāo)代碼生成,1.2,編譯過(guò)程概述,1.,詞法分析,for K:=1 to 100 do,begin,M:=I+10*K;,N:=J+10*K,end,基本字,for,標(biāo)識(shí)符,K,賦值號(hào),:=,常數(shù),1,基本字,to,常數(shù),100,基本字,do,基本字,begin,.,.,1.2,編譯過(guò)程概述,詞法分析,規(guī)則：,規(guī)則描述

5、工具：,任務(wù)：,依循詞法規(guī)則,.,正規(guī)式和有限自動(dòng)機(jī)（,FA,）,.,輸入源程序,，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，,識(shí)別出一個(gè)個(gè)的單詞符號(hào),，如基本字、標(biāo)識(shí)符、常數(shù)、算符、界符等。,1.2,編譯過(guò)程概述,2.,語(yǔ)法分析,for K:=1 to 100 do,begin,M:=I+10*K;,N:=J+10*K,end,規(guī)則：,規(guī)則描述工具：,任務(wù)：,依循語(yǔ)法規(guī)則,.,上下文無(wú)關(guān)文法,.,在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析，識(shí)別出各類語(yǔ)法單位，最終判斷輸入串是否構(gòu)成語(yǔ)法上正確的,“,程序,”,。,1.2,編譯過(guò)程概述,3.,語(yǔ)義分析和中間代碼產(chǎn)生,規(guī)則：,規(guī)則

6、描述工具：,任務(wù)：,語(yǔ)義規(guī)則,屬性文法,兩部分工作：,1.,對(duì)每種語(yǔ)法范疇進(jìn)行,靜態(tài)語(yǔ)義檢查,;,2.,若語(yǔ)義正確，則進(jìn)行,中間代碼翻譯,.,對(duì)語(yǔ)法分析器識(shí)別出的各類語(yǔ)法單位，分析其含義并進(jìn)行初步翻譯（產(chǎn)生,中間代碼,）。,中間代碼：一種獨(dú)立于具體硬件的記號(hào)系統(tǒng)，更接近于機(jī)器代碼,1.2,編譯過(guò)程概述,for K:=1 to 100 do,begin,M:=I+10*K;,N:=J+10*K,end,；,K:=1,L,1,:if 100K goto L,2,T,1,:=10*K,M:=I+T,1,T,2,:=10*K,N:=J+T,2,K:=K+1,goto L,1,L,2,:,語(yǔ)義分析后產(chǎn)生

7、的中間代碼：,三地址代碼,具體實(shí)現(xiàn)：,三元式，四元式，間接三元式,1.2,編譯過(guò)程概述,K:=1,L,1,:if 100K goto L,2,T,1,:=10*K,M:=I+T,1,T,2,:=10*K,N:=J+T,2,K:=K+1,goto L,1,L,2,:,序號(hào),OP,ARG1,ARG2,RESULT,(1),(2),(3),(4),(5),(6),(7),(8),(9),:=,j,*,+,*,+,+,j,1,100,10,I,10,J,K,K,K,T,1,K,T,2,1,K,(9),T,1,M,T,2,N,K,(2),四元式序列：,1.2,編譯過(guò)程概述,任務(wù)：,對(duì)中間代碼進(jìn)行加工變換

8、，以期在最后階段,能產(chǎn)生出更為,高效（省時(shí)間和空間）,的目標(biāo),代碼。,4.,優(yōu)化,包括：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無(wú)用代碼等,1.2,編譯過(guò)程概述,序號(hào),OP,ARG1,ARG2,RESULT,(1),(2),(3),(4),(5),(6),(7),(8),(9),:=,j,*,+,*,+,+,j,1,100,10,I,10,J,K,K,K,T,1,K,T,2,1,K,(9),T,1,M,T,2,N,K,(2),序號(hào),OP,ARG1,ARG2,RESULT,(1),(2),(3),(4),(5),(6),(7),(8),(9),:=,:=,:=,j,+,+,+,j,I,I,1,100,

9、M,N,K,K,10,10,1,M,N,K,(9),M,N,K,(2),優(yōu)化前,優(yōu)化后,1.2,編譯過(guò)程概述,任務(wù)：,把中間代碼變換成,特定機(jī)器上,的低級(jí)語(yǔ)言代碼，,實(shí)現(xiàn)最后的翻譯。,5.,目標(biāo)代碼生成,絕對(duì)指令代碼,/,可重定位的指令代碼,/,匯編指令代碼,有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義,1.2,編譯過(guò)程概述,1.3,編譯程序的結(jié)構(gòu),一,.,編譯程序總框圖,1.,表格管理,編譯各階段都要涉及到構(gòu)造、查找或 更新有關(guān)表格,。,表格的作用：,登記源程序的,各類信息,和編譯,各階段的進(jìn)展?fàn)顩r,。,符號(hào)表：,用來(lái)登記源程序中出現(xiàn)的每個(gè),名字,以及,名字的各種屬性,。,舉例：,名字,變量名,/,常量

10、名,/,過(guò)程名,？,變量名,類型？,/,內(nèi)存？,/,地址？,1.3,編譯程序的結(jié)構(gòu),2.,出錯(cuò)處理,每一階段都可能檢測(cè)出錯(cuò)誤，絕大多 數(shù)錯(cuò)誤可在前三階段檢測(cè)出來(lái),.,任務(wù)：,設(shè)法發(fā)現(xiàn)錯(cuò)誤，并把有關(guān)錯(cuò)誤信息報(bào)告給用戶,.,語(yǔ)法錯(cuò)誤,：源程序中不符合語(yǔ)法,/,詞法規(guī)則的錯(cuò)誤。,詞法,/,語(yǔ)法分析時(shí)檢測(cè),語(yǔ)義錯(cuò)誤,：源程序中不符合語(yǔ)義規(guī)則的錯(cuò)誤。,語(yǔ)義分析,/,運(yùn)行時(shí)檢測(cè)出來(lái),1.3,編譯程序的結(jié)構(gòu),二,.,遍,1.,編譯過(guò)程的劃分：,上述劃分的五個(gè)階段僅僅是,邏輯功能,上的一種劃分,2.,遍（,Pass,）,對(duì)源程序或源程序的中間結(jié)果,從頭到尾,掃描一次，并作有關(guān)的加工處理，生成,新的,中間結(jié)果或

11、目標(biāo)程序。,具體實(shí)現(xiàn)時(shí)，受各方面（如源語(yǔ)言、設(shè)計(jì)要求等）限制，往往組織成若干遍,1.3,編譯程序的結(jié)構(gòu),3.,注意：,既可以將幾個(gè)不同階段合為一遍，也可以把一個(gè)階段的工作分為若干遍,例如：,詞法分析,+,語(yǔ)法分析,一遍,語(yǔ)法分析,+,語(yǔ)義分析與中間代碼產(chǎn)生,一遍,優(yōu)化,若干遍,單遍代碼不太有效。,根據(jù)系統(tǒng)資源的狀況、運(yùn)行目標(biāo)的要求等，可以將一個(gè)編譯程序設(shè)計(jì)形成多遍掃描的形式，在每一遍掃描中完成不同的任務(wù)。,1.3,編譯程序的結(jié)構(gòu),當(dāng)一遍中包含若干階段時(shí)，各階段的工作是穿插進(jìn)行的,。,例如：,識(shí)別出一個(gè)語(yǔ)法單位時(shí),語(yǔ)法分析器,詞法分析器,語(yǔ)義分析和中間代碼產(chǎn)生器,識(shí)別語(yǔ)法結(jié)構(gòu)需要下一個(gè)單詞時(shí),單

12、詞符號(hào),1.3,編譯程序的結(jié)構(gòu),三,.,編譯前端與后端,1,、前端：,由與源語(yǔ)言,有關(guān),但與目標(biāo)機(jī),無(wú)關(guān),的那些部分組成,包括,詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼,產(chǎn)生、部分代碼優(yōu)化工作,2,、后端：,包括編譯程序中與目標(biāo)機(jī),有關(guān),的那些部分，如與,目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。,不依賴于源語(yǔ)言而僅僅,依賴于中間語(yǔ)言,1.3,編譯程序的結(jié)構(gòu),1.5,編譯程序的生成,一,.,設(shè)計(jì)目標(biāo),目標(biāo)程序小，執(zhí)行速度快,編譯程序小，執(zhí)行速度快,診斷能力強(qiáng)，可靠性強(qiáng),可移植性，可擴(kuò)充性,如何實(shí)現(xiàn)編譯器？,直接用可運(yùn)行,的代碼編制,太費(fèi)力！,1.5,編譯程序的生成,以匯編語(yǔ)言和機(jī)器語(yǔ)言為工具,優(yōu)點(diǎn),

13、:,可以針對(duì)具體的機(jī)器，充分發(fā)揮計(jì)算機(jī)的系統(tǒng)功能。生成的程序效率高。,缺點(diǎn),:,程序難讀、難寫(xiě)、易出錯(cuò)、難維護(hù)、生產(chǎn)的效率低。,五,.,編譯程序生成,高級(jí)語(yǔ)言書(shū)寫(xiě),優(yōu)點(diǎn),:,程序易讀、易理解、容易維護(hù)、生產(chǎn)的效率高。,缺點(diǎn),:,難以充分發(fā)揮計(jì)算機(jī)的系統(tǒng)功能，生成的程序效率低。,1.5,編譯程序的生成,2,、問(wèn)題,（,1,）歷史上第一個(gè)高級(jí)語(yǔ)言的編譯程序是怎樣構(gòu)造的？,-,自編譯技術(shù)（自展技術(shù)）,（,2,）已有,A,機(jī)器上的,L1,語(yǔ)言（如：,C,語(yǔ)言）的編譯程序，如何構(gòu)造,A,機(jī)器上的,L2,語(yǔ)言（如：,PASCAL,語(yǔ)言）的編譯程序？,（,3,）已有,A,機(jī)器上的,L,語(yǔ)言的編譯程序，如何構(gòu)

14、造,B,機(jī)器上的,L,語(yǔ)言的編譯程序？,-,交叉編譯,/,移植,ST,I,源語(yǔ)言,編譯程序?qū)崿F(xiàn)語(yǔ)言,目標(biāo)語(yǔ)言,一般采用基于,T,形圖的方式：,表現(xiàn)語(yǔ)言翻譯的,T,形圖,1.5,編譯程序的生成,高級(jí)語(yǔ)言書(shū)寫(xiě),利用已有的某種語(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ǔ)言,1.5,編譯程序的生成,移植方法,把一種機(jī)器上的編譯程序移植到另一種機(jī)器上。,L,語(yǔ)言,A,代碼,P1:,A,代碼,L,語(yǔ)言,B,代碼,P2:,L,語(yǔ)言,L,語(yǔ)言,B,代碼,P2:,A,代碼,L

15、,語(yǔ)言,B,代碼,P2:,L,語(yǔ)言,L,語(yǔ)言,B,代碼,P2:,B,代碼,同一種語(yǔ)言不同的機(jī)器,1.5,編譯程序的生成,L,1,+L,2,+.+L,n,L,1,+L,2,自展技術(shù),L,1,1.5,編譯程序的生成,編譯程序自動(dòng)產(chǎn)生,編譯程序,-,編譯程序，編譯程序書(shū)寫(xiě)系統(tǒng),LEX,詞法分析程序產(chǎn)生器,YACC,語(yǔ)法分析程序產(chǎn)生器,編譯程序,自動(dòng)產(chǎn)生器,L,語(yǔ)言的語(yǔ)法描述,語(yǔ)義描述,目標(biāo)語(yǔ)言,或機(jī)器描述,L,語(yǔ)言的,編譯程序,1.5,編譯程序的生成,1.5,編譯程序的生成,三,.,如何學(xué)習(xí)構(gòu)造編譯程序,要在某一臺(tái)機(jī)器上為某種語(yǔ)言構(gòu)造一個(gè)編譯程序，必須掌握以下內(nèi)容：,源語(yǔ)言,：,對(duì)被編譯的源語(yǔ)言，要深刻理解其結(jié)構(gòu)（語(yǔ)法）和,含義（語(yǔ)義）。,目標(biāo)語(yǔ)言,：,假定目標(biāo)語(yǔ)言是機(jī)器語(yǔ)言，那么，就必須搞清硬,件的系統(tǒng)結(jié)構(gòu)和,OS,的功能。,編譯方法,：,把一種語(yǔ)言程序翻譯為另一種語(yǔ)言程序的方法很,多，但必須準(zhǔn)確的掌握一、二。,關(guān)于學(xué)習(xí)編譯原理,意義,:,學(xué)習(xí)編譯程序構(gòu)造原理，技術(shù),更好地理解高級(jí)語(yǔ)言,編譯的原理和方法有助于構(gòu)造一些實(shí)用的工具,第,1,章 總結(jié),1.,編譯程序的概念,2.,編譯過(guò)程（掌握）,3.,基本概念：遍，編譯前端,/,后端（掌握）,4.T,型圖（了解）,