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

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

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

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

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

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

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

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

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

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

（如:12、6.8、’a’）<4>分界符（如:+、-、*、/、;、（、））22例如：a=10+c*20符號記號單詞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對比中文句子劃分“我們是一家人”

“我是大學(xué)生”

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

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

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

ID（a）

項(xiàng)+

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

ID（c）

NUM（10）

因子*

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

任務(wù)：依據(jù)語義規(guī)則對識別出的各種語法成分析其含義，并進(jìn)行初步翻譯，生成中間代碼。靜態(tài)：分析語法成份的含義，進(jìn)行語義上的正確性檢查動(dòng)態(tài)：根據(jù)相應(yīng)語義，生成中間代碼（介于源語言和目標(biāo)語言之間的中間語言形式）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ōu)化程序語法分析程序詞法分析程序錯(cuò)誤處理符號表管理341.3.4代碼優(yōu)化

任務(wù)：對中間代碼進(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ōu)化程序語法分析程序詞法分析程序錯(cuò)誤處理符號表管理361.3.5目標(biāo)代碼生成

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

填表：把源程序中的信息和編譯過程中所產(chǎn)生的信息登記在表格中查表：在隨后的編譯過程中同時(shí)又要不斷的查找這些表格中的信息每個(gè)階段中都要有：符號表管理和錯(cuò)誤處理標(biāo)識符名標(biāo)識符類型類型地址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ōu)化程序語法分析程序詞法分析程序錯(cuò)誤處理符號表管理401.4編譯程序的結(jié)構(gòu)

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

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

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

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

有的編譯程序把編譯程序的五項(xiàng)任務(wù)分幾遍來進(jìn)行，每遍只完成部分任務(wù)。典型的多遍編譯程序結(jié)構(gòu)如圖所示。詞法分析語法分析語義分析代碼優(yōu)化目標(biāo)代碼生成錯(cuò)誤處理符號表目標(biāo)程序源程序44多遍編譯程序的工作過程如下：調(diào)用詞法分析程序?qū)⒏呒壵Z言源程序轉(zhuǎn)換成用單詞符號表示的程序，即將字符串程序轉(zhuǎn)換成單詞符號串源程序。調(diào)用語法分析程序?qū)Ψ柎闯绦蜻M(jìn)行語法歸類檢查。調(diào)語義分析程序進(jìn)行語義檢查，并生成中間的代碼程序。調(diào)用代碼優(yōu)化程序?qū)χ虚g代碼程序進(jìn)行優(yōu)化。調(diào)用目標(biāo)生成程序?qū)?yōu)化后的中間代碼程序轉(zhuǎn)換成目標(biāo)代碼程序。詞法分析語法分析語義分析代碼優(yōu)化目標(biāo)代碼生成錯(cuò)誤處理符號表目標(biāo)程序源程序451.4.3編譯程序分遍的優(yōu)缺點(diǎn)分遍的缺點(diǎn)：每遍都要讀符號、送符號，增加了許多重復(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)的編譯部分稱為前端。 詞法分析、語法分析、語義分析、中間代碼生成 ---分析部分特點(diǎn)：與源語言有關(guān)

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

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

48

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

491.5編譯程序的前后處理器

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

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

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

541.6.1TEST語言

例如，TEST語