編譯原理-總復(fù)習(xí)_第1頁
編譯原理-總復(fù)習(xí)_第2頁
編譯原理-總復(fù)習(xí)_第3頁
編譯原理-總復(fù)習(xí)_第4頁
編譯原理-總復(fù)習(xí)_第5頁
已閱讀5頁,還剩137頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1編譯程序是將一種語言(源語言,通常是高級語言)翻譯為另一種語言(目標(biāo)語言,通常用匯編語言或機(jī)器語言表示)的計(jì)算機(jī)程序。目標(biāo)程序翻譯源程序一個(gè)編譯程序涉及到三個(gè)方面的語言,即源語言、目標(biāo)語言和編譯程序的書寫語言。為了描述方便通常用T型圖來表示這三個(gè)方面的語言。T型圖的左上角表示源語言,右上角表示目標(biāo)語言,底部表示書寫語言(實(shí)現(xiàn)語言)STI■第一章2詞法分析源程序目標(biāo)程序語法分析語義分析目標(biāo)代碼生成文字表、符號表處理錯誤處理中間代碼優(yōu)化中間代碼生成前端后端1.2編譯過程和編譯程序的基本結(jié)構(gòu)3第二章2.2.1字母表和符號串字母表是元素的非空有窮集合。例如:

={a,b,c}

字母表中至少包含一個(gè)元素。字母表中的元素可以是字母、數(shù)字或其他符號。符號(字符)字母表中的元素稱為符號,或稱為字符。43.字符串(字)

符號的有窮序列稱為符號串。例如有字母表

={a,b,c},則有字符串a(chǎn),b,ab,ba,……

符號串總是建立在某個(gè)特定字母表上的,且只能由字母表上的有窮多個(gè)符號組成。符號串中符號的順序很重要,例如ab和ba就是兩個(gè)不同的符號串。不包含任何符號的符號串,稱為空符號串,用ε表示??辗柎?個(gè)符號組成,其長度

|ε|=05注意:

ε是符號串,而不是集合

{ε}表示由空符號串ε所組成的集合,但這樣的集合不是空集合Φ={}6符號串的長度:符號串中所包含的符號的個(gè)數(shù)例s=string,|s|=6,|ε|=0符號串的連接:設(shè)α、β是兩個(gè)符號串,則αβ稱為α與β的連接例α=some,β=thing,αβ=something εα=αε=α符號串的乘積:設(shè)A、B是兩個(gè)符號串的集合,AB表示A與B的乘積。

2.2.2符號串的運(yùn)算7例:A={ab,cd},B={ef,gh}AB={abef,abgh,cdef,cdgh}

特別地,{ε}A=A{ε}=A符號串集合的正則閉包A+A+=AA2A3…An,即A+為集合A上所有符號串的集合符號串集合的閉包記為A*定義A*={ε}

A+=A+

{ε}顯然,A+=AA*=A*A8符號串的冪運(yùn)算設(shè)x是符號串,則x的冪運(yùn)算定義為

x0=ε x1= x x2= xx ……

xn

= xx…x=xxn-1(n>0)例如,設(shè)x=abc

9集合的冪運(yùn)算設(shè)A是符號串的集合,則集合A的冪運(yùn)算定義為

A0={ε} A1= A A2= AA …… An= AA…A=AAn-1(n>0)例如,設(shè)A={a,b},則A2=?A+?A*?102.文法文法是產(chǎn)生式的非空有窮集合,通常表示成四元組G=(VN,VT,P,S)。其中:VN是產(chǎn)生式中非終結(jié)符的集合。VT是產(chǎn)生式中終結(jié)符的集合。VN∩VT=?P是文法規(guī)則的集合。S是一個(gè)非終結(jié)符,稱為文法的開始符號,它至少要在一條規(guī)則的左部出現(xiàn)。由它開始,識別出我們所定義的語言。11復(fù)雜的產(chǎn)生式往往用一些基本的產(chǎn)生式組合而成。①基本式:Aα,這里α是終結(jié)符組成的串,這個(gè)語法所定義的語言只有一個(gè)符號串。例:A0②嵌套式:AαBβ,α、β是終結(jié)符串,B是一個(gè)非終結(jié)符串,A所定義的終結(jié)符串是每個(gè)B定義的語句(可推出的終結(jié)符串)前邊加α串并且后邊加β串。例:

AiBchina

Blove一些基本的產(chǎn)生式重點(diǎn)掌握給定的文法,能夠?qū)懗鑫姆ㄋ硎镜恼Z言。12③遞歸式:有兩個(gè)常用的產(chǎn)生式都能表示遞歸式。

AAα|α,A

αA|α

它們定義的串集合為:{α,αα,α…ααα}α…ααα可寫成αn,所以L(A)={αn|n≥1}例:(i)D

bD|ε(ii)AaA|d④成對符號遞歸:可用下述產(chǎn)生式表示成對符號遞歸:

AαAβ|αβA定義的語言可記為L(A)={αnβn|n≥1}例:AabAcd|abcd一些基本的產(chǎn)生式13

推導(dǎo)從開始符號開始,經(jīng)過有限次的推導(dǎo)后得到一個(gè)終結(jié)符串(句子)。從開始符到句子間,每步推導(dǎo)所得到的含有非終結(jié)符的符號串是一個(gè)句型,一個(gè)文法G經(jīng)過推導(dǎo)所能獲得的全部句子的集合就是這個(gè)文法語言L(G). =>*表示經(jīng)過0步或若干步推導(dǎo)

=>+表示經(jīng)過1步或若干步推導(dǎo)14■語言的形式定義4、句型和句子G=(VT,VN,P,S),S=>*a,a∈(VTVN)*

稱a為句型。a∈VT*,稱a為句子。句型與句子區(qū)別:句型由終結(jié)符和非終結(jié)符構(gòu)成,句子只由終結(jié)符構(gòu)成。聯(lián)系:僅含終結(jié)符的句型是一個(gè)句子。即:句子必定是句型,但句型不一定是句子。例:設(shè)有文法G[S]:S01|0S1請分別判斷:01,000S111,0SS0,0011,0S1是該文法的句子還是句型?15■句型與句子舉例例:設(shè)有文法G[E]: EE+E|E*E|(E)|i試證明符號串

i+i*i(i*i+i)是文法G[E]的句子。16例2.5設(shè)有文法G[S]: S01|0S1有

S=>*01 S=>*0S1 S=>*00S11 S=>*000111問:哪些字符串是文法G的句子?哪些是文法的句型?如何由規(guī)則推導(dǎo)句子?推導(dǎo)方法:從一個(gè)要識別的符號開始推導(dǎo),即用相應(yīng)規(guī)則的右部來替代規(guī)則的左部,每次僅用一條規(guī)則去進(jìn)行推導(dǎo)。直到所有的非終結(jié)符號都由終結(jié)符號替代為止。17由此可見,從已知文法確定語言的中心思想是:從文法的開始符號出發(fā),反復(fù)連續(xù)地使用規(guī)則(產(chǎn)生式),對非終結(jié)符施行替換和展開,找出句子的規(guī)律,用式子或自然語言描述出來。注意:(1)給定一個(gè)文法,就能唯一地確定其語言,即

GL(G)(2)給定一種語言,能確定其文法,但這個(gè)文法不一定是唯一的。文法和語言的關(guān)系■規(guī)范推導(dǎo)和規(guī)范歸約最左(右)推導(dǎo):指對于一個(gè)推導(dǎo)序列中的每一步直接推導(dǎo)α=>β,都是對α中的最左(右)非終結(jié)符進(jìn)行替換規(guī)范推導(dǎo):指最右推導(dǎo)規(guī)范句型:用規(guī)范推導(dǎo)推導(dǎo)出的句型稱為規(guī)范句型規(guī)范歸約(最左歸約):規(guī)范推導(dǎo)的逆過程例:設(shè)有文法G[S]:SAB AA0|1B B0|S1請給出句子1000的最左、最右推導(dǎo)。練習(xí):給出句子101001的最左推導(dǎo)。19◆例2.12考慮文法G[N1]:

N1N NND|D D0|1|2該文法是左遞歸的,它所描述的語言是無窮集合。當(dāng)一個(gè)語言是無窮集合時(shí),則定義該語言的文法一定是遞歸的。{0,1,2}+202.5.1推導(dǎo)和語法樹對句型的推導(dǎo)過程給出一種圖形表示,這種表示稱為語法樹,也稱推導(dǎo)樹。2.5語法樹與文法的二義性與推導(dǎo)相對應(yīng)的語法樹是一個(gè)作了標(biāo)記的樹,其中內(nèi)部的節(jié)點(diǎn)由非終結(jié)符標(biāo)出,樹葉節(jié)點(diǎn)由終結(jié)符標(biāo)出,每個(gè)內(nèi)部節(jié)點(diǎn)都表示推導(dǎo)的一個(gè)步驟中的相關(guān)非終結(jié)符的替換。樹根結(jié)點(diǎn)是文法的開始符號。21語法樹的特點(diǎn):如果句子中有括號的話,括號在文法中表示了操作的優(yōu)先次序,這個(gè)次序在語法樹中已經(jīng)被樹的層次體現(xiàn)出來了。靠近根結(jié)點(diǎn)的計(jì)算總是較遲處理,靠近葉子的結(jié)點(diǎn)被優(yōu)先處理。22短語、簡單短語G=(T,N,P,S),w=xuy

∈(T

N)*

為文法的句型,若S=>xUy,且U=>+u,則u是句型w相對于U的短語;若S=>xUy,

U=>u,則u是句型w相對于U的簡單短語;其中U∈N,u∈(T

N)+,x,y∈(T

N)*

句柄任一句型的最左簡單短語稱為該句型的句柄。

短語、簡單短語是相對于句型而言,一個(gè)句型可能有多個(gè)短語、簡單短語,句柄只能有一個(gè)。Note23子樹:由某一結(jié)點(diǎn)連同所有分支組成的部分。簡單子樹:指只有單層分支的子樹。短語/直接短語/句柄在語法樹中的直觀解釋:短語----子樹的末端結(jié)點(diǎn)形成的符號串是相對于子樹根的短語直接短語----簡單子樹的末端結(jié)點(diǎn)形成的符號串是相對于簡單子樹根的短語句柄----最左簡單子樹的末端結(jié)點(diǎn)形成的符號串是句柄24例:有文法G[E]:

ET|E+T|E-T

TF|T*F|T/F

Fi|(E)請判斷(E+T)*i+F是G的一句型嗎?如果是,請畫出它的推導(dǎo)的分析樹,并寫出該樹的短語、簡單短語、句柄。解:∵E=>*(E+T)*i+F

∴(E+T)*i+F是G的一句型E+ETTF+ET)E(F*TiF25簡單短語(每棵簡單子樹的葉組成簡單短語):E+T是句型(E+T)*i+F相對于E的簡單短語;i是句型(E+T)*i+F相對于F的簡單短語;F是句型(E+T)*i+F相對于T的簡單短語。E+ETTF+ET)E(F*TiF短語(每棵子樹的葉組成短語):(E+T)*i+F是句型(E+T)*i+F相對于E的短語;(E+T)*i是句型(E+T)*i+F相對于E、T的短語;(E+T)是句型(E+T)*i+F相對于T、F的短語;E+T是句型(E+T)*i+F相對于E的短語;i是句型(E+T)*i+F相對于F的短語;F是句型(E+T)*i+F相對于T的短語。句柄(最左簡單子樹的葉組成句柄):E+T是句型(E+T)*i+F相對于E的最左簡單短語。26◆例2.13.設(shè)有文法G[S]=({S,A,B},{a,b},P,S)其中,P為

SAB

AAa|bB

Ba|Sb請判斷baSb是G的一句型嗎?如果是,請畫出它的推導(dǎo)的分析樹,并寫出該樹的短語、簡單短語、句柄。■文法的二義性引例:已知簡單整型算術(shù)表達(dá)式文法:

exp

expopexp|(exp)|iop

+|-|*

請畫出串i

-i

*i

的語法樹!解:1)推導(dǎo)

2)根據(jù)推導(dǎo)畫語法樹同一個(gè)句子若可生成兩棵不同的語法樹,則定義該句子的文法叫二義性文法。注意理解:若一個(gè)文法中存在某個(gè)句子,它有兩個(gè)不同的最左(最右)推導(dǎo),這個(gè)文法是二義性文法。■文法二義性的消除◆不修改文法,指定正確的語法樹;◆修改文法(考慮優(yōu)先級、結(jié)合性等)注意:文法的二義性和語言的二義性是兩個(gè)不同的概念。只要某文法定義的語言中,有一個(gè)句子有2棵以上的語法樹,該文法就是二義性的;而二義性語言是指,對它不存在無二義性的文法,這樣的語言稱為先天二義性的語言。文法G[E]:

E→T|E+T|E-T T→F|T*F|T/F

F→(E)|i文法G[E]:EE+E|E*E|(E)|i29注意:文法的二義性和語言的二義性是兩個(gè)不同的概念。通常我們只說文法的二義性,而不說語言的二義性,這是因?yàn)榭赡苡袃蓚€(gè)不同的文法G和G’,一個(gè)是二義性的,一個(gè)不是二義性的,但他們所描述的語言卻是一樣的,即L(G)=L(G’).

將一個(gè)語言說是二義性的,是指對它不存在無二義性的文法,這樣的語言稱為先天二義性的語言。人們已經(jīng)證明,不存在一個(gè)算法,它能在有限步驟內(nèi)確切地判定任給的一個(gè)上下文無關(guān)文法是否是二義性文法。30

文法和語言分類:0型、1型、2型、3型(喬姆斯基層次)

0型文法稱為短語結(jié)構(gòu)文法(非限制)。產(chǎn)生式的左部和右部都可以是符號串,一個(gè)短語可以產(chǎn)生另一個(gè)短語?!?型:P:u

v

其中u∈(T

N)+

,v∈(T

N)*

■喬姆斯基層次2.6文法和語言的分類31

1型文法稱為上下文敏感或上下文有關(guān)文法。也即只有在x,y這樣的上下文中才能把U改寫為u●1型:P:xUy

xuy

其中U∈N,x,y,u∈(T

N)*例:1型(上下文有關(guān))文法文法G[S]: S→CD

C→aCA

C→ε

C→bCB

D→ε

AD→aD

BD→bD

Aa→bD322型文法稱為上下文無關(guān)文法。也即把U推導(dǎo)為v時(shí),不必考慮上下文。●2型:P:U

v

其中U∈N

,v∈(T

N)*

文法G[S]:

S→AB A→BS|0 B→SA|12型文法即上下文無關(guān)文法及相應(yīng)的語言是我們主要研究的對象。33例:G[S]:S→0A|1B|0A→0A|1B|0SB→1B|1|03型文法稱為正則文法,它是對2型文法進(jìn)行進(jìn)一步限制3型文法不能把非終結(jié)符嵌在終結(jié)符串里。如:S

aSb|ab不是3型文法,3型文法不能描述anbn這樣的符號串。●3型:(左線性)P:U

t

U

Wt

其中

U、W∈Nt∈T(右線性)P:U

t

U

tW

其中

U、W∈Nt∈T34●0型、1型、2型、3型比較產(chǎn)生式左部范圍右部范圍|左部||右部|0型u

v(T

N)+(T

N)*>=1>=01型xUy

xuy(T

N)+(T

N)*>=1>=02型U

vN(T

N)*=1>=03型U

tU

WtNT

N=1<=2●3型:P:U

t或

U

Wt其中

U、W∈Nt∈T●2型:P:U

v

其中U∈N

,v∈(T

N)*

●0型:P:u

v

其中u∈(T

N)+

,v∈(T

N)*

●1型:P:xUy

xuy

其中U∈N,x,y,u∈(T

N)*L3

L2

L1

L0353.1詞法分析程序的功能所謂詞法,即構(gòu)成詞的規(guī)則。詞法分析的任務(wù)是對字符串表示的源程序從左到右進(jìn)行掃描和分解,根據(jù)語言的詞法規(guī)則識別出一個(gè)一個(gè)具有獨(dú)立意義的單詞符號。詞法分析是編譯過程中的一個(gè)階段,在語法分析前進(jìn)行,可以作為單獨(dú)的一遍,將源程序轉(zhuǎn)換成單詞符號序列供下一遍使用。也可以和語法分析結(jié)合在一起作為一遍,由語法分析程序調(diào)用詞法分析程序獲得當(dāng)前記號,供語法分析使用。363.2單詞符號及輸出單詞的形式源程序詞法分析程序單詞符號單詞符號是語言中具有獨(dú)立意義的最小單位,包括保留字、標(biāo)識符、常量、運(yùn)算符和界符等。詞法分析程序輸出的單詞符號通常表示成如下的二元式:(單詞種別,單詞自身的值)37■正規(guī)式與正規(guī)集3.3語言單詞符號的兩種定義方式多數(shù)程序設(shè)計(jì)語言的單詞符號都能用正規(guī)文法或正規(guī)式來定義。設(shè)有字母表

={a1,a2,…,an},在字母表上的正規(guī)式和它所表示的正規(guī)集可用如下規(guī)則定義:(1)Φ是上的正規(guī)式,它所表示的正規(guī)集是Φ,即空集{}(2)ε是上的正規(guī)式,它所表示的正規(guī)集是{ε}(3)ai是上的正規(guī)式,它所表示的正規(guī)集由單個(gè)符號ai組成,即{ai}38■正規(guī)式與正規(guī)集(4)如果e1和e2都是上的正規(guī)式,它們所表示的正規(guī)集分別為L(e1)和L(e2),則e1|e2是上的一個(gè)正規(guī)式,它所表示的正規(guī)集為L(e1|e2)=

L(e1)∪L(e2)e1e2是上的一個(gè)正規(guī)式,它所表示的正規(guī)集為L(e1e2)=L(e1)L(e2)(e1)*是上的一個(gè)正規(guī)式,它所表示的正規(guī)集為L((e1)*)=L((e1))*正規(guī)式描述了單詞符號的構(gòu)成規(guī)則,正規(guī)集是正規(guī)式能描述的所有的單詞的集合。39設(shè)有字母表

={a,b},根據(jù)正規(guī)式和正規(guī)集的定義有:■例3.1(1)a和b是正規(guī)式,相應(yīng)正規(guī)集為L(a)={a}(2)a|b是正規(guī)式,相應(yīng)正規(guī)集為L(a|b)={a,b}(3)ab是正規(guī)式,相應(yīng)正規(guī)集為L(ab)={ab}(4)(a|b)*是正規(guī)式,相應(yīng)正規(guī)集為L((a|b)*)={a,b}*={ε,a,b,ab,ba,…}(5)ba*是正規(guī)式,相應(yīng)正規(guī)集為L(ba*)={b,ba,baa,baaa,…}(6)(a|b)*(aa|bb)(a|b)*是正規(guī)式,相應(yīng)正規(guī)集為L={a,b}*{aa,bb}{a,b}*練習(xí):若S=a|bb,則L((a|bb)*)=?40■正規(guī)式中運(yùn)算的優(yōu)先級括號優(yōu)先,*次之,?(連接)再次之,|最后例:a|bc*≌a|(b(c*))

ab|c*d≌(ab)|((c*)d)

L(a|bc*)=L(a)∪L(bc*) =L(a)∪L(b)L(c*) =L(a)∪L(b)(L(c))* ={a}∪{ε,c,cc,ccc……} ={a,b,bc,bcc,bccc,……}■正規(guī)式與正規(guī)集舉例思考:L(ab|c*d)=?413.4正規(guī)式與有窮自動機(jī)有窮自動機(jī)是詞法的識別工具,它的功能是:尋找(匹配)符合正規(guī)式要求的字符串,根據(jù)正規(guī)式確定正規(guī)集。有窮自動機(jī)是描述特定類型算法的數(shù)學(xué)模型,可分為確定性有窮自動機(jī)(DFA)和非確定性有窮自動機(jī)(NFA)。42■確定有窮自動機(jī)(DFA)數(shù)學(xué)定義(五元組形式):嚴(yán)密;狀態(tài)轉(zhuǎn)換表:面向編程。狀態(tài)轉(zhuǎn)移圖:直觀;DFA有三種表示形式43結(jié)點(diǎn)代表狀態(tài)(state),用圓圈○表示。狀態(tài)之間用箭頭→(transition)連結(jié),代表一個(gè)狀態(tài)向另一個(gè)狀態(tài)的轉(zhuǎn)換。一個(gè)有窮自動機(jī)只包含有限個(gè)狀態(tài)(即有限個(gè)結(jié)點(diǎn)),其中只有一個(gè)為初態(tài)(startstate)(一個(gè)有開始狀態(tài)的箭頭指向),至少一個(gè)為終態(tài)(接受狀態(tài)acceptingstate)(雙圈表示)。例:標(biāo)識符的有窮自動機(jī)?!鲇懈F自動機(jī)的狀態(tài)轉(zhuǎn)移圖表示方法44■確定有窮自動機(jī)(DFA)◆∑輸入字母表◆Q有窮狀態(tài)集◆f:Q×∑→Q(狀態(tài)轉(zhuǎn)換函數(shù))◆S∈Q唯一的初始狀態(tài)◆Z

Q終止(接受)狀態(tài)集合這里的字母表是問題固有的;狀態(tài)集合是編寫DFA時(shí)定義的,是用戶所做的命名。DFAM是一個(gè)五元組(Q,∑,f,S,Z

)確定性有窮自動機(jī)(DFA):下一狀態(tài)由當(dāng)前狀態(tài)和當(dāng)前輸入字符唯一給出的自動機(jī)。(取決于f)“確定”即狀態(tài)轉(zhuǎn)移函數(shù)是單值函數(shù)——數(shù)學(xué)定義45■非確定有窮自動機(jī)(NFA)由M接受的語言L(M)

L(M)={c1c2c3….cn

|ci∈∑U{ε},s1=T(s0,c1),s2=T(s1,c2),…,sn=T(sn-1,cn),sn∈A.}“非確定”即狀態(tài)轉(zhuǎn)移函數(shù)是多值函數(shù)◆∑:輸入字母表◆Q:有窮狀態(tài)集◆f:Sx(

U{ε})?(S)(狀態(tài)轉(zhuǎn)換函數(shù))◆S

Q初始狀態(tài)集◆Z

Q終止?fàn)顟B(tài)集NFAM也是一個(gè)五元組(Q,∑,f,S,Z

)46轉(zhuǎn)換函數(shù)T初態(tài)NFAM(S,∑,T,S0,F)S×(

U{ε})

→S的子集多值映射S0

S非空初態(tài)集DFAM(S,∑,T,s0,F)S×∑→S的元素單值映射s0∈S唯一的初態(tài)●NFA與DFA的區(qū)別:47■由正規(guī)表達(dá)式R構(gòu)造NFA

(a)對于正規(guī)式φ,所構(gòu)造NFA:xy

(b)對于正規(guī)式ε,所構(gòu)造NFA:xyε

(c)對于正規(guī)式a,a∈Σ,則NFA:xya1.基本正規(guī)表達(dá)式48■由正規(guī)表達(dá)式R構(gòu)造NFA2、若r,s為正規(guī)式:123rssr13rsr|sr*例:構(gòu)造與正規(guī)表達(dá)式R=ab*a(a|b)*等價(jià)的NFA。1r32εε49定義1:狀態(tài)集合I的ε-閉包:令I(lǐng)是一個(gè)狀態(tài)集的子集,定義ε-closure(I)為:1)若s∈I,則s∈ε-closure(I);2)若s∈I,則從s出發(fā)經(jīng)過任意條ε弧能夠到達(dá)的任何狀態(tài)都屬于ε-closure(I)。狀態(tài)集ε-closure(I)稱為I的ε-閉包為了使得NFA確定化,給出兩個(gè)定義:56432aεaaε1例:如圖所示的狀態(tài)圖:令I(lǐng)={1},求ε-closure(I)=?解:根據(jù)定義:ε-closure(I)={1,3}例:若I1={1,2},則ε-closure(I1)={1,2,3,6}DFA的確定化50——J是從狀態(tài)子集I中的每個(gè)狀態(tài)出發(fā),經(jīng)過標(biāo)記為a的弧而達(dá)到的狀態(tài)集合?!?/p>

Ia是狀態(tài)子集,其元素為J中的狀態(tài),加上從J中每一個(gè)狀態(tài)出發(fā)通過ε弧到達(dá)的狀態(tài)。定義2:狀態(tài)子集的構(gòu)造:s∈I例:令I(lǐng)={1},求Ia=?Ia=ε-closure(J)=ε-closure(T(1,a))

=ε-closure({2,4})

={2,4,6}56432aεaaε1令I(lǐng)是NFAM’的狀態(tài)集的一個(gè)子集,a∈Σ定義:Ia=ε-closure(J)其中J=∪T(s,a)51例:有NFAM,求DFAM’。a1234startabaccε

IIa

Ib

Ic

{1,4}{2,3}φφ{(diào)2,3}{2}{4}{3,4}{2}{2}{4}φ{(diào)4}φφφ{(diào)3,4}φφ{(diào)3,4}初態(tài)I=ε-closure({1})={1,4}Ia=ε-closure(T(1,a)∪T(4,a))=ε-closure({2,3}∪φ)

=ε-closure({2,3})={2,3}Ib=ε-closure(T(1,b)∪T(4,b))=ε-closure(φ)

=φIc=ε-closure(T(1,c)∪T(4,c))=φI={2,3},Ia={2},Ib={4},Ic={3,4}……DFA的狀態(tài)52

符號狀態(tài)abc02341221________3344●DFAM’狀態(tài)表將求得的狀態(tài)轉(zhuǎn)換矩陣重新編號start01423{1,4}{2,3}{4}{2}acabbc{3,4}

IIa

Ib

Ic

{1,4}{2,3}φφ{(diào)2,3}{2}{4}{3,4}{2}{2}{4}φ{(diào)4}φφφ{(diào)3,4}φφ{(diào)3,4}包含NFA終態(tài)的狀態(tài)子集全都是DFA的終態(tài)53例:將該DFA最小化5724361srartaaaaaaabbbbbbb狀態(tài)集的劃分將所有DFA的終態(tài)與其它狀態(tài)劃分成兩個(gè)子集G1,G2;分別從兩個(gè)子集G1,G2中尋找不等價(jià)狀態(tài)進(jìn)行分割。“分割法”:把一個(gè)DFA(不含多余狀態(tài))的狀態(tài)分割成一些不相關(guān)的子集,使得任何不同的兩個(gè)子集狀態(tài)都是可區(qū)別的,而同一個(gè)子集中的任何狀態(tài)都是等價(jià)的.54解:(一)區(qū)分終態(tài)與非終態(tài)123456637315467374142ab567374142ab123463731546231區(qū)號5724361srartaaaaaaabbbbbbb將所有DFA的終態(tài)與其它狀態(tài)劃分成兩個(gè)子集區(qū)號12123456637315467374142ab5512431243123456637315467374142ab5123456637315467374142ab區(qū)號區(qū)號12345ab5214355231155243aaaaabbbbb567374142ab123463731546123區(qū)號將區(qū)號代替狀態(tài)號得:56正規(guī)文法正規(guī)式NFADFA最小化ABtA

tB(2)對終態(tài)Z增加Z

ε(1)右線性文法增加終態(tài);左線性文法增加初態(tài)解方程組,若x=αx+β,則x=α*β;Aab

轉(zhuǎn)換成AaB和BbAa*b轉(zhuǎn)換成AaA|b;57為R=(a|b)*(aa|bb)(a|b)*構(gòu)造最小化的DFA,使得L(N)=L(R)■課堂練習(xí)例:構(gòu)造與正則表達(dá)式R=ba(a|b)*等價(jià)的狀態(tài)最少的DFA,并寫出該DFA的五元組形式。58語法分析程序的功能是以詞法分析器生成的單詞符號序列作為輸入,根據(jù)語言的語法規(guī)則(文法),識別出各種語法成分,并在分析過程中進(jìn)行語法檢查,檢查所給單詞符號序列是否是該語言的文法的一個(gè)句子。若是,則以該句子的某種形式的語法樹作為輸出;若不是,則表明有錯誤,并指出錯誤的性質(zhì)和位置。4.1語法分析程序的功能語法分析程序的輸入是單詞符號序列;輸出是語法樹。59遞歸下降法LL(1)分析法回溯分析方法(不確定的分析法)預(yù)測分析方法(確定的分析法)LR(0)parsingSLR(1)parsingLR(1)parsingLALR(1)parsing自頂向下分析方法從根結(jié)點(diǎn)出發(fā)構(gòu)造語法樹

自底向上分析方法從葉結(jié)點(diǎn)出發(fā)構(gòu)造語法樹

語法分析方法L:由左向右的處理輸入L:為輸入串構(gòu)造最左推導(dǎo)

60■文法左遞歸的消除4.2自上而下分析法左遞歸導(dǎo)致無限遞歸循環(huán);解決無限遞歸循環(huán)的方法:消除左遞歸。(1)左遞歸改成右遞歸——簡單直接左遞歸的消除

A→Aα|βA→βA’A’→αA’|ε解:exp→termexp’

exp’→addoptermexp’|ε例:將文法G:exp→exp

addopterm|term

消除左遞歸。左遞歸的消除不改變語言,但是改變了文法和分析樹。確定的自上而下分析法對文法要求:(1)無左遞歸;(2)無回溯61將文法G:A→αβ|αγ提取左因子。解:A→αA’

A’→β|γ■提取左因子規(guī)則例:將文法G提取左因子。

stmt-sequence→stmt;stmt-sequence|stmt

stmt→s

提取左因子的結(jié)果:stmt-sequence→stmtstmt-seq’stmt-seq’→;stmt-sequence|εstmt→s注意:不可以這樣提取:Aa(β|γ)文法中括號的含義與正規(guī)式中括號的含義不同。62First集合和Follow集合■First集合定義:FIRST(α)={a|α=>*aβ,a

T,α,β

(T

N)*

}

若α=>*ε,則規(guī)定ε

FIRST(α)該集合稱為α的頭符號集合631.若X

,則FIRST(X)={X}2.若X

N,且有產(chǎn)生式X

a…,則把a(bǔ)加入到FIRST(X)中;若X

也是一條產(chǎn)生式,則把

也加到FIRST(X)中.3.若X

Y…是一個(gè)產(chǎn)生式且Y

N,則把FIRST(Y)中的所有非元素都加到FIRST(X)中;若X

Y1Y2…YK

是一個(gè)產(chǎn)生式,Y1,Y2,…,Y(i-1)都是非終結(jié)符,而且,對于任何j,1≤j≤i-1,FIRST(Yj)都含有

(即Y1..Y(i-1)

=>*

),則把FIRST(Yi)中的所有非

元素都加到FIRST(X)中;特別是,若所有的FIRST(Yj,j=1,2,…,K)均含有

,則把

加到FRIST(X)中.■First集合算法P69令X為一個(gè)文法符號或

,則集合First(X)由終結(jié)符組成,此外還可能有

,定義如下:64■求First集合舉例2求文法G的FIRST集合G:(1)M→TB (2)T→Ba|ε (3)B→Db|eT|ε (4)D→d|ε注意:有ε產(chǎn)生式時(shí)求First集,別漏元素?。irst(M)={e,a,d,b,ε}

First(T)={e,a,d,b,ε}

First(B)=

{e,d,b,ε}

First(D)=

{d,ε}注意:除了求非終結(jié)符的First集外,還可求符號串的First集。例:求First(BaB)65定義:FOLLOW(A)={a|S=>*

…Aa…,a∈T}A∈N,S開始符號特殊地:若S=>*...A,則$∈FOLLOW(A)■Follow集合1.對于文法的開始符號S,置$于FOLLOW(S)

中;2.若A

αBβ是一個(gè)產(chǎn)生式,則把FIRST(β)-{}加至FOLLOW(B)中;3.若A

αB是一個(gè)產(chǎn)生式,或A

αBβ是一個(gè)產(chǎn)生式而

FIRST(β),則把FOLLOW(A)加至FOLLOW(B)中。算法:66練習(xí)4)求文法G的FOLLOW集合

E→TE’

E’→+TE’|ε

T→FT’T’→*FT’|ε

F→(E)|iFIRST(F)={(,i}FIRST(T’)={*,ε}FIRST(T)={(,i}FIRST(E’)={+,ε}FIRST(E)={(,i}FOLLOW(E)={$,)}FOLLOW(E’)={$,)}FOLLOW(T)={+,),$}FOLLOW(T’)={+,),$}FOLLOW(F)={*,+,),$}解:67■Select集合Select集合是針對規(guī)則(產(chǎn)生式)的。設(shè)A

α是文法的任一條規(guī)則,則定義:Select(A

α)=First(α) 若α=>*

First(α)-{}

∪Follow(A)

若α=>*

例:求下列文法的每個(gè)規(guī)則的Select集合:

AaB|d

BbBA|

68一個(gè)上下文無關(guān)文法G是LL(1)文法,當(dāng)且僅當(dāng)對G中每個(gè)非終結(jié)符A的任何兩個(gè)不同的規(guī)則A

α

β滿足:Select(A

α)∩Select(A

β)=

■LL(1)文法的要求69■預(yù)測分析表的構(gòu)造算法(1)計(jì)算每一非終結(jié)符的First集和Follow集;(2)對于First(α)中的每個(gè)記號a,都將A→α添加到表項(xiàng)M[A,a]中;(3)若ε在First(α)中,則對于Follow(A)的每個(gè)元素a(記號或是$),都將A→α添加到M[A,a]中;(4)把分析表中沒有填入內(nèi)容的空白格都標(biāo)上出錯標(biāo)志error。例:文法:Sa|^|(T) TT,S|S試判斷該文法是否是LL(1)文法,若不是請轉(zhuǎn)換,并求轉(zhuǎn)換后LL(1)文法的預(yù)測分析表。70●練習(xí)1Follow(exp)={$,)}Follow(exp’)={$,)}Follow(addop)={(,number}Follow(term)={$,+,-,)}Follow(term’)={$,+,-,)}Follow(mulop)={(,number}Follow(factor)={$,+,-,*,)}(1)First集和Follow集First(exp)={(,number}First(exp’)={+,-,ε}First(addop)={+,-}First(term)={(,number}First(term’)={*,ε}First(mulop)={*}First(factor)={(,number}文法:exp→expaddop

term∣term

addop

+|- term→termmulop

factor∣factor

mulop

→* factor→(exp)

number

注意:先消除左遞歸71Follow(exp)={$,)}Follow(exp’)={$,)}Follow(addop)={(,number)Follow(term)={$,+,-,)}Follow(term’)={$,+,-,)}Follow(mulop)={(,number)Follow(factor)={$,+,-,*,)}(2)First集和Follow集First(exp)={(,number)First(exp’)={+,-,ε}First(addop)={+,-}First(term)={(,number)First(term’)={*,ε}First(mulop)={*}First(factor)={(,number)11109788886654223311factormulopterm’termaddopexp’exp$*-+)Number(M[N,T](3)LL(1)分析表解

(1)文法1exp→termexp’2exp’→addoptermexp’3exp’→ε4addop

→+5addop

→-6term→factorterm’7term’→

mulopfactorterm’8term’→ε9mulop

→*10factor→(exp)11factor→number(1)對于First(α)中的每個(gè)記號a,都將A→α添加到表項(xiàng)M[A,a]中;(2)若ε在First(α)中,則對于Follow(A)的每個(gè)元素a(記號或是$),都將A→α添加到M[A,a]中。4.5LR分析

LR分析法是一種自上而下進(jìn)行規(guī)范規(guī)約的語法分析方法。這里的L是指從左到右掃描輸入符號串,R是指構(gòu)造最右推導(dǎo)的逆過程。這種分析法比遞歸下降分析法、預(yù)測分析法和算府優(yōu)先分析法對文法的限制要少的多,也就是說,對大多數(shù)無二義性的上下文無關(guān)文法描述的語言都可以用LR分析法進(jìn)行分析,而且分析速度快,并能準(zhǔn)確及時(shí)地指出輸入串的語法錯誤和出錯位置。缺點(diǎn):構(gòu)造LR分析器的工作量大734.5LR分析法本節(jié)介紹四種LR分析法:LR(0)、SLR(1)、LR(1)、LALR,這四種方法的區(qū)別只有分析表不同。LR分析法是一種自下而上進(jìn)行規(guī)范歸約的語法分析方法。這里L(fēng)是指從左向右掃描輸入符號串,R是只構(gòu)造最右推導(dǎo)的逆過程。優(yōu)點(diǎn):對文法的限制少的多,分析速度快;缺點(diǎn):構(gòu)造LR分析器的工作量大,實(shí)現(xiàn)困難。4.5.1LR分析器的工作原理和過程

LR分析法是一種規(guī)范規(guī)約分析方法,這種分析法的關(guān)鍵是在分析過程中如何確定分析棧棧頂?shù)姆柎欠窨尚纬删浔?/p>

LR分析法確定句柄的基本思想是在規(guī)范規(guī)約分析過程中,根據(jù)分析棧中記錄的已移進(jìn)和規(guī)約出的整個(gè)字符串(歷史)和根據(jù)使用規(guī)則推測未來可能遇到的輸入符號(即展望),以及現(xiàn)讀到的輸入符號這3方面的信息來確定分析棧的棧頂?shù)姆柎欠駱?gòu)成句柄。75輸入

a1...ai...an$LR驅(qū)動程序分析表輸出棧smXmsm-1Xm-1...s0actiongoto

LR分析器的結(jié)構(gòu)和工作過程■LR分析器的工作原理和過程

LR分析表是LR分析器的核心部分。一張LR分析表由分析動作(ACTION)表和狀態(tài)轉(zhuǎn)換表(GOTO)兩部分組成,他們都是二維數(shù)組。狀態(tài)轉(zhuǎn)換表元素GOTO[Si,X]規(guī)定了當(dāng)狀態(tài)Si面臨文法符號X時(shí),應(yīng)該轉(zhuǎn)移到的下一個(gè)狀態(tài)。分析動作表元素ACTION[Si,a]規(guī)定了當(dāng)狀態(tài)Si面臨輸入符號a時(shí)應(yīng)執(zhí)行的動作。有如下4種可能的動作:(1)移進(jìn):把狀態(tài)Sj=GOTO[Si,a]和輸入符號a移入分析棧。(2)規(guī)約:當(dāng)棧頂符號串a(chǎn)形成句柄,且文法中有A

的規(guī)則,其中|α|=β,則規(guī)約動作是從分析棧棧頂去掉β個(gè)文法符號和β個(gè)狀態(tài),并把規(guī)約符A和GOTO[Si-β,A]=Sj移入分析棧中(3)接受(acc):表示分析成功。此時(shí),分析棧中只剩文法開始符號S‘和當(dāng)前讀到的輸入符號$,即輸入的符號串已經(jīng)結(jié)束。(4)報(bào)錯:表示輸入串有錯誤,此時(shí)出現(xiàn)棧頂?shù)哪骋粻顟B(tài)遇到了不該遇到的輸入符號。78在文法產(chǎn)生式右部某個(gè)位置標(biāo)有‘.’的產(chǎn)生式,稱為文法的一個(gè)LR(0)項(xiàng)目。形如A.的項(xiàng)目稱為初始項(xiàng)目;形如A.的項(xiàng)目稱為歸約項(xiàng)目;形如A.B(B∈N)的項(xiàng)目稱為待約項(xiàng)目;形如A.a(a∈T)的項(xiàng)目稱為移進(jìn)項(xiàng)目;形如S’S.的項(xiàng)目稱為接受項(xiàng)目,其中S’為文法的唯一的開始符號■項(xiàng)目分類79設(shè)I是文法G的一個(gè)LR(0)項(xiàng)目集合,I的項(xiàng)目閉包c(diǎn)losure(I)定義為:(1)Iclosure(I)。

(2)若項(xiàng)目A.Bclosure(I),且B是G的產(chǎn)生式,則項(xiàng)目B.closure(I)。

(3)closure(I)僅包含上述兩條規(guī)則確定的LR(0)項(xiàng)目。項(xiàng)目閉包:轉(zhuǎn)移函數(shù):若I是文法G的一個(gè)LR(0)項(xiàng)目集,X是G中的文法符號。go(I,X)=closure(J)其中J={AX.|A.XI}稱函數(shù)go(I,X)為轉(zhuǎn)移函數(shù)。項(xiàng)目AX.稱為項(xiàng)目A.X后繼。■構(gòu)造識別文法所有規(guī)范句型活前綴DFA的方法80■LR(0)分析表的構(gòu)造若對于一個(gè)文法G的拓廣文法G’的LR(0)項(xiàng)目集規(guī)范族中的每個(gè)項(xiàng)目集,不存在移進(jìn)項(xiàng)目和歸約項(xiàng)目同時(shí)并存或多個(gè)歸約項(xiàng)目同時(shí)并存,則稱G為LR(0)文法。即LR(0)文法中不能存在移進(jìn)-歸約沖突或者歸約-歸約沖突。E'→·EE→·E+nE→·nE→n·E'→E·E→E·+nE→E+n·En+n012E→E+·n34根據(jù)右圖某文法識別活前綴的DFA判斷該文法是否為LR(0)文法81■LR(0)分析表的構(gòu)造LR(0)分析表包含兩個(gè)子表:ACTION表和GOTO表假定項(xiàng)目集規(guī)范族C={I0,I1,…,In},令每個(gè)項(xiàng)目集Ik的下標(biāo)k作為分析器的狀態(tài),兩個(gè)子表的構(gòu)造過程如下:(1)若項(xiàng)目A.a

屬于Ik且GO(Ik,a)=Ij,a為終結(jié)符,則置ACTION[k,a]為”sj”;(2)若項(xiàng)目A.

屬于Ik,則對任何終結(jié)符a(包括終結(jié)符$),置ACTION[k,a]為”rj”(注:j是產(chǎn)生式A的編號,而不是狀態(tài)集的狀態(tài)號);(3)若項(xiàng)目S’→S·屬于Ik(S·表示整個(gè)句子已輸入并歸約結(jié)束),則置ACTION[k,$]為“acc”,表示接受。(4)若GO[Ik,A]=Ij,A為非終結(jié)符,則置GOTO[k,A]=j;(5)分析表凡不能用規(guī)則(1)-(4)填入的空白格均置為“error”。例:S(S)|a狀態(tài)序號ACTIONGOTO終結(jié)符和$非終結(jié)符0……n分析表格式82例x:已知文法G[S],求其LR(0)的分析表。

SaA|bB

AcA|d

BcB|dS

b.BB

.cBB

.d解:(1)識別文法活前綴的DFAA

d.A

c.AA

.cAA

.dS

a.AA

.cAA

.dB

c.BB

.cBB

.dS

.SS

.aAS

.bBstartS

S.A

cA.S

aA.AddAcabSS

bB.B

cB.B

d.BddBccc0123456789101183狀態(tài)actiongotoabcd$SAB01234567891011s2s3accs5s6s8s9r1r1

r1

r1

r1s5s6r4r4

r4

r4

r4r2r2

r2

r2

r2s8s9r6r6

r6

r6

r6r3r3

r3

r3

r3r5r5

r5

r5

r51

4710

11(2)LR(0)分析表(1)識別文法活前綴的DFAA

d.A

c.AA

.cAA

.dS

a.AA

.cAA

.dS

b.BB

.cBB

.dB

c.BB

.cBB

.dS

.SS

.aAS

.bBstartS

S.A

cA.S

aA.AddAcabSS

bB.B

cB.B

d.BddBccc012367891011450SS1SaA2SbB

3AcA4Ad

5BcB6Bd84例:已知文法G[E],分析i*i+i∈L(G[E])?EE+T|TTT*F|FF(E)|i出現(xiàn)問題:由該文法識別活前綴的DFA看的出來,有的有效項(xiàng)目集中存在著移進(jìn)-歸約沖突,不能用LR(0)分析方法進(jìn)行分析。解決方法:對含有沖突的項(xiàng)目集向前查看一個(gè)輸入符號,這種分析方法稱為SLR(1)分析方法。復(fù)習(xí):LR(0)文法中不能存在移進(jìn)-歸約沖突或者歸約-歸約沖突?!鲆?5解:(1)拓廣文法G的拓廣文法G[E]:(0)EE(4)TF(1)EE+T(5)F(E)(2)ET(6)Fi(3)TT*F

(2)識別文法的活前綴的DFA(3)SLR(1)分析表

(4)分析過程例:已知文法G[E],并用SLR(1)方法分析i*i+i∈L(G[E])?EE+T|TTT*F|FF(E)|iSLR(1)的分析過程與LR(0)的分析過程完全一樣,唯一不同的是分析表!E’EEE+TETTT*FTFF(E)FidEE’EEE+TTETTT*F(F(E)EE+TETTT*FTFF(E)FidI0I1I2I6FTFI3FididI5TI2FI3idI5(EE+TTT*FTFF(E)Fid+*TT*FF(E)FidI7F(E)EE+TEI8TEE+TTT*FI9FI3idI5(FTT*FI10idI4(I4*I7)F(E)+I6I11G

:(0)EE(1)EE+T(2)ET(3)TT*F(4)TF(5)F(E)(6)Fid

(2)識別文法的活前綴的DFA87若有效項(xiàng)目集中存在沖突動作:I={X.b,A.,B.}將b移進(jìn)棧將

歸約為A將

歸約為B解決方法:設(shè)當(dāng)前輸入符號為x,1.若x=b,則移進(jìn);2.若xFollow(A),則用A進(jìn)行歸約;3.若xFollow(B),則用B進(jìn)行歸約;4.其余情況報(bào)錯.要求:移進(jìn)項(xiàng)目的符號集FOLLOW(A)FOLLOW(B)=■SLR(1)分析法88對于表達(dá)式文法的例子,F(xiàn)OLLOW集如下:G

:(0)EE(4)TF(1)EE+T(5)F(E)(2)ET(6)Fid(3)TT*FI2:FOLLOW(E)∩{*}=ΦI9:FOLLOW(E)∩{*}=Φ∴可用SLR(1)方法實(shí)現(xiàn)FOLLOW集E’$E$,),+T$,),+,*F$,),+,*EE+TTT*FETTT*FI2:I9:89●SLR分析表的構(gòu)造算法輸入:一個(gè)拓廣文法G

輸出:對于G

的分析表的action子表和goto子表方法:1.構(gòu)造G

的LR(0)項(xiàng)目集規(guī)范族。2.對于狀態(tài)Ii的分析動作如下:

(a)若A.aBIi且go(Ii,a)=

Ij

action[i,a]=shiftj(b)若A.Ii,對于所有aFollow(A)

action[i,a]=reduceA,AS(c)若SS.Ii,action[i,$]=accept3.若go(Ii,A)=Ij,AVN,則goto[i,A]=j4.分析表其余位置為error90(3)SLR分析表Follow(E)={$,+,)}ACTIONGOTO+*()id$ETF0S4S51231S6ACC2R2S7R2R23R4R4R4R44S4S58235R6R6R6R66S4S5937S4S5108S6S119R1S7R1R110R3R3R3R311R5R5R5R591(4)id*id+id的LR分析過程分析棧輸入串動作(1)0(2)0id5(3)0F3(4)0T2(5)0T2*7(6)0T2*7id5(7)0T2*7F10(8)0T2(9)0E1(10)0E1+6(11)0E1+6id5(12)0E1+6F3(13)0E1+6T9(14)0E1id*id+id$*id+id$*id+id$*id+id$id+id$+id$+id$+id$+id$id$$$$$

shiftreducebyF

idreducebyTFshiftshiftreducebyFidreducebyTT*FreducebyETshiftshiftreducebyFidreducebyTFreducebyEE+Taccept92例:已知文法G[S]:S→(S)S|ε,求其SLR(1)的分析表,并判斷()()∈L(G)?(3)SLR(1)分析表(2)構(gòu)造識別文法活前綴的DFA,并判斷用何種方法進(jìn)行分析解:(1)拓廣文法(4)分析過程注意:|ε|=0,所以用S→ε進(jìn)行歸約時(shí),不用出棧,直接將S入棧即可。LR(0)分析不了的,SLR(1)有可能能分析;LR(0)能分析的,SLR(1)都能分析!■課堂練習(xí)●example例:已知文法G[S],求其SLR(1)的分析表,并判斷()()∈L(G)?

S→rD

DD,i|i(3)構(gòu)造分析表(2)識別文法活前綴的DFA解:(1)拓廣文法(4)分析過程94SLR(1)方法與LR(0)方法的區(qū)別僅在于有效項(xiàng)目集中有歸約項(xiàng)目時(shí):在LR(0)方法中,若項(xiàng)目集Ik含有A

,則在狀態(tài)k時(shí),無論面臨什么輸入符號都用“A

”進(jìn)行歸約——即假定A

產(chǎn)生式編號為j,則在分析表ACTION部分,對應(yīng)狀態(tài)k行的所有欄目都填”rj”。在SLR(1)方法中,若項(xiàng)目集Ik含有A

,則在狀態(tài)k時(shí),僅當(dāng)輸入符號為a∈FOLLOW(A)時(shí),才用”

A

”進(jìn)行歸約,這樣在分析表ACTION部分狀態(tài)k行,所有b不屬于FOLLOW(A)的欄目將空出來。若正好在b這一列有移進(jìn)項(xiàng)目不會產(chǎn)生沖突。SLR(1)方法比LR(0)優(yōu)越,它可以解決更多的沖突。95例:已知文法G[S],請判斷id:=id∈L(G)?S→id|V:=EV→idE→V|n■引例該文法的SLR[1]分析表中存在歸約-歸約沖突,該文法不能用SLR[1]分析方法進(jìn)行分析。所以要采用另一種新的方法——LR[1]分析方法對該文法進(jìn)行語法分析。4.5.4一般的LR(1)分析由于用SLR(1)方法解決動作沖突時(shí),它僅孤立地考察對于規(guī)約項(xiàng)目Aα.,只要當(dāng)前面臨輸入符號a∈FOLLOW(A)時(shí),就確定使用規(guī)則Aα進(jìn)行規(guī)約,而沒有考察符號串α所在規(guī)范句型的環(huán)境。因?yàn)槿绻麠@锏姆柎疄?δa,規(guī)約后變成$δA,當(dāng)前讀到的輸入符號是a,若文法中不存在以δAa為前綴的規(guī)范句型,那么,這種規(guī)約無效。

LR(1)分析法的思想是在分析過程中,當(dāng)試圖用某一規(guī)則Aα規(guī)約棧頂?shù)姆柎習(xí)r,不僅應(yīng)該查看棧中符號δα,還應(yīng)向前掃視一個(gè)輸入符號a,只有當(dāng)δAa的確構(gòu)成文法某一規(guī)范句型的前綴時(shí),才能用此規(guī)則進(jìn)行規(guī)約。為此,可以考慮在原來LR(0)項(xiàng)目集中增加更多的展望信息,這些展望信息有助于克服動作沖突和排除無效規(guī)約。一個(gè)LR(1)項(xiàng)目是一個(gè)二元組[Aα.β,a],其中Aα.β是一個(gè)LR(0)項(xiàng)目,每個(gè)a是終結(jié)符,稱它為展望符或搜索符。當(dāng)β≠ε時(shí),搜索符是無意義的;當(dāng)β=ε時(shí),搜索符a明確指出當(dāng)[Aα.,a]是棧頂狀態(tài)的一個(gè)LR(1)項(xiàng)目時(shí),僅在輸入符號是a時(shí)才能用Aα規(guī)約,而不是對FOLLOW(A)中的所有符號用Aα規(guī)約。99

■LR(1)分析法LR(1)項(xiàng):LR(1)項(xiàng)是由LR(0)項(xiàng)和一個(gè)先行記號組成的對,利用中括號將LR[1]項(xiàng)寫作:

[A

,a]其中A

是一個(gè)LR[0]項(xiàng),稱為“心”;而a則是一個(gè)記號(先行),稱為“向前搜索符”。a∈FOLLOW(A)。100假設(shè)有LR[1]項(xiàng)目[AX,a],其中X是任意符號(終結(jié)符或非終結(jié)符),那么X就有一個(gè)到項(xiàng)目[AX,a]的轉(zhuǎn)換。轉(zhuǎn)換函數(shù)(1)I的任何項(xiàng)目都屬于CLOSURE(I);(2)若項(xiàng)目[AB,a]屬于CLOSURE(I),B

是文法中的一條規(guī)則,b屬于

First(a),則項(xiàng)目[B,b]屬于CLOSURE(I);(3)重復(fù)(2)直到CLOSURE(I)不再增大為止。項(xiàng)目集I的閉包函數(shù)■LR(1)分析法101■LR(1)分析表的構(gòu)造(1)若項(xiàng)目[Aa

,b]屬于Ik且GO(Ik,a)=Ij,a為終結(jié)符,則置ACTION[k,a]為“sj”;(3)若項(xiàng)目[S’S,$]屬于Ik,則置ACTION[k,$]為“acc”;(4)若GO[Ik,A]=Ij,A為非終結(jié)符,則置GOTO(Ik,A)=j;(5)分析表中凡不能用規(guī)則(1)-(4)填入信息的空白欄均置為“error”。(2)若項(xiàng)目[A

,a]屬于Ik,則置ACTION[k,a]為“rj”,其中j是產(chǎn)生式的編號;102例:已知文法G[S]:S→id|V:=E V→id E→V|n求其LR(1)的分析表,并判斷id:=id∈L(G)?(3)LR(1)分析表(2)識別文法活前綴的DFA解:(1)拓廣文法(4)分析過程103解:(1)拓廣文法并對產(chǎn)生式進(jìn)行編號0:S’→S1:S→id2:S→V:=E3:V→id4:E→V5:E→n(2)識別文法活前綴的DFA[S→V.:=E,$][S→V:=.E,$][E→.V,$][E→.n,$][V→.id,$][Sid.,$][Vid.,:=][S’→.S,$][S→.id,$][S→.V:=E,$][V→.id,:=]start[S

S.,$][E→V.,$]V:=idVS[S→V:=E.,$][E→n.,$]nE01234567[V→id.,$]id8104(3)LR(1)分析表id := n $ S V E 012345678Action gotoS2 1 3 ACC R3 R1 S4 S8 S7 6 5 R2 R4 R5 R30S’→S1S→id2S→V:=E3V→id4E→V5E→n[S→V.:=E,$][S→V:=.E,$][E→.V,$][E→.n,$][V→.id,$][Sid.,$][Vid.,:=][S’→.S,$][S→.id,$][S→.V:=E,$][V→.id,:=]start[S

S.,$][E→V.,$]V:=idVS[S→V:=E.,$][E→n.

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論