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

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

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

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

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

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

的語(yǔ)法樹賦值語(yǔ)句標(biāo)識(shí)符表達(dá)式表達(dá)式+表達(dá)式表達(dá)式標(biāo)識(shí)符整數(shù)標(biāo)識(shí)符:=表達(dá)式*id1sumid2

firstid3

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

標(biāo)識(shí)符:=表達(dá)式是語(yǔ)句。

while(表達(dá)式)do語(yǔ)句是語(yǔ)句

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

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

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

要求

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

一是使所生成的目標(biāo)代碼盡可能短；二是充分利用計(jì)算機(jī)可用資源的效率。

絕對(duì)地址的機(jī)器指令代碼這種代碼可以立即執(zhí)行。匯編語(yǔ)言形式的目標(biāo)程序

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

8、錯(cuò)誤檢查和處理程序1.最重要的是符號(hào)表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目標(biāo)代碼（匯編指令代碼）內(nèi)部形式：id1:=id2+id3*10(inttoreal 10 - t1)(* id3 t1 t2)(+ id2 t2 t3)(:= t3 - id1)代碼優(yōu)化中間代碼詞法，語(yǔ)法及語(yǔ)義分析有關(guān)名詞：（了解——自己看）前端（frontend）：主要依賴于源語(yǔ)言而與目標(biāo)機(jī)器無關(guān)的編譯階段。如：詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成、部分優(yōu)化工作、與前端有關(guān)的出錯(cuò)處理工作和符號(hào)表管理工作。后端（backend）：依賴于目標(biāo)機(jī)而一般不依賴于源語(yǔ)言，只與中間代碼有關(guān)的編譯階段。如：目標(biāo)代碼生成，以及相關(guān)出錯(cuò)處理和符號(hào)表操作。遍（趟）：對(duì)源程序或其等價(jià)的中間語(yǔ)言程序從頭到尾掃視并完成規(guī)定任務(wù)的過程。每一遍掃視可完成上述一個(gè)階段或多個(gè)階段的工作。1.4編譯階段的組合1.5編譯程序的生成1、編譯程序的設(shè)計(jì)目標(biāo)

目標(biāo)程序小，執(zhí)行速度快。編譯程序小，執(zhí)行速度快。診斷能力強(qiáng)，可靠性強(qiáng)。可移植性，可擴(kuò)充性。2、編譯器的生成合理的方法是用另一種語(yǔ)言來編寫編譯器，而使用該種語(yǔ)言的編譯器早已存在了。用語(yǔ)言B編譯語(yǔ)言A的編譯器語(yǔ)言A正運(yùn)行的編譯器語(yǔ)言B已存在的編譯器(1)LEX:自動(dòng)產(chǎn)生詞法分析器3.編譯程序生成工具詞法規(guī)則說明LEX詞法分析程序(C/C++程序)輸入： 詞法（正規(guī)表達(dá)式） 識(shí)別動(dòng)作（Ｃ程序段）輸出：

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

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

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

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