編譯原理概述

編譯原理概述第1頁，共63頁，2023年，2月20日，星期二計算機(jī)專業(yè)的專業(yè)基礎(chǔ)課，主要解決高級語言的運行問題是軟件技術(shù)的基礎(chǔ)計算機(jī)專業(yè)學(xué)生必修的一門主干課程是本學(xué)科研究生入學(xué)考試的課程之一課程概述－1：課程地位第2頁，共63頁，2023年，2月20日，星期二本課程介紹如何將高級程序設(shè)計語言變換成計算機(jī)硬件所能識別的機(jī)器語言。編譯原理介紹編譯程序的原理，如何編程使高到低。其理論基礎(chǔ)堅實，其形式化系統(tǒng)不僅應(yīng)用于編譯技術(shù)，還大量應(yīng)用于人工智能、多媒體技術(shù)及數(shù)據(jù)庫等領(lǐng)域。例如：翻譯風(fēng)，一個翻譯的過程課程概述－2：編譯的作用第3頁，共63頁，2023年，2月20日，星期二掌握編譯理論基礎(chǔ)和形式化系統(tǒng)（過程、思想，對其思想用數(shù)學(xué)格式描述）了解編譯的全過程及其具體實現(xiàn)方法課程概述－3：學(xué)習(xí)任務(wù)第4頁，共63頁，2023年，2月20日，星期二認(rèn)真聽課，理論書中基本概念、基本原理與基本算法（枯燥，原理性強(qiáng)，數(shù)學(xué)性強(qiáng)，符號多，自己看書比較麻煩）弄懂書中例題和認(rèn)真對待課后習(xí)題在看書或理解例題時，一定要劃出相應(yīng)的細(xì)節(jié)變化過程，通過畫圖來加深理解在理解基礎(chǔ)上記憶（算法原理概念都是經(jīng)典內(nèi)容）課程概述－4：學(xué)習(xí)方法第5頁，共63頁，2023年，2月20日，星期二上課認(rèn)真聽講，獨立完成作業(yè)成績考核：平時成績占30％（出勤、課堂表現(xiàn)、作業(yè)）期末考試占70％（筆試）課程概述－5：學(xué)習(xí)要求第6頁，共63頁，2023年，2月20日，星期二《編譯原理》知識結(jié)構(gòu)第7頁，共63頁，2023年，2月20日，星期二掌握編譯程序中所涉及的有關(guān)名詞術(shù)語2.理解編譯程序總的框架，明確編譯程序工作的基本過程及各階段的基本任務(wù)教學(xué)目標(biāo)第1章編譯概述第8頁，共63頁，2023年，2月20日，星期二自然語言——人與人交流的一種工具人與計算機(jī)如何交流？通過程序設(shè)計語言將問題編寫成程序，計算機(jī)按程序的計算步驟計算出結(jié)果程序設(shè)計語言第9頁，共63頁，2023年，2月20日，星期二低級語言（LowlevelLanguage)字位碼、機(jī)器語言、匯編語言特點：與特定的機(jī)器有關(guān)，功效高，但使用復(fù)雜、繁 瑣、費時、易出錯高級語言

--Fortran、Pascal、C語言等特點：不依賴具體機(jī)器，移植性好、對用戶要求低、易使用、易維護(hù)等。程序設(shè)計語言第10頁，共63頁，2023年，2月20日，星期二計算機(jī)的核心部件只能讀懂自己的指令系統(tǒng)，不能執(zhí)行非機(jī)器語言編寫的程序計算機(jī)如何執(zhí)行高級語言？把高級語言程序翻譯成機(jī)器語言程序運行所得機(jī)器語言程序求得計算結(jié)果程序設(shè)計語言第11頁，共63頁，2023年，2月20日，星期二源程序

用匯編語言或高級語言編寫的程序稱為源程序目標(biāo)程序

用目標(biāo)語言所表示的程序目標(biāo)語言：可以是介于源語言和機(jī)器語言之間的“中間語言”，可以是某種機(jī)器的機(jī)器語言,也可以是某機(jī)器的匯編語言。翻譯程序

將源程序轉(zhuǎn)換為目標(biāo)程序的程序稱為翻譯程序。它是指各種語言的翻譯器，包括匯編程序和編譯程序，是匯編程序、編譯程序以及各種變換程序的總稱。第12頁，共63頁，2023年，2月20日，星期二源程序、翻譯程序、目標(biāo)程序三者關(guān)系：源程序翻譯程序目標(biāo)程序SOURCEPROGRAMTRANSLATEROBJECTPROGRAM即源程序是翻譯程序的輸入，目標(biāo)程序是翻譯程序的輸出SOI第13頁，共63頁，2023年，2月20日，星期二匯編程序

若源程序用匯編語言書寫，經(jīng)過翻譯程序得到用機(jī)器語言表示的程序，這時的翻譯程序就稱之為匯編程序，這種翻譯過程稱為“匯編”(Assemble）編譯程序

若源程序是用高級語言書寫，經(jīng)加工后得到目標(biāo)程序，上述翻譯過程稱“編譯”（Compile)匯編程序與編譯程序都是翻譯程序，主要區(qū)別是加工對象的不同。由于匯編語言格式簡單，常與機(jī)器語言之間有一一對應(yīng)的關(guān)系。匯編程序所要做的翻譯工作比編譯程序簡單的多。第14頁，共63頁，2023年，2月20日，星期二源程序的編譯和運行編譯或匯編階段源程序目標(biāo)程序編譯程序或匯編程序輸出數(shù)據(jù)目標(biāo)程序+運行子程序輸入數(shù)據(jù)運行階段第15頁，共63頁，2023年，2月20日，星期二編譯程序是現(xiàn)代計算機(jī)系統(tǒng)的基本組成部分從功能上看，一個編譯程序就是一個語言翻譯程序它是把一種語言(稱作源語言)書寫的程序翻譯成另一種語言(稱作目標(biāo)語言)的等價的程序編譯程序第16頁，共63頁，2023年，2月20日，星期二兩階段轉(zhuǎn)換：編譯—運行（compile－run）術(shù)語編譯程序的源語言(源程序)編譯程序的目標(biāo)語言(目標(biāo)程序)源程序編譯程序目標(biāo)代碼編譯時初始數(shù)據(jù)運行子程序目標(biāo)代碼計算結(jié)果運行時(*.C/*.PAS)(*.OBJ/*.EXE)編譯的過程轉(zhuǎn)換第17頁，共63頁，2023年，2月20日，星期二三階段轉(zhuǎn)換：編譯—匯編—運行源程序編譯程序匯編語言編譯時目標(biāo)代碼匯編程序匯編時初始數(shù)據(jù)運行子程序目標(biāo)代碼計算結(jié)果運行時.exe.obj編譯的過程轉(zhuǎn)換第18頁，共63頁，2023年，2月20日，星期二高級語言程序的處理過程第19頁，共63頁，2023年，2月20日，星期二以源程序作為輸入，不產(chǎn)生目標(biāo)程序，一邊解釋一邊執(zhí)行不產(chǎn)生目標(biāo)程序，每次執(zhí)行源程序，都必須解釋一次解釋程序特點：與編譯系統(tǒng)比較，解釋系統(tǒng)較簡單、可移植性好，易于查錯，但速度慢輸出數(shù)據(jù)解釋程序輸入數(shù)據(jù)源程序第20頁，共63頁，2023年，2月20日，星期二編譯（筆譯，程序到程序）由高級語言轉(zhuǎn)換為低級語言，如C，Pascal語言解釋

（口譯，語句到語句）接受某高級語言的一個語句輸入，進(jìn)行解釋并控制計算機(jī)執(zhí)行，馬上得到這句的執(zhí)行結(jié)果，然后再接受下一句。不產(chǎn)生目標(biāo)程序，直觀簡單，但效率低，如Basic語言翻譯：能把某種語言的源程序，在不改變語義的條件下，轉(zhuǎn)換成另一種語言程序——目標(biāo)語言程序。兩種實現(xiàn)方式：程序設(shè)計語言的轉(zhuǎn)換第21頁，共63頁，2023年，2月20日，星期二編譯程序是源程序的一個轉(zhuǎn)換系統(tǒng)解釋程序是源程序的一個執(zhí)行系統(tǒng)兩者在實現(xiàn)技術(shù)上并無很大差別，都要完成詞法分析、語法分析、語義分析等工作。編譯和解釋第22頁，共63頁，2023年，2月20日，星期二1.2編譯過程和編譯程序的結(jié)構(gòu)翻譯和編譯工作的比較翻譯外文編譯程序分析識別單詞分析句子根據(jù)語義進(jìn)行初步翻譯詞法分析語法分析語義分析、生成中間代碼綜合修辭加工寫出譯文代碼優(yōu)化目標(biāo)代碼生成第23頁，共63頁，2023年，2月20日，星期二編譯程序工作時，先分析，后綜合分析：指詞法分析和語法分析；綜合：指代碼優(yōu)化，存儲分配和代碼生成。為完成上述分析綜合任務(wù)，編譯程序采用對源程序進(jìn)行一次或多次掃描的辦法。如：第一遍掃描做詞法分析；第二遍掃描做語法分析；第三遍掃描做代碼優(yōu)化和存儲分配；第四遍掃描做代碼生成。編譯過程第24頁，共63頁，2023年，2月20日，星期二從輸入源程序開始到輸出目標(biāo)程序為止的整個過程可分為六個階段：詞法分析語法分析語義分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成對源程序結(jié)構(gòu)的分析編譯過程第25頁，共63頁，2023年，2月20日，星期二任務(wù)：根據(jù)詞法規(guī)則分析和識別單詞一、詞法分析單詞：是語言的基本語法單位

<1>保留字（如:if、else、while）

<2>標(biāo)識符（如:max、min、str）

<3>常數(shù)（如:12、6.8、’a’）

<4>算符、界符（如:+、-、*、/、;、（、））字符序列編碼形式第26頁，共63頁，2023年，2月20日，星期二詞法分析程序的結(jié)果-----二元式y(tǒng)=x+r*6單詞值單詞類別y標(biāo)識符=算符（賦值）x標(biāo)識符+算符（加號）r標(biāo)識符*算符（乘號）6常數(shù)第27頁，共63頁，2023年，2月20日，星期二Voidjisuan（）{inty,c,d;floatx,a,b;x=a+b*50;y=c+)d*(x+b;}請識別上段代碼中的單詞第28頁，共63頁，2023年，2月20日，星期二詞法分析(lexicalanalysisorscanning)--Thestreamofcharactersmakingupasourceprogramisreadfromlefttorightandgroupedintotokens,whicharesequencesofcharactersthathaveacollectivemeaning.單詞---token保留字---reservedword標(biāo)識符---identifier(user-definedname)相關(guān)術(shù)語第29頁，共63頁，2023年，2月20日，星期二任務(wù)：根據(jù)語法規(guī)則（即語言的文法），分析并識別出各種語法成分（如表達(dá)式、語句、函數(shù)等），并進(jìn)行語法正確性檢查。通過語法分解，確定整個輸入串是否構(gòu)成語法上正確的句子、程序等語法規(guī)則的表示：語法規(guī)則：規(guī)定單詞如何構(gòu)成短語、語句、過程、程序A::=B|CBNF表示二、語法分析（編譯的核心）第30頁，共63頁，2023年，2月20日，星期二A::=V:=EE::=T|E+TT::=F|T*FF::=V|(E)|CV::=標(biāo)識符C::=常數(shù)遞歸定義描述程序結(jié)構(gòu)的規(guī)則賦值語句語法分析的依據(jù)——語法規(guī)則第31頁，共63頁，2023年，2月20日，星期二賦值語句標(biāo)識符表達(dá)式表達(dá)式+表達(dá)式表達(dá)式標(biāo)識符整數(shù)標(biāo)識符:=表達(dá)式*Id1Id2Id360position:=initial+rate*60id1:=id2+id3*60第32頁，共63頁，2023年，2月20日，星期二id1:=id2+id3*60:=+N60*id1Positionid2initialid3rate第33頁，共63頁，2023年，2月20日，星期二推導(dǎo)（derive)、歸約(reduce)推導(dǎo)：從文法的開始符號開始，按照語法規(guī)則，每次選擇某規(guī)則右部的一個候選式取代左部，直至識別了語句或者找到錯誤為止。其過程可用語法樹描述歸約：按照語法規(guī)則，每次選擇某規(guī)則左部取代右部的一個候選式注：語法＝詞法規(guī)則＋語法規(guī)則語法分析的方法第34頁，共63頁，2023年，2月20日，星期二三、語義分析及中間代碼生成任務(wù)：依據(jù)語義規(guī)則對識別出的各種語法成分析其含義，并進(jìn)行初步翻譯，生成中間代碼。靜態(tài)：分析語法成份的含義，進(jìn)行語義上的正確性檢查動態(tài)：根據(jù)相應(yīng)語義，生成中間代碼（介于源語言和目標(biāo)語言之間的中間語言形式）第35頁，共63頁，2023年，2月20日，星期二生成中間代碼的目的：利于代碼優(yōu)化利于目標(biāo)代碼的移植中間代碼的形式： 四元式、三元式、逆波蘭表示第36頁，共63頁，2023年，2月20日，星期二四元式其中t1、t2、t3為編譯程序引入的臨時工作單元例：y=x+r*6運算符左運算對象右運算對象結(jié)果(1)inttoreal6--t1(2)*rt1t2(3)+t2xt3(4)=t3y第37頁，共63頁，2023年，2月20日，星期二任務(wù)：對中間代碼進(jìn)行加工變換，以得到高質(zhì)量（省時間、省空間）的目標(biāo)代碼四、代碼優(yōu)化依據(jù)原則：程序的等價變換規(guī)則主要優(yōu)化內(nèi)容公共子表達(dá)式提取、合并已知量、刪除無用賦值語句、循環(huán)優(yōu)化等第38頁，共63頁，2023年，2月20日，星期二t1=b*ct2=t1+0t3=b*ct4=t2+t3a=t4t1=b*ct2=t1+t1a=t2優(yōu)化舉例第39頁，共63頁，2023年，2月20日，星期二(1)(inttoreal60-t1)(2)(* id3t1t2)(3)(+ id2t2t3)(4)(:= t3- id1)id1:=id2+id3*60（1）(* id3 60.0 t2)(2）（+id2t2 id1 )(* id3 60.0 t2)(+ id2 t2 id1)優(yōu)化舉例第40頁，共63頁，2023年，2月20日，星期二目標(biāo)代碼的形式：絕對指令代碼：可立即執(zhí)行的代碼(如.exe)匯編指令代碼：匯編語言程序，需通過匯編程序匯編后才能運行可重定位的指令代碼：先將各目標(biāo)模塊連接起來，確定變量、常數(shù)在主存中的位置，裝入主存后才能成為可運行的絕對指令代碼（如.obj）五、目標(biāo)代碼生成任務(wù)：把中間代碼變換成特定機(jī)器上的低級語言代碼第41頁，共63頁，2023年，2月20日，星期二(* , id3 60.0 t1 )(+ , id2 t1 id1 )mov id3,R2mul #60.0,R2mov id2,R1add R2,R1mov R1,id1目標(biāo)代碼生成舉例第42頁，共63頁，2023年，2月20日，星期二目標(biāo)代碼生成程序代碼優(yōu)化程序語義分析生成中間代碼語法分析程序詞法分析程序編譯過程小結(jié)S.PO.P第43頁，共63頁，2023年，2月20日，星期二編譯程序結(jié)構(gòu)(components)典型的編譯程序具有7個邏輯部分S.PO.P語義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語法分析程序詞法分析程序錯誤處理符號表管理第44頁，共63頁，2023年，2月20日，星期二診察錯誤，并能報告用戶錯誤性質(zhì)和位置出錯處理能力的優(yōu)劣是衡量編譯程序質(zhì)量好壞的一個重要指標(biāo)。填表：把源程序中的信息和編譯過程中所產(chǎn)生的信息登記在表格中查表：在隨后的編譯過程中同時又要不斷的查找這些表格中的信息符號表管理錯誤處理第45頁，共63頁，2023年，2月20日，星期二編譯階段的組合根據(jù)編譯程序各部分功能，將編譯程序分成前端和后端前端：通常將與源程序有關(guān)的編譯部分稱為前端。 詞法分析、語法分析、語義分析、中間代碼生成

---分析部分特點：與源語言有關(guān)后端：與目標(biāo)機(jī)有關(guān)的部分稱為后端。代碼優(yōu)化、代碼生成---綜合部分特點：與目標(biāo)機(jī)有關(guān)第46頁，共63頁，2023年，2月20日，星期二源程序中間代碼目標(biāo)代碼僅依賴源程序僅依賴目標(biāo)計算機(jī)遍（PASS)：對輸入文件（源程序或其等價的中間形式）從頭到尾掃視，完成預(yù)定的處理。

遍輸入文件輸出文件前端后端編譯程序（器）的組織第47頁，共63頁，2023年，2月20日，星期二指對源程序或源程序的中間結(jié)果從頭到尾掃描一次，并做有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)代碼的過程。遍與階段的關(guān)系：每一遍掃視可完成一個或多個階段的工作一階段可分幾遍掃描遍的劃分視具體情況而定（內(nèi)存的大小、源語言的繁簡、目標(biāo)程序質(zhì)量的高低）遍（pass）第48頁，共63頁，2023年，2月20日，星期二語法分析掃描器語義子程序源程序目標(biāo)代碼編譯程序取單詞類號內(nèi)碼歸約返回優(yōu)點：不必產(chǎn)生中間代碼，可避免重復(fù)性工作，速度快；缺點：當(dāng)出現(xiàn)語法語義錯誤時，前面工作半途而廢，且不便于分工、優(yōu)化，結(jié)構(gòu)和算法不夠清晰。一遍掃描第49頁，共63頁，2023年，2月20日，星期二直接用機(jī)器語言編寫編譯程序用匯編語言編寫編譯程序注：編譯程序核心部分常用匯編語言編寫用高級語言編寫編譯程序注：這是普遍采用的方法編譯程序生成第50頁，共63頁，2023年，2月20日，星期二自編譯先對語言的核心部分構(gòu)造一個小小的編譯程序，再以它為工具構(gòu)造一個能編譯更多語言成分的較大編譯器，如此擴(kuò)展下去像滾雪球般，最后形成人們期望的整個編譯程序。通過一系列自展途徑形成編譯程序的過程稱為自編譯過程。編譯工具:LEX(詞法分析)與YACC(用于自動產(chǎn)生LALR分析表)移植（同種語言的編譯程序在不同類型的機(jī)器之間移植）編譯程序生成第51頁，共63頁，2023年，2月20日，星期二功能讓計算機(jī)執(zhí)行高級語言（basic,lisp,prolog)與編譯程序的不同1）不生成目標(biāo)代碼

2）能支持交互環(huán)境（同增量式編譯系統(tǒng)）源程序

初始數(shù)據(jù)解釋程序計算結(jié)果1.3高級語言解釋系統(tǒng)(interpreter)第52頁，共63頁，2023年，2月20日，星期二直接對源程序中的語句進(jìn)行分析，執(zhí)行其隱含的操作。如：……b:=2;a:=b+2;編譯程序

writea;……Mov#2.0r1Movr1bMovbr2Addr1r2Movr1a生成代碼解釋程序直接將4的值輸出（顯示）解釋系統(tǒng)第53頁，共63頁，2023年，2月20日，星期二編譯階段和運行階段存儲結(jié)構(gòu)編譯時運行時名字表目標(biāo)代碼緩沖區(qū)編譯用源程序中間表示各種表格源程序緩沖區(qū)目標(biāo)代碼區(qū)數(shù)據(jù)區(qū)解釋系統(tǒng)存儲結(jié)構(gòu)解釋系統(tǒng)源程序工作單元名字表標(biāo)號表緩沖區(qū)(輸入輸出)棧區(qū)第54頁，共63頁，2023年，2月20日，星期二語言范型(paradigms)命