語法分析-自底向上分析技術(shù)

5.1引言5.2算符優(yōu)先分析技術(shù)5.3LR(k)分析技術(shù)本章小結(jié)第五章語法分析----自底向上分析技術(shù)5.1引言

5.1.1自底向上分析技術(shù)及識(shí)別算法

5.1.2討論的前提

5.1.3基本實(shí)現(xiàn)方法第五章語法分析----自底向上分析技術(shù)5.1引言5.1.1自底向上分析技術(shù)及識(shí)別算法

基本思想是:從輸入符號(hào)串出發(fā)，在每一分析步對(duì)相應(yīng)句型中的某個(gè)簡(jiǎn)單短語進(jìn)行歸約。如果最終能歸約到識(shí)別符號(hào)，則該輸入符號(hào)串是相應(yīng)文法的句子，否則就不是。當(dāng)句型分析過程中每個(gè)分析步都對(duì)最左的簡(jiǎn)單短語進(jìn)行直接歸約時(shí)，自底向上分析技術(shù)的兩個(gè)基本問題可以更確切地?cái)⑹鰹椋喝绾握页鼍浔鞍汛司浔苯託w約為哪個(gè)非終結(jié)符號(hào)。第五章語法分析----自底向上分析技術(shù)5.1引言5.1.1自底向上分析技術(shù)及識(shí)別算法5.1.2討論的前提

識(shí)別過程是從左到右、自底向上地進(jìn)行的，一般都將采用規(guī)范歸約；除了特別指明的以外，每一步總是對(duì)句柄——最左的簡(jiǎn)單短語進(jìn)行直接歸約。第五章語法分析----自底向上分析技術(shù)5.1.3基本實(shí)現(xiàn)方法

采用自底向上分析技術(shù)時(shí)，通常以移入-歸約法為基礎(chǔ)。一般地，動(dòng)作共有4類，即移入、歸約、接受與報(bào)錯(cuò)。移入：讀入下一個(gè)輸入符號(hào)并把它下推進(jìn)棧；歸約：當(dāng)棧頂?shù)?部分)符號(hào)串形成一個(gè)句柄時(shí)，對(duì)此句柄進(jìn)行直接歸約；接受：當(dāng)識(shí)別程序發(fā)現(xiàn)棧中除了棧底標(biāo)志符號(hào)#外僅有識(shí)別符號(hào)，而輸入也已到達(dá)右端#，則接受；報(bào)錯(cuò)：當(dāng)識(shí)別程序察覺一個(gè)錯(cuò)誤，因此輸入符號(hào)串不是句子而無法繼續(xù)識(shí)別工作時(shí)，調(diào)用一個(gè)出錯(cuò)處理子程序進(jìn)行處理或停止。第五章語法分析----自底向上分析技術(shù)例5.1設(shè)有文法G[E]：E∷=E+E|E*E|(E)|i自底向上分析技術(shù)的步驟:1)找出句柄u;2)找出規(guī)則U∷=u；

3)

把u直接歸約成U。

分析技術(shù)不同,尋找句柄的方法也不同。第五章語法分析----自底向上分析技術(shù)5.2

算符優(yōu)先分析技術(shù)一、算符優(yōu)先分析技術(shù)的引進(jìn)二、算符文法三、算符優(yōu)先關(guān)系與算符優(yōu)先文法四、算符優(yōu)先文法句型的識(shí)別五、實(shí)際應(yīng)用中的算符優(yōu)先分析技術(shù)

第五章語法分析----自底向上分析技術(shù)一、算符優(yōu)先分析技術(shù)的引進(jìn)對(duì)算術(shù)表達(dá)式，運(yùn)算符完全決定了運(yùn)算次序，運(yùn)算對(duì)象完全不起作用。因此，將文法中的終結(jié)符號(hào)看作運(yùn)算符；非終結(jié)符號(hào)看作運(yùn)算對(duì)象。算符優(yōu)先分析技術(shù)：只在終結(jié)符號(hào)之間引進(jìn)優(yōu)先關(guān)系，并利用優(yōu)先關(guān)系找出句柄（最左質(zhì)短語）。第五章語法分析----自底向上分析技術(shù)5.2算符優(yōu)先分析技術(shù)一、算符優(yōu)先分析技術(shù)的引進(jìn)二、算符文法定義5.1如果文法G中沒有形如U∷=…VW…

的規(guī)則，其中U、V、W∈VN，則該文法G稱為算符文法，縮寫為OG。第五章語法分析----自底向上分析技術(shù)5.2算符優(yōu)先分析技術(shù)一、算符優(yōu)先分析技術(shù)的引進(jìn)二、算符文法三、算符優(yōu)先關(guān)系與算符優(yōu)先文法算符優(yōu)先關(guān)系算符優(yōu)先文法第五章語法分析----自底向上分析技術(shù)5.2

簡(jiǎn)單優(yōu)先分析技術(shù)5.2.1算符優(yōu)先分析技術(shù)的引進(jìn)5.2.2算符文法算符優(yōu)先關(guān)系算符優(yōu)先文法第五章語法分析----自底向上分析技術(shù)定義5.2

設(shè)文法G是一個(gè)算符文法，Tj與Ti是兩個(gè)任意的終結(jié)符號(hào)，而U,V,W∈VN，定義算符優(yōu)先關(guān)系如下：Tj=Ti當(dāng)且僅當(dāng)文法G中存在形如U∷=…TjTi…或U∷=…TjVTi…的規(guī)則；Tj＜Ti當(dāng)且僅當(dāng)文法G中存在形如U∷=…TjV…的規(guī)則，其中V=>Ti…或V=>WTi…；Tj＞Ti當(dāng)且僅當(dāng)文法G中存在形如U∷=…VTi…的規(guī)則，其中V=>…Tj或V=>…TjW。例設(shè)有文法G[Z]:Z∷=EE∷=T|E+TT∷=F|T*FF∷=(E)|i++++

i+*()i>>>+<><<>*<>><>(<<<<=)>>>5.2算符優(yōu)先分析技術(shù)一、算符優(yōu)先分析技術(shù)的引進(jìn)二、算符文法三、算符優(yōu)先關(guān)系與算符優(yōu)先文法算符優(yōu)先關(guān)系算符優(yōu)先文法第五章語法分析----自底向上分析技術(shù)定義5.5

設(shè)有算符文法G，如果在它的任意兩個(gè)終結(jié)符號(hào)之間，算符優(yōu)先關(guān)系=、＜與＞至多只有一種關(guān)系成立，則稱該文法G為算符優(yōu)先文法，縮寫為OPG。例1文法G[Z]:Z∷=EE∷=T|E+TT∷=F|T*FF∷=(E)|i例2文法G[E]：

E∷=E+E|E*E|(E)|i5.2

簡(jiǎn)單優(yōu)先分析技術(shù)5.2.1算符優(yōu)先分析技術(shù)的引進(jìn)5.2.2算符文法四、算符優(yōu)先文法句型的識(shí)別質(zhì)短語算符優(yōu)先識(shí)別算法第五章語法分析----自底向上分析技術(shù)定義5.6

設(shè)有算符文法G[Z]，(句型的)質(zhì)短語定義為這樣一個(gè)短語：它至少包含一個(gè)終結(jié)符號(hào)，且除它自身外不再包含其他質(zhì)短語。例1文法G[Z]:Z∷=EE∷=T|E+TT∷=F|T*FF∷=(E)|i

（考慮句型T+T*F+i)定理5.3

一個(gè)算符優(yōu)先文法句型[N1]T1[N2]…[Nn]Tn[Nn+1]的最左質(zhì)短語是滿足條件：Tj－1<Tj=Tj+1=…=Ti－1=Ti>Ti+1的最左子符號(hào)串[Ｎj]Tj[Nj+1]…[Ni]Ti[Ni+1]，其中的Nk(k=1,2,…，n+1)可能有也可能無。四、算符優(yōu)先文法句型的識(shí)別質(zhì)短語算符優(yōu)先識(shí)別算法例文法G[Z]:Z∷=EE∷=T|E+TT∷=F|T*FF∷=(E)|i

設(shè)有輸入符號(hào)串i+(i+i)*i，試識(shí)別它是否是文法的句子。第五章語法分析----自底向上分析技術(shù)第五章語法分析----自底向上分析技術(shù)五、實(shí)際應(yīng)用中的算符優(yōu)先分析技術(shù)

算符優(yōu)先分析技術(shù)由于它的簡(jiǎn)單直觀、所需存儲(chǔ)容量小、且速度快而被廣泛應(yīng)用于識(shí)別各類表達(dá)式，把while、do與if之類界限符也看作運(yùn)算符(稱作廣義運(yùn)算符)，給它們優(yōu)先數(shù)，則算符優(yōu)先分析技術(shù)可擴(kuò)充到整個(gè)語言的處理。對(duì)于C等實(shí)際的程序設(shè)計(jì)語言，只需對(duì)文法稍加修改便可應(yīng)用算符優(yōu)先分析技術(shù)。算符優(yōu)先分析技術(shù)是一種行之有效、廣為應(yīng)用的分析技術(shù)。五、實(shí)際應(yīng)用中的算符優(yōu)先分析技術(shù)通常實(shí)際的編譯程序應(yīng)用算符優(yōu)先分析技術(shù)實(shí)現(xiàn)表達(dá)式的編譯時(shí)，使用的棧往往不是一個(gè)，而是兩個(gè)，即運(yùn)算分量棧與運(yùn)算符棧，分別用來存放還不能生成目標(biāo)(歸約)的運(yùn)算分量(標(biāo)識(shí)符或常量之類終結(jié)符號(hào))與運(yùn)算符(其他終結(jié)符號(hào))。算法框圖如下：第五章語法分析----自底向上分析技術(shù)5.2算符優(yōu)先分析技術(shù)第五章語法分析----自底向上分析技術(shù)第五章語法分析----自底向上分析技術(shù)5.3LR(K)分析技術(shù)

5.3.1LR(K)分析技術(shù)的邏輯結(jié)構(gòu)和分析過程

5.3.2LR(0)分析技術(shù)

5.3.3SLR(1)分析技術(shù)

5.3.4LR(1)分析技術(shù)5.3.1LR(K)分析技術(shù)的邏輯結(jié)構(gòu)和分析過程一、活前綴與可歸前綴二、LR(K)分析技術(shù)的邏輯結(jié)構(gòu)三、LR(K)分析技術(shù)的分析過程5.3.1LR(K)分析技術(shù)的邏輯結(jié)構(gòu)和分析過程一、活前綴與可歸前綴

1、定義對(duì)于文法G[S],若S=>αβ,β∈Vt*,則稱α為規(guī)范前綴,又稱活前綴。若α是含句柄的活前綴，并且每個(gè)句柄是α的后綴，則α為可歸規(guī)范前綴，或可歸前綴。例:(0)S’::=S(4)B::=C(1)S::=CbBA(5)B::=Db(2)A::=Aab(6)C::=a(3)A::=ab(7)D::=a*rr5.3.1LR(K)分析技術(shù)的邏輯結(jié)構(gòu)和分析過程一、活前綴與可歸前綴

1、定義

2、可歸前綴的求法如某文法有可歸前綴xAy,A∈Vn,

若有規(guī)則：A::=u,則xu也是文法的可歸前綴。例:設(shè)有文法G[S]:(1)S::=aAc(2)A::=Abb(3)A::=br5.3.1LR(K)分析技術(shù)的邏輯結(jié)構(gòu)和分析過程二、LR(K)分析技術(shù)的邏輯結(jié)構(gòu)

1、邏輯結(jié)構(gòu)

LR(K)分析器包括：總控程序和分析表總控程序：根據(jù)不同的分析表決定下一步的處理動(dòng)作。對(duì)不同的文法，總控程序都一樣，只是分析表不同。分析表：是LR(K)分析技術(shù)的核心，是根據(jù)具體文法按某種規(guī)則構(gòu)造出來的。圖8-3LR(K)分析方法的邏輯結(jié)構(gòu)5.3.1LR(K)分析技術(shù)的邏輯結(jié)構(gòu)和分析過程二、LR(K)分析技術(shù)的邏輯結(jié)構(gòu)

1、邏輯結(jié)構(gòu)

2、分析表的組成

(1)分析動(dòng)作表：ACTION[S,y]指明當(dāng)狀態(tài)S與向前看符號(hào)串y相匹配時(shí)所應(yīng)采取的動(dòng)作。包括：移進(jìn)、歸約、接受、出錯(cuò)

(2)狀態(tài)轉(zhuǎn)換表：GOTO[S,U]指明當(dāng)狀態(tài)S與非終結(jié)符號(hào)U相匹配時(shí)所轉(zhuǎn)換到的下一狀態(tài)。

(表8-3）LR(K)分析表5.3.1LR(K)分析技術(shù)的邏輯結(jié)構(gòu)和分析過程三、LR(K)分析技術(shù)的分析過程

分析步驟:

(1)將初始狀態(tài)S0與#壓進(jìn)分析棧.(2)根據(jù)棧頂狀態(tài)和當(dāng)前輸入符號(hào)查動(dòng)作表進(jìn)行以下工作:

a.移進(jìn):當(dāng)前輸入符號(hào)進(jìn)符號(hào)棧,新的狀態(tài)進(jìn)狀態(tài)棧,繼續(xù)掃描.

b.歸約:按某規(guī)則歸約,若規(guī)則的右部長(zhǎng)度n,則符號(hào)棧頂和狀態(tài)棧頂n個(gè)元素同時(shí)退棧.把歸約后的左部符號(hào)進(jìn)符號(hào)棧,查狀態(tài)轉(zhuǎn)換表,新的狀態(tài)進(jìn)狀態(tài)棧.

c.接受:

分析成功,結(jié)束.

d.出錯(cuò):

報(bào)告出錯(cuò)信息.(3)重復(fù)(2),直到接受或出錯(cuò)為止.5.3.1LR(K)分析技術(shù)的邏輯結(jié)構(gòu)和分析過程三、LR(K)分析技術(shù)的分析過程

分析步驟:

(1)將初始狀態(tài)S0與#壓進(jìn)分析棧.(2)根據(jù)棧頂狀態(tài)和當(dāng)前輸入符號(hào)查動(dòng)作表進(jìn)行以下工作:

a.移進(jìn):當(dāng)前輸入符號(hào)進(jìn)符號(hào)棧,新的狀態(tài)進(jìn)狀態(tài)棧,繼續(xù)掃描.

b.歸約:按某規(guī)則歸約,若規(guī)則的右部長(zhǎng)度n,則符號(hào)棧頂和狀態(tài)棧頂n個(gè)元素同時(shí)退棧.把歸約后的左部符號(hào)進(jìn)符號(hào)棧,查狀態(tài)轉(zhuǎn)換表,新的狀態(tài)進(jìn)狀態(tài)棧.

c.接受:

分析成功,結(jié)束.

d.出錯(cuò):

報(bào)告出錯(cuò)信息.(3)重復(fù)(2),直到接受或出錯(cuò)為止.例:設(shè)有文法G[L]:(1)L::=E,L(2)L::=E(3)E::=a(4)E::=b分析輸入串#a,b,a#5.3.2LR(0)分析技術(shù)

一、基本概念二、項(xiàng)集規(guī)范族和特征有窮狀態(tài)機(jī)三、LR(0)分析表的構(gòu)造四、應(yīng)用舉例5.3.2LR(0)分析技術(shù)一、基本概念(1)LR(0)項(xiàng)

定義5.14

如果Ｕ∷=uv是文法G的一個(gè)規(guī)則，其中u或v可為空串，則U→u.v稱為G的一個(gè)LR(0)項(xiàng)，簡(jiǎn)稱項(xiàng)。

完備項(xiàng)：圓點(diǎn)在整個(gè)右部之后的LR(0)項(xiàng)稱為完備項(xiàng)。

接受項(xiàng)：如果一個(gè)完備項(xiàng)呈Z→u.形，Z是識(shí)別符號(hào)。

歸約項(xiàng)：其余所有的完備項(xiàng)稱歸約項(xiàng)。

不完備項(xiàng)：不是完備項(xiàng)的項(xiàng)。

移入項(xiàng)：圓點(diǎn)之后是終結(jié)符號(hào)的不完備項(xiàng)。

待約項(xiàng)：圓點(diǎn)之后是非終結(jié)符號(hào)的不完備項(xiàng)。

5.3.2LR(0)分析技術(shù)一、基本概念

(1)LR(0)項(xiàng)

(2)初始項(xiàng)

定義5.15

文法G［Z］的LR(0)項(xiàng)Z→.u稱為G的初始LR(0)項(xiàng)，簡(jiǎn)稱初始項(xiàng)。

5.3.2LR(0)分析技術(shù)一、基本概念

(1)LR(0)項(xiàng)

(2)初始項(xiàng)定義5.20文法G［Z］的LR(0)項(xiàng)Z→.u稱為G的初始LR(0)項(xiàng)，簡(jiǎn)稱初始項(xiàng)。

(3)后繼項(xiàng)定義5.16設(shè)Ｕ→u.Av是文法G的一個(gè)LR(0)項(xiàng)，其中A∈VN∪VT，則LR(0)項(xiàng)Ｕ→uA.v稱為它的后繼項(xiàng)。

5.3.2LR(0)分析技術(shù)一、基本概念

(4)項(xiàng)集

定義5.17由LR(0)項(xiàng)組成的集合稱LR(0)項(xiàng)集，簡(jiǎn)稱項(xiàng)集。

后繼項(xiàng)集:

如果識(shí)別程序所處狀態(tài)所對(duì)應(yīng)的項(xiàng)集中有一個(gè)項(xiàng)，其中圓點(diǎn)后面是符號(hào)X，則識(shí)別程序在該符號(hào)X下將進(jìn)入所處狀態(tài)的X_后繼狀態(tài)。相應(yīng)的項(xiàng)集稱X_后繼項(xiàng)集。每個(gè)項(xiàng)集Si的后繼項(xiàng)集S通常是基本項(xiàng)集的閉包集合，基本項(xiàng)集可直接由項(xiàng)集Si生成，即｛Ｕ→uA.v|Ｕ→u.Av∈Si｝

5.3.2LR(0)分析技術(shù)一、基本概念

(5)項(xiàng)集的閉包

定義5.18設(shè)Si是文法G的一個(gè)項(xiàng)集，項(xiàng)集Si的閉包CLOSURE(Si)是按下列步驟構(gòu)造而得的項(xiàng)集。

步驟1Si中每個(gè)項(xiàng)在CLOSURE(Si)中；

步驟2

如果Ｕ→u.Vv∈CLOSURE(Si)，且V∷=w是一個(gè)規(guī)則，則把V→.w添入CLOSURE(Si)中；

步驟3

重復(fù)步驟2，直到CLOSURE(Si)不再擴(kuò)大。這時(shí)所得的便是項(xiàng)集Si的閉包CLOSURE(Si)。

5.3.2LR(0)分析技術(shù)一、基本概念二、項(xiàng)集規(guī)范族和特征有窮狀態(tài)機(jī)

一個(gè)文法G［Z］的LR(0)項(xiàng)集規(guī)范族的構(gòu)造步驟：

步驟1初始項(xiàng)集S0=CLOSURE(｛Z′→.Z｝)是G

的LR(0)項(xiàng)集，這里Z′是包含有規(guī)則

Z′∷=Z的增廣文法之識(shí)別符號(hào)；步驟2如果Si是G的項(xiàng)集，則Si的一切后繼項(xiàng)集均是G的項(xiàng)集；步驟3重復(fù)步驟2，直到再無新的項(xiàng)集可以添入。

5.3.2LR(0)分析技術(shù)一、基本概念二、項(xiàng)集規(guī)范族和特征有窮狀態(tài)機(jī)一個(gè)文法G［Z］的LR(0)項(xiàng)集規(guī)范族的構(gòu)造步驟：

步驟1初始項(xiàng)集S0=CLOSURE(｛Z′→.Z｝)是G的LR(0)項(xiàng)集，這里Z′是包含有規(guī)則Z′∷=Z的增廣文法之識(shí)別符號(hào)；步驟2如果Si是G的項(xiàng)集，則Si的一切后繼項(xiàng)集均是G的項(xiàng)集；步驟3重復(fù)步驟2，直到再無新的項(xiàng)集可以添入。

特別說明:

某一項(xiàng)集中,不同的項(xiàng),其后繼符號(hào)相同時(shí),后繼項(xiàng)集相同。

不同的項(xiàng)集中,若干個(gè)與前面對(duì)應(yīng)相同的項(xiàng),其后繼項(xiàng)集與前面的相同。例：設(shè)有文法G[S]：(1)S::=A(4)A::=c(2)S::=B(5)B::=aBb(3)A::=aAb(6)B::=d5.3.2LR(0)分析技術(shù)一、基本概念二、項(xiàng)集規(guī)范族和特征有窮狀態(tài)機(jī)一個(gè)文法G［Z］的LR(0)項(xiàng)集規(guī)范族的構(gòu)造步驟：

步驟1初始項(xiàng)集S0=CLOSURE(｛Z′→.Z｝)是G的LR(0)項(xiàng)集，這里Z′是包含有規(guī)則Z′∷=Z的增廣文法之識(shí)別符號(hào)；步驟2如果Si是G的項(xiàng)集，則Si的一切后繼項(xiàng)集均是G的項(xiàng)集；步驟3重復(fù)步驟2，直到再無新的項(xiàng)集可以添入。

特別說明:

某一項(xiàng)集中,不同的項(xiàng),其后繼符號(hào)相同時(shí),后繼項(xiàng)集相同。

不同的項(xiàng)集中,若干個(gè)與前面對(duì)應(yīng)相同的項(xiàng),其后繼項(xiàng)集與前面的相同。例：增廣文法G[S’]：(0)S’=S(1)S::=A(4)A::=c(2)S::=B(5)B::=aBb(3)A::=aAb(6)B::=d圖8-55.3.2LR(0)分析技術(shù)一、基本概念二、項(xiàng)集規(guī)范族和特征有窮狀態(tài)機(jī)文法的LR(0)項(xiàng)集規(guī)范族可以被抽象成一個(gè)有窮狀態(tài)機(jī)(FSM)，其步驟如下:步驟1

把各個(gè)項(xiàng)集定義為該FSM的內(nèi)部狀態(tài)，并用項(xiàng)集的編號(hào)來命名各個(gè)狀態(tài)，因此，每一個(gè)項(xiàng)集在FSM中有一個(gè)對(duì)應(yīng)狀態(tài)；步驟2

讓該FSM狀態(tài)之間的轉(zhuǎn)換對(duì)應(yīng)于后繼關(guān)系。步驟3

與初始項(xiàng)集對(duì)應(yīng)的狀態(tài)作為該FSM的初始狀態(tài)，與#歸約_后繼項(xiàng)集對(duì)應(yīng)的狀態(tài)作為該FSM的終止?fàn)顟B(tài)。這種有窮狀態(tài)機(jī)FSM稱為文法的特征有窮狀態(tài)機(jī)

(CFSM)。

5.3.2LR(0)分析技術(shù)一、基本概念二、項(xiàng)集規(guī)范族和特征有窮狀態(tài)機(jī)

如果項(xiàng)集中包含的全是完備項(xiàng)，則稱相應(yīng)狀態(tài)為歸約狀態(tài)；如果項(xiàng)集中包含的全是不完備項(xiàng)，則稱相應(yīng)的狀態(tài)為讀狀態(tài)；如果項(xiàng)集中既有完備項(xiàng)，又有不完備項(xiàng)，則稱相應(yīng)的狀態(tài)為不適定狀態(tài)。定義5.19一個(gè)上下文無關(guān)文法G是LR(0)文法，當(dāng)且僅當(dāng)該文法G的CFSM中無不適定狀態(tài)。5.3.2LR(0)分析技術(shù)

三、LR(0)分析表的構(gòu)造

(i)如果移入項(xiàng)Ｕ→u.av∈Si,且GO(Si,a)=Sj，其中a∈Vt，則置ACTION[Si,a]=‘把狀態(tài)j及符號(hào)a移入(下推)進(jìn)?！?，簡(jiǎn)記作‘Sj’。

(ii)如果歸約項(xiàng)Ｕ→u.∈Si，且Ｕ∷=u是增廣文法G′的第j個(gè)規(guī)則，則對(duì)任何輸入符號(hào)a,a∈Vt，置ACTION[Si,a]=‘按第j個(gè)規(guī)則Ｕ∷=u進(jìn)行直接歸約’，簡(jiǎn)記作‘rj’。

(iii)如果項(xiàng)Z′→Z.∈Si，置ACTION[Si,#]為‘接受’，簡(jiǎn)記作‘a(chǎn)cc’。

(iv)如果GO(Si,Ｕ)=Sj,Ｕ∈Vn，則置GOTO[Si,U]=j。

(v)凡不能由上述4個(gè)規(guī)則確定的分析表元素全置為報(bào)錯(cuò)標(biāo)志(空白)。

表8-5例：增廣文法G[S’]：(0)S’=S(1)S::=A(4)A::=c(2)S::=B(5)B::=aBb(3)A::=aAb(6)B::=d5.3.2LR(0)分析技術(shù)四、

應(yīng)用舉例例：設(shè)有文法G[S]:(1)S::=A(4)A::=c

(0)S’::=S(2)S::=B(5)B::=aBb(3)A::=aAb(6)B::=d

構(gòu)造項(xiàng)集規(guī)范族和LR(0)分析表，并對(duì)輸入串

#aacbb#進(jìn)行分析。

5.3.3SLR(1)分析技術(shù)

一、問題的提出二、簡(jiǎn)單向前看1集合三、SLR(1)文法四、SLR(1)分析表的構(gòu)造五、應(yīng)用舉例5.3.3SLR(1)分析技術(shù)一、問題的提出例：設(shè)有文法G[S]：(0)S::=E(1)E::=E+T(4)T::=F(2)E::=T(5)F::=(E)(3)T::=T*F(6)F::=i5.3.3SLR(1)分析技術(shù)

一、問題的提出

例：設(shè)有文法G[S]：(0)S::=E(1)E::=E+T(4)T::=F(2)E::=T(5)F::=(E)(3)T::=T*F(6)F::=iS2：{E→T.歸約項(xiàng)

T→T.*F}移入項(xiàng)

S9:{E→E+T.歸約項(xiàng)

T→T.*F}移入項(xiàng)

S2和S9均為不適定狀態(tài),文法G[S]不是LR(0)文法。5.3.3SLR(1)分析技術(shù)二、簡(jiǎn)單向前看1集合

定義5.20

一個(gè)簡(jiǎn)單向前看1集合是某些文法符號(hào)組成的集合，它和CFSM中一個(gè)不適定狀態(tài)的各個(gè)轉(zhuǎn)換相聯(lián)系。不適定狀態(tài)的轉(zhuǎn)換有兩類:

一類是文法符號(hào)X下的轉(zhuǎn)換(稱X_轉(zhuǎn)換)，簡(jiǎn)單向前看1集合便是｛X｝，另一類是#Ｕ∷=u轉(zhuǎn)換，簡(jiǎn)單向前看1集合是FT1(Ｕ)：FT1(Ｕ)=FOLLOW(Ｕ)

例：文法G[S]的CFSM的狀態(tài)S2是不適定狀態(tài)，對(duì)于它的簡(jiǎn)單向前看1集合，存在兩類轉(zhuǎn)換：*_轉(zhuǎn)換簡(jiǎn)單向前看1集合是｛*｝

#E∷=T轉(zhuǎn)換簡(jiǎn)單向前看1集合是FT1(E)FT1(E)=FOLLOW(E)=｛+,)，#｝5.3.3SLR(1)分析技術(shù)

三、SLR(1)文法

定義5.21一個(gè)上下文無關(guān)文法G是SLR(1)文法，當(dāng)且僅當(dāng)與其CFSM每個(gè)不適定狀態(tài)的各個(gè)T_轉(zhuǎn)換與#Ｕ∷=u轉(zhuǎn)換相聯(lián)系的簡(jiǎn)單向前看1集合互不相交。

5.3.3SLR(1)分析技術(shù)

四、SLR(1)分析表的構(gòu)造

分析表中的ACTION部分與GOTO部分可按下述規(guī)則構(gòu)造如下:(i)如果移入項(xiàng)Ｕ→u.av∈Si,且GO(Si,a)=Sj，其中a∈Vt，則置ACTION[Si,a]=‘把狀態(tài)j及符號(hào)a移入(下推)進(jìn)?！?jiǎn)記作‘Sj’。(ii)如果歸約項(xiàng)Ｕ→u.∈Si，且Ｕ∷=u是增廣文法G′的第j個(gè)規(guī)則，則對(duì)任何輸入符號(hào)a,a∈FT1(Ｕ)，置ACTION[Si,a]=‘按第j個(gè)規(guī)則Ｕ∷=u進(jìn)行直接歸約’，簡(jiǎn)記作‘rj’。(iii)如果項(xiàng)Z′→Z.∈Si，置ACTION[Si,#]為‘接受’，簡(jiǎn)記作‘a(chǎn)cc’。(iv)如果GO(Si,Ｕ)=Sj,Ｕ∈VN，則置GOTO［Si,Ｕ］=j。(v)凡不能由上述4個(gè)規(guī)則確定的分析表元素全置為報(bào)錯(cuò)標(biāo)志(空白)。

5.3.3SLR(1)分析技術(shù)五、應(yīng)用舉例

例：設(shè)有文法G[S]：(0)S::=E(1)E::=E+T(4)T::=F(2)E::=T(5)F::=(E)(3)T::=T*F(6)F::=i

對(duì)輸入串＃i+i*i#進(jìn)行分析。

*5.3.4LR(1)分析技術(shù)

一、問題的提出例:設(shè)有文法Ｇ[S’]:

(0)S’::=S(4)B::=C

(1)S::=CbBA(5)B::=Db

(2)A::=Aab(6)C::=a

(3)A::=ab(7)D::=a

其項(xiàng)集規(guī)范族如下圖所示:5.3.4LR(1)分析技術(shù)

一、問題的提出考察狀態(tài)S8:{C→a．,D→a．}S10:{S→CbBA．,A→A.ab}

對(duì)S10，F(xiàn)T1(S)={#}與{a}不相交,

對(duì)S8,FT1(C)=Follow(C)={a,b},FT1(D)=Follow(D)=有交集,

因此該文法不能使用SLR(1)分析技術(shù).

例:設(shè)有文法Ｇ[S’]:

(0)S’::=S(4)B::=C

(1)S::=CbBA(5)B::=Db

(2)A::=Aab(6)C::=a

(3)A::=ab(7)D::=a5.3.4LR(1)分析技術(shù)

二、幾個(gè)基本概念

1、LR(1)項(xiàng)定義：在LR(0)項(xiàng)中放一個(gè)向前搜索符號(hào)a,成為形式:[A→α.β,a],其中a∈Follow(A),稱為L(zhǎng)R(1)項(xiàng)。

2、有效項(xiàng)定義:設(shè)有文法G[S],LR(1)項(xiàng)[A→α.β,a]對(duì)活前綴Υ=δα有效,是指存在規(guī)范推導(dǎo)：S=>δAy=>δαβy,y∈Vt*,且滿足下列條件:當(dāng)y=ε,a=#

當(dāng)y≠ε,a=First(y)

考慮規(guī)范句型:Cbabab和Cbaabab*rr例:設(shè)有文法Ｇ[S’]:

(0)S’::=S(4)B::=C

(1)S::=CbBA(5)B::=Db

(2)A::=Aab(6)C::=a

(3)A::=ab(7)D::=a5.3.4LR(1)分析技術(shù)

二、幾個(gè)基本概念

3、LR(1)項(xiàng)集的閉包

定義設(shè)Si是文法G的一個(gè)LR(1)項(xiàng)集，項(xiàng)集Si的閉包CLOSURE(Si)是按下列步驟構(gòu)造而得的項(xiàng)集。

步驟1Si中每個(gè)項(xiàng)在CLOSURE(Si)中；

步驟2

如果[Ｕ→u.Vv,a]∈CLOSURE(Si)，且V∷=w是一個(gè)規(guī)則，則把[V→.w,b],添入CLOSURE(Si)中,這里b=First(va)；

步驟3

重復(fù)步驟2，直到CLOSURE(Si)不再擴(kuò)大。這時(shí)所得的便是LR(1)項(xiàng)集Si的閉包CLOSURE(Si)。

特別說明:每一個(gè)LR(1)項(xiàng)與其后繼項(xiàng)有相同的向前搜索符號(hào)