編譯原理課件(龍書為教材)

編譯原理2/5/20231自我介紹姓名：辛明影電話： 86413213教研室：計(jì)算機(jī)軟件基礎(chǔ)辦公室：綜合樓513

xmy63@xmy63@126.com助課教師：洪曉鵬，綜合樓614單麗麗，新技術(shù)樓6082/5/20232辛明影開課目的及應(yīng)用前景：

介紹設(shè)計(jì)與構(gòu)造程序設(shè)計(jì)語(yǔ)言編譯程序的原理與方法源程序編譯程序目標(biāo)程序連接可執(zhí)行程序預(yù)備知識(shí)：形式語(yǔ)言與自動(dòng)機(jī)、兩門以上的高級(jí)程序設(shè)計(jì)語(yǔ)言匯編語(yǔ)言數(shù)據(jù)結(jié)構(gòu)等How?2/5/20233辛明影內(nèi)容簡(jiǎn)介：第一章：編譯器的基本結(jié)構(gòu)第二章：高級(jí)語(yǔ)言及其語(yǔ)法描述第三章：詞法分析器第四章：語(yǔ)法分析技術(shù)第五章：語(yǔ)法制導(dǎo)翻譯的主要概念及中間代碼第六章：程序運(yùn)行時(shí)的存貯分配問題第七章：代碼優(yōu)化第八章：目標(biāo)代碼生成2/5/20234辛明影教學(xué)設(shè)計(jì)：(1)自頂向下，逐步求精的方法(2)問題驅(qū)動(dòng)(3)將課程設(shè)計(jì)成一個(gè)應(yīng)用平臺(tái)(4)用實(shí)驗(yàn)拓廣課堂教學(xué)(5)精講多練(6)承前啟后教學(xué)目標(biāo)：2/5/20235辛明影第一章緒論編譯器就是一個(gè)程序，它讀入用某種語(yǔ)言編寫的源程序，并翻譯成一個(gè)與之等價(jià)的另一種語(yǔ)言編寫的源程序。編譯器源程序目標(biāo)程序錯(cuò)誤信息Fortran、Pascal、Java、C…..另一種程序設(shè)計(jì)語(yǔ)言、匯編語(yǔ)言、機(jī)器語(yǔ)言1.1什么叫編譯程序2/5/20236辛明影1.2編譯過(guò)程概述編譯程序的工作，從輸入源程序開始，到輸出目標(biāo)程序結(jié)束，與自然語(yǔ)言之間的翻譯有很多相似之處。一段英文翻譯成中文，需經(jīng)下列步驟：識(shí)別出句子中的單詞分析句子的語(yǔ)法結(jié)構(gòu)根據(jù)句子的含義進(jìn)行初步分析對(duì)譯文進(jìn)行修飾寫出最后的譯文編譯程序詞法分析代碼優(yōu)化語(yǔ)法分析語(yǔ)義分析及中間代碼生成目標(biāo)代碼生成構(gòu)成編譯程序各個(gè)階段Iamaexperiencedteacher.2/5/20237辛明影編譯器的各個(gè)階段：編譯器是分階段執(zhí)行的。每個(gè)階段將源程序從一種表示轉(zhuǎn)換成另一種表示源程序詞法分析器錯(cuò)誤處理器符號(hào)管理表語(yǔ)法分析器語(yǔ)義分析器中間代碼生成器代碼優(yōu)化器代碼生成器編譯的各個(gè)階段2/5/20238辛明影各分析階段隨著編譯器各個(gè)階段的進(jìn)展，源程序的內(nèi)部表示不斷地發(fā)生變化。以a=b+c*d為例1。詞法分析讀入源程序完成的任務(wù)：識(shí)別出單詞：a、=、b、+、c、*、d并用記號(hào)方式表示識(shí)別出的單詞關(guān)鍵字、標(biāo)識(shí)符、常數(shù)、算符和界符例：25表示a、b、c、d；36：＝；３2：＋；31：*記號(hào)表示邏輯上相關(guān)的字符序列，常用整數(shù)來(lái)表示上述單詞表示為：(25,a),(36,_),(25,b),(32,_),(25,c),(31,_),(25,d)2/5/20239辛明影語(yǔ)法分析在詞法分析的基礎(chǔ)上，根據(jù)語(yǔ)言的語(yǔ)法規(guī)則，把單詞符號(hào)串組成各類語(yǔ)法單位.具體的說(shuō)，語(yǔ)法分析是在單詞流的基礎(chǔ)上建立一個(gè)層次結(jié)構(gòu)-----建立語(yǔ)法樹賦值語(yǔ)句標(biāo)識(shí)符=表達(dá)式a表達(dá)式標(biāo)識(shí)符b+表達(dá)式表達(dá)式*標(biāo)識(shí)符c表達(dá)式標(biāo)識(shí)符d2/5/202310辛明影語(yǔ)義分析階段語(yǔ)義分析利用語(yǔ)法分析階段確定的層次結(jié)構(gòu)來(lái)識(shí)別表達(dá)式和語(yǔ)句中的操作信息及類型信息=+ab*cdtemp1=c*dtemp2=b+temp1temp1temp2a=temp22/5/202311辛明影中間代碼生成階段本階段將產(chǎn)生源程序的一個(gè)顯式中間表示這種中間表示可以看成是某種抽象的程序，通常是與平臺(tái)無(wú)關(guān)的其重要性質(zhì)：1.易于產(chǎn)生2.易于翻譯成目標(biāo)程序下面是用三地址碼和四元式表示的例子：temp1=c*dtemp2=b+temp1a=temp2（*,c,d,tempt1)(+,b,tempt1,tempt2)(=,tempt2,,a)2/5/202312辛明影代碼優(yōu)化階段試圖改進(jìn)中間代碼，以產(chǎn)生執(zhí)行速度較快的機(jī)器代碼對(duì)上面中間代碼進(jìn)行優(yōu)化處理后，產(chǎn)生如下的代碼：temp1=c*da=b+temp1temp1=c*dtemp2=b+temp1a=temp22/5/202313辛明影代碼生成階段生成可重定位的機(jī)器代碼或匯編代碼MovfR2，cMultR2,dMovfR1,bAddfR2,R1Movfa,R22/5/202314辛明影1.3符號(hào)表管理inta,b;floate,fcharch1,ch2;為什么要先說(shuō)明?

定義了變量的類型，也就規(guī)定了變量在內(nèi)存中的存放形式，在其上所能進(jìn)行的運(yùn)算解決符號(hào)地址到存貯地址上的映射2/5/202315辛明影

編譯器的一個(gè)基本功能是記錄源程序中使用的標(biāo)識(shí)符并將它們記載到符號(hào)表中。符號(hào)表是一個(gè)數(shù)據(jù)結(jié)構(gòu)。每個(gè)標(biāo)識(shí)符在符號(hào)表中都有一條記錄名字記號(hào)類型種屬……addrid1(25)id2(25)ba例：inta,b;int簡(jiǎn)變04

并收集與每個(gè)標(biāo)識(shí)符相關(guān)的各種屬性信息，int簡(jiǎn)變2/5/202316辛明影符號(hào)表的接口：符號(hào)表的作用就是存放字符串或詞素當(dāng)一個(gè)字符串或詞素被保存時(shí)，與之相對(duì)應(yīng)的記號(hào)也被保存符號(hào)表上的操作：Insert(s,t):將符號(hào)串s和記號(hào)t插入符號(hào)表，返回相應(yīng)表項(xiàng)的指針Lookup(s):在符號(hào)表中查找字符串s，查找成功返回相應(yīng)指針，否則返回02/5/202317辛明影關(guān)鍵字的處理通常情況下，將關(guān)鍵字存在符號(hào)表中，作為符號(hào)表的初值。當(dāng)詞法分析程序識(shí)別出一個(gè)標(biāo)識(shí)符s后，用lookup(s)查找符號(hào)表，如果是關(guān)鍵字，返回相應(yīng)的記號(hào)；如果是變量名，返回記號(hào)id2/5/202318辛明影符號(hào)表的實(shí)現(xiàn)固定長(zhǎng)標(biāo)識(shí)符：采用前面的結(jié)構(gòu)不定長(zhǎng)標(biāo)識(shí)符：使用單獨(dú)的數(shù)組lexemesifeosinteospositioneosinitialeosIf(12)Int(13)Id1(25)Id2(25)存放標(biāo)識(shí)符的字符串,符號(hào)表中存放標(biāo)識(shí)符在lexemes的起始位置和相應(yīng)記號(hào)2/5/202319辛明影1.4編譯各階段的分組一、前端和后端前端包括詞法分析、詞法分析、語(yǔ)義分析，以及相關(guān)的錯(cuò)誤處理和符號(hào)表的建立前端依賴于源程序并在很大程度上獨(dú)立于目標(biāo)機(jī)器。2/5/202320辛明影后端主要包括代碼優(yōu)化、代碼生成和相關(guān)錯(cuò)誤處理。后端依賴于目標(biāo)機(jī)器。后端處理對(duì)象是由前端產(chǎn)生的結(jié)果，即中間代碼前端生成與平臺(tái)無(wú)關(guān)的字節(jié)碼后端是由與平臺(tái)有關(guān)的解釋器對(duì)所生成的字節(jié)碼文件進(jìn)行解釋執(zhí)行Java語(yǔ)言的編譯采用的是前端后端方式。2/5/202321辛明影二、編譯的遍編譯的若干階段通常是以一遍來(lái)實(shí)現(xiàn)的，每遍讀一次輸入文件、產(chǎn)生一個(gè)輸出文件。2/5/202322辛明影在編譯的各個(gè)階段都會(huì)發(fā)現(xiàn)源程序中的錯(cuò)誤，1.5錯(cuò)誤檢測(cè)與報(bào)告為了使編譯器能繼續(xù)運(yùn)行，以檢測(cè)出源程序中更多的錯(cuò)誤，在檢測(cè)到錯(cuò)誤后，必須以合適的方式進(jìn)行錯(cuò)誤處理。error2/5/202323辛明影第二章高級(jí)語(yǔ)言

及其語(yǔ)法描述2/5/202324內(nèi)容簡(jiǎn)介：本章概述程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu)2.1程序語(yǔ)言的定義任何語(yǔ)言實(shí)現(xiàn)的基礎(chǔ)是語(yǔ)言定義。語(yǔ)言的定義決定了該語(yǔ)言

具有什么樣的語(yǔ)言功能、

什么樣的數(shù)據(jù)結(jié)構(gòu)、

什么樣的程序結(jié)構(gòu)、

以及具體的使用形式等細(xì)節(jié)問題。和主要的共同特征，并介紹程序設(shè)計(jì)語(yǔ)言主要語(yǔ)句的文法描述與形式定義。2/5/202325辛明影

對(duì)于編譯程序設(shè)計(jì)者來(lái)說(shuō)：語(yǔ)言定義就是具體實(shí)現(xiàn)的理論依據(jù)。

對(duì)于語(yǔ)言用戶來(lái)說(shuō)：語(yǔ)言定義就是一本用戶手冊(cè)。2.1.1語(yǔ)法語(yǔ)言的語(yǔ)法是指這樣一組規(guī)則，用它可產(chǎn)生一個(gè)程序。規(guī)則：詞法規(guī)則語(yǔ)法規(guī)則2/5/202326辛明影詞法規(guī)則是指單詞符號(hào)的形成規(guī)則字母表就是一個(gè)有窮字符集。C語(yǔ)言的字母表為：∑={a---z、A—Z、0—9、(、)、

[、]、

、.、!、~、+、-、*、/、&、%、<、>、=、^、|、?、,、;}C語(yǔ)言的標(biāo)識(shí)符的構(gòu)成規(guī)則：

字母、下劃線打頭的字母、數(shù)字和下劃線構(gòu)成的符號(hào)串。如：a1、ave、_day一.詞法規(guī)則2/5/202327辛明影上述的定義是用文字來(lái)描述的，當(dāng)設(shè)計(jì)編譯程序時(shí)，就要把它用形式的方式描述出來(lái)，就要用到形式語(yǔ)言。各類型的常數(shù)、標(biāo)識(shí)符、基本字、算符和界符等正規(guī)式和有窮自動(dòng)機(jī)是描述詞法結(jié)構(gòu)和進(jìn)行詞法分析的有效工具在現(xiàn)今多數(shù)程序設(shè)計(jì)語(yǔ)言中，單詞符號(hào)一般包括：2/5/202328辛明影C語(yǔ)言的標(biāo)識(shí)符的文法和自動(dòng)機(jī)描述：例：C語(yǔ)言標(biāo)識(shí)符的文法描述L（G）={w/w為字母或‘-’打頭的字母數(shù)字串}解：P:I→aBI→-BI→aB→aBB→dBB→aB→d識(shí)別L（G）的自動(dòng)機(jī)IBTa-a,d其它2/5/202329辛明影SACDFEB7dddddddee+–T*例：C語(yǔ)言實(shí)常數(shù)的文法描述文法：S→dAA→dAA→eDA→.BB→dCC→dCC→eDD→-ED→+ED→dFE→dFF→dFF→d其它其它其它10003.1410e+33.14e-512e50.1e242/5/202330辛明影二.語(yǔ)法規(guī)則語(yǔ)法規(guī)則規(guī)定了如何從單詞符號(hào)形成更大的結(jié)構(gòu)（即語(yǔ)法單位），換言之，語(yǔ)法規(guī)則是語(yǔ)法單位的形成規(guī)則一般的程序設(shè)計(jì)語(yǔ)言的語(yǔ)法單位有：表達(dá)式、語(yǔ)句、分程序、函數(shù)、過(guò)程和程序等

下推自動(dòng)機(jī)理論和上下文無(wú)關(guān)文法是我們討論語(yǔ)法分析的理論基礎(chǔ)2/5/202331辛明影表達(dá)式：E→E+TE→E-TE→TT→T*FT→T/F

T→FF→(E)F→id主要語(yǔ)句的形式描述：2/5/202332辛明影布爾表達(dá)式：B→BorBB→BandBB→notBB→(E）B→idrelopidB→trueB→false2/5/202333辛明影賦值、分支、循環(huán)語(yǔ)句：S→id=ES

→ifBthenS

S→ifBthenSelseS

S→whileBdoSS→{L}

L→L;SL→S2/5/202334辛明影調(diào)用語(yǔ)句：S→callid(Elist)Elist→Elist,EElist→E|ε2/5/202335辛明影類型說(shuō)明和過(guò)程說(shuō)明語(yǔ)句：P→DD→D;DD→id:TD→id（Elist）D;ST→intT→float2/5/202336辛明影數(shù)組說(shuō)明語(yǔ)句：L→id[Elist]Elist→Elist,EElist→E2/5/202337辛明影2.1.2

語(yǔ)義例：a=b+c*d例do999I=1,10

對(duì)于一個(gè)語(yǔ)言來(lái)說(shuō)，不僅要給出它的詞法、語(yǔ)法規(guī)則，而且要定義它的單詞符號(hào)和語(yǔ)法單位的意義，這就是語(yǔ)義問題對(duì)于編譯程序來(lái)說(shuō)，只有了解程序的語(yǔ)義，才知道應(yīng)把它翻譯成什么樣的目標(biāo)指令代碼2/5/202338辛明影2.2構(gòu)造基礎(chǔ)2.2.1程序結(jié)構(gòu)簡(jiǎn)介一個(gè)高級(jí)語(yǔ)言程序通常由若干子程序段（過(guò)程、函數(shù)等）組成，許多語(yǔ)言還引入了類、程序包等更高級(jí)的結(jié)構(gòu)2/5/202339辛明影FORTRAN一個(gè)FORTRAN程序由一個(gè)主程序和若干個(gè)輔助程序段組成PROGRAMMAIN.ENDSUBROUTINESUB1..ENDFUNCTIONFUN1.END它的定義是并列的2/5/202340辛明影FORTRAN的構(gòu)成特點(diǎn)：同一名字在不同的程序段中一般都代表不同的對(duì)象，也就是說(shuō)代表不同的存貯單元PROGRAMMAIN.integerxENDSUBROUTINESUB1Integerx.ENDIntegerxXX=9999100Integerx9999X=100XPROGRAMMAIN.

ENDSUBROUTINESUB1

.END一個(gè)名字對(duì)應(yīng)多個(gè)對(duì)象2/5/202341辛明影但是不同程序段里的同名公用塊卻代表同一個(gè)存貯區(qū)域PROGRAMMAIN.

Commona,bENDSUBROUTINESUB1

commonx,y.ENDPROGRAMMAIN.

ENDSUBROUTINESUB1

.ENDCommona,babA=100B=5010050Commonx,yxyY=x+100200共享存貯單元多個(gè)名字對(duì)應(yīng)一個(gè)對(duì)象2/5/202342辛明影二。PascalPascal允許子程序嵌套定義

Programmain說(shuō)明部分Begin可執(zhí)行部分endPascal的程序結(jié)構(gòu)Programmain

BeginendProcedureP1BeginendProcedureP11BeginendProcedureP2Beginend也允許并列定義2/5/202343辛明影關(guān)于名字的作用域的規(guī)定：標(biāo)識(shí)符X的任意一次出現(xiàn)（除去說(shuō)明語(yǔ)句中）都意味著對(duì)某個(gè)說(shuō)明語(yǔ)句中說(shuō)明的這個(gè)變量X的引用此時(shí)，說(shuō)明語(yǔ)句同標(biāo)識(shí)符X應(yīng)共處一個(gè)最小程序中，即：P1中說(shuō)明的X只在P1中有效P11是P1的內(nèi)層子程序，P11中沒有再對(duì)X作新的說(shuō)明，則在P11中對(duì)X的引用，實(shí)際上引用的就是P1中說(shuō)明的X，

即內(nèi)部過(guò)程可以引用外部過(guò)程中定義的量2/5/202344辛明影三.javaJava語(yǔ)言是一種面向?qū)ο蟮母呒?jí)語(yǔ)言，它很重要的方面是類和繼承的概念，同時(shí)支持多態(tài)性和動(dòng)態(tài)綁定等特性Classcar{Intcolor_num;Intdoor_num;Intspeed;.Voidpush_break(){}

Voidadd_oil(){}}Classbenzextendscar

Doubleprice;VoidABS(){}

}2/5/202345辛明影

一個(gè)類把有關(guān)的數(shù)據(jù)及其操作封裝在一起構(gòu)成一個(gè)抽象數(shù)據(jù)類型一個(gè)子類繼承其父類的所有數(shù)據(jù)和方法，并且可以加入自己新的定義

在java中，變量和方法的定義之前可以加上public、private、pretected等修飾詞，以限制其它類的對(duì)象對(duì)于這些變量和方法的使用2/5/202346辛明影2.2.2構(gòu)造基礎(chǔ)程序設(shè)計(jì)語(yǔ)言的數(shù)據(jù)對(duì)象：數(shù)據(jù)、函數(shù)、過(guò)程常用能反映其本質(zhì)的、有助于記憶的名字來(lái)表示一.名字特性：一個(gè)名字對(duì)應(yīng)一個(gè)對(duì)象，普通變量多個(gè)名字對(duì)應(yīng)一個(gè)對(duì)象一個(gè)名字對(duì)應(yīng)多個(gè)對(duì)象，common,數(shù)組、重載、局部變量、重寫、2/5/202347辛明影

每個(gè)對(duì)象可以看做是一個(gè)存貯單元，可能是一個(gè)字，也可能是多個(gè)字名字具有屬性，通常由說(shuō)明語(yǔ)句給出一個(gè)名字的屬性，包括：類型和作用域類型決定了它有什么樣的值，作用域規(guī)定了值的存在范圍

值在計(jì)算機(jī)內(nèi)的表示，

以及對(duì)它能施加什么樣的運(yùn)算2/5/202348辛明影二.數(shù)據(jù)類型1.初等數(shù)據(jù)類型①數(shù)值數(shù)據(jù)：整形、實(shí)型、雙精度等，可施行算術(shù)運(yùn)算②邏輯數(shù)據(jù)：可施行邏輯運(yùn)算③字符數(shù)據(jù)：④指針類型：2/5/202349辛明影三。數(shù)據(jù)結(jié)構(gòu)1。數(shù)組從邏輯上講，一個(gè)數(shù)組是由同類型數(shù)據(jù)所組成的n維矩形結(jié)構(gòu)一個(gè)數(shù)組所需的存貯空間大小在編譯時(shí)就已知道的，則稱此數(shù)組是一個(gè)確定的數(shù)組；否則稱為可變數(shù)組設(shè)intA[l1‥u1,][l2‥u2]……[ln‥un]為n維數(shù)組各維的長(zhǎng)度：di=ui-li+1(1≤i≤n)2/5/202350辛明影任一數(shù)組元素A[i1,i2,……in]的地址為：D=a+(i1-l1)d2d3……

dn

+(i2-l2)d2d2……

dn……+(in-1-ln-1)dn+(in-ln)

整理后C=(……

(l1d2+l2)d3+l3)d4+……

+ln-1)dn+lnC是數(shù)組計(jì)算中不變的部分2/5/202351辛明影變量部分：v=(……

(i1d2+i2)d3+i3)d4+……

+in-1)dn+in任一數(shù)組元素A[i1,i2,……in]的地址:addr=a-c+v2/5/202352辛明影在編譯時(shí)，當(dāng)遇到說(shuō)明時(shí)，必須把數(shù)組的有關(guān)信息記錄在一個(gè)“內(nèi)情向量”之中，用于數(shù)組元素的地址計(jì)算。數(shù)組的內(nèi)情向量包括：維數(shù)，各維的上、下限，首地址及數(shù)組的類型……lnundn…………l2l1unund1d2N維數(shù)C常數(shù)T類型A首地址2/5/202353辛明影對(duì)于確定數(shù)組來(lái)說(shuō)，內(nèi)情向量可登記在符號(hào)表中；

對(duì)于可變數(shù)組，內(nèi)情向量的信息在編譯時(shí)無(wú)法全部知道，只有到運(yùn)行階段才能全部確定下來(lái)，存貯分配也要等到運(yùn)行時(shí)方能進(jìn)行2/5/202354辛明影2.記錄（結(jié)構(gòu)）從邏輯上講，記錄是由已知的數(shù)據(jù)組合起來(lái)的一種結(jié)構(gòu)Structstudent{charname[20];booleanpartmember;intage;}stu;2/5/202355辛明影記錄結(jié)構(gòu)最簡(jiǎn)單的存貯方式是連續(xù)存放上述的變量stu共占7個(gè)字，共28個(gè)字節(jié)SStu.partmemberStu.age3.字符串、表格和隊(duì)列kK+1….K+20….K+24….….……….2/5/202356辛明影四.抽象數(shù)據(jù)類型一個(gè)抽象數(shù)據(jù)類型包括：⑶這種類型對(duì)象的封裝⑵作用于這些數(shù)據(jù)對(duì)象的抽象運(yùn)算的集合⑴數(shù)據(jù)對(duì)象的一個(gè)集合C++、Java語(yǔ)言通過(guò)類對(duì)抽象類型提供支持2/5/202357辛明影五.語(yǔ)句與控制結(jié)構(gòu)1.表達(dá)式要解決的問題：①優(yōu)先級(jí)②結(jié)合率2.語(yǔ)句語(yǔ)句可分為：①說(shuō)明語(yǔ)句：②可執(zhí)行語(yǔ)句：定義各種不同數(shù)據(jù)類型的變量和運(yùn)算描述語(yǔ)句的動(dòng)作執(zhí)行語(yǔ)句分為：賦值、控制和I/O語(yǔ)句2/5/202358辛明影⑴賦值句A=B左值右值名字的左值指它所代表的存貯單元地址名字的右值指該單元的內(nèi)容2/5/202359辛明影⑵控制語(yǔ)句無(wú)條件轉(zhuǎn)移語(yǔ)句：Gotolable條件語(yǔ)句：IfBthenSIfBthenSelseS循環(huán)語(yǔ)句：WhileBdoSRepeatSuntilBForI=e1toe2stepe3過(guò)程調(diào)用語(yǔ)句：CallP(x1,x2,….xn)返回語(yǔ)句：Return(E)2/5/202360辛明影⑶說(shuō)明語(yǔ)句說(shuō)明語(yǔ)句用于定義名字的性質(zhì)。編譯程序把這些性質(zhì)登記在符號(hào)表中，并檢查程序中名字的引用和說(shuō)明是否一致。許多說(shuō)明語(yǔ)句不產(chǎn)生目標(biāo)代碼但有的說(shuō)明語(yǔ)句，如過(guò)程說(shuō)明和可變數(shù)組說(shuō)明，則要產(chǎn)生相應(yīng)的目標(biāo)代碼2/5/202361辛明影⑷簡(jiǎn)單句和復(fù)合句簡(jiǎn)單句是指不包含其它語(yǔ)句成分的基本句。賦值、goto語(yǔ)句等復(fù)合句則指那些句中有句的語(yǔ)句If(x==0)thenx=1{x=1;y=2;gotol1;}2/5/202362辛明影programreference（input，output）；

vara，b：integer；

procedureswap（x，y：integer）；

vartemp：integer；

begintemp:＝x；

x：＝y(tǒng)；

y：＝temp

end;

begin

a：＝1;b：＝2;

swap(a，b);

writeln('a='，a，

'b=',b）

end.2.2.3參數(shù)傳遞

結(jié)果是什么？2/5/202363辛明影1傳值調(diào)用實(shí)在參數(shù)和形式參數(shù)結(jié)合的方法：傳值調(diào)用（call-by-value）引用調(diào)用（call-by-reference）復(fù)制恢復(fù)（copy-restore）傳名調(diào)用（call-by-name）2/5/202364辛明影

子程序?yàn)槊恳粋€(gè)形參開辟一個(gè)存貯單元，用于存放相應(yīng)實(shí)參的值。子程序執(zhí)行時(shí)，每當(dāng)訪問形參時(shí)，就直接訪問形參單元。實(shí)參：形參：傳值調(diào)用可以實(shí)現(xiàn)如下：主調(diào)過(guò)程計(jì)算實(shí)在參數(shù)，并把它們的右-值放入到形式參數(shù)的存儲(chǔ)空間中。2/5/202365辛明影使用傳值的方法，調(diào)用swap（a,b）等價(jià)于下面幾步：

x：=a

y：=b

temp：=x

x：=y

y：=temp2/5/202366辛明影2引用調(diào)用（傳地址）

把實(shí)在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù),

在目標(biāo)代碼中，在被調(diào)用過(guò)程中對(duì)形式參數(shù)的一次引用就成為對(duì)傳遞給被調(diào)用過(guò)程的指針的一個(gè)間接引用。Referenceabxy12swapabtemp2/5/202367辛明影子程序?yàn)槊總€(gè)形參開辟一個(gè)單元，用于存放相應(yīng)實(shí)參的地址，執(zhí)行時(shí)，子程序間址方式訪問這些形參單元

當(dāng)實(shí)參為表達(dá)式或常數(shù)時(shí)，則存放它們值的臨時(shí)單元。實(shí)參：地址形參：@Temp:=x;

x:=y;y:=temp;temp:=a;a:=b;b:=temp;2/5/202368辛明影3復(fù)制恢復(fù)（傳值結(jié)果）實(shí)現(xiàn)：

1.當(dāng)控制流入到被調(diào)用過(guò)程之前，把實(shí)在參數(shù)的右-值和左-值傳遞到被調(diào)用過(guò)程中；2.當(dāng)控制返回時(shí)，把形式參數(shù)的現(xiàn)行右-值復(fù)制回到相應(yīng)的實(shí)在參數(shù)的左-值中。2/5/202369辛明影

子程序?yàn)槊總€(gè)形參分配兩個(gè)存貯單元B1和B2，B1用于存放實(shí)參地址，B2用于存放實(shí)參值。

執(zhí)行時(shí)，對(duì)B2單元使用直接訪問形式；返回前，按B1中的地址把B2中的內(nèi)容存入主調(diào)程序的實(shí)參單元中。實(shí)參：地址形參：B1B2@B12/5/202370辛明影

在主調(diào)程序中設(shè)置計(jì)算實(shí)參地址和右值的形實(shí)替換子程序THUNK

子程序中為相應(yīng)實(shí)參開辟一個(gè)形式單元，用于存放該實(shí)參的THUNK子程序的入口地址。

執(zhí)行時(shí)，每當(dāng)要對(duì)形參進(jìn)行訪問時(shí)，就調(diào)用THUNK子程序，以獲得相應(yīng)實(shí)參地址或值4傳名調(diào)用對(duì)形參的訪問是發(fā)生在實(shí)參單元上的2/5/202371辛明影例：有程序段：procedurep(x,y,z)beginy=y+1;z=z+x;end

Begina=2;b=3;c=4;P(a,b,c);printa,b,c;end2/5/202372辛明影傳值：abc實(shí)參形參xyz234P(a,b,c);234y=y+1;

輸出：23446Z=z+x;A=2B=3C=42/5/202373辛明影傳地址：abc實(shí)參形參xyz234P(a,b,c);&a&b&cy=y+1;@y=@y+1輸出：24646Z=z+x;@z=@z+@x2/5/202374辛明影傳值結(jié)果：abc實(shí)參形參X—B1B2Y—B1B2Z—B1B2234&a&by=y+1;

輸出：246Z=z+x;&c

按@B1返回B2的值4

6

2344

62/5/202375辛明影傳名：abc實(shí)參形參xyz234P(a,b,c);&thunk&thunk&thunky=y+1;JSRThunkY→b輸出：24646Z=z+x;jsrThunkZ→c,x→a2/5/202376辛明影例：有程序段：procedurep(x,y,z)beginy=y+1;z=z+x;end

Begina=2;b=3;P(a+b,a,a);printaend2/5/202377辛明影傳值：aba+b實(shí)參形參xyz23P(a+b,a,a);522y=y+1;

輸出：2

37Z=z+x;A=2B=352/5/202378辛明影傳地址：aba+b實(shí)參形參xyz235P(a+b,a,a);&a+b&a&ay=y+1;@y=@y+1輸出：83Z=z+x;@z=@z+@x82/5/202379辛明影傳名：ab實(shí)參形參xyz23P(a+b,a,a);&thunk&thunk&thunky=y+1;JSRThunkY→a輸出：939Z=z+x;jsrThunkZ→a,x→a+b2/5/202380辛明影第三章詞法分析2/5/202381編譯器的各個(gè)階段：編譯器是分階段執(zhí)行的。每個(gè)階段將源程序從一種表示轉(zhuǎn)換成另一種表示源程序詞法分析器錯(cuò)誤處理器符號(hào)管理表語(yǔ)法分析器語(yǔ)義分析器中間代碼生成器代碼優(yōu)化器代碼生成器編譯的各個(gè)階段2/5/202382辛明影3.2詞法分析器的手工構(gòu)造：用DFA能識(shí)別3.3詞法分析程序自動(dòng)構(gòu)造工具LEX簡(jiǎn)介3.1詞法分析程序的設(shè)計(jì)：

2/5/202383辛明影=80;0134256eniL字母字母字母字母數(shù)字?jǐn)?shù)字?jǐn)?shù)字==；；0124563Line=80;id(25),‘Line’=(36),num(27),‘80’;(45),數(shù)字字母字母11==0003;;1輸入輸出有窮控制器單詞的詞類和屬性（詞類符號(hào)，單詞的屬性）2/5/202384辛明影

3.1詞法分析程序的設(shè)計(jì)二、掃描器的任務(wù)

一、詞法分析程序的功能

源程序

單詞序列

詞法分析器1、組織源程序的輸入2、識(shí)別單詞，轉(zhuǎn)換成機(jī)內(nèi)表示形式3、刪除注釋行、空格及無(wú)用符號(hào)4、查填符號(hào)表5、檢查詞法錯(cuò)誤2/5/202385辛明影<12,><25,符號(hào)表入口><39,><25,符號(hào)表入口><20,><25,符號(hào)表入口><36,><26,常數(shù)表入口><8,><25,符號(hào)表入口><36,><26,常數(shù)表入口>ifi＞jtheni:＝0

elsej:=1詞法分析if

I＞JThenI＝0

elsej=12/5/202386辛明影三、詞類和屬性2．標(biāo)識(shí)符：用來(lái)表示各種名字3．字面常數(shù)：256，3.14，true,‘a(chǎn)bc’4．運(yùn)算符：如，＋、－、*、/等等5．分界符：如逗號(hào)，分號(hào)，冒號(hào)等程序語(yǔ)言單詞的分類：

1．關(guān)鍵字(保留字或基本字)：while,if2/5/202387辛明影界符和運(yùn)算符:詞法分析器的輸出：（詞類編碼，單詞自身的屬性值）關(guān)鍵字可分成一類，也可以一個(gè)關(guān)鍵字分成一類。常數(shù)可統(tǒng)歸一類，也可按類型（整型、實(shí)型、布爾型等），每個(gè)類型的常數(shù)劃分成一類。所有的標(biāo)識(shí)符分為一類。詞類編碼原則:一字一碼。一類型一碼。一類一碼。一符一碼。2/5/202388辛明影

表3.1單詞詞類編碼2/5/202389辛明影對(duì)于關(guān)鍵字、界符、運(yùn)算符來(lái)說(shuō)，它們的詞類編碼就可以表示其完整的信息，而對(duì)于標(biāo)識(shí)符，詞類編碼所反映的信息不夠充分，標(biāo)識(shí)符的具體特性還要通過(guò)單詞自身的屬性進(jìn)行互相區(qū)分。標(biāo)識(shí)符的單詞自身的屬性常用其在符號(hào)表中的入口指針來(lái)表示故對(duì)于這類單詞，其單詞自身的屬性值通常為空2/5/202390辛明影對(duì)于常數(shù)，其單詞自身的屬性常用其在常數(shù)表中的入口指針來(lái)表示2/5/202391辛明影

以語(yǔ)句子a=b+c*d為例，假設(shè)按表3.1為單詞編碼，詞法分析后的結(jié)果為：Token字符號(hào)表a=b+c*da25<25,><36,--------><25,><32,--------><25,>b25<25,>c25

d25<31,-------->

2/5/202392辛明影

四、詞法分析的設(shè)計(jì)形式（1）設(shè)計(jì)成一個(gè)獨(dú)立程序，完成詞法分析的任務(wù)，結(jié)果以文件的形式組織，做為語(yǔ)法分析的輸入源程序詞法分析符號(hào)表TOKEN字錯(cuò)誤信息2/5/202393辛明影詞法分析語(yǔ)法分析語(yǔ)義分析和中間代碼生成源程序中間代碼

符號(hào)表管理

錯(cuò)誤的診查處理（2）作為語(yǔ)法分析和語(yǔ)義分析的子程序2/5/202394辛明影

五、詞法分析程序的設(shè)計(jì)框圖SCANNEROUTPUTsort字母RECOGID數(shù)字RECOGDIG/HANDLCOMRECOGDEC界符’RECOGSTRLOOKUP2/5/202395辛明影32詞法分析器的手工構(gòu)造為了構(gòu)造詞法分析器，要研究構(gòu)詞法，每種詞類的結(jié)構(gòu)模式以及識(shí)別它的數(shù)學(xué)模型——有窮自動(dòng)機(jī)。321確定的有限自動(dòng)機(jī)（DFA）322構(gòu)造識(shí)別單詞的DFA323編寫詞法分析程序2/5/202396辛明影SCANNEROUTPUTsort字母RECOGID數(shù)字RECOGDIG/HANDLCOMRECOGDEC界符’RECOGSTRLOOKUP2/5/202397辛明影一、手工構(gòu)造識(shí)別單詞的DFAm根椐DFA識(shí)別單詞的定義，在研究給定程序語(yǔ)言單詞結(jié)構(gòu)的基礎(chǔ)上，能直接構(gòu)造出識(shí)別它的DFAm。例如：對(duì)于C語(yǔ)言整數(shù)：非空數(shù)字串。無(wú)符號(hào)實(shí)數(shù)（用d表示數(shù)字）:(a)dd.ddE(+-)ddddE(+-)dd(c)dd.dd0.1e+1412e-43.141592(d)dd…dd10002/5/202398辛明影IBTTa-a,d其它例：C語(yǔ)言的標(biāo)識(shí)符標(biāo)識(shí)符：字母開始的字母數(shù)字串。2/5/202399辛明影例：C語(yǔ)言實(shí)常數(shù)的文法描述01234567dddEdEd-+dd10003.141512e-40.1e+14.2/5/2023100辛明影在識(shí)別標(biāo)識(shí)符的過(guò)程中，首先要拼寫出來(lái)，并和保留字區(qū)別開來(lái)；識(shí)別出的標(biāo)識(shí)符要填入符號(hào)表中二、編寫詞法分析程序根據(jù)畫出的狀態(tài)轉(zhuǎn)換圖（識(shí)別單詞的）構(gòu)造詞法分析程序，每個(gè)狀態(tài)對(duì)應(yīng)一段程序，完成到達(dá)此狀態(tài)的工作；在識(shí)別常數(shù)的過(guò)程中，要把它轉(zhuǎn)換成機(jī)器表示以作為屬性值，記錄到常數(shù)表中。

詞法分析程序的控制程序模擬狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換。2/5/2023101辛明影programSCANNER;Begininitiate符號(hào)表,字符串表,行,列計(jì)數(shù)器;Open源文件,TOKEN文件,打印機(jī)文件;RepeatFIRSTCH(CH);ifCH!=EOLthencallSORT(CH)elseRDLINE;untilCH=EOF;把符號(hào)表,字符串表做成文件;close源文件,TOKEN文件;callOUTPUTR;模塊0：掃描器主控2/5/2023102辛明影單詞分類模塊(SORT)輸入：CH內(nèi)含單詞首符；procedureSORT(CH);{caseCHof‘字母’:‘字母’:callRECOGID(CH,TOKEN);‘/’:callHANDLECOM(CH,TOKEN);‘?dāng)?shù)字’:callRECOGDIG(CH,TOKEN);‘’‘callRECOGSTR(CH,TOKEN);otherwisecallRECOGDEL(CH,TOKEN);endcase;writeTOKENintoTOKEN文件;Return}

2/5/2023103辛明影procedureRECOGID(CH,TOKEN);{WORD:=‘’;WORD:=WORD||CH;Repeat{callGETCH(CH);ifCH是字母或數(shù)字thenWORD:=WORD||CH;}untilCH!=字母或數(shù)字;ifCH是非法字符thencallPRINTERR(‘非法字符’)else列計(jì)數(shù)-1;ifWORD是關(guān)鍵字thenTOKEN:=(關(guān)鍵字種別碼,_)else{callLOOPUP(WORD,'標(biāo)識(shí)符',ENTRY)TOKEN:=(標(biāo)識(shí)符種別碼,ENTRY)};Return};識(shí)別標(biāo)識(shí)符；輸入：CH中含標(biāo)識(shí)符的首字母；輸出：TOKEN(二元式形式);2/5/2023104辛明影procedureHANDLECOM(TOKEN);{callGETCH(CH);ifCH!='*'then{列計(jì)數(shù)-1;TOKEN=(‘/’的識(shí)別碼,_);return};TOKEN='-1';GETCH(CH);while列計(jì)數(shù)<=行長(zhǎng)-1do{CH1:=CH;callGETCH(CH);ifCH1='*'andCH='/'thenTOKEN:=‘';}ifTOKEN!=‘’thencallPRINTERR(‘注解未完’);TOKEN:=‘';return}處理注解(HANDLECOM);輸入：‘/’;進(jìn)入該模塊之前已掃描了一個(gè)字符‘/’輸出：‘/’的TOKEN字或空TOKEN字;

2/5/2023105辛明影識(shí)別界限符(RECOGDEL)輸入：CH內(nèi)含單界限符；輸出：各種界符的TOKEN字;procedureRECOGDEL(CH,TOKEN);{caseCHof‘+’:TOKEN:=(‘+’的種別碼,_);‘)’:TOKEN:=(‘)’的種別碼,_);‘<’:{callGETCH(CH);ifCH=‘=’thenTOKEN:=(‘<=’的種別碼,_)elseifCH=‘>’thenTOKEN:=(‘<>’的種別碼,_)else{列計(jì)數(shù)-1;TOKEN:=(‘<’的種別碼,_)}}……..endcase;return}2/5/2023106辛明影3.3詞法分析程序的自動(dòng)構(gòu)造工具LEX簡(jiǎn)介一.原理單詞的結(jié)構(gòu)用正規(guī)式描述正規(guī)式NFADFAminDFALEX編譯器LEX源程序lex.1Lex.yy.c二.用LEX建立詞法分析程序的過(guò)程2/5/2023107辛明影C編譯器Lex.yy.ca.outa.out輸入流單詞序列三.lex源程序lex源程序由三部分組成2/5/2023108辛明影聲明%%翻譯規(guī)則%%輔助過(guò)程2/5/2023109辛明影

聲明包括變量，符號(hào)常量和正規(guī)定義式。翻譯規(guī)則的形式為：

p1{動(dòng)作1}p2{動(dòng)作2}……pn{動(dòng)作n}2/5/2023110辛明影

每個(gè)pi是正規(guī)定義式的名子，每個(gè){動(dòng)作i}是正規(guī)定義式pi識(shí)別某類單詞時(shí)，詞法分析器應(yīng)執(zhí)行動(dòng)作的程序段。用C書寫。標(biāo)識(shí)符{字母}({字母}|{數(shù)字})*%%標(biāo)識(shí)符{入口地址=LOOKUP();}%%LOOKUP()2/5/2023111辛明影輔助過(guò)程是動(dòng)作需要的，這些過(guò)程用C書寫，可以分別編譯.例：LOOKUP()2/5/2023112辛明影第四章語(yǔ)法分析該講語(yǔ)法分析了！這可是很重要的章節(jié)2/5/2023113主要內(nèi)容：本章將重點(diǎn)介紹典型的語(yǔ)法分析方法及相關(guān)的概念和實(shí)現(xiàn)技術(shù)語(yǔ)法分析分為：自上而下:自下而上：遞歸下降分析法LL（1）預(yù)測(cè)分析法推導(dǎo)算符優(yōu)先分析法LR分析法歸約從根向葉的方向建立分析樹從葉向根的方向建立分析樹2/5/2023114辛明影4.1語(yǔ)法分析器的功能詞法分析器語(yǔ)法分析器語(yǔ)義分析符號(hào)表源程序單詞符號(hào)語(yǔ)法樹中間表示完成的任務(wù)：①對(duì)詞法分析器產(chǎn)生的單詞符號(hào)進(jìn)行處理，輸出分析樹②與單詞相關(guān)的信息記錄到符號(hào)表中③類型檢查④錯(cuò)誤處理4.1.1語(yǔ)法分析器任務(wù)2/5/2023115辛明影4.1.2相關(guān)約定一.符號(hào)的使用約定1.終結(jié)符①.字母表中比較靠前的小寫字,如a,b,c②.操作符，如+、-等③.標(biāo)點(diǎn)符號(hào)，如括號(hào)、逗號(hào)等④.數(shù)字0、1、。。。9⑤.黑體串，如if、id等2/5/2023116辛明影2.下列符號(hào)是非終結(jié)符①.字母表中比較靠前的大寫字,如A、B、C②.字母S，常用來(lái)表示開始符號(hào)③.小寫斜體名字，如expr、stmt2/5/2023117辛明影3.字母表中比較靠后的大寫字母，如X、Y、Z等，用來(lái)表示文法符號(hào)，也就是說(shuō)，可以是終結(jié)符，也可以是非終結(jié)符4.字母表中比較靠后的小寫字母，如u、v…z等，表示終結(jié)符的串聯(lián)5.小寫希臘字母α、β、γ等表示文法符號(hào)的串，所以一個(gè)產(chǎn)生式可寫作：A→α2/5/2023118辛明影4.2自頂向下分析法4.2.1使用的技術(shù)、存在的問題及解決方法2/5/2023119辛明影一、推導(dǎo)推導(dǎo)：就是用產(chǎn)生式的右部的串來(lái)代替左部的非終結(jié)符事實(shí)上推導(dǎo)給出了自頂向下構(gòu)成分析樹過(guò)程的精確描述例：有描述算術(shù)表達(dá)式的文法G字符串id+id*id是該文法的句子，其推導(dǎo)過(guò)程如下：E→E+E|E*E|（E）|-E|id2/5/2023120辛明影E幾個(gè)約定：=〉E+T=>E+T*F=>E+T*id

=〉E+F*id=〉E+id*idE=〉-EE推導(dǎo)出-E=>一步或多步推導(dǎo)=>零步或多步推導(dǎo)*+=〉T+id*id=〉F+id*id=〉id+id*id2/5/2023121辛明影最左推導(dǎo)：每一步都堅(jiān)持替換當(dāng)前句型中

最左非終結(jié)符的推導(dǎo)最右推導(dǎo)：每一步都堅(jiān)持替換當(dāng)前句型中

最右非終結(jié)符的推導(dǎo)，也稱為

規(guī)范推導(dǎo)+句子：S=〉w稱終結(jié)符串w是文法G句子

+句型：S=〉α

稱α是文法G的句型

+語(yǔ)言：L（G）={w/S=〉w

}2/5/2023122辛明影二、語(yǔ)法樹語(yǔ)法描繪了如何從文法的開始符號(hào)推導(dǎo)出一個(gè)句子的過(guò)程語(yǔ)法樹可以看成是推導(dǎo)的圖形表示，但它不能顯示出替代的順序前面句子id+id*id推導(dǎo)過(guò)程所對(duì)應(yīng)的分析樹如下：2/5/2023123辛明影EE+TTT*FFFididid2/5/2023124辛明影4.如杲A是某個(gè)內(nèi)結(jié)點(diǎn)的非終結(jié)符標(biāo)記，A1，A2，……An是該結(jié)點(diǎn)從左到右排列的所有子結(jié)點(diǎn)的標(biāo)記，則A→A1A2……An是一個(gè)產(chǎn)生式3.每個(gè)內(nèi)結(jié)點(diǎn)由一個(gè)非終結(jié)符標(biāo)記1.樹根標(biāo)記為開始符號(hào)2.每個(gè)葉結(jié)點(diǎn)由終結(jié)符或者ε標(biāo)記語(yǔ)法具有如下特性的樹：2/5/2023125辛明影語(yǔ)法樹的葉結(jié)點(diǎn)從左到右的排列，剛好是這個(gè)文法所產(chǎn)生的語(yǔ)言的一個(gè)句子一個(gè)文法生成的語(yǔ)言就是它的某個(gè)分析樹所生成的句子的集合為給定的終結(jié)符串（句子）構(gòu)造一棵分析樹的過(guò)程稱為這個(gè)串（句子）的語(yǔ)法分析（parsing)2/5/2023126辛明影三、二義性句子id+id*id有兩棵分析樹與之對(duì)應(yīng)EE+EidE*EididEE*EE+Eididid2/5/2023127辛明影給定一個(gè)文法G，如果L（G）中存在一個(gè)具有兩棵或兩棵以上分析樹的句子，很顯然，描述算術(shù)表達(dá)式的文法G

E→E+E|E*E|（E）|-E|id是一個(gè)二義性文法造成二義性的原因是：文法中沒有體現(xiàn)出結(jié)合率和優(yōu)先級(jí)我們就稱該文法為二義性的，G也叫二義性文法。2/5/2023128辛明影

大多數(shù)的語(yǔ)法分析器都要求文法是無(wú)二義性的消除二義性：可以通過(guò)改寫文法來(lái)消除二義性例：stmt→ifexprthenstmt|ifexprthenstmtelsestmt|other2/5/2023129辛明影通過(guò)例子ifE1thenifE2thenS2elseS3很容易證明這是一個(gè)二義性文法sifEthenSelseSifEthenS2/5/2023130辛明影SifEthenSifEthenSelseS2/5/2023131辛明影在程序設(shè)計(jì)語(yǔ)言中，我們常常采用“最近匹配”原則來(lái)解決這種二義性文法改寫出為：

stmt→matched_stmt|unmatched_stmtmatched_stmt→

ifexprthenmatched_stmt

elsematched_stmt|otherunmatched_stmt→

ifexprthenmatched_stmt

elseunmatched_stmt

|ifexprthen_stmt2/5/2023132辛明影四、左遞歸如果文法G具有一個(gè)非終結(jié)符A使得對(duì)

某個(gè)字符串α存在推導(dǎo)A=>Aα,例：下面是描述算術(shù)表達(dá)式的算法S→EE→E+T|TT→T*F|FF→(E)|id為句子id*id+id構(gòu)造分析樹SE+TE+TE+T：則稱文法G是左遞歸的；如果A→Aα，則稱文法G是直接左遞歸的+2/5/2023133辛明影左遞歸會(huì)使分析進(jìn)入到無(wú)限循環(huán)之中消除簡(jiǎn)單左遞歸的方法：

對(duì)于含有左遞歸的產(chǎn)生式A→Aα|β可用下面的非左遞歸的產(chǎn)生式代替：

A→βA’A’→αA’|ε2/5/2023134辛明影例：下面是描述算術(shù)表達(dá)式的算法E→E+T|TT→T*F|FF→(E)|id消除E和T的直接左遞歸，得到：

E→TE’

E’→+TE’|εT→FT’F→(E)|idT’→*FT’|ε2/5/2023135辛明影對(duì)于一般情況而言，若某一文法G的產(chǎn)生式具有如下形式：

則可用如下方法消除左遞歸:A→Aα1|Aα2

|…|Aαm|

β1|β2|…|βn

A→β1A’|β2A’|…|βn

A’A’→α1A’|α2A’|…|αmA’|

ε很容易證明改造前后的文法是等價(jià)的2/5/2023136辛明影例：文法G（P）：P→（Q）|aP|aQ→Q,P|P試消除左遞歸2/5/2023137辛明影消除左遞歸后，方法改為：P→（Q）|aP｜aQ→PＱ’Q→，ＰＱ’｜ε2/5/2023138辛明影S→Qc|cQ→Rb|bR→Sa|aS這樣的遞歸無(wú)法用前面的方法消除對(duì)于含有間接左遞歸的文法：=>Qc=>Rbc=>Sabc出現(xiàn)了左遞歸2/5/2023139辛明影消除左遞歸的一般算法：輸入：無(wú)循環(huán)推導(dǎo)和ε產(chǎn)生式的方法G輸出：與G等價(jià)的無(wú)左遞歸文法算法：2/5/2023140辛明影1.以某種順序排列非終結(jié)符A1A2…An2.fori=1tondobeginforj=1toi-1dobegin改寫Ai→Ajγ

規(guī)則，方法如下：如果Aj→δ1|δ2|…|δk

則Ai→δ1γ

|δ2γ

|…|δnγ；end消除Ai中的所有直接左遞歸End3.化簡(jiǎn)由2所得文法2/5/2023141辛明影S→Qc|cQ→Rb|bR→Sa|a對(duì)如下文法消除左遞歸：1.將非終結(jié)符排序?yàn)镽、Q、S2.R不存在左遞歸，將R代入Q：

Q→Sab|ab|b3.Q不存在左遞歸，將Q代入S

S→Sabc|abc|bc|c4.消除直接左遞歸后，得文法：2/5/2023142辛明影S→abcS’|bcS’|cS’S’→abcS’|ε

Q→Rb|bR→Sa|a5.化簡(jiǎn)文法S→abcS’|bcS’|cS’S’→abcS’|ε

2/5/2023143辛明影

Z->A

A->aB|aC|Ad|Ae

B->bBC|f

C->c

2/5/2023144辛明影五、提取左因子為句子ifE1thenS1elseS2構(gòu)造一棵語(yǔ)法樹文法：stmt→ifexprthenstmt|S|ifexprthenstmtelsestmtstmt

ifexprthenstmtE1ifＥ２

thenstmt

回溯2/5/2023145辛明影造成這種情況的原因是產(chǎn)生式具有相同的首符號(hào)，從而導(dǎo)致不清楚該用哪個(gè)來(lái)替換非終結(jié)符可通過(guò)改寫產(chǎn)生式來(lái)推遲這種決定，直到看見足夠多的輸入符號(hào)，可以作出正確選擇為止上例可改為：

stmt→ifexprthenstmtS’|S

S’→

elsestmt|ε2/5/2023146辛明影stmt

ifexprthenstmtS’

E1

elsestmt

提取左因子算法：輸入：文法G輸出：一個(gè)等價(jià)的提取了左因子的文法方法：對(duì)于A→αβ1|α

β2|…|α

βn|γ可改寫為：A→αA’|γA’→β1|β2|…|βn2/5/2023147辛明影例：文法G（P）：P→（Q）|aP|aQ→Q,P|P試消除回朔2/5/2023148辛明影六、FIRST與FOLLOW集1.FIRST集回朔和左遞歸搞的人真煩哪！

怎樣才能做到每次選的產(chǎn)生都正確呢？

郁悶?zāi)?！FIRST（α

）={a|α=>a…,a∈VT}如果α=>ε則ε∈FIRST（α

）。例：stmt→ifexprthenstmtS’S’→

elsestmtS’→

ε定義：FIRST（α）是由α推導(dǎo)出的所有的第一個(gè)終結(jié)符號(hào)組成的集合，即：2/5/2023149辛明影算法：求FIRST（X）的算法描述如下：例：First(ifexprthenstmtS’)={if}First(elsestmt)={else}First(ε)={ε}2/5/2023150辛明影⑶如果X是非終結(jié)符，且X→Y1Y2……Yk,則a)Y1=>εFIRST(Y1)中的所有符號(hào)都在FIRST（X）中b)Y1Y2……Yi-1=>ε,

FIRST（Yi）,中的所有符號(hào)都在FIRST（X）中②如果X→ε是一個(gè)產(chǎn)生式，則ε∈FIRST（X）①如果X是終結(jié)符，則FIRST（X）是{X}c)

Y1Y2……Yk=>ε,則ε∈FIRST（X）2/5/2023151辛明影例1：有文法G（S）S→BAA→BSA→dB→aAB→bSB→c試寫出其FIRST集First(B)={a}First(B)=First(B)={c}First(S)=First(BA)={a,b,c}First(A)=First(BS)={a,b,c}First(A)=wtj9rsx2/5/2023152辛明影2.FOLLOW集定義：FOLLOW（A）是由所有句型中緊跟在A后面的終結(jié)符a組成的集合*FOLLOW（