《編譯原理第1章》由會(huì)員分享,可在線閱讀,更多相關(guān)《編譯原理第1章(38頁珍藏版)》請?jiān)谘b配圖網(wǎng)上搜索。
1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,編譯原理,程序設(shè)計(jì)語言,第一章 引論,1.1,什么叫編譯程序,1.2,編譯過程概述,1.3,編譯程序的結(jié)構(gòu),1.4,編譯程序與程序設(shè)計(jì)環(huán)境(略),1.5,編譯程序的生成,1.,什么是編譯程序?,1.1,什么叫編譯程序,翻譯程序,:一種語言程序,-,-,另一種語言程序,源語言,目標(biāo)語言,編譯程序,:高級(jí)語言程序,-,-,低級(jí)語言程序,匯編程序,:匯編語言程序,-,-,機(jī)器語言程序,解釋程序,:源語言程序,-,-,邊解釋邊執(zhí)行,(,1,)編譯方式:先編譯后執(zhí)行。,(,2,)解釋方式:,以源程序作為輸入,但,不產(chǎn)
2、生目標(biāo)代碼,,而,是,邊解釋邊執(zhí)行,源程序本身。,2.,“,高級(jí)語言程序,”,的執(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)化的理論與方法,并開發(fā)出了一些好的編譯
3、程序的實(shí)現(xiàn)語言、環(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ā)展的重要成果與精華。,通過本課程的學(xué)習(xí),一方面要理解、掌握編譯系統(tǒng)的結(jié)構(gòu)、工作流程以及編譯程序各組成部分的設(shè)計(jì)原理和實(shí)現(xiàn)技術(shù),獲得分析、設(shè)計(jì)、實(shí)現(xiàn)和維護(hù)編譯系統(tǒng)的初步能力;另一面,通過學(xué)習(xí)編譯的理論和方法,提高對(duì)程序設(shè)計(jì)語言、操作系統(tǒng)、計(jì)算機(jī)原理和體系結(jié)構(gòu)等課程知識(shí)的綜合理解。,1.2,編譯過程概述,The elephant ate an banana.,什么是語言?,for K:=1 to 100 d
4、o,begin,M:=I+10*K;,N:=J+10*K,end,一,.,類比自然語言翻譯和編譯過程,英漢 編譯的工作過程,1),識(shí)別單詞,詞法分析,2),分析句子語法結(jié)構(gòu),語法分析,3),根據(jù)句子含義初步翻譯,語義分析與中間代碼產(chǎn)生,4),修飾譯文,優(yōu)化,5),寫出最后譯文,目標(biāo)代碼生成,1.2,編譯過程概述,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ī)則描述
5、工具:,任務(wù):,依循詞法規(guī)則,.,正規(guī)式和有限自動(dòng)機(jī)(,FA,),.,輸入源程序,,對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解,,識(shí)別出一個(gè)個(gè)的單詞符號(hào),,如基本字、標(biāo)識(shí)符、常數(shù)、算符、界符等。,1.2,編譯過程概述,2.,語法分析,for K:=1 to 100 do,begin,M:=I+10*K;,N:=J+10*K,end,規(guī)則:,規(guī)則描述工具:,任務(wù):,依循語法規(guī)則,.,上下文無關(guān)文法,.,在詞法分析的基礎(chǔ)上,根據(jù)語言的語法規(guī)則,對(duì)單詞符號(hào)串進(jìn)行語法分析,識(shí)別出各類語法單位,最終判斷輸入串是否構(gòu)成語法上正確的,“,程序,”,。,1.2,編譯過程概述,3.,語義分析和中間代碼產(chǎn)生,規(guī)則:,規(guī)則
6、描述工具:,任務(wù):,語義規(guī)則,屬性文法,兩部分工作:,1.,對(duì)每種語法范疇進(jìn)行,靜態(tài)語義檢查,;,2.,若語義正確,則進(jìn)行,中間代碼翻譯,.,對(duì)語法分析器識(shí)別出的各類語法單位,分析其含義并進(jìn)行初步翻譯(產(chǎn)生,中間代碼,)。,中間代碼:一種獨(dú)立于具體硬件的記號(hào)系統(tǒng),更接近于機(jī)器代碼,1.2,編譯過程概述,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,:,語義分析后產(chǎn)生
7、的中間代碼:,三地址代碼,具體實(shí)現(xiàn):,三元式,四元式,間接三元式,1.2,編譯過程概述,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,編譯過程概述,任務(wù):,對(duì)中間代碼進(jìn)行加工變換
8、,以期在最后階段,能產(chǎn)生出更為,高效(省時(shí)間和空間),的目標(biāo),代碼。,4.,優(yōu)化,包括:公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無用代碼等,1.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),序號(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,編譯過程概述,任務(wù):,把中間代碼變換成,特定機(jī)器上,的低級(jí)語言代碼,,實(shí)現(xiàn)最后的翻譯。,5.,目標(biāo)代碼生成,絕對(duì)指令代碼,/,可重定位的指令代碼,/,匯編指令代碼,有賴于硬件系統(tǒng)結(jié)構(gòu)和機(jī)器指令含義,1.2,編譯過程概述,1.3,編譯程序的結(jié)構(gòu),一,.,編譯程序總框圖,1.,表格管理,編譯各階段都要涉及到構(gòu)造、查找或 更新有關(guān)表格,。,表格的作用:,登記源程序的,各類信息,和編譯,各階段的進(jìn)展?fàn)顩r,。,符號(hào)表:,用來登記源程序中出現(xiàn)的每個(gè),名字,以及,名字的各種屬性,。,舉例:,名字,變量名,/,常量
10、名,/,過程名,?,變量名,類型?,/,內(nèi)存?,/,地址?,1.3,編譯程序的結(jié)構(gòu),2.,出錯(cuò)處理,每一階段都可能檢測出錯(cuò)誤,絕大多 數(shù)錯(cuò)誤可在前三階段檢測出來,.,任務(wù):,設(shè)法發(fā)現(xiàn)錯(cuò)誤,并把有關(guān)錯(cuò)誤信息報(bào)告給用戶,.,語法錯(cuò)誤,:源程序中不符合語法,/,詞法規(guī)則的錯(cuò)誤。,詞法,/,語法分析時(shí)檢測,語義錯(cuò)誤,:源程序中不符合語義規(guī)則的錯(cuò)誤。,語義分析,/,運(yùn)行時(shí)檢測出來,1.3,編譯程序的結(jié)構(gòu),二,.,遍,1.,編譯過程的劃分:,上述劃分的五個(gè)階段僅僅是,邏輯功能,上的一種劃分,2.,遍(,Pass,),對(duì)源程序或源程序的中間結(jié)果,從頭到尾,掃描一次,并作有關(guān)的加工處理,生成,新的,中間結(jié)果或
11、目標(biāo)程序。,具體實(shí)現(xiàn)時(shí),受各方面(如源語言、設(shè)計(jì)要求等)限制,往往組織成若干遍,1.3,編譯程序的結(jié)構(gòu),3.,注意:,既可以將幾個(gè)不同階段合為一遍,也可以把一個(gè)階段的工作分為若干遍,例如:,詞法分析,+,語法分析,一遍,語法分析,+,語義分析與中間代碼產(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è)語法單位時(shí),語法分析器,詞法分析器,語義分析和中間代碼產(chǎn)生器,識(shí)別語法結(jié)構(gòu)需要下一個(gè)單詞時(shí),單
12、詞符號(hào),1.3,編譯程序的結(jié)構(gòu),三,.,編譯前端與后端,1,、前端:,由與源語言,有關(guān),但與目標(biāo)機(jī),無關(guān),的那些部分組成,包括,詞法分析、語法分析、語義分析與中間代碼,產(chǎn)生、部分代碼優(yōu)化工作,2,、后端:,包括編譯程序中與目標(biāo)機(jī),有關(guān),的那些部分,如與,目標(biāo)機(jī)有關(guān)的代碼優(yōu)化和目標(biāo)代碼生成等。,不依賴于源語言而僅僅,依賴于中間語言,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,編譯程序的生成,以匯編語言和機(jī)器語言為工具,優(yōu)點(diǎn),
13、:,可以針對(duì)具體的機(jī)器,充分發(fā)揮計(jì)算機(jī)的系統(tǒng)功能。生成的程序效率高。,缺點(diǎn),:,程序難讀、難寫、易出錯(cuò)、難維護(hù)、生產(chǎn)的效率低。,五,.,編譯程序生成,高級(jí)語言書寫,優(yōu)點(diǎn),:,程序易讀、易理解、容易維護(hù)、生產(chǎn)的效率高。,缺點(diǎn),:,難以充分發(fā)揮計(jì)算機(jī)的系統(tǒng)功能,生成的程序效率低。,1.5,編譯程序的生成,2,、問題,(,1,)歷史上第一個(gè)高級(jí)語言的編譯程序是怎樣構(gòu)造的?,-,自編譯技術(shù)(自展技術(shù)),(,2,)已有,A,機(jī)器上的,L1,語言(如:,C,語言)的編譯程序,如何構(gòu)造,A,機(jī)器上的,L2,語言(如:,PASCAL,語言)的編譯程序?,(,3,)已有,A,機(jī)器上的,L,語言的編譯程序,如何構(gòu)
14、造,B,機(jī)器上的,L,語言的編譯程序?,-,交叉編譯,/,移植,ST,I,源語言,編譯程序?qū)崿F(xiàn)語言,目標(biāo)語言,一般采用基于,T,形圖的方式:,表現(xiàn)語言翻譯的,T,形圖,1.5,編譯程序的生成,高級(jí)語言書寫,利用已有的某種語言的編譯程序?qū)崿F(xiàn)另一語言的編譯程序。,L1,語言,A,代碼,P1:,A,代碼,L2,語言,A,代碼,P2:,L1,語言,L2,語言,A,代碼,P2:,A,代碼,同一臺(tái)機(jī)器,不同的語言,1.5,編譯程序的生成,移植方法,把一種機(jī)器上的編譯程序移植到另一種機(jī)器上。,L,語言,A,代碼,P1:,A,代碼,L,語言,B,代碼,P2:,L,語言,L,語言,B,代碼,P2:,A,代碼,L
15、,語言,B,代碼,P2:,L,語言,L,語言,B,代碼,P2:,B,代碼,同一種語言不同的機(jī)器,1.5,編譯程序的生成,L,1,+L,2,+.+L,n,L,1,+L,2,自展技術(shù),L,1,1.5,編譯程序的生成,編譯程序自動(dòng)產(chǎn)生,編譯程序,-,編譯程序,編譯程序書寫系統(tǒng),LEX,詞法分析程序產(chǎn)生器,YACC,語法分析程序產(chǎn)生器,編譯程序,自動(dòng)產(chǎn)生器,L,語言的語法描述,語義描述,目標(biāo)語言,或機(jī)器描述,L,語言的,編譯程序,1.5,編譯程序的生成,1.5,編譯程序的生成,三,.,如何學(xué)習(xí)構(gòu)造編譯程序,要在某一臺(tái)機(jī)器上為某種語言構(gòu)造一個(gè)編譯程序,必須掌握以下內(nèi)容:,源語言,:,對(duì)被編譯的源語言,要深刻理解其結(jié)構(gòu)(語法)和,含義(語義)。,目標(biāo)語言,:,假定目標(biāo)語言是機(jī)器語言,那么,就必須搞清硬,件的系統(tǒng)結(jié)構(gòu)和,OS,的功能。,編譯方法,:,把一種語言程序翻譯為另一種語言程序的方法很,多,但必須準(zhǔn)確的掌握一、二。,關(guān)于學(xué)習(xí)編譯原理,意義,:,學(xué)習(xí)編譯程序構(gòu)造原理,技術(shù),更好地理解高級(jí)語言,編譯的原理和方法有助于構(gòu)造一些實(shí)用的工具,第,1,章 總結(jié),1.,編譯程序的概念,2.,編譯過程(掌握),3.,基本概念:遍,編譯前端,/,后端(掌握),4.T,型圖(了解),