第01章 編譯原理概述

編譯原理基礎(chǔ)1教材《編譯原理及實(shí)現(xiàn)》作者：孫悅紅大學(xué)本科計(jì)算機(jī)專業(yè)應(yīng)用型規(guī)劃教材清華大學(xué)出版社2學(xué)時(shí)與參考教材學(xué)分：3學(xué)時(shí)：48參考教材：[1]陳火旺、劉春林等編著，《程序設(shè)計(jì)語(yǔ)言編譯原理》，國(guó)防工業(yè)出版社。[2]張素琴、呂映芝等編著，《編譯原理》，清華大學(xué)出版社。[3]陳意云等編著，《編譯原理》，高等教育出版社?！?成績(jī)?cè)u(píng)定平時(shí)成績(jī)30％出勤率課后作業(yè)課程設(shè)計(jì)（編譯器）期末考試70％4作業(yè)課后題：第1、2、3、4、7、10章全部課后習(xí)題第5章：1、2、3小題第6章：1小題課程設(shè)計(jì)5程序語(yǔ)言中涉及編譯的一些問(wèn)題？為什么有些語(yǔ)言規(guī)定標(biāo)識(shí)符不能超過(guò)8個(gè)字符？而有些語(yǔ)言對(duì)標(biāo)識(shí)符的長(zhǎng)度無(wú)限制？為什么有些語(yǔ)言能實(shí)現(xiàn)遞歸，而有些語(yǔ)言不能？C語(yǔ)言規(guī)定數(shù)組下界為0，上界為聲明的數(shù)減1，為什么？嵌套的IF語(yǔ)句規(guī)定ELSE與上面最近的IF配對(duì)，為什么？為什么有些程序運(yùn)行一段時(shí)間后會(huì)導(dǎo)致內(nèi)存溢出？當(dāng)我們學(xué)完編譯后，這些問(wèn)題就可以得到解答。6第一章編譯概述1.1程序設(shè)計(jì)語(yǔ)言1.2編譯程序1.3編譯程序的組成1.4編譯程序的結(jié)構(gòu)1.5編譯程序的前后處理器1.6TEST語(yǔ)言和編譯器7什么是“編譯”？把高級(jí)語(yǔ)言程序翻譯成等價(jià)的低級(jí)語(yǔ)言程序。編譯系統(tǒng)：編譯程序和運(yùn)行程序編譯程序目標(biāo)程序源程序8學(xué)習(xí)本課程的目的加深對(duì)程序設(shè)計(jì)語(yǔ)言的理解，提升自身的能力掌握編譯程序的基本結(jié)構(gòu)，掌握常用的編譯技術(shù)和方法將編譯原理的理論和方法應(yīng)用于一般的軟件設(shè)計(jì)中9如：詞法分析中的字符串匹配技術(shù)可以應(yīng)用于文本編輯程序、信息檢索、通訊程序、模式識(shí)別中上下文無(wú)關(guān)文法和語(yǔ)法制導(dǎo)的翻譯可以用于分析表達(dá)式，寫(xiě)打字程序，繪圖程序等小系統(tǒng)代碼優(yōu)化技術(shù)更可以用于自己的結(jié)構(gòu)化程序中，用于改進(jìn)性能、優(yōu)化已有的程序等10主要內(nèi)容編譯概述（編譯組成、總體結(jié)構(gòu)）文法和語(yǔ)言（文法、推導(dǎo)、句型、歸約、語(yǔ)法樹(shù)）詞法分析（詞法分析、正規(guī)表達(dá)式、正規(guī)文法、NFA、DFA）語(yǔ)法分析（自頂向下：遞歸下降分析、LL(1)；自底向上：LR分析法）語(yǔ)義制導(dǎo)翻譯（屬性文法翻譯、語(yǔ)法制導(dǎo)翻譯）運(yùn)行環(huán)境（符號(hào)表管理、存儲(chǔ)分配）語(yǔ)義分析和代碼生成代碼優(yōu)化111.1程序設(shè)計(jì)語(yǔ)言

機(jī)器語(yǔ)言(MachineLanguage)0、1代碼匯編語(yǔ)言(AssembleLanguage)0、1代碼與助記符：更接近于計(jì)算機(jī)硬件指令系統(tǒng)的工作高級(jí)語(yǔ)言(HighLevelLanguage)定義數(shù)據(jù)、描述算法（程序）如：C、FORTRAN、PASCAL、C++、JAVA、SQL(數(shù)據(jù)定義、數(shù)據(jù)操作)12

用匯編語(yǔ)言或高級(jí)語(yǔ)言編寫(xiě)的程序稱為源程序用目標(biāo)語(yǔ)言所表示的程序目標(biāo)語(yǔ)言：可以是介于源語(yǔ)言和機(jī)器語(yǔ)言之間的“中間語(yǔ)言”，可以是某種機(jī)器的機(jī)器語(yǔ)言,也可以是某機(jī)器的匯編語(yǔ)言

將源程序轉(zhuǎn)換為目標(biāo)程序的程序稱為翻譯程序。它是指各種語(yǔ)言的翻譯器，包括匯編程序和編譯程序，是匯編程序、編譯程序以及各種變換程序的總稱源程序目標(biāo)程序翻譯程序13源程序、翻譯程序、目標(biāo)程序三者關(guān)系：即源程序是翻譯程序的輸入，目標(biāo)程序是翻譯程序的輸出源程序翻譯程序目標(biāo)程序SOURCEPROGRAMTRANSLATEROBJECTPROGRAM14匯編程序

若源程序用匯編語(yǔ)言書(shū)寫(xiě)，經(jīng)過(guò)翻譯程序得到用機(jī)器語(yǔ)言表示的程序，這時(shí)的翻譯程序就稱之為匯編程序，這種翻譯過(guò)程稱為“匯編”(Assemble）。編譯程序

若源程序是用高級(jí)語(yǔ)言書(shū)寫(xiě)，經(jīng)加工后得到目標(biāo)程序，上述翻譯過(guò)程稱“編譯”（Compile）。匯編程序與編譯程序都是翻譯程序，主要區(qū)別是加工對(duì)象的不同。由于匯編語(yǔ)言格式簡(jiǎn)單，常與機(jī)器語(yǔ)言之間有一一對(duì)應(yīng)的關(guān)系。匯編程序所要做的翻譯工作比編譯程序簡(jiǎn)單的多。1.2翻譯程序

15編譯到被執(zhí)行的過(guò)程1、編譯程序的目標(biāo)程序是機(jī)器語(yǔ)言（編譯方式）高級(jí)語(yǔ)言源程序編譯程序機(jī)器語(yǔ)言目標(biāo)程序目標(biāo)程序+運(yùn)行子程序運(yùn)行結(jié)果數(shù)據(jù)編譯階段執(zhí)行階段16編譯到被執(zhí)行的過(guò)程2、編譯程序的目標(biāo)程序是匯編語(yǔ)言（編譯方式）高級(jí)語(yǔ)言源程序編譯程序匯編語(yǔ)言目標(biāo)程序匯編程序機(jī)器語(yǔ)言目標(biāo)程序運(yùn)行結(jié)果目標(biāo)程序+運(yùn)行子程序數(shù)據(jù)

編譯階段匯編階段運(yùn)行階段17編譯到被執(zhí)行的過(guò)程3、從源程序的編譯到執(zhí)行只有一個(gè)階段——解釋執(zhí)行階段（解釋方式）源程序數(shù)據(jù)解釋程序結(jié)果

在解釋方式下，最終并不生成目標(biāo)程序，這是編譯方式與解釋方式的根本區(qū)別。181.3編譯程序的組成

按照編譯程序的執(zhí)行過(guò)程和所完成的任務(wù)，編譯分成前后兩個(gè)階段：分析階段和綜合階段。詞法分析語(yǔ)法分析語(yǔ)義分析代碼優(yōu)化目標(biāo)代碼生成分析階段綜合階段錯(cuò)誤處理符號(hào)表19對(duì)比翻譯外文資料：1、能識(shí)別出句子中的一個(gè)單詞（詞法分析）；2、分析句子的語(yǔ)法結(jié)構(gòu)（語(yǔ)法分析）；3、根據(jù)句子的含義進(jìn)行初步翻譯（語(yǔ)義分析）；4、對(duì)譯文進(jìn)行修飾（代碼優(yōu)化）；5、寫(xiě)出最后的譯文（目標(biāo)代碼生成）。20S.PO.P語(yǔ)義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語(yǔ)法分析程序詞法分析程序錯(cuò)誤處理符號(hào)表管理211.3.1詞法分析詞法分析又稱掃描器。任務(wù)：根據(jù)詞法規(guī)則分析和識(shí)別單詞字符序列編碼形式單詞：是語(yǔ)言的基本語(yǔ)法單位<1>保留字（如:if、else、while）<2>標(biāo)識(shí)符（如:max、min、str）<3>常數(shù)

（如:12、6.8、’a’）<4>分界符（如:+、-、*、/、;、（、））22例如：a=10+c*20符號(hào)記號(hào)單詞100IDa21==200NUM1022++100IDc25**200NUM20a=10+C*20a=10+C*20a=10+C*2023例res=fact*(term1+term2);結(jié)果IDN res‘=’IDNfact‘*’‘(’IDN term1‘+’IDNterm2‘)’‘;’24對(duì)比中文句子劃分“我們是一家人”

“我是大學(xué)生”

“叔叔親了我媽媽也親了我”我們是一家人我是大學(xué)生25S.PO.P語(yǔ)義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語(yǔ)法分析程序詞法分析程序錯(cuò)誤處理符號(hào)表管理261.3.2語(yǔ)法分析程序

編譯程序的核心任務(wù)：根據(jù)語(yǔ)法規(guī)則（即語(yǔ)言的文法），分析并識(shí)別出各種語(yǔ)法成分（如表達(dá)式、語(yǔ)句、函數(shù)等），并進(jìn)行語(yǔ)法正確性檢查。文法<賦值語(yǔ)句>::=<標(biāo)識(shí)符>“=”<表達(dá)式><表達(dá)式>::=<表達(dá)式>“+”<表達(dá)式>|<表達(dá)式>“*”<表達(dá)式><表達(dá)式>::=“(”<表達(dá)式>“)”|<標(biāo)識(shí)符>|<整數(shù)>|<實(shí)數(shù)>

27句子謂語(yǔ)主語(yǔ)賓語(yǔ)動(dòng)詞(吃)名詞(猴子)名詞(香蕉)圖1.5句子“猴子吃香蕉”的語(yǔ)法分析樹(shù)語(yǔ)法分析與語(yǔ)文中分析句子成分相類(lèi)似，根據(jù)句子由主語(yǔ)、謂語(yǔ)組成，謂語(yǔ)由動(dòng)詞、賓語(yǔ)組成等語(yǔ)言規(guī)則，可對(duì)句子“猴子吃香蕉”的進(jìn)行分析，分析過(guò)程常用語(yǔ)法樹(shù)來(lái)表示句子。28表達(dá)式:a=10+c*20表達(dá)式=

ID（a）

項(xiàng)+

表達(dá)式項(xiàng)表達(dá)式NUM（20）

ID（c）

NUM（10）

因子*

因子因子項(xiàng)如何畫(huà)a=10*(c+20)的語(yǔ)法分析樹(shù)？29S.PO.P語(yǔ)義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語(yǔ)法分析程序詞法分析程序錯(cuò)誤處理符號(hào)表管理301.3.3語(yǔ)義分析及中間代碼生成程序

任務(wù)：依據(jù)語(yǔ)義規(guī)則對(duì)識(shí)別出的各種語(yǔ)法成分析其含義，并進(jìn)行初步翻譯，生成中間代碼。靜態(tài)：分析語(yǔ)法成份的含義，進(jìn)行語(yǔ)義上的正確性檢查動(dòng)態(tài)：根據(jù)相應(yīng)語(yǔ)義，生成中間代碼（介于源語(yǔ)言和目標(biāo)語(yǔ)言之間的中間語(yǔ)言形式）31表達(dá)式：a=10+c*20表達(dá)式=ID（a）項(xiàng)+表達(dá)式項(xiàng)表達(dá)式NUM（20）ID（c）NUM（10）因子*因子因子項(xiàng)32例如表達(dá)式(a+b)*(c+d)翻譯成四元的中間代碼如下：(+,a,b,t1)(+,c,d,t2)(*,t1,t2,t3)LOADa將a的內(nèi)容加載到操作數(shù)棧LOADb將a的內(nèi)容加載到操作數(shù)棧ADD

將操作數(shù)棧頂?shù)膬蓚€(gè)單元的內(nèi)容相加STOt1將操作數(shù)棧頂?shù)膬?nèi)容存入單元t1LOADc將c的內(nèi)容加載到操作數(shù)棧LOADd將d的內(nèi)容加載到操作數(shù)棧ADD

將操作數(shù)棧頂?shù)膬蓚€(gè)單元的內(nèi)容相加STOt2將操作數(shù)棧頂?shù)膬?nèi)容存入單元t2LOADt1將t1的內(nèi)容加載到操作數(shù)棧LOADt2將t2的內(nèi)容加載到操作數(shù)棧MULT

將操作數(shù)棧頂?shù)膬蓚€(gè)單元的內(nèi)容相乘STOt3將累加器的內(nèi)容存入單元t3翻譯成某個(gè)抽象機(jī)的匯編指令代碼：中間代碼生成33S.PO.P語(yǔ)義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語(yǔ)法分析程序詞法分析程序錯(cuò)誤處理符號(hào)表管理341.3.4代碼優(yōu)化

任務(wù)：對(duì)中間代碼進(jìn)行加工變換，以得到高質(zhì)量的目標(biāo)代碼有四元式指令代碼如下：(*，3.14，2，t1)(=,t1,_,x)(*,2,5,t2)(*,t2,a,t3)(=,t3,_,y)(+,x,1,t4)(=,t4,_,z)而優(yōu)化后的代碼如下：(=,6.28,_,x)(*,10,a,y)(=,7.28,_,z)代碼優(yōu)化不是編譯程序的必要組成部分，不同的編譯程序所進(jìn)行的代碼優(yōu)化程度差別很大，能夠完成代碼優(yōu)化的編譯程序稱為“優(yōu)化編譯程序”。35S.PO.P語(yǔ)義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語(yǔ)法分析程序詞法分析程序錯(cuò)誤處理符號(hào)表管理361.3.5目標(biāo)代碼生成

任務(wù)：把中間代碼變換成特定機(jī)器上的低級(jí)語(yǔ)言代碼目標(biāo)代碼的形式可以是絕對(duì)指令代碼、可重定位的機(jī)器指令代碼或匯編指令代碼。371.3.6符號(hào)表管理

填表：把源程序中的信息和編譯過(guò)程中所產(chǎn)生的信息登記在表格中查表：在隨后的編譯過(guò)程中同時(shí)又要不斷的查找這些表格中的信息每個(gè)階段中都要有：符號(hào)表管理和錯(cuò)誤處理標(biāo)識(shí)符名標(biāo)識(shí)符類(lèi)型類(lèi)型地址aaa1（表示變量）1（表示整型）0001381.3.7錯(cuò)誤處理診察錯(cuò)誤，并能報(bào)告用戶錯(cuò)誤性質(zhì)和位置出錯(cuò)處理能力的優(yōu)劣是衡量編譯程序質(zhì)量好壞的一個(gè)重要指標(biāo)39典型的編譯程序具有7個(gè)邏輯部分S.PO.P語(yǔ)義分析及生成中間代碼程序代碼生成程序代碼優(yōu)化程序語(yǔ)法分析程序詞法分析程序錯(cuò)誤處理符號(hào)表管理401.4編譯程序的結(jié)構(gòu)

對(duì)源程序（包括源程序中間形式）從頭到尾掃描一次，并做有關(guān)的加工處理，生成新的源程序中間形式或目標(biāo)程序，通常稱之為一遍。第一遍 第二遍 ……

S.P中間形式1S.P中間形式2C2C1S.PO.P

上一遍的結(jié)果是下一遍的輸入，最后一遍生成目標(biāo)程序。411.4.1單遍編譯程序

單遍編譯程序只對(duì)源程序進(jìn)行一遍掃描，就完成編譯的各項(xiàng)任務(wù)，產(chǎn)生目標(biāo)代碼。在單遍編譯程序中，不產(chǎn)生中間代碼，往往以語(yǔ)法分析程序?yàn)橹行?，詞法分析和語(yǔ)義分析作為語(yǔ)法分析的子程序。語(yǔ)法分析函數(shù)｛詞法分析子程序；語(yǔ)義分析子程序；｝42詞法分析源程序取單詞目標(biāo)程序開(kāi)始語(yǔ)法分析語(yǔ)義分析及代碼生成送單詞典型的單遍編譯程序結(jié)構(gòu)如圖所示1、當(dāng)語(yǔ)法分析需要讀進(jìn)一個(gè)新單詞時(shí)，就調(diào)用詞法分析子程序。詞法分析子程序則從源程序中依次讀入字符，組合成單詞符號(hào)，并將單詞符號(hào)返回給語(yǔ)法分析程序。2、當(dāng)語(yǔ)法分析程序識(shí)別出一個(gè)語(yǔ)法成分時(shí)，就調(diào)用語(yǔ)義分析子程序進(jìn)行語(yǔ)義分析，并生成目標(biāo)程序。3、當(dāng)源程序處理完后，進(jìn)行善后處理，優(yōu)化目標(biāo)程序。431.4.2多遍編譯程序

有的編譯程序把編譯程序的五項(xiàng)任務(wù)分幾遍來(lái)進(jìn)行，每遍只完成部分任務(wù)。典型的多遍編譯程序結(jié)構(gòu)如圖所示。詞法分析語(yǔ)法分析語(yǔ)義分析代碼優(yōu)化目標(biāo)代碼生成錯(cuò)誤處理符號(hào)表目標(biāo)程序源程序44多遍編譯程序的工作過(guò)程如下：調(diào)用詞法分析程序?qū)⒏呒?jí)語(yǔ)言源程序轉(zhuǎn)換成用單詞符號(hào)表示的程序，即將字符串程序轉(zhuǎn)換成單詞符號(hào)串源程序。調(diào)用語(yǔ)法分析程序?qū)Ψ?hào)串源程序進(jìn)行語(yǔ)法歸類(lèi)檢查。調(diào)語(yǔ)義分析程序進(jìn)行語(yǔ)義檢查，并生成中間的代碼程序。調(diào)用代碼優(yōu)化程序?qū)χ虚g代碼程序進(jìn)行優(yōu)化。調(diào)用目標(biāo)生成程序?qū)?yōu)化后的中間代碼程序轉(zhuǎn)換成目標(biāo)代碼程序。詞法分析語(yǔ)法分析語(yǔ)義分析代碼優(yōu)化目標(biāo)代碼生成錯(cuò)誤處理符號(hào)表目標(biāo)程序源程序451.4.3編譯程序分遍的優(yōu)缺點(diǎn)分遍的缺點(diǎn)：每遍都要讀符號(hào)、送符號(hào)，增加了許多重復(fù)性工作，降低編譯效率。目前的編譯程序中，有單遍的，也有二遍的、三遍的，還有多到十幾遍的。

編譯程序分為多遍，其優(yōu)點(diǎn)是：可以減少內(nèi)存容量的需求。分遍后，以遍為單位分別調(diào)用編譯的各個(gè)程序，各遍程序可以相互覆蓋；可使各遍的編譯程序相互獨(dú)立，結(jié)構(gòu)清晰；能夠進(jìn)行充分的優(yōu)化，產(chǎn)生高質(zhì)量的目標(biāo)程序；可將編譯程序分為“前端”和“后端”，有利于編譯程序的移植。461.4.4“端”的概念

根據(jù)編譯程序各部分功能，將編譯程序分成前端和后端前端：通常將與源程序有關(guān)的編譯部分稱為前端。 詞法分析、語(yǔ)法分析、語(yǔ)義分析、中間代碼生成 ---分析部分特點(diǎn)：與源語(yǔ)言有關(guān)

后端：與目標(biāo)機(jī)有關(guān)的部分稱為后端。代碼優(yōu)化、代碼生成---綜合部分特點(diǎn)：與目標(biāo)機(jī)有關(guān)47

同一前端+不同后端不同機(jī)器構(gòu)成同一語(yǔ)言的編譯程序例如.NET框架

48

不同前端+同一后端同一機(jī)器生成幾個(gè)語(yǔ)言的編譯程序例如GCC

491.5編譯程序的前后處理器

源程序往往分許多模塊并保存在不同的文件中，編譯前應(yīng)將這些不同文件中保存的程序連接起來(lái)。有些語(yǔ)言為了提高編程效率還提供了一些“預(yù)處理命令”，例如C語(yǔ)言的宏定義#Define、文件包含#include等等。這樣在進(jìn)行編譯前就需要有一個(gè)預(yù)處理器將各種源文件連接起來(lái)，將宏擴(kuò)展成源語(yǔ)言語(yǔ)句。50預(yù)處理器編譯程序匯編程序加載、連接編譯框架源程序標(biāo)準(zhǔn)源程序目標(biāo)匯編程序可重定位的機(jī)器代碼絕對(duì)機(jī)器代碼庫(kù)、可重定位目標(biāo)文件程序員編制的程序經(jīng)過(guò)預(yù)處理后的程序511.5.1預(yù)處理器編譯之前，預(yù)處理器對(duì)源程序進(jìn)行處理，產(chǎn)生標(biāo)準(zhǔn)源程序。不同語(yǔ)言的預(yù)處理功能有所不同，C語(yǔ)言編譯系統(tǒng)的預(yù)處理器主要完成以下幾個(gè)功能：宏處理：C語(yǔ)言允許用戶在程序中定義宏，以便提高編程效率，如#definePI3.1415926是一個(gè)宏定義，那么在編譯之前，預(yù)處理器要將源程序中的所有符號(hào)PI換成3.1415926。文件包含：如果C源程序中含有#include“stdio.h”，那么預(yù)處理器處理到這條語(yǔ)句時(shí)，就用stdio.h的實(shí)際內(nèi)容替換該語(yǔ)句。條件編譯：并非源程序的每一行都要進(jìn)行編譯，有時(shí)情況不同要編譯不同的語(yǔ)句。C語(yǔ)言預(yù)處理器處理?xiàng)l件編譯，將真正要編譯的語(yǔ)句組成標(biāo)準(zhǔn)源程序。521.5.2匯編程序

有些編譯程序直接產(chǎn)生可重定位的機(jī)器語(yǔ)言目標(biāo)代碼，而有些編譯程序只產(chǎn)生匯編語(yǔ)言目標(biāo)代碼，這樣就需要匯編程序做進(jìn)一步翻譯，生成可重定位的機(jī)器代碼?？芍囟ㄎ坏臋C(jī)器代碼可以裝載到內(nèi)存的任何地方，這種代碼采用相對(duì)地址，起始地址為0，各條指令及所訪問(wèn)的地址都是相對(duì)應(yīng)于0的邏輯地址。如果加載到內(nèi)存單元L處，則所有指令地址及訪問(wèn)的地址都要加上L。匯編語(yǔ)言采用助記符表示操作碼，用標(biāo)識(shí)符表示存儲(chǔ)地址，如完成a=b+5的80x86匯編語(yǔ)言程序如下：MOVa，R1ADD#2，R1MOVR1，b其中a，b表示存儲(chǔ)地址，R1表示寄存器，#2表示立即常數(shù)。有些匯編語(yǔ)言還提供宏指令來(lái)提高匯編語(yǔ)言編程效率，這種匯編語(yǔ)言稱為宏匯編語(yǔ)言。531.6TEST語(yǔ)言與編譯器

任何一本關(guān)于編譯結(jié)構(gòu)的書(shū)如果不包括編譯過(guò)程步驟的示例就不能算完整。因此，寫(xiě)出一個(gè)完整的編譯器并對(duì)其操作進(jìn)行注釋仍是很必要的。但要描述真實(shí)的編譯器非常困難，“真正的”編譯器內(nèi)容太復(fù)雜而且不易在本教材中掌握。為了解決上述問(wèn)題，本教材設(shè)計(jì)了一種非常小的語(yǔ)言TEST，一旦能明白TEST語(yǔ)言的編譯技術(shù)，就能夠很容易地理解各種語(yǔ)言的編譯器了。在第3、4、9章里，以這種小語(yǔ)言為示例，講解編譯技術(shù)的具體實(shí)現(xiàn)，而且在附錄B中列出該語(yǔ)言完整的編譯程序代碼。

541.6.1TEST語(yǔ)言

例如，TEST語(yǔ)