編譯原理簡(jiǎn)明教程(第2版)馮秀芳,崔冬華,段富電子教案第1章

《編譯原理簡(jiǎn)明教程》普通高等教育“十二五”規(guī)劃計(jì)算機(jī)教材---太原理工大學(xué)---計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院---馮秀芳、崔冬華、段富等第一章引言第二章形式語(yǔ)言理論基礎(chǔ)第三章自動(dòng)機(jī)理論基礎(chǔ)第四章詞法分析第五章語(yǔ)法分析—自頂向下分析方法第六章語(yǔ)法分析—自底向上分析方法第七章語(yǔ)義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號(hào)表第十一章目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織與分配第十二章出錯(cuò)處理第十三章編譯程序自動(dòng)生成工具簡(jiǎn)介第十四章面向?qū)ο笳Z(yǔ)言的編譯第十五章并行編譯技術(shù)目錄第一章引言

學(xué)習(xí)目標(biāo)了解和掌握高級(jí)程序設(shè)計(jì)語(yǔ)言與編譯程序的關(guān)系了解和掌握編譯程序的功能了解和掌握編譯程序的體系結(jié)構(gòu)了解和掌握編譯程序的工作過(guò)程了解和掌握編譯程序的組織方式了解和掌握編譯程序的構(gòu)造方法

“編譯原理”，“編譯技術(shù)”是計(jì)算機(jī)專(zhuān)業(yè)一門(mén)重要的專(zhuān)業(yè)課。目的是系統(tǒng)地向?qū)W生講授編譯程序的基本結(jié)構(gòu)。闡述編譯原理的一般理論和常用的有效方法與技術(shù)。學(xué)習(xí)本課后，使學(xué)生掌握編譯理論和方法方面的基本知識(shí)，具有設(shè)計(jì)、實(shí)現(xiàn)、分析和維護(hù)編譯程序等方面的初步能力。主要內(nèi)容：形式語(yǔ)言與自動(dòng)機(jī)、詞法分析、語(yǔ)法、語(yǔ)義、中間語(yǔ)言代碼生成、優(yōu)化、存儲(chǔ)組織與分配、程序的查錯(cuò)與處理等。1.1編譯程序、匯編程序、解釋程序1.2編譯過(guò)程概述1.3編譯程序的結(jié)構(gòu)框圖1.4編譯程序的開(kāi)發(fā)目錄1.1程序的翻譯及運(yùn)行

計(jì)算機(jī)系統(tǒng)：硬件軟件：系統(tǒng)軟件：OS、編譯系統(tǒng)、診斷系統(tǒng)應(yīng)用軟件等程序設(shè)計(jì)語(yǔ)言：機(jī)器匯編高級(jí)翻譯程序：指能把A語(yǔ)言程序翻譯成與之等價(jià)的B語(yǔ)言程序的程序。

A語(yǔ)言----源程序B語(yǔ)言----目標(biāo)語(yǔ)言1.1.1什么是編譯程序編譯程序：A——高級(jí)語(yǔ)言B——機(jī)器語(yǔ)言1.1.2

匯編程序

A語(yǔ)言——匯編語(yǔ)言（符號(hào)表示）

B語(yǔ)言——機(jī)器語(yǔ)言

1.1.3

解釋程序不產(chǎn)生目標(biāo)程序，逐句翻譯。優(yōu)點(diǎn)：l提供一種直接的交互調(diào)試能力，在執(zhí)行用戶(hù)程序時(shí)可以修改用戶(hù)程序。l

對(duì)新的類(lèi)型可動(dòng)態(tài)地修改，如符號(hào)的意義。

l

提高良好的診斷信息l

不依賴(lài)于目標(biāo)機(jī)，移植性較好。缺點(diǎn)：開(kāi)銷(xiāo)大、速度慢如APL與編譯程序相比1：100BASIC1：10事實(shí)上，純粹的解釋程序并不多見(jiàn)，通常做某種程序的結(jié)合。

1.2編譯過(guò)程概述

綜合分析翻譯外文資料閱讀原文、識(shí)別單詞分析句子的語(yǔ)法結(jié)構(gòu)根據(jù)句子含義初步分析修辭加工寫(xiě)出譯文編譯源程序掃描源程序、詞法分析語(yǔ)法分析語(yǔ)義分析優(yōu)化生成目標(biāo)代碼編譯程序一般分五個(gè)部分一、詞法分析

輸入源程序，對(duì)源程序構(gòu)成的字符串進(jìn)行掃描和分析，識(shí)別出一個(gè)個(gè)的單詞，如保留字、標(biāo)識(shí)符、常數(shù)、特殊符號(hào)等。如保留字(if、for、while等)、標(biāo)識(shí)符、常數(shù)、特殊符號(hào)(標(biāo)點(diǎn)符號(hào)、左右括號(hào)、運(yùn)算符等)。例如，對(duì)于C語(yǔ)言的循環(huán)語(yǔ)句：for(i=1;i<=100;i++)sum=sum+1;詞法分析：遵循詞法規(guī)則，描述詞法規(guī)則正規(guī)式和有限自動(dòng)機(jī)

二、語(yǔ)法分析

根據(jù)語(yǔ)言語(yǔ)法規(guī)則，把詞法分析后的單詞合成各類(lèi)語(yǔ)法單位（語(yǔ)法范疇），如“短語(yǔ)”，“句子”，“程序段”，“程序”。

例：Z=X+2*Y；賦值語(yǔ)句遵循語(yǔ)法規(guī)則，采用上下文無(wú)關(guān)文法描述。三、語(yǔ)義分析及中間代碼的生成

根據(jù)語(yǔ)法結(jié)構(gòu)，分析其含義，并進(jìn)行初步翻譯（生成中間代碼），或直接生成目標(biāo)代碼。例，對(duì)常用的一些語(yǔ)言來(lái)說(shuō)，語(yǔ)義分析生成語(yǔ)法成分的含義和用途，以及應(yīng)進(jìn)行的運(yùn)算和操作，而且要進(jìn)行語(yǔ)義檢查，如在說(shuō)明語(yǔ)句中是否有矛盾的類(lèi)型說(shuō)明；在表達(dá)式中，對(duì)某些運(yùn)算符而言，是否有類(lèi)型不匹配的運(yùn)算對(duì)象；在過(guò)程調(diào)用中，實(shí)參和形參是否在個(gè)數(shù)、次序、種屬等方面按相應(yīng)語(yǔ)言的規(guī)定進(jìn)行對(duì)應(yīng)等等。

“中間代碼”是一種含義明確、便于處理的記號(hào)系統(tǒng)。如：三元式、四元式、逆波蘭式。例：四元式（運(yùn)算符，第一運(yùn)算量，第二運(yùn)算量，結(jié)果）

z=(x

+3)*y/w;（+，x，3，T1）（*，T1,y,T2

）

(/,T2,w，z)四、代碼優(yōu)化

優(yōu)化的任務(wù)在于對(duì)前階段產(chǎn)生的中間代碼進(jìn)行加工變換，以期在最后階段產(chǎn)生出更為高效(節(jié)省時(shí)間和空間)的目標(biāo)代碼。優(yōu)化的主要方面有：公共子表達(dá)式的提取、循環(huán)優(yōu)化、刪除無(wú)用代碼等。有時(shí)，為了便于“并行運(yùn)算”，還可以對(duì)代碼進(jìn)行并行優(yōu)化處理。優(yōu)化所依循的原則是程序的等價(jià)變換規(guī)則。優(yōu)化涉及的范圍很廣。與機(jī)器有關(guān)的從與具體計(jì)算機(jī)的關(guān)系分與機(jī)器無(wú)關(guān)的局部?jī)?yōu)化從與源程序的關(guān)系分全局優(yōu)化五、目標(biāo)代碼生成

把中間代碼變成特定機(jī)器上的機(jī)器代碼。這部分涉及到硬件,如各種數(shù)據(jù)類(lèi)型變量的存儲(chǔ)空間分配，寄存器的調(diào)度等。例：盡量使用執(zhí)行速度快的指令，充分利用計(jì)算機(jī)的寄存器，以節(jié)省訪(fǎng)問(wèn)內(nèi)存所用時(shí)間等。1.3編譯程序的結(jié)構(gòu)框圖信息表管理源程序目標(biāo)代碼生成目標(biāo)程序出錯(cuò)處理詞法分析優(yōu)化語(yǔ)義分析語(yǔ)法分析1.4編譯程序的開(kāi)發(fā)

編譯程序是一個(gè)非常復(fù)雜的軟件系統(tǒng)，雖然編譯理論和技術(shù)不斷發(fā)展，開(kāi)發(fā)周期縮短，但研制仍需大量時(shí)間。追求目標(biāo)過(guò)程自動(dòng)化。

1.4.1開(kāi)發(fā)步驟

1.認(rèn)真分析，合理分工

2.算法設(shè)計(jì)，方案確定

3.語(yǔ)言選擇，編制程序

4.調(diào)試程序，確保質(zhì)量

5.資料整理，文本形成1.4.2開(kāi)發(fā)技術(shù)

一、系統(tǒng)程序設(shè)計(jì)語(yǔ)言

70年代以前，用機(jī)器語(yǔ)言、匯編語(yǔ)言，手工編寫(xiě)工作量大、可靠性差、難以維護(hù)。

80年代以后，高級(jí)語(yǔ)言如PASCAL、ADA、C，工作量大大減少，縮短開(kāi)發(fā)周期。系統(tǒng)程序程序設(shè)計(jì)語(yǔ)言：

編寫(xiě)編譯程序或其它系統(tǒng)軟件的高級(jí)語(yǔ)言。二、開(kāi)發(fā)技術(shù)1.

自編譯：用某一高級(jí)語(yǔ)言編寫(xiě)其自己的編譯程序。2.交叉編譯：A機(jī)器上的編譯程序能產(chǎn)生B機(jī)器上的目標(biāo)代碼。3.自展：首先確定一個(gè)非常簡(jiǎn)單的核心語(yǔ)言L(fǎng)0，用機(jī)器的匯編語(yǔ)言寫(xiě)其編譯程序T0，擴(kuò)充L0L1，用L0寫(xiě)L1的T1,L1L2……滾雪球一樣，直到所需編程序。

4.移植：將