編譯原理課件 第 1 講 緒論 (1)

1、1編譯原理：編譯原理指的是編譯程序的構(gòu)造原理和技術(shù)。 第一講 緒 論2第一節(jié) 什么叫編譯程序 一、程序設(shè)計語言1.計算機語言的分類計算機語言低級語言高級語言：如PASCAL，C等 機器語言匯編語言唯一能被計算機執(zhí)行的3(1)把高級語言程序或匯編語言程序轉(zhuǎn)換成計算機所能理解的語言程序機器語言程序 。 轉(zhuǎn)換的辦法：轉(zhuǎn)換的辦法：翻譯或解釋。(2)運行所得的機器語言程序得到計算結(jié)果 。2.執(zhí)行高級語言或匯編語言的步驟：41.1. 翻譯程序翻譯程序 是這樣一種程序,它能夠把某一種語言程序(稱為源語言程序)轉(zhuǎn)換成另一種語言程序(稱為目標語言程序),而后者與前者在邏輯上是等價的。 二、翻譯程序5(1)(1)

2、定義定義 源語言程序是諸如PASCAL、C這樣的高級語言，而目標語言是諸如匯編語言或機器語言之類的低級語言，這樣的一個翻譯程序稱為編譯程序。 匯編程序匯編程序是用于特定計算機上的匯編語言的翻譯程序。2.編譯程序6 交叉編譯程序交叉編譯程序: 源程序的編譯和目標程序的執(zhí)行不一定在同一種計算機上完成。當源程序由另一種計算機的編譯程序進行編譯時,我們將此編譯程序稱為交叉編譯程序。嵌入式系統(tǒng)中的應(yīng)用程序正是借助這樣的編譯程序生成。 診斷編譯程序診斷編譯程序: 專門用于幫助程序開發(fā)和調(diào)試程序的編譯程序。 優(yōu)化編譯程序優(yōu)化編譯程序: 著重于提高目標代碼效率的編譯程序。(2)(2)分類分類7源程序P計算機A

3、目標程序P計算機B運行結(jié)果S編譯程序C運行程序原始數(shù)據(jù)D編譯階段運行階段計算機按編譯方式執(zhí)行高級語言程序的步驟8定義定義: : 一個源程序的解釋程序是這樣一個程序,它以該語言寫的源程序作為輸入,但不產(chǎn)生目標程序,而是邊解釋邊執(zhí)行源程序本身。 與編譯程序的主要區(qū)別: 不產(chǎn)生目標程序不產(chǎn)生目標程序三、解釋程序源程序運行結(jié)果解釋程序邊翻譯邊執(zhí)行9第二節(jié) 編譯過程概述一、編譯程序的組成例：一段英文翻譯為中文時，通常經(jīng)過以下步驟： 識別句子中的一個個單詞； 詞法分析 分析句子的語法結(jié)構(gòu)； 語法分析 分析句子的含義； 語義分析 進行初步翻譯； 中間代碼生成 對譯文進行修飾； 中間代碼優(yōu)化 寫出最后的譯文。

4、 目標代碼生成10第三節(jié) 編譯程序的邏輯結(jié)構(gòu)詞法分析程序語法分析程序語義分析程序中間代碼生成代碼優(yōu)化程序目標代碼生成信息表管理程序錯誤檢查程序源程序源程序 單詞符號單詞符號中間代碼中間代碼中間代碼中間代碼中間代碼中間代碼語法單位語法單位目標代碼目標代碼111.1. 任務(wù)任務(wù): :2.2. 1) 輸入源程序,對構(gòu)成源程序的字符串(從左到右從左到右)進行掃描和分解,識別出一個個的基本語法單位(也稱為單詞符號或語法符號)。2) 刪除無用的空白字符、回車符以及其它與輸入介質(zhì)相關(guān)的非實質(zhì)性字符。3) 刪除注釋。4) 進行詞法檢查,報告所發(fā)現(xiàn)的錯誤。一、詞法分析程序(掃描器)12例: For i:=1 T

5、o 100 DoFor i:=1 To 100 Do 保留字: ForFor 標識符: i i 賦值符: := := 整常數(shù): 1 1 保留字: ToTo 整常數(shù): 100100 保留字: DoDo 132.單詞符號的表示與分類 (1)表示:二元組（ClassClass，ValueValue） 單詞的類別 單詞的值 (2)分類 關(guān)鍵字(保留字)、標識符、數(shù)字 、運算符、界符3.詞法分析階段的工作中依循的是語言的詞法規(guī)則(即構(gòu)詞規(guī)則)。描述詞法規(guī)則的有效工具是正規(guī)式和有限自動機。它是一種線性分析。 14二、語法分析程序1. 任務(wù)： 在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號重構(gòu)成各類語法

6、范疇(語法單位)。 如“語句”、“程序段”和“程序”等。 例：Z:=X+0.6*Y 語法分析的任務(wù)是識別X+0.6*Y為算術(shù)表達式，同時，識別上述整個符號串屬于賦值表達式。 15例：sum:=first+count*10 ;規(guī)則： := “:=” := “+” := “*” := “(”“)” := := := 16賦值語句標識符 := 表達式 表達式 + 表達式表達式 * 表達式標識符id2(first)標識符id3(count)整數(shù)(10)id1(sum)sum:=first+count*10 ;172. 分析方法： 完成這種分析,一般的途徑是由語法分析程序試著為其構(gòu)造一棵完整的語法樹。描

7、述手段： 在語法分析階段的工作中依循的是語言的語法規(guī)則。描述語法規(guī)則的有效工具是上下文無關(guān)文法上下文無關(guān)文法。它是一種層次結(jié)構(gòu)分析。18三、語義分析程序1.任務(wù) 對語法分析程序所識別出的各類語法成分，分析其含義，以保證源程序在語義上的正確性。 2.語義的分類 語義靜態(tài)語義：指在編譯階段能檢查出的語義。 動態(tài)語義：則指只有在目標碼的運行階段 才能檢查出的語義。 典型靜態(tài)語義包括聲明和類型檢查。 193.分析方法 這一階段依循的是語言的語義規(guī)則。通常使用語法制導翻譯描述語義規(guī)則。 20四、中間代碼生成1.任務(wù) 按語言的語義規(guī)則把各類語法范疇翻譯成中間語言代碼。 2.中間代碼的定義 所謂“中間代碼”

8、是一種含義明確、便于處理的記號系統(tǒng),是位于源代碼和目標代碼之間的代碼形式,它獨立于具體的硬件。這種記號系統(tǒng)比較容易變換成現(xiàn)代計算機的機器指令。簡單的說,中間代碼是一種獨立于具體硬件的記號系統(tǒng)。 213.3.中間代碼的形式中間代碼的形式 四元式,三元式,間接三元式,逆波蘭式等。 例如，四元式的格式為: (算符,左操作數(shù),右操作數(shù),結(jié)果)例：Z:=（X+0.8)*Y/W序號 算符 左操作數(shù) 右操作數(shù) 結(jié)果（1） + X 0.8 T1（2） * T1 Y T2（3） / T2 W Z T1和T2是編譯期間引進的臨時工作變量 22五、代碼優(yōu)化程序1. 任 務(wù) 對前段產(chǎn)生的中間代碼進行加工變換,以期在最

9、后階段能產(chǎn)生更為高效(省時間和空間)的目標代碼。2. 分 類 優(yōu)化分為局部優(yōu)化和全局優(yōu)化。3. 優(yōu)化所遵循的原則 程序的等價變換規(guī)則的原則。 234.例1： aindex:=4+2 中間代碼：t=4+2 aindex=t（其中t是一個臨時變量）優(yōu)化: t=6 aindex=t優(yōu)化: aindex=6 24例2： for k:=1 to 100 do begin m:=i+10*k; n:=j+10*k end序號 算符 左操作數(shù) 右操作數(shù) 結(jié)果注 解(1) :=1 k(2) j 100 k (9) 若100K轉(zhuǎn)至第(9)四元式(3)* 10 kT1 T1:=10*k;T1為臨時變量(4)+ i

10、 T1 m m:=i+T1(5)*10kT2 T2:=10*k;T2為臨時變量(6)+jT2n n:=j+T2(7)+k1k k:=k+1(8) j (2) 轉(zhuǎn)到第(2)個四元式(9) (jump - - L) Goto L25序號 算符 左操作數(shù) 右操作數(shù) 結(jié)果注解(1):= i mm:=i(2):= j nn:=j(3):= 1 kk:=1(4)j 100 k (9) If(100k) GOTO(9)(5)+m 10 mm:=m+10(6)+n 10 mn:=n+10(7)+k 1 kk:=k+1(8) j (4)GOTO(4)(9) for k:=1 to 100 do begin m:

11、=i+10*k; n:=j+10*k end26六、目標代碼生成程序1.任務(wù) 把中間代碼（或經(jīng)過優(yōu)化處理之后）變換成特定機器上的低級語言代碼(匯編語言或機器語言)。 說明:它依賴于具體的計算機的硬件系統(tǒng)結(jié)構(gòu)和 指令系統(tǒng)。 2.要求 對于所用的翻譯策略或算法要做到: 一是使所生成的目標代碼盡可能短； 二是充分利用計算機可用資源的效率。 27絕對地址的機器指令代碼 這種代碼可以立即執(zhí)行。匯編語言形式的目標程序 這種代碼還需要匯編程序匯編之后才能運行。模塊結(jié)構(gòu)的機器指令(可重定位的指令代碼) 這種代碼在運行前必須借助于一個連接裝配程序把各個目標模塊連接在一起，裝入內(nèi)存中，使之成為一個可以運行的絕對地

12、址的機器指令代碼程序。3.目標代碼的形式28錯誤的種類：語法錯誤 語法錯誤是指源程序中有不符合語法(或詞法)規(guī)則的錯誤,它們可在詞法分析或語法分析時檢測出來。 語義錯誤 語義錯誤是指源程序中不符合語義規(guī)則的錯誤,這些錯誤一般在語義分析時檢測出來,有的要在運行時才能檢測出來。 七、錯誤檢查和處理程序29 1. 最重要的是符號表 2. 信息表的結(jié)構(gòu) 3.編譯過程中源程序的各種信息被保留在不同的信息表里，各階段的工作都涉及到構(gòu)造、查找或更新有關(guān)的表格。八、信息表管理程序名 字信息30第四節(jié) 編譯階段的組合一、遍 1.定義 是對源程序或源程序的中間結(jié)果從頭到尾掃描一次，并作有關(guān)的加工處理，生成新的中間

13、代碼或目標程序。 31源程序詞法分析程序語法分析程序語義分析及代碼生成程序整理目標程序停機目標程序開 始取單詞送單詞語法單位返回2.一遍和多遍 (1)一遍 (2)多遍32二、前端和后端前端后端源代碼中間代碼目標代碼1.前端：主要與源程序有關(guān)但與目標機（運行編譯程序的 計算機稱宿主機，運行編譯程序所產(chǎn)生目標代碼 的計算機稱目標機）無關(guān)。 2.后端：包括編譯程序中與目標機有關(guān)的那些部分。3.優(yōu)點：取編譯程序的前端，改寫其后端以生成不同目標 機上的相同語言的編譯程序。 33第五節(jié) 編譯程序的生成一、編譯程序的設(shè)計目標 目標程序小，執(zhí)行速度快。編譯程序小，執(zhí)行速度快。診斷能力強，可靠性強?？梢浦残?，可

14、擴充性。34二、編譯器的生成1.合理的方法是用另一種語言來編寫編譯器，而使用該種語言的編譯器早已存在了。用語言B編寫語言A的編譯器語言A正運行的編譯器語言B已存在的編譯器35(1) LEX: (1) LEX: 自動產(chǎn)生詞法分析器自動產(chǎn)生詞法分析器2.編譯程序生成工具詞法規(guī)則說明詞法規(guī)則說明LEX詞法分析程序詞法分析程序(C /C/C+程序程序)輸入：輸入：詞法（正規(guī)表達式）詞法（正規(guī)表達式）識別動作（程序段）識別動作（程序段）輸出：輸出：yylexyylex( ) ( ) 函數(shù)函數(shù)36語法規(guī)則說明語法規(guī)則說明YACC語法分析程序語法分析程序(C /C/C+程序程序)輸入：輸入：語法規(guī)則（產(chǎn)生式

15、）語法規(guī)則（產(chǎn)生式）語義動作語義動作( (/C/C+程序段程序段) )輸出：輸出：yyparseyyparse( ) ( ) 函數(shù)函數(shù)(2) YACC: (2) YACC: 自動產(chǎn)生語法分析器自動產(chǎn)生語法分析器37LexLex 與與 YaccYacc 介紹（摘自介紹（摘自IBMIBM網(wǎng)站）網(wǎng)站） Ashish Bansal (), 軟件工程師, Sapient 公司簡介：簡介： Lex 和 Yacc 是 UNIX 兩個非常重要的、功能強大的工具。事實上，如果你熟練掌握 Lex 和 Yacc 的話，它們的強大功能使創(chuàng)建 FORTRAN 和 C 的編譯器如同兒戲。Ashish Bansal 為您詳細的討論了編寫自己的語言和編譯器所用到的這兩種工