編譯原理chpt1

1、編譯原理課程信息編譯程序的用途和地位：編譯程序的用途和地位：u計算機只直接認識0、1序列u怎么辦？配翻譯！u回顧回顧: 程序上機過程 高級語言書寫的程序 編譯程序低級語言程序u地位：計算機（系統(tǒng)及課程體系）的核心、基礎(chǔ)。u目標：(1)理解編譯程序是如何工作的； (2)對任何一個程序設(shè)計語言，如何實現(xiàn)它； (3)編譯構(gòu)造工具的實現(xiàn)及使用； (4)能將常用技術(shù)和算法應(yīng)用于軟件的設(shè)計和實現(xiàn)中。為什么學習編譯？編譯是與數(shù)據(jù)結(jié)構(gòu)、OS等同樣重要的基礎(chǔ)性課程專業(yè)基礎(chǔ)能力的四個方面：計算思維、算法設(shè)計、程序?qū)崿F(xiàn)和系統(tǒng)開發(fā)在編譯中都有較為充分的體現(xiàn)編譯程序的構(gòu)造原理和技術(shù)可以說是計算機科學技術(shù)中理論和實踐相結(jié)

2、合的最好典范學習編譯才能透徹理解、熟練運用程序設(shè)計語言日后科研工作中將長期受益，是優(yōu)秀專業(yè)人員必修課圖靈獎獲得者Perlis教授的名言“To understand a program you must become both the machine and the program.”。編譯有助于你達成這個愿望編寫編譯器的原理和技術(shù)具有十分普遍的意義，以至于在每一個計算機科學家的研究生涯中，它的原理和技術(shù)都回反復用到 。措施：作業(yè)、提問、上機、測驗、討論、計算思維是什么計算思維是什么n計算思維（計算思維（Computational Thinking）計算思維計算思維是運用計算機科學的基礎(chǔ)概念去求

3、解問是運用計算機科學的基礎(chǔ)概念去求解問題、設(shè)計系統(tǒng)和理解人類的行為，它包括了一系題、設(shè)計系統(tǒng)和理解人類的行為，它包括了一系列廣泛的計算機科學的思維工具列廣泛的計算機科學的思維工具 計算思維和閱讀、寫作和算術(shù)一樣，是計算思維和閱讀、寫作和算術(shù)一樣，是21世紀每世紀每個人的基本技能，而不僅僅屬于計算機科學家個人的基本技能，而不僅僅屬于計算機科學家計算思維在生物、物理、化學、經(jīng)濟學、統(tǒng)計學計算思維在生物、物理、化學、經(jīng)濟學、統(tǒng)計學等其他學科中的影響已經(jīng)顯現(xiàn)等其他學科中的影響已經(jīng)顯現(xiàn) n計算思維包括一系列廣泛的計算機科學的思計算思維包括一系列廣泛的計算機科學的思維方法維方法遞歸遞歸抽象和問題分解抽象和

4、問題分解保護、冗余、容錯、糾錯和恢復保護、冗余、容錯、糾錯和恢復利用啟發(fā)式推理來尋求解答利用啟發(fā)式推理來尋求解答在不確定情況下的規(guī)劃、學習和調(diào)度在不確定情況下的規(guī)劃、學習和調(diào)度課程特點：1 理論和實踐并重的課程2 記分方法： 上機(50)平時(20)期末筆試(30)教師聯(lián)系信息教師聯(lián)系信息王顯榮：電話 4994019-？ 辦公室 計算機樓210房間 教材及主要參考書n教材：編譯原理（第2版），張素琴、呂映芝等，清華大學出版社 2004n參考書：Compilers: Principles, Technigues, and Tools(Second Edition) Alfred V.Aho, M

5、onica S.Lam, Ravi Sethi, Jeffrey D.Ullman, Addison-Wesley, 2007n參考書:編譯原理，陳意云、張昱，高等教育出版社 2003教學內(nèi)容簡介1 編譯程序概述 詞法分析、語法分析、語義分析、中間代碼生成、目標代碼生成、代碼優(yōu)化、符號表管理和錯誤處理等成分。 編譯成分的主要功能、編譯階段的邏輯關(guān)系？2 PL/0 編譯程序剖析通過剖析一個用C語言實現(xiàn)的PL/0語言的編譯程序以理解各編譯成分的功能及手工實現(xiàn)方法。3 高級語言的認識 理解和定義程序設(shè)計語言是學習和構(gòu)造編譯程序的前提。 每個程序設(shè)計語言都包含語法和語義兩個基本方面。 上下文無關(guān)文法給

6、出程序設(shè)計語言的精確的,易于理解的語法說明。流行的描述語義規(guī)則的方法屬性文法。4 詞法分析程序的自動構(gòu)造 詞法分析程序的主要任務(wù)是掃描源程序，按構(gòu)詞規(guī)則識別單詞，并報告發(fā)現(xiàn)的詞法錯誤。 正則表達式和有窮狀態(tài)自動機分別作為單詞的描述工具和識別機制。5 語法分析程序的構(gòu)造n自頂向下的語法分析。相當于從根開始，按前序生成結(jié)點，為輸入串構(gòu)造分析樹的過程。討論預測分析法，介紹對于LL(1)文法, 如何自動構(gòu)造預測分析程序 n自底向上語法分析法：對輸入符號串自左向右掃描，并將輸入符依次移入棧中，邊移進邊分析，一旦棧頂形成可歸約串，就將其替換為相應(yīng)非終結(jié)符，重復此過程，直到棧中只剩文法的開始符時，成功結(jié)束。

7、n介紹LR分析法，LR分析表的構(gòu)造原理。6 語義分析和中間代碼生成引入屬性文法和語法制導翻譯的概念，介紹中間代碼，針對一些語法成分討論相應(yīng)語義處理工作的描述。7 符號表介紹符號表的一般組織和使用方法，討論分程序結(jié)構(gòu)語言的名字作用域分析及符號表設(shè)計方案。8 運行時的存儲組織和管理生成目標程序之前，編譯程序必須對目標程序運行時的數(shù)據(jù)空間進行組織和安排。主要討論棧式存儲分配。9 代碼優(yōu)化和目標代碼生成介紹優(yōu)化技術(shù)，優(yōu)化分類以及優(yōu)化工作的基礎(chǔ)控制流和數(shù)據(jù)流分析問題。將討論目標代碼生成程序設(shè)計的一般問題，包括指令選擇，寄存器分配和計算順序選擇。目錄n第一章 引論n第二章 PL/0編譯系統(tǒng)n第三章 詞法分

8、析程序及其自動構(gòu)造n第四章 文法和語言n第五章 預測分析、算符優(yōu)先分析n第六章 LR分析程序及其自動構(gòu)造n第七章 語法制導翻譯和中間代碼n第八章 代碼優(yōu)化n第九章 其它編譯技術(shù)第1章 概述1.1 編譯程序及其結(jié)構(gòu)1.2 程序設(shè)計語言的實現(xiàn)途徑1.3 編譯程序的實現(xiàn)方式1.4 編譯技術(shù)的應(yīng)用-處理源程序的軟件工具1.5 編譯技術(shù)的發(fā)展一、編譯程序的作用u計算機只直接認識0、1序列u它如何處理各種高級語言程序？配翻譯?。ㄕ绮欢⒄Z的人可通過翻譯與說英語的人交談一樣）u回顧回顧: 程序上機過程1.1 編譯程序及其結(jié)構(gòu)(compiler) 高級語言書寫的程序 編譯程序低級語言程序 目標程序匯編語言（

9、符號化的指令系統(tǒng)）、機器語言 源程序pascal、c、易學、易用、易讀、易改、易移植n語言轉(zhuǎn)(變)換系統(tǒng)n編譯系統(tǒng)的結(jié)構(gòu)、工作流程、設(shè)計原理和基本實現(xiàn)技術(shù)？C+編譯器C+CJavaBytecodeJava編譯器操作系統(tǒng)編譯系統(tǒng)裸機術(shù)語n編譯程序(compiler)n編譯程序的源語言(源程序) (source language)(source program)n編譯程序的目標語言(目標程序) (object or target language)(object or target program) n編譯程序的實現(xiàn)語言(implementation language)n語言處理程序(langua

10、ge processor)n語言轉(zhuǎn)（變）換(language transformation)二、編譯邏輯過程n詞法分析n語法分析n語義分析n中間代碼生成n代碼優(yōu)化n目標代碼生成從左至右掃描字符流的源程序、分解構(gòu)成源程序的字符串，拼出一個個的單詞 單詞符號是語言中具有獨立意義的最基本結(jié)構(gòu)。多數(shù)程序語言中，單詞符號一般包括 各類型的常數(shù)、保留字、標識符、運算符、界符等等。n單詞-tokenn保留字-reserved wordn標識符 -identifier(user-defined name)詞法分析(lexical analysis or scanning) -The stream of cha

11、racters making up a source program is read from left to right and grouped into tokens,which are sequences of characters that have a collective meaning. （字母組成的有集體含義的最小成分）語言的單詞符號是由詞法規(guī)則所確定的。詞法規(guī)則規(guī)定了啥樣的字符串是一個單詞符號position := initial + rate * 60;單詞類型單詞類型單詞值單詞值 標識符1(id1) position 算符(賦值) := 標識符2(id2) initial

12、 算符(加) + 標識符3(id3) rate 算符(乘) * 整數(shù) 60 分號 ；語法分析(Syntax Analysis or parsing)n功能：層次分析，依據(jù)依據(jù)源程序的語法規(guī)則語法規(guī)則把源程序的單詞序列組成語法短語(表示成語法樹). n結(jié)構(gòu)上的合法性Structural validationThis line is a longer sentence語言的語法規(guī)則規(guī)定了如何從單詞符號形成更大的結(jié)構(gòu)（即語法單位：表達式、語句、子程序等）nposition:=initial + rate * 60 ;結(jié)構(gòu)描述結(jié)構(gòu)描述 :=“:=” :=“+” :=“*” :=“(”“)” := :=

13、 := 賦值語句標識符表達式表達式+表達式表達式標識符整數(shù)標識符:=表達式*id1:=id2+id3*N:=+N 60*id1 Positionid2 initialid3 rate語法分析n語法分析(syntax analysis or parsing)The purpose of syntax analysis is to determine the source programs phrase structure.This process is also called parsing.The source program is parsed to check whether it con

14、forms to the source languages syntax,and to construct a suitable representation of its phrase structure.n語法樹(推導樹)(parse tree or derivation tree)語義分析進一步分析語法結(jié)構(gòu)正確的程序是否符合源程序的上下文約束、運算相容性等規(guī)定。審查靜態(tài)語義 使用的變量聲明了嗎？ 允許操作的運算對象嗎？ 類型正確嗎？ 例:Program p();Var rate:real;procedure initial;position := initial + rate * 60

15、/* error */ /* error */ /* warning */; int arr2, c; c = arr * 10;60:=+*Id1 positionId2 initialId3 rateinttorealProgram p(); Var rate:real; Var initial :real; Var position :real ; position := initial + rate * 60 /*warning*/語義分析n語義分析(semantic analysis) The parsed program is further analyzed to determi

16、ne whether it conforms to the source languages contextual constraints:scope rules, type rulese.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration. 中間代碼（中間表示）生成(翻譯）源程序的中間表示：三元式、四元式、P-Code、bytecode、id1:= id2 + id3 * 60(1)(inttoreal,60-t1)(2)(*,

17、id3t1t2)(3)(+,id2t2t3)(4)(:=,t3-id1)翻譯為中間代碼 Three-address codej = 2 * i + 1;if (j = n) j = 2 * i + 3;return aj;t1 = 2 * it2 = t1 + 1j = t2t3 = j nif t3 goto L0t4 = 2 * it5 = t4 + 3j = t5L0: t6 = ajreturn t6中間代碼(intermediate code) Intermediate code is a intermediate representation of the source progr

18、am . We want this representation （ intermediate representation） to be easy to generate,and easy to translate into the target program. The representation can have a variety of forms, a common one is called three-address code or 4- tuple code.代碼優(yōu)化（Code Optimization）應(yīng)用一些技術(shù)對代碼進行變換以使得編譯產(chǎn)生的目標代碼高效。nExample

19、（中間代碼一級）t1 = 2 * it2 = t1 + 1j = t2t3 = j nif t3 goto L0t4 = 2 * it5 = t4 + 3j = t5L0: t6 = ajreturn t6t1 = 2 * ij = t1 + 1t3 = j nif t3 goto L0 j = t1 + 3L0: t6 = ajreturn t6id1:= id2 + id3 * 60(1)(inttoreal60-t1)(2)( * id3t1t2)(3)( +id2t2t3)(4)( :=t3-id1) 變換變換 （1） ( *id360.0t1) ( 2）（ + id2 t1id1)目

20、標代碼生成Object code generation 生成目標機匯編或機器指令nExample: a in R0, i in R1, n in R2t1 = 2 * ij = t1 + 1t3 = j 機器語言n編譯程序：高級語言-匯編語言或機器語言-筆譯n解釋程序：邊翻譯邊解釋，并不產(chǎn)生目標程序-口譯編譯程序和解釋系統(tǒng)(interpreter)如對源程序： b := 2 ; a := b+2 ; 編譯程序編譯程序 write a ; 解釋程序解釋程序 直接將4的值輸出（顯示）（直接對源程序中的語句進行分析，執(zhí)行其隱含的操作。）n解釋系統(tǒng) 1）不生成目標代碼 2）能支持交互環(huán)境Int 2St

21、 bLd badd 2St a生成代碼編譯程序和解釋程序n編譯程序把一個高級語言程序翻譯成某個機器的匯編或二進制代碼程序, 這個二進制代碼程序在機器上運行以生成結(jié)果. 編譯和運行是兩個獨立分開的階段。n但在一個交互環(huán)境中,不需要將這兩個階段分隔開,解釋程序是這樣一個程序,它接受某個語言的程序并立即運行這個源程序.它的工作模式是一個個的獲取,分析并執(zhí)行源程序語句.n著名的解釋程序有Basic語言解釋程序 ,Lisp語言解釋程序,UNIX命令語言解釋程序(shell),數(shù)據(jù)庫查詢語言SQL 解釋程序以及bytecode解釋程序.解釋程序計算結(jié)果源 程 序初始數(shù)據(jù)編譯程序和解釋程序的存儲組織有很大不

22、同 編譯時 運行時 名字表目標代碼緩沖區(qū)編譯用源程序中間表示各種表格目標代碼區(qū)數(shù)據(jù)區(qū)源程序緩沖區(qū)編譯階段和運行階段存儲結(jié)構(gòu)解釋系統(tǒng)存儲結(jié)構(gòu)解釋系統(tǒng)源程序臨時工作單元名字表標號表緩沖區(qū)(輸入輸出)棧區(qū)語言處理過程語言處理過程C語言程序： #include #include #define MAX_LINES 75enum booleans (FALSE,TRUE);main (int argc,char *argv*) 預處理器編譯器匯編器裝配連接編輯骨架程序 源程序 目標匯編程序 可重定位機器代碼 絕對機器碼可重定位目標文件庫語言處理過程語言處理過程手工：工作量大，可靠性差機器語言匯編系統(tǒng)程序

23、設(shè)計語言：C、PASCAL等，BASIC、FORTRAN等不是自展，交叉編譯，移植自動構(gòu)造工具，如 lex yacc編譯基礎(chǔ)設(shè)施（多源語言多目標機體系結(jié)構(gòu)的編譯程序構(gòu)造和編譯技術(shù)研究平臺） 1.3 編譯程序的實現(xiàn)方式先進的開發(fā)方式縮短了開發(fā)周期，提高了開發(fā)效率，大大增加了可靠性、可移植性、可維護性和可擴展性。u自編譯：用某一高級語言書寫另一種語言的編譯程序用語言L1寫的語言L2的編譯程序comp.L2 同一機器上的語言L2的編譯程序comp.L2 語言L1的編譯程序comp.L1u自展：滾雪球式 L0-L1-L2-Li-1 -L（Li由Li-1實現(xiàn)） 弱小- 強大用機器或匯編語言實現(xiàn)u移植：將

24、A機上的某高級語言的編譯程序稍加修改得到B機上的編譯程序。 在 A機上用LA編寫能生成B機代碼的LB的編譯程序LA的編譯程序A機代碼的LB的編譯程序LA源程序B機上目標程序B機LB的編譯程序u交叉編譯：LA（A機語言L）=LB（B機語言L）交叉編譯程序為另一系統(tǒng)配同一語言：由于目標機指令系統(tǒng)與宿主機的指令系統(tǒng)不同，編譯程序在宿主機A上運行，將應(yīng)用程序的源程序生成目標機B的代碼，這種編譯稱為交叉編譯。A機與B機的指令系統(tǒng)不同編譯程序的自動生成問題:只告訴做什么,而不用告訴怎么做源語言的定義機器語言的描述編譯程序自動生成工具編譯程序編譯程序復雜、龐大，手工編制時間長 開發(fā)過程自動化LEX / YA

25、CC、Antlr一些編譯基礎(chǔ)設(shè)施n編譯基礎(chǔ)設(shè)施（Compiler Infrastructure） NCI (National Compiler Infrastructure) project SUIF (Stanford University) Zephyr (Virginia University and Princeton University ) Trimaran compiler infrastructure IMPACT (UIUC ) CAR (Hewlett Packard Laboratories) ReaCT-ILP (NYU and GIT) GCC GNU project

26、 , everyone can get and maintain freely1.4 編譯技術(shù)的應(yīng)用-處理源程序的軟件工具處理源程序的軟件工具n結(jié)構(gòu)化編緝器n程序分析工具 靜態(tài)分析 動態(tài)分析 度量工具 結(jié)構(gòu)度量 模塊接口復雜度 c分析工具(source insight) n廣泛的語言領(lǐng)域 數(shù)據(jù)庫系統(tǒng)查詢（SQL） 腳本語言 置標語言(SGML.HTML.XML)處理源程序的軟件工具：處理源程序的軟件工具：語言的結(jié)構(gòu)化編輯器、語言程序的調(diào)試工具、程序格式化工具、語言程序測試工具、程序理解工具、高級語言之間的轉(zhuǎn)換工具。1.語言的結(jié)構(gòu)化編輯器語言的結(jié)構(gòu)化編輯器 結(jié)構(gòu)化編輯器不僅具有通常的正文編輯器的

27、正文編輯和修改功能，而且還能執(zhí)行一些對編制程序有用的附加的任務(wù)。例如，當用戶敲入if后，編輯器立即顯示then并將這兩個關(guān)鍵字之間必須出現(xiàn)的條件留給用戶輸入，并能檢查括號是否相匹配等等。這樣，既可保證編出的源程序無語法錯誤，并有統(tǒng)一的可讀性好的程序格式，這無疑將會提高程序的開發(fā)效率和質(zhì)量。 Editplus、Ultraedit、，很多集成開發(fā)環(huán)境中的編輯器都是結(jié)構(gòu)化編輯器.2. 語言程序的調(diào)試工具語言程序的調(diào)試工具結(jié)構(gòu)化編輯器只能解決語法錯誤的問題，而對一個已通過編譯的程序來說，需進一步了解的是程序執(zhí)行的結(jié)果與編程人員的意圖是否一致，程序的執(zhí)行是否實現(xiàn)預計的算法和功能。這種對算法的錯誤或程序沒

28、能反映算法的功能等錯誤就需用調(diào)試器來協(xié)助解決。源程序級調(diào)試器允許逐行跟蹤源程序的執(zhí)行,查看變量和數(shù)據(jù)結(jié)構(gòu)的變化。當然,它們的信息須由編譯程序提供。調(diào)試器的實現(xiàn)有很多途徑。其中一種是寫一個解釋器,以交互的方式翻譯和執(zhí)行每一行。解釋器必須維護程序運行時的所有資源以便實時查詢它們的當前值；另一種調(diào)試途徑是編譯程序在目標代碼生成時同時生成特定的調(diào)試信息,如變量名與它的地址的對應(yīng)關(guān)系等。3.程序格式化工具程序格式化工具分析源程序，使之以清晰可讀的結(jié)構(gòu)形式進行顯示。例如，注釋可以以一種專門的字形出現(xiàn)，且語句的嵌套層次結(jié)構(gòu)可以用齒形結(jié)構(gòu)體現(xiàn)出來。 4.語言程序測試工具語言程序測試工具：靜態(tài)分析器和動態(tài)測試器

29、 靜態(tài)分析器靜態(tài)分析器是在不運行程序的情況下對源程序進行靜態(tài)分析，以發(fā)現(xiàn)其中潛在的錯誤或異常。它檢查變量定值與引用的關(guān)系。如某變量未被賦值就被引用、定值后未被引用、多余的源代碼等非語法錯誤。動態(tài)測試器動態(tài)測試器是在對源程序進行分析的同時將用于記錄和顯示程序執(zhí)行軌跡的語句或函數(shù)插入到源程序的適當位置，并用測試用例記錄和顯示程序運行時的實際路徑，將運行結(jié)果與期望的結(jié)果進行比較分析，幫助編程人員查找問題。5.程序理解工具程序理解工具分析程序，確定模塊間的調(diào)用關(guān)系，記錄程序數(shù)據(jù)的靜態(tài)屬性和結(jié)構(gòu)屬性，畫出控制流程圖，以幫助用戶理解程序。6. 高級語言之間的轉(zhuǎn)換工具高級語言之間的轉(zhuǎn)換工具 Human-or

30、ientedlanguageComputer-orientedlanguage計算模式，語言范式語言應(yīng)用領(lǐng)域編譯程序萬諾曼機體系結(jié)構(gòu)并行體系結(jié)構(gòu)嵌入系統(tǒng)1.5 編譯技術(shù)的發(fā)展S OI高級程序語言v不同的應(yīng)用側(cè)重:數(shù)值計算- Fortran 系統(tǒng)程序設(shè)計-C事務(wù)處理-Cobol VLSI設(shè)計-VHDL人工智能-Prolog 其它-大型嵌入式實時處理-Ada 符號處理-Snobolv語言范型:強制式語言-C,Fortran,Pascal應(yīng)用式(函數(shù)式）語言-ML，Lisp基于規(guī)則(邏輯）的語言-Prolog,Yacc面向?qū)ο笳Z言-Ada,C+,Java強制式語言(Imperative Langua

31、ge)也稱過程式語言其特點是命令驅(qū)動，面向語句，一個強制式語言程序由一系列的語句組成，每個語句的執(zhí)行引起若干存儲單元中的值的改變.語言執(zhí)行的解釋與萬諾曼機的體系結(jié)構(gòu)對應(yīng)：改變機器狀態(tài)（內(nèi)存，各種寄存器和外存的內(nèi)容）面向?qū)ο笳Z言：支持封裝性，繼承性和多態(tài)性 基于規(guī)則的語言( Rule-based Language) ： 條件1 動作1 條件2 動作2 條件3 動作3程序的執(zhí)行過程是：檢查一定的條件，當它滿足值，則執(zhí)行適當?shù)膭幼鳌Ｋ卜Q邏輯程序設(shè)計語言。 Example: 一個簡單的Prolog程序：father(a,b);father(b,c);grandfather(X,Y):-father(

32、X,Z),father(Z,Y);?grandfather(a,c).Yes?grandfather(X,c).X=a?grandfather(X,Y).X=a,Y=c編譯技術(shù)與體系結(jié)構(gòu)的發(fā)展密切相關(guān)n CISC （Complex Instruction Set Computing） 傳統(tǒng)的編譯技術(shù)與之伴隨n RISC （Reduced Instruction Set Computing） 編譯技術(shù)與體系結(jié)構(gòu)設(shè)計的協(xié)同 軟硬件協(xié)同設(shè)計n EPIC （Explicitly Parallel Instruction Computing） 現(xiàn)代編譯技術(shù)的發(fā)展推動體系結(jié)構(gòu)的進步 IA-64 處理器產(chǎn)品系列（IPF）的上市現(xiàn)代編譯技術(shù)必須面對應(yīng)用需求和目標體系結(jié)構(gòu)的多樣化n 高性能計算（High Performance Computing） 指令級并行（Instruction Level Parallelism） 線程級并行（Thread Level