編譯原理第1章

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