第1章 編譯程序概論(lly)3

編譯原理教材：編譯原理張素琴呂映芝清華大學出版社參考教材：編譯原理（第2版）蔣立源西北工業(yè)大學出版社主講教師:

劉立月Office:創(chuàng)新西樓-405（軟件理論）E_mail:lly_nwpu@163.com教學內(nèi)容及學時分配（56學時：44+12）課程成績評定平時成績(30%)（考勤20、書面作業(yè)30、上機練習30、態(tài)度與提問20）期末考試(70%)第1章編譯程序概論考查重點：編譯程序編譯程序與解釋程序的根本區(qū)別編譯程序各部分的功能編譯程序的邏輯結(jié)構(gòu)1.1什么是編譯程序計算機語言低級語言高級語言：如PASCAL，C等機器語言匯編語言(唯一能被計算機執(zhí)行的)2、執(zhí)行高級語言或匯編語言的步驟：(1)把高級語言程序或匯編語言程序轉(zhuǎn)換成計算機所能理解的語言程序—機器語言程序。轉(zhuǎn)換的辦法：解釋、翻譯(2)運行所得的機器語言程序得到計算結(jié)果1、計算機語言的分類3、解釋程序定義:一個源程序的解釋程序是這樣一個程序,它以源語言書寫的程序作為輸入,但不產(chǎn)生目標程序,而是邊解釋邊執(zhí)行源程序本身。源語言:BASIC、LISP等解釋程序源程序輸入數(shù)據(jù)計算結(jié)果邊解釋邊執(zhí)行4、翻譯程序：把一種語言(源語言）書寫的程序翻譯成另一種語言（目標語言）等價的程序。

匯編程序：源語言程序為匯編語言；目標語言為機器語言的翻譯程序。（區(qū)別：匯編語言程序與匯編程序）編譯程序：源語言程序為高級語言，而目標語言為低級語言（匯編語言或機器語言）的翻譯程序。編譯程序高級語言程序（源程序）低級語言程序（目標程序）思考：翻譯與編譯的關(guān)系？解釋與編譯的主要區(qū)別是？編譯程序運行系統(tǒng)目標程序輸入數(shù)據(jù)計算結(jié)果源程序需預處理的源程序預處理程序源程序編譯程序匯編程序裝配/連接編輯程序目標匯編程序可再裝配的機器代碼絕對機器代碼可再裝配目標文件5、高級語言程序的處理過程（目標程序：匯編語言）1.2編譯過程概述1、編譯程序的組成例：一段英文翻譯為中文時，通常經(jīng)過以下步驟：識別句子中的一個個單詞；詞法分析分析句子的語法結(jié)構(gòu)；語法分析分析句子的含義；語義分析進行初步翻譯；中間代碼生成對譯文進行修飾；中間代碼優(yōu)化寫出最后的譯文。目標代碼生成編譯程序的邏輯結(jié)構(gòu)詞法分析程序語法分析程序語義分析程序中間代碼生成代碼優(yōu)化程序目標代碼生成信息表管理程序錯誤檢查程序源程序

單詞符號中間代碼中間代碼中間代碼語法單位目標代碼功能：從左到右讀入源程序的每個字符，對構(gòu)成源程序的字符流進行掃描和分解，從而識別出一個個單詞（邏輯上緊密相連的一組字符，具有集體含義。如：標識符、保留字（關(guān)鍵字）、算符、界符等）。例.某源程序片斷如下：beginvarsum,first,count:real;sum:=first+count*10end.保留字 begin保留字 var標識符 sum逗號 ,標識符 first逗號 ,標識符 count冒號 :保留字 real分號 ;標識符 sum賦值號 :=標識符 first加號 +標識符 count乘號 *整數(shù) 10保留字 end界符 .2、詞法分析3、語法分析功能：在詞法分析的基礎上，將單詞序列分解成各類語法短語（也叫語法單位，可用語法樹來表示），如“程序”、“語句”、“表達式”等。依據(jù)：語言的語法規(guī)則（一般通過遞歸來定義）。目的：通過語法分析確定整個輸入串是否構(gòu)成一個語法上正確的程序。語法短語可用語法樹表示：如：sum:=first+count*10

內(nèi)部形式：id1:=id2+id3*10

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

firstid3

count10:=id1+id2*id310簡化形式語法規(guī)則的遞歸表示如：表達式的表示任何標識符是表達式。任何常數(shù)（整常數(shù)、實常數(shù)）是表達式。若表達式1和表達式2都是表達式，那么表達式1+表達式2，表達式1*表達式2（表達式1）都是表達式。如：語句的表示

標識符:=表達式是語句。

while(表達式)do語句是語句

if(表達式)then語句else語句是語句。結(jié)合上述語法規(guī)則理解語法短語即語句：sum:=first+count*10

的語法樹的構(gòu)成。4、語義分析功能：審查源程序是否有語義錯誤，為代碼生成階段收集類型信息。如：類型檢查。:=id1+id2*id310inttoreal語句：sum:=first+count*10內(nèi)部形式：id1:=id2+id3*105、中間代碼生成功能：將源語言轉(zhuǎn)換為編譯系統(tǒng)內(nèi)部表示方式，中間語言，即中間代碼（一種結(jié)構(gòu)簡單、含義明確的記號系統(tǒng)。）中間代碼設計原則：容易生成；容易將它翻譯成目標代碼。四元式：（運算符，運算對象1，運算對象2，結(jié)果）如：源程序sum:=first+count*10內(nèi)部形式：id1:=id2+id3*10生成的四元式可以是：(inttoreal 10 - t1)(* id3 t1 t2)(+ id2 t2 t3)(:= t3 - id1):=id1+id2*id310inttoreal6、代碼優(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)功能：對中間代碼進行變換或改造，使生成的目標代碼更高效。（省時間與空間）7、目標代碼生成程序任務

把中間代碼（或經(jīng)過優(yōu)化處理之后）變換成特定機器上的低級語言代碼(匯編語言或機器語言)。說明:它依賴于具體的計算機的硬件系統(tǒng)結(jié)構(gòu)和指令系統(tǒng)。

要求

對于所用的翻譯策略或算法要做到:

一是使所生成的目標代碼盡可能短；二是充分利用計算機可用資源的效率。

絕對地址的機器指令代碼這種代碼可以立即執(zhí)行。匯編語言形式的目標程序

這種代碼還需要匯編程序匯編之后才能運行。模塊結(jié)構(gòu)的機器指令(可重定位的指令代碼)這種代碼在運行前必須借助于一個連接裝配程序把各個目標模塊連接在一起，裝入內(nèi)存中，使之成為一個可以運行的絕對地址的機器指令代碼程序。目標代碼的形式錯誤的種類：語法錯誤語法錯誤是指源程序中有不符合語法(或詞法)規(guī)則的錯誤,它們可在詞法分析或語法分析時檢測出來。語義錯誤語義錯誤是指源程序中不符合語義規(guī)則的錯誤,這些錯誤一般在語義分析時檢測出來,有的要在運行時才能檢測出來。

8、錯誤檢查和處理程序1.最重要的是符號表2.信息表的結(jié)構(gòu)9、信息表管理程序名字信息……(* id3 10.0 t1)(+ id2 t1 id1)sum:=first+count*10MOVF id3, R2MULF #10.0, R2MOVF id2, R1ADDF R1, R2MOV R1, id1目標代碼（匯編指令代碼）內(nèi)部形式：id1:=id2+id3*10(inttoreal 10 - t1)(* id3 t1 t2)(+ id2 t2 t3)(:= t3 - id1)代碼優(yōu)化中間代碼詞法，語法及語義分析有關(guān)名詞：（了解——自己看）前端（frontend）：主要依賴于源語言而與目標機器無關(guān)的編譯階段。如：詞法分析、語法分析、語義分析、中間代碼生成、部分優(yōu)化工作、與前端有關(guān)的出錯處理工作和符號表管理工作。后端（backend）：依賴于目標機而一般不依賴于源語言，只與中間代碼有關(guān)的編譯階段。如：目標代碼生成，以及相關(guān)出錯處理和符號表操作。遍（趟）：對源程序或其等價的中間語言程序從頭到尾掃視并完成規(guī)定任務的過程。每一遍掃視可完成上述一個階段或多個階段的工作。1.4編譯階段的組合1.5編譯程序的生成1、編譯程序的設計目標

目標程序小，執(zhí)行速度快。編譯程序小，執(zhí)行速度快。診斷能力強，可靠性強?？梢浦残裕蓴U充性。2、編譯器的生成合理的方法是用另一種語言來編寫編譯器，而使用該種語言的編譯器早已存在了。用語言B編譯語言A的編譯器語言A正運行的編譯器語言B已存在的編譯器(1)LEX:自動產(chǎn)生詞法分析器3.編譯程序生成工具詞法規(guī)則說明LEX詞法分析程序(C/C++程序)輸入： 詞法（正規(guī)表達式） 識別動作（Ｃ程序段）輸出：

yylex()函數(shù)語法規(guī)則說明YACC語法分析程序

(C/C++程序)輸入： 語法規(guī)則（產(chǎn)生式） 語義動作(Ｃ/C++程序段)輸出：

yyparse()函數(shù)(2)YACC:自動產(chǎn)生語法分析器1.源語言

對被編譯的語言要深刻理解其結(jié)