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

編譯原理9/7/20231自我介紹姓名：辛明影電話： 86413213

教研室：計(jì)算機(jī)軟件基礎(chǔ)辦公室：綜合樓513

xmy63@xmy63@126.com助課教師：洪曉鵬，綜合樓614

單麗麗，新技術(shù)樓6089/7/2023計(jì)算機(jī)學(xué)院

2辛明影開課目的及應(yīng)用前景：

介紹設(shè)計(jì)與構(gòu)造程序設(shè)計(jì)語言編譯程序的原理與方法源程序編譯程序目標(biāo)程序連接可執(zhí)行程序預(yù)備知識：形式語言與自動機(jī)、兩門以上的高級程序設(shè)計(jì)語言匯編語言數(shù)據(jù)結(jié)構(gòu)等How?9/7/2023計(jì)算機(jī)學(xué)院

3辛明影內(nèi)容簡介：第一章：編譯器的基本結(jié)構(gòu)第二章：高級語言及其語法描述第三章：詞法分析器第四章：語法分析技術(shù)第五章：語法制導(dǎo)翻譯的主要概念及中間代碼第六章：程序運(yùn)行時(shí)的存貯分配問題第七章：代碼優(yōu)化第八章：目標(biāo)代碼生成9/7/2023計(jì)算機(jī)學(xué)院

4辛明影教學(xué)設(shè)計(jì)：(1)自頂向下，逐步求精的方法(2)問題驅(qū)動(3)將課程設(shè)計(jì)成一個(gè)應(yīng)用平臺(4)用實(shí)驗(yàn)拓廣課堂教學(xué)(5)精講多練(6)承前啟后教學(xué)目標(biāo)：9/7/2023計(jì)算機(jī)學(xué)院

5辛明影第一章緒論編譯器就是一個(gè)程序，它讀入用某種語言編寫的源程序，并翻譯成一個(gè)與之等價(jià)的另一種語言編寫的源程序。編譯器源程序目標(biāo)程序錯(cuò)誤信息Fortran、Pascal、Java、C…..另一種程序設(shè)計(jì)語言、匯編語言、機(jī)器語言1.1什么叫編譯程序9/7/2023計(jì)算機(jī)學(xué)院

6辛明影1.2編譯過程概述編譯程序的工作，從輸入源程序開始，到輸出目標(biāo)程序結(jié)束，與自然語言之間的翻譯有很多相似之處。一段英文翻譯成中文，需經(jīng)下列步驟：識別出句子中的單詞分析句子的語法結(jié)構(gòu)根據(jù)句子的含義進(jìn)行初步分析對譯文進(jìn)行修飾寫出最后的譯文編譯程序詞法分析代碼優(yōu)化語法分析語義分析及中間代碼生成目標(biāo)代碼生成構(gòu)成編譯程序各個(gè)階段Iamaexperiencedteacher.9/7/2023計(jì)算機(jī)學(xué)院

7辛明影編譯器的各個(gè)階段：編譯器是分階段執(zhí)行的。每個(gè)階段將源程序從一種表示轉(zhuǎn)換成另一種表示源程序詞法分析器錯(cuò)誤處理器符號管理表語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器編譯的各個(gè)階段9/7/2023計(jì)算機(jī)學(xué)院

8辛明影各分析階段隨著編譯器各個(gè)階段的進(jìn)展，源程序的內(nèi)部表示不斷地發(fā)生變化。以a=b+c*d

為例1。詞法分析讀入源程序完成的任務(wù)：識別出單詞：a、=、b、+、c、*、d并用記號方式表示識別出的單詞關(guān)鍵字、標(biāo)識符、常數(shù)、算符和界符例：25表示a、b、c、d；36：＝；３2：＋；31：*記號表示邏輯上相關(guān)的字符序列，常用整數(shù)來表示上述單詞表示為：(25,a),(36,_),(25,b),(32,_),(25,c),(31,_),(25,d)9/7/2023計(jì)算機(jī)學(xué)院

9辛明影語法分析在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則，把單詞符號串組成各類語法單位.具體的說，語法分析是在單詞流的基礎(chǔ)上建立一個(gè)層次結(jié)構(gòu)-----建立語法樹賦值語句標(biāo)識符=表達(dá)式a表達(dá)式標(biāo)識符b+表達(dá)式表達(dá)式*標(biāo)識符c表達(dá)式標(biāo)識符d9/7/2023計(jì)算機(jī)學(xué)院

10辛明影語義分析階段語義分析利用語法分析階段確定的層次結(jié)構(gòu)來識別表達(dá)式和語句中的操作信息及類型信息=+ab*c

dtemp1=c*dtemp2=b+temp1temp1temp2a=temp29/7/2023計(jì)算機(jī)學(xué)院

11辛明影中間代碼生成階段本階段將產(chǎn)生源程序的一個(gè)顯式中間表示這種中間表示可以看成是某種抽象的程序，通常是與平臺無關(guān)的其重要性質(zhì)：1.易于產(chǎn)生

2.易于翻譯成目標(biāo)程序下面是用三地址碼和四元式表示的例子：temp1=c*dtemp2=b+temp1a=temp2（*,c,d,tempt1)(+,b,tempt1,tempt2)(=,tempt2,,a)9/7/2023計(jì)算機(jī)學(xué)院

12辛明影代碼優(yōu)化階段試圖改進(jìn)中間代碼，以產(chǎn)生執(zhí)行速度較快的機(jī)器代碼對上面中間代碼進(jìn)行優(yōu)化處理后，產(chǎn)生如下的代碼：temp1=c*da=b+temp1temp1=c*dtemp2=b+temp1a=temp29/7/2023計(jì)算機(jī)學(xué)院

13辛明影代碼生成階段生成可重定位的機(jī)器代碼或匯編代碼MovfR2，cMultR2,dMovfR1,bAddfR2,R1Movfa,R29/7/2023計(jì)算機(jī)學(xué)院

14辛明影1.3符號表管理int

a,b;floate,fcharch1,ch2;為什么要先說明?

定義了變量的類型，也就規(guī)定了變量在內(nèi)存中的存放形式，在其上所能進(jìn)行的運(yùn)算解決符號地址到存貯地址上的映射9/7/2023計(jì)算機(jī)學(xué)院

15辛明影

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

0

4

并收集與每個(gè)標(biāo)識符相關(guān)的各種屬性信息，int簡變9/7/2023計(jì)算機(jī)學(xué)院

16辛明影符號表的接口：符號表的作用就是存放字符串或詞素當(dāng)一個(gè)字符串或詞素被保存時(shí)，與之相對應(yīng)的記號也被保存符號表上的操作：Insert(s,t):將符號串s和記號t插入符號表，返回相應(yīng)表項(xiàng)的指針Lookup(s):在符號表中查找字符串s，查找成功返回相應(yīng)指針，否則返回09/7/2023計(jì)算機(jī)學(xué)院

17辛明影關(guān)鍵字的處理通常情況下，將關(guān)鍵字存在符號表中，作為符號表的初值。當(dāng)詞法分析程序識別出一個(gè)標(biāo)識符s后，用lookup(s)查找符號表，如果是關(guān)鍵字，返回相應(yīng)的記號；如果是變量名，返回記號id9/7/2023計(jì)算機(jī)學(xué)院

18辛明影符號表的實(shí)現(xiàn)固定長標(biāo)識符：采用前面的結(jié)構(gòu)不定長標(biāo)識符：使用單獨(dú)的數(shù)組lexemesifeosinteospositioneosinitialeosIf(12)Int(13)Id1(25)Id2(25)存放標(biāo)識符的字符串,符號表中存放標(biāo)識符在lexemes的起始位置和相應(yīng)記號9/7/2023計(jì)算機(jī)學(xué)院

19辛明影1.4編譯各階段的分組一、前端和后端前端包括詞法分析、詞法分析、語義分析，以及相關(guān)的錯(cuò)誤處理和符號表的建立前端依賴于源程序并在很大程度上獨(dú)立于目標(biāo)機(jī)器。9/7/2023計(jì)算機(jī)學(xué)院

20辛明影后端主要包括代碼優(yōu)化、代碼生成和相關(guān)錯(cuò)誤處理。后端依賴于目標(biāo)機(jī)器。后端處理對象是由前端產(chǎn)生的結(jié)果，即中間代碼前端生成與平臺無關(guān)的字節(jié)碼后端是由與平臺有關(guān)的解釋器對所生成的字節(jié)碼文件進(jìn)行解釋執(zhí)行Java語言的編譯采用的是前端后端方式。9/7/2023計(jì)算機(jī)學(xué)院

21辛明影二、編譯的遍編譯的若干階段通常是以一遍來實(shí)現(xiàn)的，每遍讀一次輸入文件、產(chǎn)生一個(gè)輸出文件。9/7/2023計(jì)算機(jī)學(xué)院

22辛明影在編譯的各個(gè)階段都會發(fā)現(xiàn)源程序中的錯(cuò)誤，1.5錯(cuò)誤檢測與報(bào)告為了使編譯器能繼續(xù)運(yùn)行，以檢測出源程序中更多的錯(cuò)誤，在檢測到錯(cuò)誤后，必須以合適的方式進(jìn)行錯(cuò)誤處理。error9/7/2023計(jì)算機(jī)學(xué)院

23辛明影第二章高級語言

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

具有什么樣的語言功能、

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

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

以及具體的使用形式等細(xì)節(jié)問題。和主要的共同特征，并介紹程序設(shè)計(jì)語言主要語句的文法描述與形式定義。9/7/2023計(jì)算機(jī)學(xué)院

25辛明影

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

對于語言用戶來說：語言定義就是一本用戶手冊。2.1.1語法語言的語法是指這樣一組規(guī)則，用它可產(chǎn)生一個(gè)程序。規(guī)則：詞法規(guī)則語法規(guī)則9/7/2023計(jì)算機(jī)學(xué)院

26辛明影詞法規(guī)則是指單詞符號的形成規(guī)則字母表就是一個(gè)有窮字符集。C語言的字母表為：

∑={a---z、

A—Z、

0—9、(、)、

[、]、

、.、!、~、+、-、*、

/、&、%、<、>、=、^、

|、?、,、;}C語言的標(biāo)識符的構(gòu)成規(guī)則：

字母、下劃線打頭的字母、數(shù)字和下劃線構(gòu)成的符號串。如：a1、ave

、_day一.詞法規(guī)則9/7/2023計(jì)算機(jī)學(xué)院

27辛明影上述的定義是用文字來描述的，當(dāng)設(shè)計(jì)編譯程序時(shí)，就要把它用形式的方式描述出來，就要用到形式語言。各類型的常數(shù)、標(biāo)識符、基本字、算符和界符等正規(guī)式和有窮自動機(jī)是描述詞法結(jié)構(gòu)和進(jìn)行詞法分析的有效工具在現(xiàn)今多數(shù)程序設(shè)計(jì)語言中，單詞符號一般包括：9/7/2023計(jì)算機(jī)學(xué)院

28辛明影C語言的標(biāo)識符的文法和自動機(jī)描述：例：C語言標(biāo)識符的文法描述L（G）={w/w為字母或‘-’打頭的字母數(shù)字串}解：P:I→aBI→-BI→aB→aB

B→dBB→aB→d識別L（G）的自動機(jī)IBTa-a,d其它9/7/2023計(jì)算機(jī)學(xué)院

29辛明影SACDFEB7ddddddd

ee+–T*例：C語言實(shí)常數(shù)的文法描述文法：S→dAA→dAA→eDA→.BB→dCC→dCC→eDD→-ED→+ED→dFE→dFF→dFF→d其它其它其它10003.1410e+33.14e-512e50.1e249/7/2023計(jì)算機(jī)學(xué)院

30辛明影二.語法規(guī)則語法規(guī)則規(guī)定了如何從單詞符號形成更大的結(jié)構(gòu)（即語法單位），換言之，語法規(guī)則是語法單位的形成規(guī)則一般的程序設(shè)計(jì)語言的語法單位有：表達(dá)式、語句、分程序、函數(shù)、過程和程序等

下推自動機(jī)理論和上下文無關(guān)文法是我們討論語法分析的理論基礎(chǔ)9/7/2023計(jì)算機(jī)學(xué)院

31辛明影表達(dá)式：

E→E+TE→E-TE→TT→T*FT→T/F

T→FF→(E)F→id主要語句的形式描述：9/7/2023計(jì)算機(jī)學(xué)院

32辛明影布爾表達(dá)式：

B→BorBB→BandBB→notBB→(E）

B→idrelopidB→trueB→false9/7/2023計(jì)算機(jī)學(xué)院

33辛明影賦值、分支、循環(huán)語句：

S→id=ES

→ifBthenS

S→ifBthenSelseS

S→whileBdoSS→{L}

L→L;S

L→S9/7/2023計(jì)算機(jī)學(xué)院

34辛明影調(diào)用語句：

S→callid(Elist)

Elist→Elist,E

Elist→E|ε9/7/2023計(jì)算機(jī)學(xué)院

35辛明影類型說明和過程說明語句：

P→DD→D;DD→id:TD→id（Elist）D;S

T→intT→float9/7/2023計(jì)算機(jī)學(xué)院

36辛明影數(shù)組說明語句：

L→id[Elist]

Elist→Elist,E

Elist→E9/7/2023計(jì)算機(jī)學(xué)院

37辛明影2.1.2

語義例：a=b+c*d例do999I=1,10

對于一個(gè)語言來說，不僅要給出它的詞法、語法規(guī)則，而且要定義它的單詞符號和語法單位的意義，這就是語義問題對于編譯程序來說，只有了解程序的語義，才知道應(yīng)把它翻譯成什么樣的目標(biāo)指令代碼9/7/2023計(jì)算機(jī)學(xué)院

38辛明影2.2構(gòu)造基礎(chǔ)2.2.1程序結(jié)構(gòu)簡介一個(gè)高級語言程序通常由若干子程序段（過程、函數(shù)等）組成，許多語言還引入了類、程序包等更高級的結(jié)構(gòu)9/7/2023計(jì)算機(jī)學(xué)院

39辛明影FORTRAN一個(gè)FORTRAN程序由一個(gè)主程序和若干個(gè)輔助程序段組成PROGRAMMAIN.ENDSUBROUTINESUB1..ENDFUNCTIONFUN1.END它的定義是并列的9/7/2023計(jì)算機(jī)學(xué)院

40辛明影

FORTRAN

的構(gòu)成特點(diǎn)：同一名字在不同的程序段中一般都代表不同的對象，也就是說代表不同的存貯單元PROGRAMMAIN.integerxENDSUBROUTINESUB1Integerx.ENDIntegerxXX=9999100Integerx9999X=100XPROGRAMMAIN.

ENDSUBROUTINESUB1

.END一個(gè)名字對應(yīng)多個(gè)對象9/7/2023計(jì)算機(jī)學(xué)院

41辛明影但是不同程序段里的同名公用塊卻代表同一個(gè)存貯區(qū)域PROGRAMMAIN.

Commona,bENDSUBROUTINESUB1

commonx,y.ENDPROGRAMMAIN.

ENDSUBROUTINESUB1

.ENDCommona,babA=100B=50

10050Commonx,yxyY=x+100200共享存貯單元多個(gè)名字對應(yīng)一個(gè)對象9/7/2023計(jì)算機(jī)學(xué)院

42辛明影二。PascalPascal允許子程序嵌套定義

Programmain

說明部分Begin

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

BeginendProcedureP1BeginendProcedureP11BeginendProcedureP2Beginend也允許并列定義9/7/2023計(jì)算機(jī)學(xué)院

43辛明影關(guān)于名字的作用域的規(guī)定：標(biāo)識符X的任意一次出現(xiàn)（除去說明語句中）都意味著對某個(gè)說明語句中說明的這個(gè)變量X的引用此時(shí)，說明語句同標(biāo)識符X應(yīng)共處一個(gè)最小程序中，即：P1中說明的X只在P1中有效

P11是P1的內(nèi)層子程序，P11中沒有再對X作新的說明，則在P11中對X的引用，實(shí)際上引用的就是P1中說明的X，

即內(nèi)部過程可以引用外部過程中定義的量9/7/2023計(jì)算機(jī)學(xué)院

44辛明影三.javaJava語言是一種面向?qū)ο蟮母呒壵Z言，它很重要的方面是類和繼承的概念，同時(shí)支持多態(tài)性和動態(tài)綁定等特性Classcar{Intcolor_num;Intdoor_num;Intspeed;.Voidpush_break(){}

Voidadd_oil(){}}Classbenzextendscar

Doubleprice;VoidABS(){}

}9/7/2023計(jì)算機(jī)學(xué)院

45辛明影

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

在java中，變量和方法的定義之前可以加上public、private、pretected等修飾詞，以限制其它類的對象對于這些變量和方法的使用9/7/2023計(jì)算機(jī)學(xué)院

46辛明影2.2.2構(gòu)造基礎(chǔ)程序設(shè)計(jì)語言的數(shù)據(jù)對象：數(shù)據(jù)、函數(shù)、過程常用能反映其本質(zhì)的、有助于記憶的名字來表示一.名字特性：一個(gè)名字對應(yīng)一個(gè)對象，普通變量多個(gè)名字對應(yīng)一個(gè)對象一個(gè)名字對應(yīng)多個(gè)對象，common,數(shù)組、重載、局部變量、重寫、9/7/2023計(jì)算機(jī)學(xué)院

47辛明影

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

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

以及對它能施加什么樣的運(yùn)算9/7/2023計(jì)算機(jī)學(xué)院

48辛明影二.數(shù)據(jù)類型1.初等數(shù)據(jù)類型①數(shù)值數(shù)據(jù)：整形、實(shí)型、雙精度等，可施行算術(shù)運(yùn)算②邏輯數(shù)據(jù)：可施行邏輯運(yùn)算③字符數(shù)據(jù)：④指針類型：9/7/2023計(jì)算機(jī)學(xué)院

49辛明影三。數(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ù)組各維的長度：di=ui-li+1(1≤i≤n)9/7/2023計(jì)算機(jī)學(xué)院

50辛明影任一數(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+ln

C是數(shù)組計(jì)算中不變的部分9/7/2023計(jì)算機(jī)學(xué)院

51辛明影變量部分：v=(……

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

+in-1)dn+in任一數(shù)組元素A[i1,i2,……in]的地址:

addr=a-c+v9/7/2023計(jì)算機(jī)學(xué)院

52辛明影在編譯時(shí)，當(dāng)遇到說明時(shí)，必須把數(shù)組的有關(guān)信息記錄在一個(gè)“內(nèi)情向量”之中，用于數(shù)組元素的地址計(jì)算。數(shù)組的內(nèi)情向量包括：維數(shù)，各維的上、下限，首地址及數(shù)組的類型……lnundn…………l2l1unund1d2N維數(shù)C常數(shù)T類型A首地址9/7/2023計(jì)算機(jī)學(xué)院

53辛明影對于確定數(shù)組來說，內(nèi)情向量可登記在符號表中；

對于可變數(shù)組，內(nèi)情向量的信息在編譯時(shí)無法全部知道，只有到運(yùn)行階段才能全部確定下來，存貯分配也要等到運(yùn)行時(shí)方能進(jìn)行9/7/2023計(jì)算機(jī)學(xué)院

54辛明影2.記錄（結(jié)構(gòu)）從邏輯上講，記錄是由已知的數(shù)據(jù)組合起來的一種結(jié)構(gòu)

Structstudent{charname[20];

boolean

partmember;

intage;}stu;9/7/2023計(jì)算機(jī)學(xué)院

55辛明影記錄結(jié)構(gòu)最簡單的存貯方式是連續(xù)存放上述的變量stu共占7個(gè)字，共28個(gè)字節(jié)

SStu.partmember

Stu.age3.字符串、表格和隊(duì)列kK+1….K+20….K+24….….……….9/7/2023計(jì)算機(jī)學(xué)院

56辛明影四.抽象數(shù)據(jù)類型一個(gè)抽象數(shù)據(jù)類型包括：⑶這種類型對象的封裝⑵作用于這些數(shù)據(jù)對象的抽象運(yùn)算的集合⑴數(shù)據(jù)對象的一個(gè)集合C++、Java語言通過類對抽象類型提供支持9/7/2023計(jì)算機(jī)學(xué)院

57辛明影五.語句與控制結(jié)構(gòu)1.表達(dá)式要解決的問題：①優(yōu)先級②結(jié)合率2.語句語句可分為：①說明語句：②可執(zhí)行語句：定義各種不同數(shù)據(jù)類型的變量和運(yùn)算描述語句的動作執(zhí)行語句分為：賦值、控制和I/O語句9/7/2023計(jì)算機(jī)學(xué)院

58辛明影⑴賦值句A=B左值右值名字的左值指它所代表的存貯單元地址名字的右值指該單元的內(nèi)容9/7/2023計(jì)算機(jī)學(xué)院

59辛明影⑵控制語句無條件轉(zhuǎn)移語句：Goto

lable條件語句：IfBthenSIfBthenSelseS循環(huán)語句：WhileBdoSRepeatSuntilBForI=e1toe2stepe3過程調(diào)用語句：CallP(x1,x2,….xn)返回語句：Return(E)9/7/2023計(jì)算機(jī)學(xué)院

60辛明影⑶說明語句說明語句用于定義名字的性質(zhì)。編譯程序把這些性質(zhì)登記在符號表中，并檢查程序中名字的引用和說明是否一致。許多說明語句不產(chǎn)生目標(biāo)代碼但有的說明語句，如過程說明和可變數(shù)組說明，則要產(chǎn)生相應(yīng)的目標(biāo)代碼9/7/2023計(jì)算機(jī)學(xué)院

61辛明影⑷簡單句和復(fù)合句簡單句是指不包含其它語句成分的基本句。賦值、goto語句等復(fù)合句則指那些句中有句的語句If(x==0)thenx=1{x=1;y=2;gotol1;}9/7/2023計(jì)算機(jī)學(xué)院

62辛明影

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é)果是什么？9/7/2023計(jì)算機(jī)學(xué)院

63辛明影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）9/7/2023計(jì)算機(jī)學(xué)院

64辛明影

子程序?yàn)槊恳粋€(gè)形參開辟一個(gè)存貯單元，用于存放相應(yīng)實(shí)參的值。子程序執(zhí)行時(shí)，每當(dāng)訪問形參時(shí)，就直接訪問形參單元。實(shí)參：形參：傳值調(diào)用可以實(shí)現(xiàn)如下：主調(diào)過程計(jì)算實(shí)在參數(shù)，并把它們的右-值放入到形式參數(shù)的存儲空間中。9/7/2023計(jì)算機(jī)學(xué)院

65辛明影使用傳值的方法，調(diào)用swap（a,b）等價(jià)于下面幾步：

x：=a

y：=b

temp：=x

x：=y

y：=temp9/7/2023計(jì)算機(jī)學(xué)院

66辛明影2引用調(diào)用（傳地址）

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

在目標(biāo)代碼中，在被調(diào)用過程中對形式參數(shù)的一次引用就成為對傳遞給被調(diào)用過程的指針的一個(gè)間接引用。Referenceabxy12swapabtemp9/7/2023計(jì)算機(jī)學(xué)院

67辛明影子程序?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;9/7/2023計(jì)算機(jī)學(xué)院

68辛明影3復(fù)制恢復(fù)（傳值結(jié)果）實(shí)現(xiàn)：

1.當(dāng)控制流入到被調(diào)用過程之前，把實(shí)在參數(shù)的右-值和左-值傳遞到被調(diào)用過程中；

2.當(dāng)控制返回時(shí)，把形式參數(shù)的現(xiàn)行右-值復(fù)制回到相應(yīng)的實(shí)在參數(shù)的左-值中。9/7/2023計(jì)算機(jī)學(xué)院

69辛明影

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

執(zhí)行時(shí)，對B2單元使用直接訪問形式；返回前，按B1中的地址把B2中的內(nèi)容存入主調(diào)程序的實(shí)參單元中。實(shí)參：地址形參：B1B2@B19/7/2023計(jì)算機(jī)學(xué)院

70辛明影

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

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

執(zhí)行時(shí)，每當(dāng)要對形參進(jìn)行訪問時(shí)，就調(diào)用THUNK子程序，以獲得相應(yīng)實(shí)參地址或值4傳名調(diào)用對形參的訪問是發(fā)生在實(shí)參單元上的9/7/2023計(jì)算機(jī)學(xué)院

71辛明影例：有程序段：procedurep(x,y,z)beginy=y+1;z=z+x;end

Begina=2;b=3;c=4;P(a,b,c);printa,b,c;end9/7/2023計(jì)算機(jī)學(xué)院

72辛明影傳值：abc實(shí)參形參xyz234P(a,b,c);234y=y+1;

輸出：23446Z=z+x;A=2B=3C=49/7/2023計(jì)算機(jī)學(xué)院

73辛明影傳地址：abc實(shí)參形參xyz234P(a,b,c);&a&b&cy=y+1;@y=@y+1輸出：24646Z=z+x;@z=@z+@x9/7/2023計(jì)算機(jī)學(xué)院

74辛明影傳值結(jié)果：abc實(shí)參形參X—B1B2Y—B1B2Z—B1B2234&a&b

y=y+1;

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

按@B1返回B2

的值4

6

2344

69/7/2023計(jì)算機(jī)學(xué)院

75辛明影傳名：abc實(shí)參形參xyz234P(a,b,c);&thunk&thunk&thunky=y+1;JSRThunkY→b輸出：24646Z=z+x;

jsr

ThunkZ→c,x→a9/7/2023計(jì)算機(jī)學(xué)院

76辛明影例：有程序段：procedurep(x,y,z)beginy=y+1;z=z+x;end

Begina=2;b=3;P(a+b,a,a);printaend9/7/2023計(jì)算機(jī)學(xué)院

77辛明影傳值：aba+b實(shí)參形參xyz23P(a+b,a,a);522y=y+1;

輸出：2

37Z=z+x;A=2B=359/7/2023計(jì)算機(jī)學(xué)院

78辛明影傳地址：aba+b實(shí)參形參xyz235P(a+b,a,a);&a+b&a&ay=y+1;@y=@y+1輸出：83Z=z+x;@z=@z+@x89/7/2023計(jì)算機(jī)學(xué)院

79辛明影傳名：ab實(shí)參形參xyz23P(a+b,a,a);&thunk&thunk&thunky=y+1;JSRThunkY→a輸出：939Z=z+x;

jsr

ThunkZ→a,x→a+b9/7/2023計(jì)算機(jī)學(xué)院

80辛明影第三章詞法分析9/7/202381編譯器的各個(gè)階段：編譯器是分階段執(zhí)行的。每個(gè)階段將源程序從一種表示轉(zhuǎn)換成另一種表示源程序詞法分析器錯(cuò)誤處理器符號管理表語法分析器語義分析器中間代碼生成器代碼優(yōu)化器代碼生成器編譯的各個(gè)階段9/7/2023計(jì)算機(jī)學(xué)院

82辛明影3.2詞法分析器的手工構(gòu)造：用DFA能識別3.3詞法分析程序自動構(gòu)造工具LEX簡介3.1詞法分析程序的設(shè)計(jì)：

9/7/2023計(jì)算機(jī)學(xué)院

83辛明影=80;0134256eniL字母字母字母字母數(shù)字?jǐn)?shù)字?jǐn)?shù)字==；；0124563Line=80;

id(25),‘Line’

=(

36),

num(27),‘80’

;(45),數(shù)字字母字母11==0003;;1輸入輸出有窮控制器單詞的詞類和屬性（詞類符號，單詞的屬性）9/7/2023計(jì)算機(jī)學(xué)院

84辛明影

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

一、詞法分析程序的功能

源程序

單詞序列

詞法分析器1、組織源程序的輸入2、識別單詞，轉(zhuǎn)換成機(jī)內(nèi)表示形式3、刪除注釋行、空格及無用符號4、查填符號表5、檢查詞法錯(cuò)誤9/7/2023計(jì)算機(jī)學(xué)院

85辛明影<12,><25,符號表入口><39,><25,符號表入口><20,><25,符號表入口><36,><26,常數(shù)表入口><8,><25,符號表入口><36,><26,常數(shù)表入口>ifi＞jtheni:＝0

elsej:=1詞法分析if

I＞JThenI＝0

elsej=19/7/2023計(jì)算機(jī)學(xué)院

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

1．關(guān)鍵字(保留字或基本字)：while,if9/7/2023計(jì)算機(jī)學(xué)院

87辛明影界符和運(yùn)算符:詞法分析器的輸出：（詞類編碼，單詞自身的屬性值）關(guān)鍵字可分成一類，也可以一個(gè)關(guān)鍵字分成一類。常數(shù)可統(tǒng)歸一類，也可按類型（整型、實(shí)型、布爾型等），每個(gè)類型的常數(shù)劃分成一類。所有的標(biāo)識符分為一類。詞類編碼原則:一字一碼。一類型一碼。一類一碼。一符一碼。9/7/2023計(jì)算機(jī)學(xué)院

88辛明影

表3.1單詞詞類編碼9/7/2023計(jì)算機(jī)學(xué)院

89辛明影對于關(guān)鍵字、界符、運(yùn)算符來說，它們的詞類編碼就可以表示其完整的信息，而對于標(biāo)識符，詞類編碼所反映的信息不夠充分，標(biāo)識符的具體特性還要通過單詞自身的屬性進(jìn)行互相區(qū)分。標(biāo)識符的單詞自身的屬性常用其在符號表中的入口指針來表示故對于這類單詞，其單詞自身的屬性值通常為空9/7/2023計(jì)算機(jī)學(xué)院

90辛明影對于常數(shù)，其單詞自身的屬性常用其在常數(shù)表中的入口指針來表示9/7/2023計(jì)算機(jī)學(xué)院

91辛明影

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

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

9/7/2023計(jì)算機(jī)學(xué)院

92辛明影

四、詞法分析的設(shè)計(jì)形式（1）設(shè)計(jì)成一個(gè)獨(dú)立程序，完成詞法分析的任務(wù)，結(jié)果以文件的形式組織，做為語法分析的輸入源程序詞法分析符號表TOKEN字錯(cuò)誤信息9/7/2023計(jì)算機(jī)學(xué)院

93辛明影詞法分析語法分析語義分析和中間代碼生成源程序中間代碼

符號表管理

錯(cuò)誤的診查處理（2）作為語法分析和語義分析的子程序9/7/2023計(jì)算機(jī)學(xué)院

94辛明影

五、詞法分析程序的設(shè)計(jì)框圖SCANNEROUTPUTsort字母RECOGID數(shù)字RECOGDIG/HANDLCOMRECOGDEC界符’RECOGSTRLOOKUP9/7/2023計(jì)算機(jī)學(xué)院

95辛明影3

2詞法分析器的手工構(gòu)造為了構(gòu)造詞法分析器，要研究構(gòu)詞法，每種詞類的結(jié)構(gòu)模式以及識別它的數(shù)學(xué)模型——有窮自動機(jī)。3

21確定的有限自動機(jī)（DFA）3

22構(gòu)造識別單詞的DFA3

23編寫詞法分析程序9/7/2023計(jì)算機(jī)學(xué)院

96辛明影SCANNEROUTPUTsort字母RECOGID數(shù)字RECOGDIG/HANDLCOMRECOGDEC界符’RECOGSTRLOOKUP9/7/2023計(jì)算機(jī)學(xué)院

97辛明影一、手工構(gòu)造識別單詞的DFAm

根椐DFA識別單詞的定義，在研究給定程序語言單詞結(jié)構(gòu)的基礎(chǔ)上，能直接構(gòu)造出識別它的DFAm。例如：對于C語言整數(shù)：非空數(shù)字串。無符號實(shí)數(shù)（用d表示數(shù)字）:(a)dd.ddE(+-)ddddE(+-)dd(c)dd.dd0.1e+1412e-43.141592(d)dd…dd10009/7/2023計(jì)算機(jī)學(xué)院

98辛明影IBTTa-a,d其它例：C語言的標(biāo)識符標(biāo)識符：字母開始的字母數(shù)字串。9/7/2023計(jì)算機(jī)學(xué)院

99辛明影例：C語言實(shí)常數(shù)的文法描述01234567dddEdEd-+dd10003.141512e-40.1e+14.9/7/2023計(jì)算機(jī)學(xué)院

100辛明影在識別標(biāo)識符的過程中，首先要拼寫出來，并和保留字區(qū)別開來；識別出的標(biāo)識符要填入符號表中二、編寫詞法分析程序根據(jù)畫出的狀態(tài)轉(zhuǎn)換圖（識別單詞的）構(gòu)造詞法分析程序，每個(gè)狀態(tài)對應(yīng)一段程序，完成到達(dá)此狀態(tài)的工作；在識別常數(shù)的過程中，要把它轉(zhuǎn)換成機(jī)器表示以作為屬性值，記錄到常數(shù)表中。

詞法分析程序的控制程序模擬狀態(tài)轉(zhuǎn)換圖的狀態(tài)轉(zhuǎn)換。9/7/2023計(jì)算機(jī)學(xué)院

101辛明影programSCANNER;Begininitiate符號表,字符串表,行,列計(jì)數(shù)器;Open源文件,TOKEN文件,打印機(jī)文件;RepeatFIRSTCH(CH);ifCH!=EOLthencallSORT(CH)elseRDLINE;untilCH=EOF;把符號表,字符串表做成文件;close源文件,TOKEN文件;callOUTPUTR;模塊0：掃描器主控9/7/2023計(jì)算機(jī)學(xué)院

102辛明影單詞分類模塊(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}

9/7/2023計(jì)算機(jī)學(xué)院

103辛明影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)識符',ENTRY)TOKEN:=(標(biāo)識符種別碼,ENTRY)};Return};識別標(biāo)識符；輸入：CH中含標(biāo)識符的首字母；輸出：TOKEN(二元式形式);9/7/2023計(jì)算機(jī)學(xué)院

104辛明影procedureHANDLECOM(TOKEN);{callGETCH(CH);ifCH!='*'then{列計(jì)數(shù)-1;TOKEN=(‘/’的識別碼,_);return};TOKEN='-1';GETCH(CH);while列計(jì)數(shù)<=行長-1do{CH1:=CH;callGETCH(CH);ifCH1='*'andCH='/'thenTOKEN:=‘';}ifTOKEN!=‘’thencallPRINTERR(‘注解未完’);TOKEN:=‘';return}處理注解(HANDLECOM);輸入：‘/’;進(jìn)入該模塊之前已掃描了一個(gè)字符‘/’輸出：‘/’的TOKEN字或空TOKEN字;

9/7/2023計(jì)算機(jī)學(xué)院

105辛明影識別界限符(RECOGDEL)輸入：CH內(nèi)含單界限符；輸出：各種界符的TOKEN字;procedureRECOGDEL(CH,TOKEN);{caseCHof‘+’:TOKEN:=(‘+’的種別碼,_);‘)’:TOKEN:=(‘)’的種別碼,_);‘<’:{callGETCH(CH);ifCH=‘=’thenTOKEN:=(‘<=’的種別碼,_)elseifCH=‘>’thenTOKEN:=(‘<>’的種別碼,_)

else{列計(jì)數(shù)-1;TOKEN:=(‘<’的種別碼,_)}}……..

endcase;return}9/7/2023計(jì)算機(jī)學(xué)院

106辛明影3.3詞法分析程序的自動構(gòu)造工具LEX簡介一.原理單詞的結(jié)構(gòu)用正規(guī)式描述正規(guī)式

NFA

DFA

minDFALEX編譯器LEX源程序lex.1Lex.yy.c二.用LEX建立詞法分析程序的過程9/7/2023計(jì)算機(jī)學(xué)院

107辛明影C編譯器Lex.yy.ca.outa.out輸入流單詞序列三.lex源程序

lex源程序由三部分組成9/7/2023計(jì)算機(jī)學(xué)院

108辛明影聲明%%翻譯規(guī)則%%輔助過程9/7/2023計(jì)算機(jī)學(xué)院

109辛明影

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

p1{動作1}

p2{動作2}……

pn{動作n}9/7/2023計(jì)算機(jī)學(xué)院

110辛明影

每個(gè)pi是正規(guī)定義式的名子，每個(gè){動作i}是正規(guī)定義式pi識別某類單詞時(shí)，詞法分析器應(yīng)執(zhí)行動作的程序段。用C書寫。標(biāo)識符{字母}({字母}|{數(shù)字})*%%標(biāo)識符{入口地址=LOOKUP();}%%LOOKUP()9/7/2023計(jì)算機(jī)學(xué)院

111辛明影輔助過程是動作需要的，這些過程用C書寫，可以分別編譯.例：LOOKUP()9/7/2023計(jì)算機(jī)學(xué)院

112辛明影第四章語法分析該講語法分析了！這可是很重要的章節(jié)9/7/2023113主要內(nèi)容：本章將重點(diǎn)介紹典型的語法分析方法及相關(guān)的概念和實(shí)現(xiàn)技術(shù)語法分析分為：自上而下:自下而上：遞歸下降分析法

LL（1）預(yù)測分析法推導(dǎo)算符優(yōu)先分析法LR分析法歸約從根向葉的方向建立分析樹從葉向根的方向建立分析樹9/7/2023計(jì)算機(jī)學(xué)院

114辛明影4.1語法分析器的功能詞法分析器語法分析器語義分析符號表源程序單詞符號語法樹中間表示完成的任務(wù)：

①對詞法分析器產(chǎn)生的單詞符號進(jìn)行處理，輸出分析樹

②與單詞相關(guān)的信息記錄到符號表中③類型檢查④錯(cuò)誤處理4.1.1語法分析器任務(wù)9/7/2023計(jì)算機(jī)學(xué)院

115辛明影4.1.2相關(guān)約定一.符號的使用約定1.終結(jié)符①.字母表中比較靠前的小寫字,如a,b,c②.操作符，如+、-等③.標(biāo)點(diǎn)符號，如括號、逗號等④.數(shù)字0、1、。。。9⑤.黑體串，如if、id等9/7/2023計(jì)算機(jī)學(xué)院

116辛明影2.下列符號是非終結(jié)符①.字母表中比較靠前的大寫字,如A、B、C②.字母S，常用來表示開始符號③.小寫斜體名字，如expr、stmt9/7/2023計(jì)算機(jī)學(xué)院

117辛明影3.字母表中比較靠后的大寫字母，如X、Y、Z等，用來表示文法符號，也就是說，可以是終結(jié)符，也可以是非終結(jié)符4.字母表中比較靠后的小寫字母，如u、v…z等，表示終結(jié)符的串聯(lián)5.小寫希臘字母α、β、γ等表示文法符號的串，所以一個(gè)產(chǎn)生式可寫作：

A→α9/7/2023計(jì)算機(jī)學(xué)院

118辛明影4.2自頂向下分析法4.2.1使用的技術(shù)、存在的問題及解決方法9/7/2023計(jì)算機(jī)學(xué)院

119辛明影一、推導(dǎo)推導(dǎo)：就是用產(chǎn)生式的右部的串來代替左部的非終結(jié)符事實(shí)上推導(dǎo)給出了自頂向下構(gòu)成分析樹過程的精確描述例：有描述算術(shù)表達(dá)式的文法G字符串id+id*id

是該文法的句子，其推導(dǎo)過程如下：E→E+E|E*E|（E）|-E|id9/7/2023計(jì)算機(jī)學(xué)院

120辛明影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*id9/7/2023計(jì)算機(jī)學(xué)院

121辛明影最左推導(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的句型

+語言：L（G）={w/S=〉w

}9/7/2023計(jì)算機(jī)學(xué)院

122辛明影二、語法樹語法描繪了如何從文法的開始符號推導(dǎo)出一個(gè)句子的過程語法樹可以看成是推導(dǎo)的圖形表示，但它不能顯示出替代的順序前面句子id+id*id推導(dǎo)過程所對應(yīng)的分析樹如下：9/7/2023計(jì)算機(jī)學(xué)院

123辛明影

EE+TTT*FFFididid9/7/2023計(jì)算機(jī)學(xué)院

124辛明影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)記為開始符號2.每個(gè)葉結(jié)點(diǎn)由終結(jié)符或者ε標(biāo)記語法具有如下特性的樹：9/7/2023計(jì)算機(jī)學(xué)院

125辛明影語法樹的葉結(jié)點(diǎn)從左到右的排列，剛好是這個(gè)文法所產(chǎn)生的語言的一個(gè)句子一個(gè)文法生成的語言就是它的某個(gè)分析樹所生成的句子的集合為給定的終結(jié)符串（句子）構(gòu)造一棵分析樹的過程稱為這個(gè)串（句子）的語法分析（parsing)9/7/2023計(jì)算機(jī)學(xué)院

126辛明影三、二義性句子id+id*id有兩棵分析樹與之對應(yīng)EE+EidE*EididEE*EE+Eididid9/7/2023計(jì)算機(jī)學(xué)院

127辛明影給定一個(gè)文法G，如果L（G）中存在一個(gè)具有兩棵或兩棵以上分析樹的句子，很顯然，描述算術(shù)表達(dá)式的文法G

E→E+E|E*E|（E）|-E|id

是一個(gè)二義性文法造成二義性的原因是：文法中沒有體現(xiàn)出結(jié)合率和優(yōu)先級我們就稱該文法為二義性的，G也叫二義性文法。9/7/2023計(jì)算機(jī)學(xué)院

128辛明影

大多數(shù)的語法分析器都要求文法是無二義性的消除二義性：可以通過改寫文法來消除二義性例：stmt→ifexprthenstmt|ifexprthenstmtelsestmt|other9/7/2023計(jì)算機(jī)學(xué)院

129辛明影通過例子

ifE1thenifE2thenS2elseS3很容易證明這是一個(gè)二義性文法sifEthenSelseSifEthenS9/7/2023計(jì)算機(jī)學(xué)院

130辛明影SifEthenSifEthenSelseS9/7/2023計(jì)算機(jī)學(xué)院

131辛明影在程序設(shè)計(jì)語言中，我們常常采用“最近匹配”原則來解決這種二義性文法改寫出為：

stmt→matched_stmt|unmatched_stmtmatched_stmt→

ifexprthenmatched_stmt

elsematched_stmt|otherunmatched_stmt→

ifexprthenmatched_stmt

elseunmatched_stmt

|ifexprthen_stmt9/7/2023計(jì)算機(jī)學(xué)院

132辛明影四、左遞歸如果文法G具有一個(gè)非終結(jié)符A使得對

某個(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是直接左遞歸的+9/7/2023計(jì)算機(jī)學(xué)院

133辛明影左遞歸會使分析進(jìn)入到無限循環(huán)之中消除簡單左遞歸的方法：

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

A→βA’A’→αA’|ε9/7/2023計(jì)算機(jī)學(xué)院

134辛明影例：下面是描述算術(shù)表達(dá)式的算法

E→E+T|TT→T*F|FF→(E)|id消除E和T的直接左遞歸，得到：

E→TE’

E’→+TE’|εT→FT’F→(E)|idT’→*FT’|ε9/7/2023計(jì)算機(jī)學(xué)院

135辛明影對于一般情況而言，若某一文法G的產(chǎn)生式具有如下形式：

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

|…|Aαm|

β1|β2|…|βn

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

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

ε很容易證明改造前后的文法是等價(jià)的9/7/2023計(jì)算機(jī)學(xué)院

136辛明影例：文法G（P）：

P→（Q）|aP|aQ→Q,P|P試消除左遞歸9/7/2023計(jì)算機(jī)學(xué)院

137辛明影消除左遞歸后，方法改為：

P→（Q）|aP｜aQ→PＱ’

Q→，ＰＱ’｜ε9/7/2023計(jì)算機(jī)學(xué)院

138辛明影

S→Qc|cQ→Rb|bR→Sa|aS這樣的遞歸無法用前面的方法消除對于含有間接左遞歸的文法：=>Qc=>Rbc=>Sabc出現(xiàn)了左遞歸9/7/2023計(jì)算機(jī)學(xué)院

139辛明影消除左遞歸的一般算法：輸入：無循環(huán)推導(dǎo)和ε產(chǎn)生式的方法G輸出：與G等價(jià)的無左遞歸文法算法：9/7/2023計(jì)算機(jī)學(xué)院

140辛明影1.以某種順序排列非終結(jié)符A1A2…An2.fori=1tondobeginforj=1toi-1dobegin

改寫Ai→Aj

γ

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

則Ai→δ1γ

|δ2γ

|…|δnγ；end

消除Ai中的所有直接左遞歸End3.化簡由2所得文法9/7/2023計(jì)算機(jī)學(xué)院

141辛明影

S→Qc|cQ→Rb|bR→Sa|a對如下文法消除左遞歸：1.將非終結(jié)符排序?yàn)镽、Q、S2.R不存在左遞歸，將R代入Q：

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

S→Sabc|abc|bc|c4.消除直接左遞歸后，得文法：9/7/2023計(jì)算機(jī)學(xué)院

142辛明影

S→abcS’|bcS’|cS’

S’→abcS’|ε

Q→Rb|bR→Sa|a5.化簡文法

S→abcS’|bcS’|cS’

S’→abcS’|ε

9/7/2023計(jì)算機(jī)學(xué)院

143辛明影

Z->A

A->aB|aC|Ad|Ae

B->bBC|f

C->c

9/7/2023計(jì)算機(jī)學(xué)院

144辛明影五、提取左因子為句子ifE1thenS1elseS2構(gòu)造一棵語法樹文法：

stmt→ifexprthenstmt|S|ifexprthenstmtelsestmt

stmt

ifexpr