編譯原理課件1.ppt

編譯原理(PrinciplesofCompiling),主講：段忠祥電話mail：13799928,學(xué)時與參考教材,學(xué)時：64參考教材：1、陳火旺等，程序設(shè)計語言編譯原理，國防工業(yè)出版社，2003.8.印刷2、AlfredAhoect.編譯原理，李建中等譯，機(jī)械工業(yè)出版社，2003.8.(原版-郵電出版社)3、KennethC.Louden，編譯原理及實踐，馮博琴等譯，機(jī)械工業(yè)出版社，2001.2.印刷4、金成植，編譯程序構(gòu)造原理和實現(xiàn)技術(shù)，高等教育出版社，2000.7.,學(xué)時與參考教材,5、何炎祥等，編譯原理，華中理工大學(xué)出版社，2010.4.6、P.M.劉易斯，編譯程序設(shè)計理論，科學(xué)出版社，1984.5.7、高仲儀等，編譯技術(shù)，西北工業(yè)大學(xué)出版社，1985.98、杜淑敏等，編譯程序設(shè)計原理北京大學(xué)出版社，1990.11.,主要內(nèi)容,概述(總體結(jié)構(gòu)、設(shè)計方法2)語言與文法(文法、推導(dǎo)、歸約、分類、分析樹6)有窮自動機(jī)（fa正則表達(dá)式，dfa2）詞法分析(詞法分析、正規(guī)式與正規(guī)文法、DFA狀態(tài)轉(zhuǎn)移圖6)語法分析(自頂向下：LL(1)、遞歸子程序；自底向上：算符優(yōu)先、LR14)語義分析(屬性文法、各種語句的語法制導(dǎo)翻譯8)運行環(huán)境(存儲分配、過程調(diào)用、符號表管理8)中間代碼生成、優(yōu)化（6）目標(biāo)代碼生成（6）總結(jié)（4）,教學(xué)目的,涉及的是一個比較適當(dāng)?shù)某橄髮用嫔系臄?shù)據(jù)變換（既抽象，又實際）一些具體的表示和變換算法“自頂向下”和“自底向上”的系統(tǒng)設(shè)計方法（思想、方法、實現(xiàn)全方位討論）一個相當(dāng)規(guī)模的系統(tǒng)的設(shè)計（含總體結(jié)構(gòu)）AlfredV.Aho：編寫編譯器的原理和技術(shù)具有十分普遍的意義，以至于在每個計算機(jī)科學(xué)家的研究生涯中，本書中的原理和技術(shù)都會反復(fù)用到結(jié)論：計算機(jī)專業(yè)最恰當(dāng)、有效的知識載體之一,教學(xué)要求,掌握編譯程序總體結(jié)構(gòu)在系統(tǒng)級上認(rèn)識算法、系統(tǒng)的設(shè)計具有把握系統(tǒng)的能力學(xué)習(xí)有關(guān)的原理、實現(xiàn)方法和技術(shù)，了解計算學(xué)科的基本方法、思想掌握典型方法?！霸诿恳粋€計算機(jī)科技工作者的職業(yè)生涯中，這些原理和技術(shù)都被反復(fù)用到?！奔骖櫿Z言的描述方法、設(shè)計、應(yīng)用形式化進(jìn)一步培養(yǎng)“計算機(jī)思維能力”程序的非物理性質(zhì),學(xué)習(xí)方法,勤于思考博覽、多思（學(xué)而不思則罔、思而不學(xué)則??；書由厚到薄、由薄到厚）、常實踐思考由懷疑和答案組成。懷疑是智慧的大門，知道得越多，就越會發(fā)問，而問題就越多。發(fā)問使人進(jìn)步。強(qiáng)化基礎(chǔ)在獨立思考之前，必須先有基礎(chǔ)知識。所謂“獲得基礎(chǔ)知識”并不是形式上讀過某門課程，而是將學(xué)過的東西完全弄懂。理論與實踐的結(jié)合能力,學(xué)習(xí)方法,應(yīng)對困難不畏懼困難從教訓(xùn)到經(jīng)驗親身體驗要實踐（作業(yè)、實驗），加深理解學(xué)習(xí)是一個過程上課、讀書、復(fù)習(xí)、做作業(yè)、討論、做實驗、自己編程序、上機(jī)調(diào)試排錯是絕對必要的輔導(dǎo)答疑教師是最寶貴的資源自己要思考，以獲得最大收獲：習(xí)題、問題,第1章引論,1.1計算機(jī)語言的發(fā)展1.2翻譯系統(tǒng)1.3編譯系統(tǒng)的功能分析1.4編譯程序總體結(jié)構(gòu)1.5編譯程序的生成1.6編譯技術(shù)的應(yīng)用,1.1計算機(jī)語言的發(fā)展,機(jī)器語言(MachineLanguage)匯編語言(AssembleLanguage)0、1代碼與助記符：更接近于計算機(jī)硬件指令系統(tǒng)的工作高級語言(HighLevelLanguage)定義數(shù)據(jù)、描述算法（程序）如：C、FORTRAN、PASCAL、C+、JAVA、SQL(數(shù)據(jù)定義、數(shù)據(jù)操作)命令語言(Command)以功能封裝為特征,高級語言的分類,強(qiáng)制式語言(ImperativeLanguage)FORTRAN(段結(jié)構(gòu))、BASIC、Pascal(嵌套結(jié)構(gòu))、C函數(shù)(應(yīng)用)式語言(FunctionalLanguage)LISP、ML邏輯式(基于規(guī)則)語言(LogicalLanguage)Prolog面向?qū)ο笳Z言(Object-OrientedLanguage)Smalltalk、C+、Java、Ada(程序包),1.2翻譯系統(tǒng),翻譯程序(Translator)將某一種語言描述的程序(源程序SourceProgram)翻譯成等價的另一種語言描述的程序(目標(biāo)程序ObjectProgram)的程序。,翻譯程序,源程序,目標(biāo)程序,(*.C/*.PAS/*.AS),(*.OBJ/*.EXE/*.*),1.2翻譯系統(tǒng),解釋程序(Interpreter)口譯與筆譯（單句提交與整篇提交）,源程序,輸入數(shù)據(jù),計算結(jié)果,解釋程序,1.2翻譯系統(tǒng),編譯程序(Compiler)高級語言程序匯編/機(jī)器語言程序,源程序,目標(biāo)程序,編譯程序,1.2編譯系統(tǒng),SPCompilerS-SourceO-ObjectOPP-ProgramInputRSRS-RunSys.Output,編譯系統(tǒng)(CompilingSystem)編譯系統(tǒng)=編譯程序+運行系統(tǒng),支撐環(huán)境、運行庫等,1.2翻譯系統(tǒng),其它：診斷編譯程序（DiagnosticCompiler)優(yōu)化編譯程序（OptimizingCompiler)交叉編譯程序（CrossCompiler)可變目標(biāo)編譯程序（RetargetableCompiler)并行編譯程序（ParallelizingCompiler）匯編程序(Assembler)、交叉匯編程序(CrossAssembler)、反匯編程序（Disassembler),1.2翻譯系統(tǒng)匯總,MLMLPAssemblerDisassemblerALALPCompilerDataHLHLPInterpreterResult,M-MachineL-LangugeP-ProgramA-AssembleH-HighLevel,1.3編譯系統(tǒng)的功能分析,程序分析詞法、語法、語義分析綜合語句的翻譯、代碼生成例如：標(biāo)識符左值與右值的綁定(binding)變量：存儲單元函數(shù)：目標(biāo)代碼序列,1.4編譯程序總體結(jié)構(gòu)請參閱P5圖1.1,目標(biāo)代碼生成器,代碼優(yōu)化器,語義分析與中間代碼生成器,語法分析器,1.詞法分析,例：res=fact*(term1+term2);,結(jié)果IDNres=IDNfact*(IDNterm1+IDNterm2);,1、詞法分析,詞法分析器(LexicalAnalyzer)又叫做掃描器(Scanner)，完成詞法分析功能：詞法分析器從左到右掃描源程序（字符串），并將其轉(zhuǎn)換成單詞(記號Token)串；同時查詞法錯誤，進(jìn)行標(biāo)識符登記符號表管理。輸入：字符串輸出：(種別碼，屬性值)序?qū)傩灾祎oken的機(jī)內(nèi)表示,2、語法分析,語法分析器(SyntaxAnalyzer，又叫Parser)完成語法分析功能：Parser實現(xiàn)“組詞成句”，構(gòu)造分析樹，指出語法錯誤，指導(dǎo)翻譯輸入：Token序列輸出：語法成分,2.語法分析,res=fact*(term1+term2);,字符串,3.語義分析,功能：分析由語法分析器給出的語法單位的語義獲取標(biāo)識符的屬性：類型、作用域等語義檢查：運算的合法性、取值范圍等子程序的靜態(tài)綁定：代碼的相對地址變量的靜態(tài)綁定：數(shù)據(jù)的相對地址,4.中間代碼生成,中間代碼(intermediateCode)例:id1+id2*id3,后綴表示(逆波蘭ReversePolishNotation)id1id2id3*+前綴表示(波蘭PolishNotation)+id1*id2id3,四元組表示(三地址碼)1(*,id1,id2,T1)2(+,id3,T1,T2),三元組表示1(*,id2,id3)2(+,id1,(1),波蘭表示問題Lukasiewicz1929/1951年發(fā)明,中綴表示(Infixnotation):(a+b)*(-c+d)+e/f波蘭表示（Polish/Prefix/Parenthesis-free/Lukasiewicznotation）也就是前綴表示+*+ab+cd/ef運算順序從右向左逆波蘭表示(ReversePolish/Suffix/Postfixnotation)也就是后綴表示ab+cd+*ef/+運算順序從左向右,4.中間代碼生成,中間代碼的特點簡單規(guī)范機(jī)器無關(guān)易于優(yōu)化與轉(zhuǎn)換,三地址碼的另一種表示形式T1=id2*id3T2=id1*T1,其它類型的語句舉例printf(“hello”)x:=s（賦值）paramx（參數(shù)）callf（函數(shù)調(diào)用）s是hello的地址f是函數(shù)printf的地址,對中間代碼的優(yōu)化處理:對代碼進(jìn)行等價變換以求提高執(zhí)行效率提高運行速度和節(jié)省存儲空間與機(jī)器無關(guān)的優(yōu)化與機(jī)器有關(guān)的優(yōu)化,5.代碼優(yōu)化,與機(jī)器無關(guān)的優(yōu)化,局部優(yōu)化常量合并：常數(shù)運算在編譯期間完成，如8+9*4公共子表達(dá)式的提取:基本塊內(nèi)循環(huán)優(yōu)化強(qiáng)度削減代碼外提,與機(jī)器有關(guān)的優(yōu)化,寄存器的利用將常用量放入寄存器，以減少訪問內(nèi)存的次數(shù)體系結(jié)構(gòu)MIMD、SIMD、SPMD、向量機(jī)、流水機(jī)存儲策略根據(jù)算法訪存的要求安排：Cache、并行存儲體系減少訪問沖突任務(wù)劃分按運行的算法即體系結(jié)構(gòu)，劃分子任務(wù)(MPMD),6.目標(biāo)代碼生成,將中間代碼轉(zhuǎn)換成目標(biāo)機(jī)上的機(jī)器指令代碼或匯編代碼,7、表格管理,管理各種符號表（常數(shù)、標(biāo)號、變量、過程、結(jié)構(gòu)），查、填（登記、查找）源程序中出現(xiàn)的符號和編譯程序生成的符號，為編譯的各個階段提供信息。輔助語法檢查、語義檢查完成靜態(tài)綁定、管理編譯過程Hash表、鏈表等各種查、填表技術(shù),8、錯誤處理,進(jìn)行各種錯誤的檢查、報告、糾正，以及相應(yīng)的續(xù)編譯處理（如：錯誤的定位與局部化）詞法：拼寫語法：語句結(jié)構(gòu)、表達(dá)式結(jié)構(gòu)語義：類型不匹配,模塊分類,分析：詞法分析、語法分析、語義分析綜合：中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成輔助：符號表管理、出錯處理8項功能對應(yīng)8個模塊,編譯程序總體結(jié)構(gòu),例一個語句的翻譯,9編譯的遍（Pass）,根據(jù)系統(tǒng)資源的狀況、運行目標(biāo)的要求等，可以將一個編譯程序設(shè)計成多遍掃描的形式，在每一遍掃描中，完成不同的任務(wù)。遍可以和階段相對應(yīng)，也可無關(guān)單遍代碼不太有效,10、編譯的前端與后端,前端與源語言有關(guān)、與目標(biāo)機(jī)無關(guān)的部分詞法分析、語法分析、語義分析與中間代碼生成、與機(jī)器無關(guān)的代碼優(yōu)化后端與目標(biāo)機(jī)有關(guān)的部分與機(jī)器有關(guān)的代碼優(yōu)化、目標(biāo)代碼生成,1.5編譯程序的生成,設(shè)計目標(biāo)目標(biāo)程序小，執(zhí)行速度快。編譯程序小，執(zhí)行速度快。診斷能力強(qiáng)，可靠性高?？梢浦残?，可擴(kuò)充性。如何實現(xiàn)編譯器？直接用可運行的代碼編制太費力！,形圖,表示語言翻譯的形圖,源語言,表示語言,目標(biāo)語言,1）交叉編譯(CrossCompiling)/移植,問題一：A機(jī)上有一個C語言編譯器，是否可利用此編譯器實現(xiàn)B機(jī)上的C語言編譯器？條件：機(jī)有語言的編譯程序目的：實現(xiàn)機(jī)的語言的編譯,1.(人)用語言編制B機(jī)的編譯程序P0(CB)(機(jī)的C編譯P1)編譯P0，得到在A機(jī)上可運行的P2(CB),上次課主要內(nèi)容,基本概念翻譯程序、編譯程序、解釋程序、編譯系統(tǒng)匯編程序、其他編譯的掃描遍數(shù)、前端、后端,編譯程序總體結(jié)構(gòu),上次課主要內(nèi)容,T形圖移植,3.(機(jī)的P2)編譯P0，得到在B機(jī)上可運行的P3(CB),獲得一個工具,2)本機(jī)編譯器利用,問題二：A機(jī)上有一個C語言編譯器，現(xiàn)要實現(xiàn)一個新語言NEW的編譯器？能利用交叉編譯技術(shù)么？用C編寫NEW的編譯，并用C編譯器編譯它,問題三：直接在一個機(jī)上實現(xiàn)C語言編譯器，還有別的技術(shù)么？解決：用匯編語言實現(xiàn)一個子集的編譯程序(P0人)用匯編程序處理該程序,得到P2(P2:可直接運行)用子集編制語言的編譯程序(P3人)用P2編譯P3，得到P4,3)編譯程序的自展技術(shù),4)利用編譯程序自動生成器,詞法分析器的自動生成程序,詞法規(guī)則說明,詞法分析程序,(C程序),輸入：詞法（正規(guī)表達(dá)式）識別動作（程序段）輸出：yylex()函數(shù),LEX,語法分析器的自動生成程序,語法規(guī)則說明,語法分析程序,(C程序),輸入：語法規(guī)則（產(chǎn)生式）語義動作（程序段）輸出：yyparse()函數(shù),1.6編譯技術(shù)的應(yīng)用,把復(fù)雜數(shù)據(jù)看作一條語句數(shù)據(jù)格式的分析利用詞法分析、語法分析方法數(shù)據(jù)處理的框架基于語法制導(dǎo)的語義處理框架編譯技術(shù)可以用于各種復(fù)雜數(shù)據(jù)的分析處理,例1-1,DOS命令date的輸出格式例：9-2-1993、09-03-1993、9-03-93語法datemonth-day-y