第1章 編譯原理引論

編譯原理

(CompilerPrinciples)主講:陳有英

E-Mail:cyyanswer@126.com編譯原理課程的地位和作用地位是軟件技術的基礎是計算機專業(yè)的基礎課程，是專業(yè)必修課是研究生入學考試的課程之一作用編譯原理是介紹如何將高級語言程序變換成低級語言程序的方法。其理論基礎堅實，其形式化系統(tǒng)不僅用于編譯程序，還大量用于人工智能、多媒體技術、數據庫等領域。編譯原理的相關技術可應用于其它許多領域a.文本編輯器、信息檢索系統(tǒng)、模式識別器b.排版、繪圖系統(tǒng)c.程序驗證器、語言程序的調試或測試工具、高級語言間的轉換工具d.集成電路設計e.外文翻譯學習任務和學習方法學習任務掌握編譯的理論基礎和形式化系統(tǒng)了解編譯的全部過程和具體實現方法（實驗）學習方法預習、聽課、練習、復習理解基本概念、基本原理和基本算法。弄懂例題，獨立完成課后作業(yè)。認真總結每章的要點，在理解的基礎上記憶。理論結合實踐，認真獨立地完成實驗。進行大量的閱讀，通過閱讀加強理解。參考書目Compilers:Principles,Techniques,andToolsAlfredV.AhoRaviSethiJeffreyD.Ullman人民郵電出版社CompilerConstructionPrincipleandPracticeKennethC.Louden機械工業(yè)出版社程序設計語言編譯原理陳火旺等國防工業(yè)出版社先修課程高級程序設計語言如：PascalCC++Fortran等匯編語言程序設計其它課程如：離散數學、數據結構等課程要求基礎理論：熟悉基于形式語言理論的編譯程序構造原理和高級語言的實現原理。基礎知識：全面掌握詞法分析、語法分析和語法制導翻譯方法等計算機處理技術，了解高級語言中各種語言成分的實現方法?；炯寄埽赫莆沼嬎銠C語言處理系統(tǒng)中各種通用的分析和翻譯技術，以及自動生成系統(tǒng)的運用。成績考核方法（1）平時成績30%課堂考勤10%平時作業(yè)10%上機實驗10%（2）考試成績70%課前思考及學習目標【課前思考】

自然語言的自動翻譯有什么哪些困難？

什么是編譯程序？

編譯過程和編譯程序的結構？【學習目標】

明確編譯程序的功能及其在計算機系統(tǒng)中的作用。

了解源語言程序被編譯為目標程序的整個過程，這個過程一般劃分為哪些階段？

了解解釋與編譯的差別。

知道編譯技術可用于哪類軟件的設計和開發(fā)。1）自然語言及其翻譯谷歌翻譯

百度翻譯例：我是一名教師。你是一個優(yōu)秀的學生。2）計算機語言及其編譯高級語言：接近人類自然語言。匯編語言：一般為機器語言的記號系統(tǒng)，便于記憶。低級語言：0、1代碼的語言，計算機能夠認識的語言。問題：書寫程序用什么語言？－－高級語言，甚至自然語言。問題：可是，計算機根本就“聽不懂”高級語言，怎么辦？－－給它聘請一個翻譯，即編譯程序，亦稱編譯器。用戶高級語言程序計算機二進制代碼編譯編寫執(zhí)行匯編指令第1章引論1.1什么是編譯程序1.2編譯過程和編譯程序的結構1.2.1編譯過程1.2.2編譯程序結構1.2.3編譯階段的組合1.3解釋程序和一些軟件工具1.3.1解釋程序1.3.2處理源程序的軟件工具1.4程序設計語言范型程序設計語言低級語言特定的計算機系統(tǒng)所固有的語言即：機器語言、匯編語言特點：執(zhí)行效率高、編制效率低高級語言與自然語言比較接近的語言如：過程式語言：C,Pascal,Fortran,ADA對象式語言：Java,C++等函數式語言：LISP邏輯式語言：Prolog特點：執(zhí)行效率低、編制效率高1.1什么是編譯程序一、編譯程序（又稱“編譯器”）是語言的翻譯器功能：高級語言的源程序低級語言的目標程序重要性：使編程者不必考慮與機器有關的細節(jié)本課程主要研究：順序過程式語言的編譯原理和技術源程序預處理程序源程序編譯程序匯編程序裝配/連接程序目標匯編程序可再裝配的機器代碼絕對機器代碼將機器代碼與一些庫文件連接匯集分散的源程序、宏展開、…二、高級語言程序的處理過程三、編譯程序的分類一趟編譯多趟編譯具有調試、優(yōu)化功能的編譯都使用相同的基本編譯技術??！1、20世紀50年代早期：將計算公式翻譯成機器碼2、20世紀50年代中期：出現了FORTRAN等一批高級語言

（也就出現了相應的編譯程序）3、20世紀50年代后期：出現了編譯程序的編譯程序

（即編譯程序的自動生成工具）4、20世紀60年代：用自展技術構造編譯程序

（用被編譯語言書寫其自身的編譯程序，1971年PASCAL的成功）5、并行技術與并行語言的發(fā)展：——發(fā)展方向并行語言的并行編譯自動并行編譯技術（將串行程序轉換成并行程序）四、編譯程序的歷史和發(fā)展1.2編譯過程和編譯程序的結構一、編譯過程表格管理詞法分析語法分析語義分析中間代碼生成代碼優(yōu)化目標代碼生成出錯處理源程序目標程序詞法分析任務：從左到右讀入源程序的每個字符，對構成源程序的字符流進行掃描和分解，從而識別出一個個單詞（也叫單詞符號或符號）。單詞是具有獨立意義的最小語法單位。如：標識符、保留字（關鍵字或基本字）、算符、界符、常數等。例.某源程序片斷如下：beginvarsum,first,count:real;sum:=first+count*10end.保留字 begin保留字 var標識符 sum逗號 ,標識符 first逗號 ,標識符 count冒號 :保留字 real分號 ;標識符 sum賦值號 :=標識符 first加號 +標識符 count乘號 *整數 10保留字 end界符 .語法分析任務：依據語言的語法規(guī)則，確定源程序的輸入串是否構成一個語法上正確的程序。最終將單詞序列分解成各類語法短語（也叫語法單位），如“程序”、“語句”、“表達式”等。語法：由程序語言基本符號組成程序中各個語法成分的一組規(guī)則。一般語法規(guī)則：由單詞符號構成語法成分的規(guī)則；詞法規(guī)則：由基本符號構成的符號書寫規(guī)則。舉例：id1:=id2+id3*10

的語法樹賦值語句標識符表達式表達式+表達式表達式標識符整數標識符:=表達式*id1sumid2

firstid3

count10id1:=id2+id3*10

的語法樹的另一種形式:=id1+id2*id310程序結構的遞歸表示表達式的表示：1）任何標識符是表達式。2）任何常數（整常數、實常數）是表達式。3）若表達式1和表達式2都是表達式，那么表達式1+表達式2表達式1*表達式2（表達式1）都是表達式。語句的表示：1）標識符:=表達式是語句2）while(表達式)do語句是語句3）if(表達式)then語句else語句是語句語義分析任務：審查源程序有無語義錯誤，為代碼生成階段收集類型信息。主要功能：類型檢查、報語義錯誤、類型轉換等語義：是程序設計語言中按語法規(guī)則構成的各個語法成分的意義。靜態(tài)語義：編譯時刻即可確定的語法成分含義。動態(tài)語義：運行時刻才能確定的語法成分含義。語義分析:=id1+id2*id310inttorealrealfirst,count,sum……sum:=first+count*10舉例：類型檢查和轉換中間代碼生成任務：在語法和語義分析之后，將源程序變成一種“內部表示形式”。

中間代碼：一種結構簡單、含義明確的記號系統(tǒng)。特征：1）結構簡單、含義明確2）復雜性介于源語言和機器語言之間3）容易生成；4）容易將它翻譯成目標代碼。四元式：（運算符，運算對象1，運算對象2，結果）四元式：（運算符，運算對象1，運算對象2，結果）舉例：源程序sum:=first+count*10生成的四元式可以是：(inttoreal, 10, -, t1)(* , id3, t1, t2)(+ , id2, t2, t3)(:= , t3, -, id1):=id1+id2*id310inttoreal波蘭表示問題——Lukasiewicz1929/1951年發(fā)明

中綴表示(Infixnotation):(a+①b)*(-c+②d)+③e/f波蘭表示（Polish/Prefix/Parenthesis-free/Lukasiewicznotation）——也就是前綴表示+③*+①ab+②@cd/ef運算順序從右向左逆波蘭表示(ReversePolish/Suffix/Postfixnotation)——也就是后綴表示

ab+①c@d+②*ef/+③運算順序從左向右代碼優(yōu)化任務：對中間代碼進行變換或改造，使之更為高效（時間、空間）。

(inttoreal, 10, -, t1)(* , id3, t1, t2)(+ , id2, t2, t3)(:= , t3, -, id1)(*, id3, 10.0, t2)(+, id2, t2, id1)(* id3 10.0 t1)(+ id2 t1 id1)目標代碼生成任務：把中間代碼變換成特定機器上的絕對指令代碼或可重定位的機器指令代碼或匯編指令代碼。特點：1）與硬件系統(tǒng)結構和指令含義有關，涉及到硬件系統(tǒng)功能部件的運用、機器指令的選擇、各種數據類型變量的存儲空間分配以及寄存器和后緩寄存器的調度等。2）高級語言低級語言轉換是基于語義的等價變換，不是結構上的變換。(* id3 10.0 t1)(+ id2 t1 id1)sum:=first+count*10MOVF id3, R2MULF #10.0, R2MOVF id2, R1ADDF R1, R2MOV R1, id1表格管理任務：用于保存源程序的各種信息。因為上述各階段工作均需要查找、更新、構造表格。管理各種符號表（常數、標號、變量、過程、結構……），查、填（登記、查找）源程序中出現的符號和編譯程序生成的符號，為編譯的各個階段提供信息。輔助語法檢查、語義檢查完成靜態(tài)綁定、管理編譯過程Hash表、鏈表等各種查、填表技術出錯處理任務：報告源程序中錯誤的性質、地點，將錯誤所造成的影響限制在盡可能小的范圍。有些編譯程序還可以自動糾錯。一個程序是正確的，包括兩層含義：

1）書寫正確（合乎語法規(guī)則）

2）含義正確（合乎語義規(guī)則）說明多數實用的編譯程序都采用以上幾個階段的工作過程。有些編譯程序沒有“中間代碼生成”和“代碼優(yōu)化”。

詞法分析

語法分析

語義分析中間代碼生成

優(yōu)化目標代碼生成目標代碼源程序

符號表管理

錯誤診查處理

二、編譯程序的結構例一個語句的翻譯三、編譯階段的組合前端：主要依賴于源語言而與目標機器無關的編譯階段。如：詞法分析、語法分析、語義分析、中間代碼生成、部分代碼優(yōu)化、與前端有關的出錯處理工作和表格管理工作。后端：依賴于目標機而一般不依賴于源語言，只與中間代碼有關的編譯階段。如：目標代碼生成，以及相關出錯處理和表格處理。遍（趟）：對源程序或其等價的中間語言程序從頭到尾掃視并完成規(guī)定任務的過程。每一遍掃視可完成編譯的一個階段或多個階段工作。多遍編譯：占內存少，邏輯結構清晰，耗時長一遍編譯：占內存多，邏輯結構不清晰，耗時短1.3解釋程序和一些軟件工具一、解釋程序接受高級語言程序，并立即運行這個源程序。例如：BASIC語言解釋程序，LISP解釋程序，SQL解釋程序，Java語言中的BYTECODE解釋程序解釋程序源程序輸入數據結果編譯程序高級語言程序（源程序）低級語言程序（目標程序）解釋程序源程序結果輸入數據運行程序輸入數據結果編譯與解釋的根本區(qū)別：是否生成目標代碼。二、解釋程序與編譯程序的比較三、解釋程序的優(yōu)、缺點優(yōu)點：可移植性較好。缺點：（1）速度慢（2）空間開銷大有些語言既有編譯程序，又有解釋程序。四、處理源程序的軟件工具1語言的結構化編輯器正文編輯、修改對源程序正文進行分析（檢查用戶輸入是否正確、自動提供關鍵字、檢查括號的匹配情況）2語言程序的調試工具

了解程序執(zhí)行的結果與編程人員的意圖是否一致允許用戶一行一行跟蹤程序，查看變量值的變化3程序格式化工具

分析源程序，并使程序結構變得清晰可讀（如縮排）四、處理源程序的軟件工具4語言程序測試工具靜態(tài)分析器：不運行源程序，就可以發(fā)現其中潛藏的錯誤或異常。動態(tài)分析器：對源程序進行分析，把記錄和顯示程序執(zhí)行軌跡的語句或函數插入源程序，將運行結果與期望結果進行比較和分析。5程序理解工具

對程序進行分析，確定模塊間的調用關系，并畫出控制流程圖。6高級語言之間的轉換工具將一種高級語言程序轉換成另一種高級語言程序1.4程序設計語言范型一、強制式語言（過程式語言、命令式語言）由一系列的語句組成，每個語句的執(zhí)行引起若干存儲單元中值的改變。如：C，Fortran，Pascal二、函數式語言（應用式語言）從前面已有的函數出發(fā)構造出更復雜的函數。Functionn(…Function2(Function1(data))…)如：ML，LISP1.4程序設計語言范型三、基于規(guī)則的語言（基于邏輯的語言）檢查一定的使能條件，當它滿足時，則執(zhí)行適當的動作。條件動作如：PROLOG四、面向對象語言提供抽象數據類型，支持封裝性、繼承性和多態(tài)性。如：Ada，C++，Java練習1、程序語言一般分為（1）和（2）兩大類。其中（3）與人類自然語言比較接近，（4）又稱為面向機器的語言。

A高級語言

B專用程序語言

C低級語言

D通用程序語言ACAC練習2、面向機器的語言是指（1），其特點是（2）。（1） A.用于解決機器硬件設計問題的語言 B.特定計算機系統(tǒng)所固有的語言 C.各種計算機系統(tǒng)都通用的語言 D.只能在一臺計算機上使用的語言（2） A.程序執(zhí)行效率低，編寫效率低，可讀性差 B.程序執(zhí)行效率低，編寫效率高，可讀性強 C.程序執(zhí)行效率高，編寫效率高，可讀性強 D.程序執(zhí)行效率高，編寫效率低，可讀性差BD練習3、編譯程序是將（1）翻譯成（2）；匯編程序是將（3）翻譯成（4）。 A.匯編語言程序 B.高級語言程序 C.機器語言程序 D.匯編語言程序或機器語言程序 E.匯編語言程序或高級語言程序BDAC練習4、編譯程序的工作過程可以劃分為（1）等六個階段，同時還伴有（2）和（3）。（1）詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化、目標代碼生成。（2）表格管理 （3）出錯處理5、編譯程序可以發(fā)現源程序的全部（1）錯誤和部分（2）錯誤。 A.語用 B.語義

C. 語法 D.運行CB練習6、要在某臺機器上為某種語言構造一個編譯程序（編譯器），必須掌握的內容有（1）。 A.匯編語言 B.源語言 C.目標語言 D.程序設計方法學 E.編譯方法 F.測試方法 G.機器語言BCE7、一個編譯程序，不僅包含詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化和目標代碼生成，還應包括（1）。 其中（2）和（3）不是每個編譯程序都必需的。 詞法分析器用于識別（4）。 語法分析器可以發(fā)現源程序中的（5）。

（1）表格處理和出錯處理 （2）中間代碼生成 （3）代碼優(yōu)化（4）單詞（5）語法錯誤練習8、程序語言的語言處理程序是一種（1）。（2）都是程序語言的處理程序，兩者的主要區(qū)別在于（3）。（1） A.系統(tǒng)軟件 B.應用軟件 C.實時軟件 D.分布式系統(tǒng)軟件（2） A.高級語言程序和低級語言程序

B.解釋程序和編譯程序 C.編譯程序和操作系統(tǒng) D.系統(tǒng)程序和應用程序（3） A.單用戶與多用戶的差別

B.對用戶程序的查錯能力不同 C.機器執(zhí)行的效率不同 D.是否生成目標代碼 ABD練習9、編譯器必須完成的工作有（1）。A.

詞法分析B.

語法分析C.

語義分析D.