1、編 譯 原 理,長春理工大學,2020年7月,與課程有關的問題, 時間安排： 講課：32學時 實驗：16學時,參考書 ： 程序設計語言編譯原理，陳火旺等，第三版，國防工業(yè)出版社 計算機編譯原理 ，第二版，張幸兒，科學出版社 編譯程序原理與技術，李贛生、王華民，清華大學出版社,作業(yè)：視所講內容布置1-2道習題,成績 ：以考試為主，參考平時成績(作業(yè)、實驗等),與課程有關的問題,本課程的性質、目的和任務 ： 本課程是計算機類專業(yè)的專業(yè)課，目的是使學生了解并掌握編譯程序的基本理論和方法，具有分析和實現(xiàn)編譯程序的初步能力。,本課程的基本要求 ： 通過對本課程的學習，對形式語言有初步了解，并能對編譯程序

2、的整個結構有較清楚地了解，熟悉和掌握幾種主要編譯方法。,課程內容的重點、深度與廣度 ： 重點是：文法和形式語言、詞法分析和有窮自動機、語法分析、語義分析。此外還涉及到目標代碼的生成，此外還要求掌握和了解符號表的構造、存儲分配與管理、代碼優(yōu)化和錯誤校正。,課程內容,第1章 ：編譯程序概述 第2章 ：文法和語言的形式定義 第3章 ：有窮自動機與詞法分析 第4章 ：語法分析 第5章 ：語義分析和中間代碼生成 第6章 ：符號表的組織與管理 第7章 ：代碼優(yōu)化 第8章 ：運行階段的存儲組織與分配 第9章 ：目標代碼生成 第10章 ：并行編譯技術基本知識,本節(jié)內容簡介, 程序的翻譯, 編譯程序的工作過程,

3、 編譯程序的結構, 編譯程序的組織方式, 編譯程序的構造,1.1翻譯程序與編譯程序,問題: 計算機只能識別二進制數(shù)0、1表示的指令和數(shù)構成的本計算機系統(tǒng)的機器語言。如何讓計算機執(zhí)行高級語言程序呢？, 高級語言 begin x:=9+2 end,1.1.1 程序設計語言的發(fā)展, 機器語言 001110010010, 匯編語言 ADD R1 2, 所謂翻譯程序是指這樣一種程序，它能將用甲語言（源語言）編寫的程序翻譯成與之等價的用乙語言（目標語言）書寫的程序。, 程序翻譯的方式： 一是“編譯”方式，二是“解釋”方式。,1.1 翻譯程序與編譯程序,1.1.2翻譯程序,編譯方式是一種分階段進行的翻譯方式

4、。, 翻譯階段,高級語言或匯編語言源程序,機器語言的目標程序,翻譯程序, 運行階段,1.1翻譯程序與編譯程序,輸入數(shù)據(jù),運行結果,目標程序,運行子程序,1.1.3 編譯方式, 編譯程序,高級語言 源程序,匯編語言或機器語言 目標程序,編譯程序, 匯編程序,匯編語言 源程序,機器語言 目標程序,匯編程序, 編譯程序編譯方式下的 翻譯程序,1.1 程序的翻譯編譯方式,在編譯方式下，源程序的執(zhí)行需要分階段。, 如果目標程序是機器語言程序， 則源程序的執(zhí)行分 為兩大階段：編譯階段和運行階段。, 如果目標程序是匯編語言程序， 則源程序的執(zhí)行分 為三大階段：編譯階段、匯編階段和運行階段。,編譯方式下，生成

5、了目標代碼，且可多次執(zhí)行。, 編譯方式的特點,1.1 程序的翻譯編譯方式,關于編譯程序的幾點說明,編譯程序生成的目標程序不一定是機器語言的程序，也有可能是匯編語言程序；,編譯程序與具體的機器和語言有關，即任何一個具體的編譯程序都是某一特定類型的計算機系統(tǒng)中關于某一特定語言的編譯程序；,對編譯程序而言，源程序是輸入數(shù)據(jù)，目標程序是輸出結果。,關于編譯程序的幾點說明,（4）編譯程序實際上只可能發(fā)現(xiàn)并報告在靜態(tài)可計算性制約下的那些錯誤。 （5）理想的編譯程序應該具有單獨編譯某個模塊的能力，同時它不應因為源程序的一兩處修改就對源程序重新編譯。,完成解釋工作的解釋程序將按源程序中語句的動態(tài)順序，逐句地進

6、行分析解釋，并立即予以執(zhí)行。,1.1 程序的翻譯解釋方式,1.1.4 解釋方式,1.編輯器 2.預處理器 3.編譯器 4.連接程序 5.裝入程序 6.調試程序,程序設計環(huán)境,集成開發(fā)環(huán)境（IDE）,源程序解釋執(zhí)行的歷程,計算機,解 釋 程 序,源程序 （高級語言）,初始數(shù)據(jù),計 算 結 果,在解釋方式下，并不生成目標代碼，而是直接執(zhí)行源程序本身。這是編譯方式與解釋方式的根本區(qū)別。,所謂編譯過程是指將高級語言程序翻譯為等價的目標程序的過程。,翻譯外文資料： 1、能識別出句子中的一個單詞； 2、分析句子的語法結構； 3、根據(jù)句子的含義進行初步翻譯； 4、對譯文進行修飾； 5、寫出最后的譯文。,1.

7、2編譯程序的組成,翻譯和編譯工作的比較,編譯過程,詞法分析,語法分析,語義分析及中間代碼生成,代碼優(yōu)化,目標代碼生成,習慣上是將編譯過程劃分為5個基本階段：,1.2 編譯程序的工作過程,例： 一個簡要的C 程序 Main() /* used for illustrating compiling process */ Int a,b,c,x; a=a+b*c+b*c; x=a*3-b*c; b=a+)b*(x- ; ,依據(jù)語言詞法規(guī)則，分析由字符組成的源程序，把它識別為一個一個具有獨立意義的最小語法單位，即“單詞”，并識別出與其相關的屬性(如是標識符，是界限符，還是數(shù)，等等)，再轉換成長度上統(tǒng)一

8、的標準形式(這種統(tǒng)一的標準形式既刻畫了單詞本身，又刻畫了它所具有的屬性，稱為屬性字)，以供其它部分使用。,1.2 編譯程序的工作過程詞法分析,上述源程序通過詞法分析識別出如下單詞符號： 基本字：main, int 標識符：a,b,c,x 常數(shù)： 3 運算符：,*, 界符： ( , ) , ; , , , /* , */, = 長度上統(tǒng)一的標準形式TOKEN串 TOKEN串是一個二元組：（單詞類別，單詞的值） 其中：“單詞的類別”用既已存在的一組整數(shù)值（稱為單詞的種別 碼）表示。用以區(qū)分不同種類的單詞。 “單詞的值”是單詞的機內表示形式。一般是ASCII碼。,Main() /* used for

9、 illustrating compiling process */ Int a,b,c,x; a=a+b*c+b*c; x=a*3-b*c; b=a+)b*(x- ; ,依據(jù)語法規(guī)則，逐一分析詞法分析時得到的單詞，把單詞串分解成各類語法單位，即確定它們是怎樣組成說明和語句，以及說明和語句又是怎樣組成程序的。分析時如發(fā)現(xiàn)有不合語法規(guī)則的地方，便將出錯的位置及出錯性質打印報告給程序員；如無語法錯誤，則用另一種中間形式給出正確的語法結構，供下一階段分析使用。,1.2 編譯程序的工作過程 語法分析,通過語法分析，識別出： a,b,x 是這個語法單位； a+b*c+b*c組合成這樣的語法單位； 識別出

10、，這樣的語法單位，并檢查正確性。例如， 由 =構成； 這里發(fā)現(xiàn)b=a+)b*(x-的語法錯誤。 原因是 a+)b*(x-錯誤,Main() /* used for illustrating compiling process */ Int a,b,c,x; a=a+b*c+b*c; x=a*3-b*c; b=a+)b*(x- ; ,依據(jù)語言的語義規(guī)則對語法分析得到的語法結構進行靜態(tài)語義檢查(確定類型、類型和運算合法性檢查、識別含義與相應的語義處理及其它一些靜態(tài)語義檢查)，并用另一種內部形式（如中間代碼）表示出來，或者直接用目標語言表示出來。 凡在編譯時可以確定的內容稱為“靜態(tài)”的；凡必須推遲到

11、程序運行時才能確定的內容稱為“動態(tài)”的。,1.2 編譯程序的工作過程 語義分析,具體說來語義分析包括兩方面： （1）靜態(tài)語義檢查。要檢查標識符是否被定義，前后的數(shù)據(jù)類型是否一致。如上述源程序中x=a*3-b*c，要查看賦值號左右的變量和表達式的類型是否一致。 （2）進行語義處理。針對不同類型的語句語義處理的方式不同。對說明語句，要將說明性語句中所定義的變量名字及其有關信息送進符號表，并為之分配存儲單元；對可執(zhí)行語句（如賦值語句、條件語句、循環(huán)語句等），就要生成可表達語義的中間代碼。,分析到說明語句int a,b,c,x;后，應把變量a,b,c的類型int填入符號表中，分析到 后，將產(chǎn)生以下四元

12、式序列： 運算符 左運算對象 右運算對象 工作單元 注釋 (1) * b c T1 b*cT1 (2) + a T1 T2 a+T1T2 (3) * b c T3 b*cT3 (4) + T2 T3 T4 a+b*c+b*cT4 (5) = T4 _ a T4a (6) * a 3 T5 a*3T5 (7) * b c T6 b*cT6 (8) _ T5 T6 T7 a*3-b*cT7 (9) = T7 _ x T7x 語義翻譯工作通常穿插在語法分析過程當中，因而語義翻譯程序是由一組語法子程序構成的。, a:=a+b*c+b*c; x:=a*3-b*c; b:=a+)b*(x- ,依據(jù)程序的等

13、價變換規(guī)則，盡量壓縮目標程序運行所需的時間和所占的存儲空間，以提高目標程序的質量。 代碼優(yōu)化分為兩類： (1)與機器有關的優(yōu)化：主要涉及如何分配寄存器。這種優(yōu)化是在生成目標代碼時進行的。 (2)與機器無關的優(yōu)化：包括對中間代碼的優(yōu)化，局部優(yōu)化和循環(huán)優(yōu)化。,1.2 編譯程序的工作過程 代碼優(yōu)化,上述四元式經(jīng)優(yōu)化得： （1）（*，b, c, T1） （2）(+, a, T1,T2) （3）(+, T1,T2,T4) （4）(=,T4,_, a ) （5）(*, a, 3, T5) （6）(_, T5,T1,T7) （7）(=,T7,_, x ) 編譯程序所產(chǎn)生的目標代碼質量的高低，主要取決于這一階

14、段里代碼優(yōu)化程序功能的強弱。,如果語義分析時把源程序表示成中間形式而不是表示成目標指令，則由本部分完成從中間形式到目標指令的轉換。如果語義分析時，已直接生成目標指令，則無需另外再做代碼生成工作。,目標指令可能是絕對指令代碼，或可重新定位的指令代碼或匯編指令代碼。該階段的工作有賴于硬件系統(tǒng)結構和機器指令含義。,1.2 編譯程序的工作過程 代碼生成,登記源程序中出現(xiàn)的每個名字以及名字的各種屬性。有些名字的屬性需要在各個階段才能填入。即編譯各階段的工作都涉及到構造、查找或更新有關的符號表，編譯過程的絕大部分時間是用在造表、查表和更新表格的事務上。因此，編譯程序中還應包括一個表格管理程序。,1.2 編

15、譯程序的工作過程 表格管理,源程序中的錯誤有語法錯誤和語義錯誤兩種。,語法錯誤：源程序中不符合語法(或詞法)規(guī)則的錯誤，它們可在詞法分析或語法分析時檢測出來。,語義錯誤：源程序中不符合語義規(guī)則的錯誤，一般在語義分析時檢測出來，有的語義錯誤要在運行時才能檢測出來。通常包括：說明錯誤、作用域錯誤、類型不一致等等。,1.2 編譯程序的工作過程 出錯處理,1.3 編譯程序的結構,1.4.1 遍(趟，趟程),所謂一趟或一遍是指一個編譯程序在編譯時刻把源程序或源程序的等價物(中間程序)從頭到尾掃描一遍并做有關的加工處理，生成新的源程序的中間形式或目標程序。,根據(jù)編譯程序在完成翻譯任務的過程中需要對源程序或

16、其中間等價物掃描的遍數(shù)，可以把編譯程序分為單遍掃描的編譯程序(只需掃描一遍)和多遍掃描的編譯程序(需掃描多遍)。,1.4 編譯程序的組織形式,單遍掃描的編譯程序,多遍掃描的編譯程序,例如，可以把詞法分析作為第一遍；語法分析和語義分析作為第二遍；代碼優(yōu)化和存儲分配作為第三遍；代碼生成作為第四遍：從而構成一個四遍掃描的編譯程序。 每遍完成上述某個階段的一部分、全部或幾個階段的工作，并將結構存入外存儲器里，作為下一遍的輸入。,那么一個編譯程序究竟應分成幾遍，這和源程序語言的結構與目標機器的特征有關。 分多遍完成編譯過程的優(yōu)點：可以使整個編譯程序的邏輯結構更清晰，能減少對主存容量的要求，使優(yōu)化工作更為

17、充分，并為可移植創(chuàng)造條件。缺點：遍數(shù)多勢必增加讀寫中間文件的次數(shù)，從而消耗過多的時間。 總之，對一個具體的編譯器，要確定用幾遍掃描來完成，需要綜合考慮各種因素，從中取得最佳方案。,前端主要由與源語言有關但與目標機器無關的那些部分組成，如詞法分析、語法分析、語義分析與中間代碼生成及部分代碼優(yōu)化工作。,后端主要包括編譯中與目標機器有關的那些部分，如與目標機有關的代碼優(yōu)化和目標代碼生成等。后端不依賴于源語言而僅依賴于中間語言。,可以通過改變編譯程序的后端來實現(xiàn)編譯程序的移植。,1.4 編譯程序的組織形式,編譯的前端和后端,如果宿主機的內存空間有限，則需要外存輔助，這種情況下，編譯程序可以按照下面的方

18、式組織。 首先在內存中開辟三個覆蓋區(qū)（共享區(qū)）：一個存放最大的Comp1；一個存放輸入對象（掃描對象）；一個存放加工結果（部分處理結果）。 然后在外存開辟編譯程序的暫存區(qū)和輸入對象/加工結果的存放區(qū)。并且由“編譯總控程序”負責控制和調度編譯程序的各遍。,編譯程序組織方式,構造編譯程序可以用機器言語、匯編語言和高級語言。,高級語言的自編譯性：一個語言可以用來編寫自己的編譯程序。,1.5 編譯程序的構造及相關技術 P5,1.5.1 高級語言的自編譯性,通過一系列自展途徑而形成編譯程序的過程。,先對語言的核心部分構造一個小小編譯程序(可用低級語言實現(xiàn))，再以它為工具構造一個能夠編譯更多語言成分的較大

19、編譯程序。如此擴展下去，越滾越大，最后形成所期望的整個編譯程序。,1.5 編譯程序的構造及相關技術,1.5.2 編譯的自展技術,將一個機器（宿主機）上的一個具有自編譯性的高級語言編譯程序移植到另一個機器（目標機）上。,利用A機器上的高級語言L編寫能在B機器上運行的高級語言L的編譯程序。,1.5 編譯程序的構造及相關技術,1.5.3 編譯的移植,1.5 編譯程序的構造及相關技術,1.5.2編譯程序的自動化,在編譯程序自動化進程中，開發(fā)早且應用廣泛的是詞法分析程序生成器和語法分析程序生成器。 詞法分析程序生成器：LEX。它輸入的是正規(guī)表達式，輸出的是詞法分析程序。LEX的基本思想是由正規(guī)表達式構造有窮自動機。 語法分析程序生成器：基于LALR（1）文法的YACC（Yet A