編譯原理課件chap01(陳火旺).ppt

1、第一章 引 論,第一章 引論,1.1 什么叫編譯程序 編譯程序:是指這樣的程序，它能夠把某種語(yǔ)言的程序轉(zhuǎn)換成另一種語(yǔ)言的程序，而后者與前者在邏輯上是等價(jià)的。如果源語(yǔ)言是諸如FORTRAN、Pascal、C、Ada、Smalltalk或Java這樣的“高級(jí)語(yǔ)言”，而目標(biāo)語(yǔ)言如匯編語(yǔ)言之類的“低級(jí)語(yǔ)言”這樣的翻譯程序則稱之為編譯程序。 本課程主要介紹設(shè)計(jì)和構(gòu)造編譯程序的基本原理和方法。,第一章 引 論,編譯程序又簡(jiǎn)稱為“編譯器”,第一個(gè)編譯器是20世界50年代的后期出現(xiàn)的FORTRAN語(yǔ)言編譯器。 同樣，解釋程序又簡(jiǎn)稱為“解釋器”，但是在概念上與編譯器有明顯區(qū)別： 編譯程序是源轉(zhuǎn)換系統(tǒng)，而解釋程序

2、是源程序的一個(gè)執(zhí)行系統(tǒng)。 編譯程序的結(jié)果是得到等價(jià)源程序的某種目標(biāo)機(jī)程序，而解釋程序的結(jié)果是得到源程序的執(zhí)行結(jié)果，即它相當(dāng)于執(zhí)行源程序的抽象機(jī)。,第一章 引 論,注意編譯程序與解釋程序的區(qū)別，一個(gè)語(yǔ)言的解釋程序是這樣的程序：它以該語(yǔ)言寫的源程序作為輸入，但不產(chǎn)生目標(biāo)程序，而是邊解釋邊執(zhí)行源程序本身。 術(shù)語(yǔ)“編譯”的內(nèi)涵是實(shí)現(xiàn)從源語(yǔ)言表示的算法向目標(biāo)語(yǔ)言表示的算法的等價(jià)變換。,第一章 引 論,高級(jí)語(yǔ)言分類及其編譯： 過程式語(yǔ)言：FORTRAN Pascal Ada C （特點(diǎn)：面向驅(qū)動(dòng)，面向語(yǔ)句，由系列的語(yǔ)句組成） 函數(shù)式語(yǔ)言：LISP ML ASL （注重程序表示的功能，而不是一個(gè)語(yǔ)句接一個(gè)語(yǔ)

3、句的執(zhí)行） 從已有的函數(shù)出發(fā)構(gòu)造更復(fù)雜的函數(shù)。 邏輯式語(yǔ)言：PROLOG （檢查一定的條件，當(dāng)滿足時(shí)，則執(zhí)行適當(dāng)?shù)膭?dòng)作。） 對(duì)象式語(yǔ)言：SMALLTALK C+ （封裝性、繼承性、多態(tài)性）,第一章 引 論,這里主要研究過程式語(yǔ)言的編譯,高級(jí)語(yǔ)言分類及其編譯： 過程式語(yǔ)言：FORTRAN Pascal ADA C 函數(shù)式語(yǔ)言：LISP ML ASL 邏輯式語(yǔ)言：PROLOG 對(duì)象式語(yǔ)言：SMALLTALK C+ 函數(shù)式語(yǔ)言與邏輯式語(yǔ)言，特別是邏輯式語(yǔ)言，其編譯技術(shù)與過程式語(yǔ)言的差別比較大；因?qū)ο笫秸Z(yǔ)言的載體基本上是過程式的，所以其編譯程序也不難理解。,第一章 引 論,1.2 編譯過程概述 編譯程

4、序的工作，從輸入源程序開始到輸出目標(biāo)程序?yàn)橹沟恼麄€(gè)過程，是非常復(fù)雜的。 掌握編譯過程的五個(gè)基本階段，是我們學(xué)習(xí)編譯原理課程的基本內(nèi)容，把編譯的五個(gè)基本階段與英譯中的五個(gè)步驟相比較，有利于對(duì)編譯過程的理解：,第一章 引 論,英譯與編譯的比較,1。識(shí)別出句子中的一個(gè)個(gè)單字 2。分析句子的語(yǔ)法結(jié)構(gòu) 3。初步翻譯句子的含意 4。譯文修飾 5。寫出最后譯文,1。詞法分析 2。語(yǔ)法分析 3。語(yǔ)義分析中間代碼生成 4。優(yōu)化 5。目標(biāo)代碼生成,第一章 引 論,源程序是以文本文件方式存在,注意：程序總是以字符串的方式存在。,第一章 引 論,1.2.1 詞法分析 輸入源程序，對(duì)構(gòu)成源程序的字符串進(jìn)行掃描和分解，識(shí)

5、別出一個(gè)個(gè)單詞（也稱單詞符號(hào)，或簡(jiǎn)稱符號(hào)） 在詞法分析階段工作所依循的是語(yǔ)言的詞法規(guī)則。描述詞法規(guī)則的有效工具是正規(guī)式和有限自動(dòng)機(jī)。,第一章 引 論,1.2.1 詞法分析 什么是單詞 邏輯上相連的一組字符，從語(yǔ)法的角度來看，這些字符所具有的集體含義已不能再區(qū)分了，通常包括：保留字、標(biāo)識(shí)符、界符、算符和常量等,第一章 引 論,例. 考慮下面的一段源程序,var area, radius:real; begin read(radius); area:3.1415926*radius*radius; end. 保留字： var， begin， end， read，real 運(yùn)算符： *， : 界符：

6、(，)，; ，. 標(biāo)識(shí)符： radius， area,第一章 引 論,有關(guān)術(shù)語(yǔ),詞法分析(lexical analysis or scanning) -The stream of characters 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. 單詞-token 保留字-reserved word 標(biāo)識(shí)符 -identifier(user-defined

7、 name),第一章 引 論,1.2.2語(yǔ)法分析 語(yǔ)法分析的任務(wù)：在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)分解成各類語(yǔ)法單位（語(yǔ)法范疇），如“短語(yǔ)”、“句子”、 “子句”、“程序段”等。 語(yǔ)法規(guī)則通常用上下文無關(guān)文法描述。 例. 對(duì)賦值語(yǔ)句area:3.1415926*radius*radius進(jìn)行語(yǔ)法分析,第一章 引 論,賦值語(yǔ)句的語(yǔ)法樹,*,第一章 引 論,術(shù)語(yǔ),語(yǔ)法分析(syntax analysis or parsing) The purpose of syntax analysis is to determine the source programs phrase str

8、ucture.This process is also called parsing.The source program is parsed to check whether it conforms to the source languages syntax,and to construct a suitable representation of its phrase structure. 語(yǔ)法樹(推導(dǎo)樹)(parse tree or derivation tree),第一章 引 論,1.2.3語(yǔ)義分析與中間代碼的產(chǎn)生 對(duì)語(yǔ)法分析所識(shí)別出的各類語(yǔ)法范疇，分析其含義，并進(jìn)行初步翻譯（產(chǎn)生中

9、間代碼）。 這一階段通常包括兩方面的工作首先對(duì)各種語(yǔ)法范疇進(jìn)行靜態(tài)語(yǔ)義檢查（如：變量是否定義，類型是否正確等），如果正確則進(jìn)行另一方面的工作，即進(jìn)行中間代碼的翻譯。 通常使用屬性文法描述語(yǔ)義規(guī)則,第一章 引 論,1.2.3語(yǔ)義分析與中間代碼的產(chǎn)生 什么是中間代碼 是將源程序轉(zhuǎn)變成的一種內(nèi)部表現(xiàn)形式，是一種結(jié)構(gòu)簡(jiǎn)單、含義明確的記號(hào)系統(tǒng) 中間代碼的兩種性質(zhì) 容易生成這種中間代碼 容易將它翻譯成目標(biāo)代碼 主要形式 四元式、三元式、間接三元式、逆波蘭式等,第一章 引 論,中間代碼生成：,如：sum：firstcount10 生成四元式序列： （inttoreal 10 t1 ） （ id3 t1 t2

10、） （ id2 t2 t3） （： t3 id1）,運(yùn)算符,運(yùn)算對(duì)象1,運(yùn)算對(duì)象2,結(jié)果,四元式的形式為： （算符，運(yùn)算對(duì)象1，運(yùn)算對(duì)象2，結(jié)果）,id1,id2,id3,t1，t2，t3是臨時(shí)變量,第一章 引 論,術(shù)語(yǔ),語(yǔ)義分析(semantic analysis) The parsed program is further analyzed to determine whether it conforms to the source languages contextual constraints:scope rules, type rules e.g. To relate each ap

11、plied occurrence of an identifier in the source program to the corresponding declaration.,第一章 引 論,1.2.4 優(yōu)化 優(yōu)化的任務(wù)在于對(duì)前段產(chǎn)生的中間代碼進(jìn)行加工，以期在最后階段產(chǎn)生更為高效（省時(shí)間和空間）的代碼 優(yōu)化所依循的原則是程序的等價(jià)變換規(guī)則 其方法有：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無用代碼等。,第一章 引 論,代碼優(yōu)化,主要任務(wù)：對(duì)中間代碼進(jìn)行變換，使目標(biāo)代碼更為高效。（節(jié)省時(shí)間和空間） id1:= id2 + id3 * 60 (1)(inttoreal60-t1) (2)( * id

12、3t1t2) (3)( +id2t2t3) (4)( :=t3-id1) 變換 （1） ( *id360.0t1) ( 2）（ + id2 t1id1) 例2 見P4,第一章 引 論,1.2.5 目標(biāo)代碼生成 主要工作 是整個(gè)編譯過程的最后一個(gè)階段，這一階段的工作是把中間代碼變換成特定目標(biāo)機(jī)器上的絕對(duì)指令代碼或可重定向的指令代碼或匯編指令代碼,第一章 引 論,目標(biāo)代碼生成,(*id360.0t1) (+id2t1id1),MOVid3,R2 MUL#60.0,R2 MOVid2,R1 ADDR2,R1 MOVR1,id1,主要與硬件系統(tǒng)結(jié)構(gòu)和指令含義有關(guān)。,第一章 引 論,1。3 編譯程序的結(jié)

13、構(gòu),表 格 管 理,詞法分析器,語(yǔ)法分析器,語(yǔ)義分析與中間代碼產(chǎn)生,優(yōu)化器,目標(biāo)代碼生成器,源程序,單詞符號(hào),語(yǔ)法單位,中間代碼,中間代碼,目標(biāo)代碼,出 錯(cuò) 處 理,第一章 引 論,我們可以按照上頁(yè)的總框圖設(shè)計(jì)編譯程序。從圖中我們可以看到除編譯的五個(gè)基本階段外，一個(gè)完整的編譯程序還應(yīng)包括“表格管理”和“出錯(cuò)處理”兩部分 1.3.2 表格與表格管理 在編譯程序使用的表格中最重要的是符號(hào)表它用來登記源程序中出現(xiàn)的每一個(gè)名字以及名子的各種屬性。如一個(gè)名字是常量名、變量名，還是過程名等；如果是變量名它的類型又是什麼、所占內(nèi)存是多大、地址是什么等。,第一章 引 論,1.3.3 出錯(cuò)處理 一個(gè)編譯程序不僅

14、能對(duì)書寫正確的程序進(jìn)行編譯，而且應(yīng)能對(duì)處現(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。如果源程序有錯(cuò)，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤報(bào)告給用戶。這部分的工作是由專門的一組程序（叫做處錯(cuò)處理程序）完程的。,第一章 引 論,1.3.5 編譯前端與后端 前端主要由與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無關(guān)的那些部分組成。通常包括詞法分析、語(yǔ)法分析、語(yǔ)義分析與中間代碼產(chǎn)生，有的代碼優(yōu)化工作，也可以包括在前端。 后端包括編譯程序中與目標(biāo)代碼有關(guān)的部分，如與目標(biāo)機(jī)有關(guān)的有關(guān)的優(yōu)化，和目標(biāo)代碼的生成等。,第一章 引 論,1.3.6 遍 遍 含義：對(duì)源語(yǔ)言或等價(jià)的中間語(yǔ)言程序從頭到尾地掃描并完成規(guī)定的任務(wù)的過程 分遍的相關(guān)因素 源語(yǔ)言和目

15、標(biāo)機(jī)器的特征、編譯程序的工作環(huán)境 編譯程序模塊的軟件接口,從時(shí)間和空 間角度看,多遍編譯 少占內(nèi)存，多耗時(shí)間 一遍編譯 多占內(nèi)存，少耗時(shí)間,第一章 引 論,1.4 編譯程序與程序設(shè)計(jì)環(huán)境 編譯程序無疑是實(shí)現(xiàn)高級(jí)語(yǔ)言的一個(gè)最重要的工具。但支持程序設(shè)計(jì)人員進(jìn)行程序設(shè)計(jì)開發(fā)通常還需要其它一些工具：如編輯程序、連接程序、調(diào)試程序等。編譯程序與這些程序設(shè)計(jì)工具一起構(gòu)成所謂的程序設(shè)計(jì)環(huán)境。 在一個(gè)程序設(shè)計(jì)環(huán)境中，編譯程序起著中心的作用。連接程序、調(diào)試程序、程序分析等工具直接依賴于編譯程序所產(chǎn)生的結(jié)果，而其它工具的構(gòu)造也常常要用到編譯的原理、方法和技術(shù)。,第一章 引 論,1.5 編譯程序的生成 以前構(gòu)造編譯程序大多是用機(jī)器語(yǔ)言或匯編語(yǔ)言作工具的。為了充分發(fā)揮各種不同硬件系統(tǒng)的效率，為了滿足各種不同的具體要求，現(xiàn)在許多人仍然使用這種工具來構(gòu)造編譯程