西安電子科技大學(xué)編譯原理復(fù)試第一章 引言

1編譯原理西安電子科技大學(xué)計算理論與技術(shù)研究所王小兵xbwang@2相關(guān)領(lǐng)域程序設(shè)計語言的應(yīng)用－程序設(shè)計（PLA）程序設(shè)計語言的翻譯－編譯器的構(gòu)造（PLT）程序設(shè)計語言的設(shè)計－語法、語義（PLD）知識點

中國計算機科學(xué)與技術(shù)學(xué)科教程(CCC2002)程序設(shè)計基礎(chǔ)(PF)：程序設(shè)計基本結(jié)構(gòu)、算法與問題求解、基本數(shù)據(jù)結(jié)構(gòu)、遞歸、事件驅(qū)動程序設(shè)計。(PLA)程序設(shè)計語言(PL)：程序設(shè)計語言概論、虛擬機、語言翻譯簡介、聲明和類型、抽象機制、面向?qū)ο蟪绦蛟O(shè)計(核心)；函數(shù)程序設(shè)計、語言翻譯系統(tǒng)、類型系統(tǒng)、程序設(shè)計語言的語義、程序設(shè)計語言的設(shè)計(選修)。(PLA、PLT、PLD)課程簡介3課程簡介目的了解PL的基本要素、工作原理、語言翻譯的基本方法；用不同的PL進行程序設(shè)計，即自學(xué)計算機語言的能力；具備語言翻譯的基本技能；了解計算機科學(xué)的基礎(chǔ)理論；課程特點提高自學(xué)能力；理論與實踐并重；理論的演變是緩慢的、理論基礎(chǔ)是相通的；相同的原理可應(yīng)用于不同的技術(shù)；適應(yīng)飛速變化的技術(shù)的根本是注重基礎(chǔ)理論學(xué)習；4課程簡介教材劉堅編譯原理基礎(chǔ)西電出版社劉堅《編譯原理基礎(chǔ)》習題與上機解答西電出版社參考書目呂映芝等編譯原理清華大學(xué)出版社陳火旺等程序設(shè)計語言編譯原理國防工業(yè)出版社Aho等編譯原理技術(shù)與工具人民郵電出版社AndrewW.Appel現(xiàn)代編譯程序?qū)崿F(xiàn)－Java語言高等教育出版社StevenS.Muchnick高級編譯器設(shè)計與實現(xiàn)機械工業(yè)出版社Hopcroft等自動機理論、語言和計算機導(dǎo)論機械工業(yè)出版社5課程簡介學(xué)習方法要作筆記；多思考，勤發(fā)問；多實踐、以用促學(xué)；合理使用參考解答；作業(yè)與上機提前一星期通知交作業(yè)；驗收上機題，并交上機報告；6往屆學(xué)生報告編譯原理是四大天書中的天書，事實上沒有那么恐怖。第二、三章只要多看書，勤做作業(yè)，學(xué)好也不難。第四、五章盡管沒有涉及算法，但是它與程序的運行方面有很大關(guān)系，理解起來還是比較吃力的。課隨好學(xué)，但是上機就困難了，由于平時編程方面的欠缺，對于程序如何組織，如何編寫，總感覺無從下手。7往屆學(xué)生報告函數(shù)繪圖語言采用的分析方法是遞歸子程序，優(yōu)點是分析方法非常簡單易懂，但涉及到大量棧存儲空間操作，大大降低了分析的效率。實際中的編譯器和解釋器的構(gòu)造方法通常采用自動化工具（Lex/Yacc），其語法分析大部分采用LALR(1)文法，其驅(qū)動器具有通用性，與文法無關(guān)，效率高，但分析表十分復(fù)雜，難于手工構(gòu)造。8第一章引言1.1從面向機器的語言到面向人類的語言面向機器的語言：機器指令、匯編語言面向人類的語言：通用程序設(shè)計語言、非過程式語言計算機語言舉例[例1]通用程序設(shè)計語言與匯編語言（包括機器指令）

Pascal語句：x:=a+b；

C++語句： x=a+b； 匯編指令： 十六進制代碼

匯編指令

A10002 MOVAX,[A] 8B1E0202 MOVBX,[B] 01D8 ADDAX,BX A30402 MOV[X],AX91.1從面向機器的語言到面向人類的語言[例2]SQL：查詢003號學(xué)生所選課程與成績SELECT學(xué)號,姓名,課程名,成績FROM學(xué)生,選課WHERE學(xué)生.學(xué)號="003";學(xué)號姓名性別001張梧男002李煦男003王沁女004劉荔女學(xué)號課程代碼課程名成績0010104離散數(shù)學(xué)800010205數(shù)據(jù)結(jié)構(gòu)900030104離散數(shù)學(xué)850030205數(shù)據(jù)結(jié)構(gòu)95學(xué)號姓名課程名成績003王沁離散數(shù)學(xué)85003王沁數(shù)據(jù)結(jié)構(gòu)95對嗎？101.1從面向機器的語言到面向人類的語言[例3]Lex和Yacc

Lex的正規(guī)式：char(char|digit)*returnid Yacc的產(chǎn)生式：E:E'+'E|E'*'E|id[例4]Unix的shell命令

SHELL=/bin/sh #includeenv_precomp.mk CPDIR=/u/pbsrc/chp ORAHOME=/oracle/app/oracle/product/734

111.1從面向機器的語言到面向人類的語言按范型劃分的程序設(shè)計語言SimpleProceduralLanguages：FORTRANCBlock-StructuredProceduralLanguages：PascalObject-BasedLanguages：AdaC++SmalltalkFunctionalLanguages：LISPMLLogicProgrammingLanguages：PrologCC2002-PL過程式語言、面向?qū)ο笳Z言：通用程序設(shè)計語言，如FORTRAN、Pascal、C/C++、Ada83/Ada95、Java等；函數(shù)語言：面向特點領(lǐng)域的、遞歸特性，如Lisp；說明性、非算法式語言：濃厚的數(shù)學(xué)特征，如LEX/YACC、SQL等；腳本式語言：僅是一種安排，如shell語言，XML等。121.1從面向機器的語言到面向人類的語言其他面向特定應(yīng)用領(lǐng)域的語言計算機輔助設(shè)計：MATLAB集成電路設(shè)計：VHDL、Verilog虛擬現(xiàn)實與人機交互：VRML……問題：如何將形形色色的語言翻譯成可以在計算機上運行的0、1串？131.2語言之間的翻譯習慣稱法匯編語言－機器指令：匯編（或交叉匯編）程序設(shè)計語言－匯編語言或機器指令：編譯（或解釋）高級語言之間：轉(zhuǎn)換（或預(yù)編譯）逆向：反匯編、反編譯141.3編譯器與解釋器語言翻譯的兩種基本形態(tài) 先翻譯后執(zhí)行 邊翻譯邊執(zhí)行編譯器源程序目標程序目標程序輸入數(shù)據(jù)輸出解釋器源程序輸出輸入數(shù)據(jù)[例5]假設(shè)有源程序P：read(x);write("x=",x);

編譯器P目標程序目標程序3x=3解釋器x=3P3151.3編譯器與解釋器編譯器源程序目標程序目標程序輸入數(shù)據(jù)輸出解釋器源程序輸出輸入數(shù)據(jù)特點編譯器：工作效率高，即時間快、空間?。唤换バ耘c動態(tài)特性差、可移植性差。被大多數(shù)PL的翻譯所采用；解釋器：工作效率低，即時間慢、空間費；交互性與動態(tài)特性好、可移植性好。早期的Basic和現(xiàn)在的Java等?；竟δ埽憾呦嗤?；采用技術(shù)：從翻譯的角度來講，兩種方式所涉及的原理、方法、技術(shù)相似。161.4編譯器的工作原理與基本組成通用程序設(shè)計語言的主要成份從語言抽象的演變看： 過程→抽象數(shù)據(jù)類型（ADT，程序包）→類共同特點：兩大部分組成，聲明＋操作＝完整定義以過程式語言為例：聲明性語句：提供操作對象的性質(zhì)，如數(shù)據(jù)類型、值、作用域等；操作性語句：確定操作的計算次序，完成實際操作。過程頭＋過程體＝過程定義

編譯器對兩類語句的翻譯：聲明：生成相應(yīng)的環(huán)境，一般是配置存儲空間；操作：生成可執(zhí)行的代碼序列。171.4編譯器的工作原理與基本組成[例6]一Pascal的過程如下：(1)proceduresample(y:integer); {過程頭}(2)varx:integer; {過程體（開始）}(3)beginx:=y;(4)ifx>100thenx:=0(5)end; {過程體（結(jié)束）}(1)：聲明，提供調(diào)用信息，如過程名、參數(shù)、返回值等。（接口）(2)至(5)：過程體，可含聲明或操作。（實現(xiàn)）。編譯器對聲明性語句的處理一般是生成相應(yīng)的環(huán)境（存儲空間），對操作性語句則是生成此環(huán)境中的可執(zhí)行代碼序列。為便于編譯器的處理，操作性語句中使用的每個操作對象，均應(yīng)在使用前聲明，即符合先聲明后引用的原則。181.4編譯器的工作原理與基本組成以階段劃分編譯器自然語言的翻譯過程： 識別單詞 識別句子結(jié)構(gòu) 理解意思 譯成中文并修飾編譯器的工作過程： 詞法分析 語法分析 語義分析 目標代碼生成編譯器的階段（邏輯模塊）中間代碼的重要作用191.4編譯器的工作原理與基本組成編譯器各階段的工作[例7]Pascal源程序語句如下：

varx,y,z:real; x:=y+z*60;（源程序）varx,y,z:real;x:=y+z*60;

（記號流）varid1,id2,id3:real;id1:=id2+id3*60;（語法樹）詞法分析語法分析201.4編譯器的工作原理與基本組成語義分析中間代碼生成(1)(itr,60,, T1)(2)(*,id3,T1, T2)(3)(+,id2,T2, T3)(4)(:=,T3,,id1)中間代碼的形式與作用：(序號)(op，arg1,arg2,result)result:=arg1oparg2211.4編譯器的工作原理與基本組成(1)(itr,60,, T1)(2)(*,id3,T1, T2)(3)(+,id2,T2, T3)(4)(:=,T3,,id1)中間代碼優(yōu)化(1)(*,id3,60.0,T1)(2)(+,id2,T1,id1)MOVF id3,R2MULF #60.0,R2MOVF id2,R1ADDFR2,R1MOVF R1,id1目標代碼生成R2:=id3R2:=R2*60.0R1:=id2R1:=R1+R2id1:=R1id1:=id2+id3*60.0x:=y+z*60;221.4編譯器的工作原理與基本組成各階段工作的歸納

詞法分析：識別單詞，至少分以下幾大類：關(guān)鍵字（保留字）、標識符、字面量、特殊符號；語法分析：得到語言結(jié)構(gòu)并以樹的形式表示；語義分析：考察結(jié)構(gòu)正確的句子是否語義合法，修改樹結(jié)構(gòu)；中間代碼生成（可選）：生成一種既接近目標語言，又與具體機器無關(guān)的表示，便于優(yōu)化與代碼生成；（到目前為止，編譯器與解釋器可以一致）231.4編譯器的工作原理與基本組成中間代碼優(yōu)化（可選）：局部優(yōu)化、循環(huán)優(yōu)化、全局優(yōu)化等；優(yōu)化實際上是一個等價變換，變換前后的指令序列完成相同功能，但在占用的空間上和程序執(zhí)行的時間上都更省、更有效。目標代碼生成：不同形式的目標代碼－匯編、可重定位、內(nèi)存形式（Load-and-Go）;符號表管理：合理組織符號，便于各階段查找、填寫等；出錯處理：錯誤的種類－詞法錯、語法錯、靜態(tài)語義錯、動態(tài)語義錯。241.4編譯器的工作原理與基本組成編譯器的分析/綜合模式

前端：語言結(jié)構(gòu)和意義的分析；后端：語言意義處理；中間代碼：前端與后端的分界；251.4編譯器的工作原理與基本組成編譯器基礎(chǔ)架構(gòu)(Infrastructure)：源代碼的中間表示、一組前端、一組后端；261.4編譯器的工作原理與基本組成編譯器掃描的遍數(shù)每個階段將程序完整分析一遍的工作模式稱為一遍掃描。確定掃描遍數(shù)的因素有：軟、硬件條件，如內(nèi)存太小，或全局優(yōu)化語言結(jié)構(gòu)，如規(guī)定標識符的先聲明后引用x:=f(a);…functionf(a:integer):integer;編譯技術(shù)，如拉