編譯原理 第一章 引論

1、李波李波 教授教授西安交通大學(xué)西安交通大學(xué)編譯原理編譯原理Page 2西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心課程簡(jiǎn)介課程簡(jiǎn)介n為什么學(xué)習(xí)？為什么學(xué)習(xí)？n課程知識(shí)體系課程知識(shí)體系n課程安排課程安排編譯原理Page 3西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心核高基重大專項(xiàng)核高基重大專項(xiàng)核高核高基基核心電子器件高端通用芯片基礎(chǔ)軟件產(chǎn)品編譯原理Page 4西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心編譯原理Page 5西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心 核心核心1 1級(jí)課時(shí)級(jí)課時(shí)核心核心2 2級(jí)課時(shí)級(jí)課時(shí)是否選修是否選修面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蟪绦蛟O(shè)計(jì)46否函數(shù)式程序設(shè)計(jì)函數(shù)式程序設(shè)計(jì)34否事件驅(qū)動(dòng)和反應(yīng)性程序設(shè)計(jì)事件驅(qū)動(dòng)和反應(yīng)性程序設(shè)

2、計(jì)2否基本類型系統(tǒng)基本類型系統(tǒng)14否程序表示程序表示1否語(yǔ)言翻譯與執(zhí)行語(yǔ)言翻譯與執(zhí)行3否語(yǔ)法分析語(yǔ)法分析是編譯語(yǔ)義分析編譯語(yǔ)義分析是代碼生成代碼生成是運(yùn)行時(shí)系統(tǒng)運(yùn)行時(shí)系統(tǒng)是靜態(tài)分析靜態(tài)分析是高級(jí)程序構(gòu)造高級(jí)程序構(gòu)造是并發(fā)與并行并發(fā)與并行是類型系統(tǒng)類型系統(tǒng)是正則語(yǔ)義正則語(yǔ)義是語(yǔ)言語(yǔ)用學(xué)語(yǔ)言語(yǔ)用學(xué)是邏輯式程序設(shè)計(jì)邏輯式程序設(shè)計(jì)是Programming Languages (PLProgramming Languages (PL) )知識(shí)體知識(shí)體編譯原理Page 6西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心涉及程序設(shè)計(jì)與程序處理兩部分內(nèi)容涉及程序設(shè)計(jì)與程序處理兩部分內(nèi)容l面向?qū)ο蟪绦蛟O(shè)計(jì)面向?qū)ο蟪绦蛟O(shè)計(jì)l函數(shù)式

3、程序設(shè)計(jì)函數(shù)式程序設(shè)計(jì)l邏輯式程序設(shè)計(jì)邏輯式程序設(shè)計(jì)l事件驅(qū)動(dòng)事件驅(qū)動(dòng)和和反應(yīng)式程序設(shè)反應(yīng)式程序設(shè)計(jì)計(jì)l高級(jí)程序構(gòu)造高級(jí)程序構(gòu)造l并發(fā)與并發(fā)與并行并行l(wèi)語(yǔ)言語(yǔ)用學(xué)語(yǔ)言語(yǔ)用學(xué)l基本類型系統(tǒng)基本類型系統(tǒng)l程序表示程序表示l語(yǔ)言翻譯與執(zhí)行語(yǔ)言翻譯與執(zhí)行l(wèi)語(yǔ)法分析語(yǔ)法分析l編譯語(yǔ)義分析編譯語(yǔ)義分析l代碼生成代碼生成l運(yùn)行時(shí)系統(tǒng)運(yùn)行時(shí)系統(tǒng)l靜態(tài)分析靜態(tài)分析l類型系統(tǒng)類型系統(tǒng)l正則語(yǔ)義正則語(yǔ)義編譯原理Page 7西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心課程課程說(shuō)明說(shuō)明n課程課程內(nèi)容內(nèi)容u介紹把介紹把高級(jí)語(yǔ)言程序高級(jí)語(yǔ)言程序轉(zhuǎn)換為轉(zhuǎn)換為低級(jí)語(yǔ)言程序低級(jí)語(yǔ)言程序的原理和實(shí)現(xiàn)技術(shù)。的原理和實(shí)現(xiàn)技術(shù)。n課程課程目的目的u系

4、統(tǒng)系統(tǒng)地介紹地介紹程序分析程序分析、變換變換、運(yùn)行管理運(yùn)行管理及及優(yōu)化優(yōu)化等技術(shù)等技術(shù)。u提高提高程序構(gòu)造程序構(gòu)造能力能力u訓(xùn)練訓(xùn)練編譯技術(shù)的應(yīng)用編譯技術(shù)的應(yīng)用能力能力n編譯器編譯器設(shè)計(jì)實(shí)現(xiàn)設(shè)計(jì)實(shí)現(xiàn)、程序分析與驗(yàn)證程序分析與驗(yàn)證、程序轉(zhuǎn)換和程序轉(zhuǎn)換和優(yōu)化優(yōu)化。 編譯原理Page 8西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心教學(xué)安排教學(xué)安排n總總學(xué)時(shí)學(xué)時(shí)64 64 u課內(nèi)課內(nèi)學(xué)時(shí)學(xué)時(shí)5656，主要講授大綱中的知識(shí)點(diǎn)主要講授大綱中的知識(shí)點(diǎn)u上機(jī)實(shí)驗(yàn)上機(jī)實(shí)驗(yàn)8 8，將安排具體題目，提交結(jié)果，將安排具體題目，提交結(jié)果n綜合綜合成績(jī)：成績(jī)：u平時(shí)成績(jī)平時(shí)成績(jī)20%20%，包括上機(jī)、作業(yè)，包括上機(jī)、作業(yè) 上機(jī)上機(jī)：詞

5、法分析、語(yǔ)法分析：詞法分析、語(yǔ)法分析 作業(yè)作業(yè)：指定時(shí)間提交，過后不補(bǔ)：指定時(shí)間提交，過后不補(bǔ) u期末考試期末考試 8080編譯原理Page 9西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心教材及參考書教材及參考書n陳火旺等陳火旺等. 程序設(shè)計(jì)語(yǔ)言編譯原理（第程序設(shè)計(jì)語(yǔ)言編譯原理（第3版）版）. 國(guó)防工國(guó)防工業(yè)出版社業(yè)出版社.nKenneth C. Louden. Compiler Construction: Principles and Practice (英文版英文版1997). 機(jī)械工業(yè)出版社機(jī)械工業(yè)出版社, 2002nAlfred V. Aho, Ravi Sethi, Jeffrey D. Ullm

6、an. Compilers :principles, techniques, and tools(2001) 有有翻譯本：南大趙建華等譯翻譯本：南大趙建華等譯. 編譯原理編譯原理. 機(jī)械工業(yè)，機(jī)械工業(yè)，2009.編譯原理Page 10西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心主要教學(xué)內(nèi)容主要教學(xué)內(nèi)容l第一章, 1.1-1.5l第二章, 2.1-2.3l第三章, 3.1-3.3, 3.4l第四章, 4.1-4.6l第五章, 5.1, 5.2*, 5.3,5.4l第六章, 6.1-6.2, -*l第七章, 7.1-7.7l第八章, 8.1-8.4l第九章, 9.1-9.5, 9.6*l第十章, 10.1-10

7、.3, 11.4*引論引論形式語(yǔ)言簡(jiǎn)介形式語(yǔ)言簡(jiǎn)介詞法分析詞法分析自頂向下語(yǔ)法分析自頂向下語(yǔ)法分析自底向上語(yǔ)法分析自底向上語(yǔ)法分析屬性文法屬性文法中間代碼生成中間代碼生成符號(hào)表符號(hào)表運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織代碼優(yōu)化、寄存器分配代碼優(yōu)化、寄存器分配注意：講課內(nèi)容與教材內(nèi)容不是嚴(yán)格一致，對(duì)于一些內(nèi)容，課件中講注意：講課內(nèi)容與教材內(nèi)容不是嚴(yán)格一致，對(duì)于一些內(nèi)容，課件中講得更深入細(xì)致，另一些內(nèi)容則相比教材更簡(jiǎn)略，總體服從大綱要求。得更深入細(xì)致，另一些內(nèi)容則相比教材更簡(jiǎn)略，總體服從大綱要求。編譯原理Page 11西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明n先修課程：離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、程

8、序設(shè)計(jì)語(yǔ)言。先修課程：離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)語(yǔ)言。形形式語(yǔ)言與自動(dòng)機(jī)式語(yǔ)言與自動(dòng)機(jī)n學(xué)習(xí)本課程的目標(biāo)：理解學(xué)習(xí)本課程的目標(biāo)：理解編譯過程編譯過程；能夠編寫簡(jiǎn)單的；能夠編寫簡(jiǎn)單的編譯程序編譯程序；有進(jìn)行；有進(jìn)行程序分析、變換、評(píng)價(jià)程序分析、變換、評(píng)價(jià)的基礎(chǔ)。的基礎(chǔ)。n學(xué)習(xí)的途徑學(xué)習(xí)的途徑：u原理原理入手（掌握知識(shí)點(diǎn)入手（掌握知識(shí)點(diǎn)）u掌握掌握相關(guān)理論方法和技術(shù)相關(guān)理論方法和技術(shù)方法方法u多多做練習(xí)。做練習(xí)。n本課程的編程實(shí)驗(yàn)推薦采用本課程的編程實(shí)驗(yàn)推薦采用C C或或JavaJava編程進(jìn)行編程進(jìn)行。編譯原理Page 12西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心編譯理論自動(dòng)機(jī)和形式語(yǔ)言離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)

9、機(jī)器、操作系統(tǒng)支撐工具基礎(chǔ)控制對(duì)象編譯理論與其他課程關(guān)系編譯理論與其他課程關(guān)系編譯原理Page 13西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心課堂討論：學(xué)習(xí)的意義和課程特點(diǎn)課堂討論：學(xué)習(xí)的意義和課程特點(diǎn)n意義：意義：u學(xué)習(xí)編譯程序構(gòu)造原理，技術(shù)學(xué)習(xí)編譯程序構(gòu)造原理，技術(shù)u更好地理解高級(jí)語(yǔ)言更好地理解高級(jí)語(yǔ)言u(píng)編譯的原理和方法可用于構(gòu)造一些實(shí)用的工具編譯的原理和方法可用于構(gòu)造一些實(shí)用的工具n課程特點(diǎn)課程特點(diǎn): :u理解性理解性原理原理u技術(shù)性技術(shù)性實(shí)現(xiàn)實(shí)現(xiàn)u因?yàn)榫幾g程序極其復(fù)雜，故討論中將其肢解，學(xué)習(xí)中應(yīng)注意因?yàn)榫幾g程序極其復(fù)雜，故討論中將其肢解，學(xué)習(xí)中應(yīng)注意前后聯(lián)系，多做聯(lián)系前后聯(lián)系，多做聯(lián)系編譯原理Pa

10、ge 14西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心有窮狀態(tài)技術(shù)模式識(shí)別情報(bào)檢索文本編輯程序上下文無(wú)關(guān)文法語(yǔ)法制導(dǎo)翻譯建立多種文本處理程序代碼優(yōu)化技術(shù)由非結(jié)構(gòu)化到結(jié)構(gòu)化的程序轉(zhuǎn)換程序校驗(yàn)編譯技術(shù)的應(yīng)用編譯技術(shù)的應(yīng)用CTEC.XJTU.EDU.CN編譯原理Page 15西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心第一章第一章 引論引論李波 計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心 高效能建模與仿真研究小組西安交通大學(xué) 編譯原理Page 16西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心第一章第一章 引論引論n什么叫編譯程序什么叫編譯程序n編譯過程概述編譯過程概述n編譯程序的結(jié)構(gòu)及生成編譯程序的結(jié)構(gòu)及生成編譯原理Page 17西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心1.

11、1 1.1 什么叫編譯程序？什么叫編譯程序？錯(cuò)誤及警告錯(cuò)誤及警告輸入輸入輸出輸出編譯程序編譯程序源程序源程序目標(biāo)程序目標(biāo)程序源源語(yǔ)語(yǔ)言言目目標(biāo)標(biāo)語(yǔ)語(yǔ)言言實(shí)現(xiàn)語(yǔ)言實(shí)現(xiàn)語(yǔ)言if(a=b) a=2; b=4;.mov a, R1mov b, R2.詞法分析詞法分析語(yǔ)法分析語(yǔ)法分析語(yǔ)義處理語(yǔ)義處理代碼生成代碼生成代碼優(yōu)化代碼優(yōu)化功能上等價(jià)功能上等價(jià)編譯原理Page 18西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心幾個(gè)注意的問題幾個(gè)注意的問題源語(yǔ)言是高級(jí)語(yǔ)言源語(yǔ)言是高級(jí)語(yǔ)言, ,目標(biāo)語(yǔ)言是低級(jí)語(yǔ)言時(shí)目標(biāo)語(yǔ)言是低級(jí)語(yǔ)言時(shí)? ? 源語(yǔ)言源語(yǔ)言和目標(biāo)語(yǔ)言任意時(shí)和目標(biāo)語(yǔ)言任意時(shí)? ?書寫編譯器的語(yǔ)言可以是高級(jí)語(yǔ)言也可以是低級(jí)

12、語(yǔ)言書寫編譯器的語(yǔ)言可以是高級(jí)語(yǔ)言也可以是低級(jí)語(yǔ)言. .運(yùn)行編譯器的機(jī)器跟運(yùn)行目標(biāo)程序的機(jī)器可以相同也運(yùn)行編譯器的機(jī)器跟運(yùn)行目標(biāo)程序的機(jī)器可以相同也可以不同可以不同. .編譯器編譯器/ /翻譯程序翻譯程序用什么語(yǔ)言編寫編譯器無(wú)關(guān)緊要用什么語(yǔ)言編寫編譯器無(wú)關(guān)緊要編譯器編譯器/ /交叉編譯器交叉編譯器宿主機(jī)宿主機(jī)/ /目標(biāo)機(jī)目標(biāo)機(jī)編譯原理Page 19西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心語(yǔ)言的抽象層次語(yǔ)言的抽象層次n機(jī)器語(yǔ)言：機(jī)器語(yǔ)言：能夠被計(jì)算機(jī)的硬件直接能夠被計(jì)算機(jī)的硬件直接執(zhí)行的指令程序執(zhí)行的指令程序 n匯編語(yǔ)言：匯編語(yǔ)言：將硬件指令用一些助記符表將硬件指令用一些助記符表 示。如示。如ADDADD

13、表示加法操作，表示加法操作， SUBSUB表示減法操作等等表示減法操作等等 n高級(jí)語(yǔ)言：高級(jí)語(yǔ)言：相對(duì)于前二者而言且更接近相對(duì)于前二者而言且更接近 于自然語(yǔ)言的程序設(shè)計(jì)語(yǔ)言于自然語(yǔ)言的程序設(shè)計(jì)語(yǔ)言Properties：need to be preciseneed to be conciseneed to be expressiveneed to be at a high-level (lot of abstractions)編譯原理Page 20西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心編譯器的種類編譯器的種類n診斷編譯程序診斷編譯程序u側(cè)重于錯(cuò)誤信息，幫助開發(fā)調(diào)試側(cè)重于錯(cuò)誤信息，幫助開發(fā)調(diào)試n優(yōu)化編譯程

14、序優(yōu)化編譯程序u側(cè)重于提高代碼效率側(cè)重于提高代碼效率n交叉編譯程序交叉編譯程序u宿主機(jī)和目標(biāo)機(jī)不是同一個(gè)機(jī)器宿主機(jī)和目標(biāo)機(jī)不是同一個(gè)機(jī)器n可變目標(biāo)編譯程序可變目標(biāo)編譯程序u僅定制編譯器中跟機(jī)器有關(guān)部分實(shí)現(xiàn)針對(duì)新目標(biāo)機(jī)的代碼生僅定制編譯器中跟機(jī)器有關(guān)部分實(shí)現(xiàn)針對(duì)新目標(biāo)機(jī)的代碼生成成編譯原理Page 21西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心解釋器和編譯器特點(diǎn)解釋器和編譯器特點(diǎn)n概念上的不同（翻譯概念上的不同（翻譯/ /直接執(zhí)行）。直接執(zhí)行）。n基于解釋執(zhí)行的程序可以動(dòng)態(tài)修改自身，而基于編譯基于解釋執(zhí)行的程序可以動(dòng)態(tài)修改自身，而基于編譯執(zhí)行的程序動(dòng)態(tài)性較弱。執(zhí)行的程序動(dòng)態(tài)性較弱。n基于解釋方式有利于人機(jī)交

15、互。基于解釋方式有利于人機(jī)交互。n基于解釋執(zhí)行的速度較慢。基于解釋執(zhí)行的速度較慢。n解釋器需要保存的信息較多，空間開銷大解釋器需要保存的信息較多，空間開銷大n二者實(shí)現(xiàn)技術(shù)相似。二者實(shí)現(xiàn)技術(shù)相似。編譯原理Page 22西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心課堂討論：英譯漢的預(yù)備知識(shí)、能力、過程課堂討論：英譯漢的預(yù)備知識(shí)、能力、過程預(yù)備預(yù)備知識(shí)及能力知識(shí)及能力設(shè)計(jì)設(shè)計(jì)/ /掌握掌握源語(yǔ)言源語(yǔ)言理解理解/ /掌握掌握目標(biāo)語(yǔ)言目標(biāo)語(yǔ)言應(yīng)用應(yīng)用/ /掌握掌握翻譯翻譯方法方法把把英文英文翻譯翻譯為為中文中文 的主要過程的主要過程識(shí)別識(shí)別出英文句子中的一個(gè)個(gè)出英文句子中的一個(gè)個(gè)單詞單詞；分析分析句子的句子的語(yǔ)法結(jié)構(gòu)

16、語(yǔ)法結(jié)構(gòu)；根據(jù)句子的根據(jù)句子的含義含義進(jìn)行進(jìn)行初步翻譯初步翻譯；對(duì)譯文進(jìn)行對(duì)譯文進(jìn)行修飾修飾；寫出最后的寫出最后的譯文譯文。編譯原理Page 23西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心1.2 1.2 編譯過程概述編譯過程概述int sumcalc(int a, int b, int N) int i; int x, y; x = 0; y = 0; for(i = 0; i = N; i+) x = x + ( 4 * a / b ) * i + (i+1)*(i+1); x = x + b*y; return x;編譯原理Page 24西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心編譯過程編譯過程詞法分析語(yǔ)法分析語(yǔ)

17、義分析代碼優(yōu)化代碼生成源程序（字符流）源程序（字符流）單詞符號(hào)（單詞符號(hào)（Token流）流）語(yǔ)法單位（語(yǔ)法樹語(yǔ)法單位（語(yǔ)法樹Parse樹）樹）中間表示中間表示優(yōu)化的中間表示優(yōu)化的中間表示目標(biāo)代碼（匯編代碼）目標(biāo)代碼（匯編代碼）編譯原理Page 25西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心Step1 Step1 詞法分析詞法分析l依循語(yǔ)言的詞法規(guī)則，掃描源程序的字符串，識(shí)別每依循語(yǔ)言的詞法規(guī)則，掃描源程序的字符串，識(shí)別每一個(gè)單詞，并將其表示成內(nèi)部表示形式，即一個(gè)單詞，并將其表示成內(nèi)部表示形式，即TOKEN.Num(234) mul_op lpar_op Num(11) add_op Num(-22) rp

18、ar_op源程序字符流：源程序字符流：TOKENTOKEN流：流：編譯原理Page 26西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心Step1 Step1 詞法分析詞法分析不是數(shù)不是數(shù)變量名不能有字符變量名不能有字符文法；文法； 正規(guī)式；正規(guī)式； 有限自動(dòng)機(jī)有限自動(dòng)機(jī) 18.23val#ue+編譯原理Page 27西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心TokenToken例子例子l標(biāo)識(shí)符標(biāo)識(shí)符( (用戶定義的名字用戶定義的名字); identifier); identifierl保留字保留字( (關(guān)鍵字關(guān)鍵字/ /基本字基本字); reserved words); reserved wordsl常數(shù)常數(shù)( (整數(shù)整

19、數(shù), ,雙精度數(shù)雙精度數(shù), ,浮點(diǎn)數(shù)浮點(diǎn)數(shù));constant);constantl界符界符( (分隔符分隔符); delimiters); delimitersl運(yùn)算符運(yùn)算符( (操作符操作符); operators ); operators 編譯原理Page 28西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心例子例子; ; ; l ll la aa ae ee e1 1z z1 1x xa aa ar rn ni ib be et ti ir rw w; ;5 55 5+ +1 1x x= =: :z z1 1x x5 5. .0 0= =1 1= =z z; ;) )1 1( (d da ae er r

20、) ); ;. .5 51 1z z( (. .# #n nd d 1 1x x1 1z z源程序在文件中的表示源程序在文件中的表示e eg gv vr rr rr rv v: : : :; ;+ +5 5V V1 1+ +e e: :編譯原理Page 29西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心($id,z1)($id,z1)（$begin$begin，），）($line($line，-)-)($line($line，-)-)（$semi$semi，），）（$assig $assig ，），）($id,x1)($id,x1)（$semi$semi，），）（$semi$semi，），）（$real$re

21、al，），）（$real$real，），）（$colon$colon，），）($line($line，-)-)($line($line，-)-)（$var$var，）（$var$var，）$assig$assig($realC($realC，0.5)0.5)（$colon$colon，），）($id,x1)($id,x1)($line($line，-)-)($line($line，-)-)（$semi$semi，）($intC($intC，55)55)（$plus$plus，），）（$assig$assig，），）($id,x1)($id,x1)($id,z1)($id,z1)$Lparen$

22、Lparen，），）（$read$read，），）（$semi$semi，）($realC($realC，5.5)5.5)$Rparen$Rparen，），）（$plus$plus，），）($id,z1)($id,z1)（$write$write，），）$LparenLparen，)# #（$stop $stop ，），）（$end $end ，），）($id,x1)($id,x1)（$plus $plus ，），）($id,z1)($id,z1)($id,z1)($id,z1)（$semi$semi，），）($id,x1)($id,x1)$Rparen$Rparen，），）詞法分析后的詞法分

23、析后的TOKENTOKEN表示表示編譯原理Page 30西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心課堂練習(xí)課堂練習(xí)nFOR I := 1 TO 100 DOFOR I := 1 TO 100 DOn保留字保留字 標(biāo)識(shí)符標(biāo)識(shí)符 等符等符 整常數(shù)整常數(shù) 保留字保留字 整常數(shù)整常數(shù) 保留字保留字編譯原理Page 31西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心Step2 Step2 語(yǔ)法分析語(yǔ)法分析n依據(jù)語(yǔ)言的語(yǔ)法規(guī)則，將程序的依據(jù)語(yǔ)言的語(yǔ)法規(guī)則，將程序的TokenToken序列轉(zhuǎn)化為語(yǔ)序列轉(zhuǎn)化為語(yǔ)法單位（語(yǔ)法范疇）（短語(yǔ)、子句、句子、程序段、法單位（語(yǔ)法范疇）（短語(yǔ)、子句、句子、程序段、程序），并確定整個(gè)輸入串是否構(gòu)成一個(gè)

24、語(yǔ)法上正確程序），并確定整個(gè)輸入串是否構(gòu)成一個(gè)語(yǔ)法上正確的程序。的程序。n確定確定TokenToken之間有什么之間有什么關(guān)系關(guān)系例：例：Z Z := X + 0.618 := X + 0.618 * * Y Y 算術(shù)表達(dá)式算術(shù)表達(dá)式(0.618 (0.618 * * Y Y) ) 算術(shù)表達(dá)式算術(shù)表達(dá)式(X + 0.618 (X + 0.618 * * Y Y) ) 賦值賦值語(yǔ)句語(yǔ)句( (全部全部) )編譯原理Page 32西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心TONEXTFORKNMIJKKK:=100:=:=11010+*+變量、常數(shù)及其運(yùn)算結(jié)果均是表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式表達(dá)式賦值句

25、的形式為“變量：表達(dá)式”賦值句賦值句多個(gè)賦值句可構(gòu)成語(yǔ)句塊語(yǔ)句塊表達(dá)式可作為循環(huán)的初值和終值初值終值簡(jiǎn)單數(shù)值變量可作為循環(huán)的控制變量控制變量控制變量此時(shí)可以看出上述結(jié)果符合循環(huán)語(yǔ)句的語(yǔ)法定義，故語(yǔ)法分析成功完成示例示例編譯原理Page 33西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心語(yǔ)法分析語(yǔ)法分析num * ( num + num ) *num()+numnum文法；語(yǔ)法樹； 推導(dǎo)； 規(guī)約；LL(1)分析法LR分析法 Token流：流： 語(yǔ)法樹：語(yǔ)法樹： 例如：例如：10*（9+13）編譯原理Page 34西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心語(yǔ)法分析語(yǔ)法分析int * foo(i, j, k) int i; i

26、nt j; for(i=0; i j) fi(ij) return j;多余的括號(hào)缺少步長(zhǎng)不是表達(dá)式不是保留字編譯原理Page 35西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心Step3 Step3 語(yǔ)義分析語(yǔ)義分析n對(duì)語(yǔ)法分析所識(shí)別出的各類語(yǔ)法范疇，分析其含義，對(duì)語(yǔ)法分析所識(shí)別出的各類語(yǔ)法范疇，分析其含義，查錯(cuò)查錯(cuò), , 并產(chǎn)生源程序所對(duì)應(yīng)的中間表示（中間代碼）。并產(chǎn)生源程序所對(duì)應(yīng)的中間表示（中間代碼）。n確定確定整體結(jié)構(gòu)的含義整體結(jié)構(gòu)的含義屬性文法； 語(yǔ)義函數(shù) 編譯原理Page 36西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心語(yǔ)義分析語(yǔ)義分析int * foo(i, j, k) int i; int j; int x

27、; x = x + j + N; return j; 類型未說(shuō)明類型未說(shuō)明返回結(jié)果類型不匹配返回結(jié)果類型不匹配使用了沒有初始化的變量使用了沒有初始化的變量變量未說(shuō)明變量未說(shuō)明編譯原理Page 37西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心TONEXTFORKNMIJKKK:=100:=:=11010+*+(1) ( :=, 1, , K )(2) ( j,100, K, )(3) ( *, 10, K, T1 )(8) ( j, , , (2)(7) ( +, K, 1, K )(4) ( +, I, T1, M )(9) ( )(9)(5) ( *, 10, K, T2 )(6) ( +, J, T2,

28、 N )T1T2(1) K := 1(2) if 100K goto (9)(3) T1 := 10 * K(8) goto (2)(7) K := K + 1(4) M := I + T1(9)(5) T2 := 10 * K(6) N := J + T2循環(huán)語(yǔ)句出口語(yǔ)句循環(huán)塊STEP 1生成四元式將四元式重寫為另一種形式的中間代碼(1) ( :=, 1, , K )(2) ( j,100, K, (9)(3) ( *, 10, K, T1 )(8) ( j, , , (2)(7) ( +, K, 1, K )(4) ( +, I, T1, M )(9) ( )(5) ( *, 10, K,

29、 T2 )(6) ( +, J, T2, N )循環(huán)語(yǔ)句和出口語(yǔ)句 彼此相連地被定義包括循環(huán)語(yǔ)句開始到有同一控制變量的第一個(gè)出口語(yǔ)句的那些語(yǔ)句的自然序列稱為一循環(huán)塊塊嵌套不可交叉，嵌套塊控制變量不可同名不正確正確嵌套缺省的 STEP = STEP 1中間代碼產(chǎn)生示例中間代碼產(chǎn)生示例編譯原理Page 38西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心Step4 Step4 優(yōu)優(yōu) 化化int sumcalc(int a, int b, int N)int i;int x, t, u, v;x = 0;u = (a2/b);v = 0;for(i = 0; i = N; i+) t = i+1;x = x + v

30、+ t*t;v = v + u;return x;int sumcalc(int a, int b, int N)int i;int x, y;x = 0;y = 0;for(i = 0; i = N; i+) x = x + (4*a/b)*i + (i+1)*(i+1);x = x + b*y;return x;程序等價(jià)變換； 控制流、數(shù)據(jù)流分析 編譯原理Page 39西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心(1) K := 1(2) if 100K goto (9)(3) T1 := 10 * K(8) goto (2)(7) K := K + 1(4) M := I + T1(9)(5) T2

31、:= 10 * K(6) N := J + T2(3) K := 1(4) if 100K goto (9)(8) goto (4)(7) K := K + 1(9)(3) T1 := 10 * K(4) M := I + T1(1) M := I(5) M := M + 10 (5) T2 := 10 * K(6) N := J + T2(2) N := J(6) N := N + 10(1) K := 1(2) if 100K goto (9)(8) goto (2)(7) K := K + 1(9)中間代碼優(yōu)化中間代碼優(yōu)化編譯原理Page 40西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心40編譯原理P

32、age 41西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心Step5 Step5 代碼生成代碼生成n中間代碼變換為特定機(jī)器上的絕對(duì)指令代碼或可重定中間代碼變換為特定機(jī)器上的絕對(duì)指令代碼或可重定位的指令代碼或匯編指令代碼位的指令代碼或匯編指令代碼。n目標(biāo)代碼目標(biāo)代碼三種形式三種形式: :u絕對(duì)指令絕對(duì)指令代碼代碼: : 可可直接運(yùn)行直接運(yùn)行 u可重新定位指令可重新定位指令代碼代碼: : 連接裝配連接裝配u匯編指令匯編指令代碼代碼: : 需要進(jìn)行需要進(jìn)行匯編匯編編譯原理Page 42西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心LD R1, IL2: ST R1, MLD R2, JST R2, NLD R0, 1L1: CMP

33、 100, R0J L2ADD R1, 10ADD R2, 10ADD R0, 1J L1(8) goto (4)(7) K := K + 1(1) M := I(9)(6) N := N + 10(3) K := 1(2) N := J(5) M := M + 10 (4) if 100K goto (9)(9)(8) goto (4)(7) K := K + 1(1) M := I(6) N := N + 10(3) K := 1(2) N := J(4) if 100K goto (9)(5) M := M + 10 目標(biāo)代碼生成示例目標(biāo)代碼生成示例編譯原理Page 43西安交通大學(xué)計(jì)算

34、機(jī)教學(xué)實(shí)驗(yàn)中心1.3 1.3 編譯程序的編譯程序的結(jié)構(gòu)及生成結(jié)構(gòu)及生成表表格格管管理理詞法分析詞法分析語(yǔ)法分析語(yǔ)法分析中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成源程序源程序單詞符號(hào)單詞符號(hào)中間代碼中間代碼語(yǔ)法單位語(yǔ)法單位目標(biāo)代碼目標(biāo)代碼中間代碼中間代碼出出錯(cuò)錯(cuò)處處理理編譯原理Page 44西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心表格管理表格管理n表格的作用和種類表格的作用和種類u保存編譯各階段的有用信息保存編譯各階段的有用信息u符號(hào)表符號(hào)表u常數(shù)表常數(shù)表u保留字表保留字表u其他其他n表格操作表格操作u關(guān)注方便性和時(shí)空效率關(guān)注方便性和時(shí)空效率編譯原理Page 45西安交通大學(xué)計(jì)算機(jī)教

35、學(xué)實(shí)驗(yàn)中心出錯(cuò)處理出錯(cuò)處理n語(yǔ)法錯(cuò)誤語(yǔ)法錯(cuò)誤 不符合語(yǔ)法（或詞法）規(guī)則的錯(cuò)誤。不符合語(yǔ)法（或詞法）規(guī)則的錯(cuò)誤。單詞單詞拼寫錯(cuò)誤、括號(hào)不匹配等拼寫錯(cuò)誤、括號(hào)不匹配等 n語(yǔ)義錯(cuò)誤語(yǔ)義錯(cuò)誤 不符合語(yǔ)義規(guī)則的錯(cuò)誤不符合語(yǔ)義規(guī)則的錯(cuò)誤。說(shuō)明錯(cuò)誤、作用。說(shuō)明錯(cuò)誤、作用域錯(cuò)誤、類型不匹配等域錯(cuò)誤、類型不匹配等n全全 最大限度發(fā)現(xiàn)錯(cuò)誤最大限度發(fā)現(xiàn)錯(cuò)誤n準(zhǔn)準(zhǔn) 準(zhǔn)確指出錯(cuò)誤的性質(zhì)和發(fā)生地點(diǎn)準(zhǔn)確指出錯(cuò)誤的性質(zhì)和發(fā)生地點(diǎn)n局部化局部化 將錯(cuò)誤的影響限制在盡可能小的范圍內(nèi)將錯(cuò)誤的影響限制在盡可能小的范圍內(nèi)編譯原理Page 46西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心一遍與多遍編譯一遍與多遍編譯n是對(duì)源程序或編譯中間結(jié)果從頭到尾掃

36、描一次，并做是對(duì)源程序或編譯中間結(jié)果從頭到尾掃描一次，并做有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。有關(guān)的加工處理，生成新的中間結(jié)果或目標(biāo)程序。n注意注意各遍間的中間結(jié)果（內(nèi)部形式、外部形式各遍間的中間結(jié)果（內(nèi)部形式、外部形式）nOne-pass compiler: One-pass compiler: uType Type of software compiler that passes through the source of software compiler that passes through the source code only once. code only once.

37、 uOne-pass One-pass compilers are faster, but may not generate an compilers are faster, but may not generate an as efficient program. as efficient program. uIn In addition, one-pass compilers cannot compile all types addition, one-pass compilers cannot compile all types of source codes. of source co

38、des. uhttp:/ 47西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心詞法分析語(yǔ)法分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成一遍語(yǔ)法分析器處于核心地位一遍 局部?jī)?yōu)化一遍一遍 全局優(yōu)化課題討論：遍設(shè)計(jì)示例課題討論：遍設(shè)計(jì)示例編譯原理Page 48西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心編譯前端與后端編譯前端與后端n前端指跟目標(biāo)機(jī)無(wú)關(guān)的部分，一般包括：詞法、語(yǔ)法、前端指跟目標(biāo)機(jī)無(wú)關(guān)的部分，一般包括：詞法、語(yǔ)法、語(yǔ)義分析；語(yǔ)義分析；n后端指跟目標(biāo)機(jī)有關(guān)的部分，一般包括優(yōu)化和代碼生后端指跟目標(biāo)機(jī)有關(guān)的部分，一般包括優(yōu)化和代碼生成；成；n前后端之間的接口：前后端之間的接口：u中間表示中間表示u符號(hào)表符號(hào)表編譯原理Page 49西

39、安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心詞法分析語(yǔ)法分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成編譯前端主要由與源語(yǔ)言有關(guān)但與目標(biāo)機(jī)無(wú)關(guān)的那些部分組成編譯后端包括編譯程序中與目標(biāo)機(jī)有關(guān)的那些部分編譯前端與后端編譯前端與后端 編譯原理Page 50西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心n5050編譯原理Page 51西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心中間表示的應(yīng)用：中間表示的應(yīng)用：JAVAJAVA語(yǔ)言語(yǔ)言編譯原理Page 52西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心中間表示的應(yīng)用：中間表示的應(yīng)用：.NET.NET框架框架編譯原理Page 53西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心用什么語(yǔ)言書寫編譯程序？用什么語(yǔ)言書寫編譯程序？n用高級(jí)語(yǔ)言書寫編譯程序優(yōu)缺點(diǎn)課堂討論用高級(jí)語(yǔ)言書寫編譯程序優(yōu)缺點(diǎn)課堂討論編譯原理Page 54西安交通大學(xué)計(jì)算機(jī)教學(xué)實(shí)驗(yàn)中心T T型圖型圖nS Source LanguagenT Target LanguagenI Implementation LanguageS TI由用由用I I語(yǔ)言寫的編譯程序把用語(yǔ)言寫的編譯程序把用S S語(yǔ)言寫的源程序語(yǔ)言寫的源程序翻譯成用翻譯