1編譯原理西安電子科技大學計算理論與技術研究所王小兵xbwang@2相關領域程序設計語言的應用－程序設計（PLA）程序設計語言的翻譯－編譯器的構造（PLT）程序設計語言的設計－語法、語義（PLD）知識點

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

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號學生所選課程與成績SELECT學號,姓名,課程名,成績FROM學生,選課WHERE學生.學號="003";學號姓名性別001張梧男002李煦男003王沁女004劉荔女學號課程代碼課程名成績0010104離散數學800010205數據結構900030104離散數學850030205數據結構95學號姓名課程名成績003王沁離散數學85003王沁數據結構95對嗎？101.1從面向機器的語言到面向人類的語言[例3]Lex和Yacc

Lex的正規式：char(char|digit)*returnid Yacc的產生式：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從面向機器的語言到面向人類的語言按范型劃分的程序設計語言SimpleProceduralLanguages：FORTRANCBlock-StructuredProceduralLanguages：PascalObject-BasedLanguages：AdaC++SmalltalkFunctionalLanguages：LISPMLLogicProgrammingLanguages：PrologCC2002-PL過程式語言、面向對象語言：通用程序設計語言，如FORTRAN、Pascal、C/C++、Ada83/Ada95、Java等；函數語言：面向特點領域的、遞歸特性，如Lisp；說明性、非算法式語言：濃厚的數學特征，如LEX/YACC、SQL等；腳本式語言：僅是一種安排，如shell語言，XML等。121.1從面向機器的語言到面向人類的語言其他面向特定應用領域的語言計算機輔助設計：MATLAB集成電路設計：VHDL、Verilog虛擬現實與人機交互：VRML……問題：如何將形形色色的語言翻譯成可以在計算機上運行的0、1串？131.2語言之間的翻譯習慣稱法匯編語言－機器指令：匯編（或交叉匯編）程序設計語言－匯編語言或機器指令：編譯（或解釋）高級語言之間：轉換（或預編譯）逆向：反匯編、反編譯141.3編譯器與解釋器語言翻譯的兩種基本形態 先翻譯后執行 邊翻譯邊執行編譯器源程序目標程序目標程序輸入數據輸出解釋器源程序輸出輸入數據[例5]假設有源程序P：read(x);write("x=",x);

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

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

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

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