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

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

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

5.1.2討論的前提

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

基本思想是:從輸入符號串出發(fā)，在每一分析步對相應(yīng)句型中的某個簡單短語進行歸約。如果最終能歸約到識別符號，則該輸入符號串是相應(yīng)文法的句子，否則就不是。當句型分析過程中每個分析步都對最左的簡單短語進行直接歸約時，自底向上分析技術(shù)的兩個基本問題可以更確切地敘述為：如何找出句柄及把此句柄直接歸約為哪個非終結(jié)符號。第五章語法分析----自底向上分析技術(shù)5.1引言5.1.1自底向上分析技術(shù)及識別算法5.1.2討論的前提

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

采用自底向上分析技術(shù)時，通常以移入-歸約法為基礎(chǔ)。一般地，動作共有4類，即移入、歸約、接受與報錯。移入：讀入下一個輸入符號并把它下推進棧；歸約：當棧頂?shù)?部分)符號串形成一個句柄時，對此句柄進行直接歸約；接受：當識別程序發(fā)現(xiàn)棧中除了棧底標志符號#外僅有識別符號，而輸入也已到達右端#，則接受；報錯：當識別程序察覺一個錯誤，因此輸入符號串不是句子而無法繼續(xù)識別工作時，調(diào)用一個出錯處理子程序進行處理或停止。第五章語法分析----自底向上分析技術(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ù)的引進二、算符文法三、算符優(yōu)先關(guān)系與算符優(yōu)先文法四、算符優(yōu)先文法句型的識別五、實際應(yīng)用中的算符優(yōu)先分析技術(shù)

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

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

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

設(shè)文法G是一個算符文法，Tj與Ti是兩個任意的終結(jié)符號，而U,V,W∈VN，定義算符優(yōu)先關(guān)系如下：Tj=Ti當且僅當文法G中存在形如U∷=…TjTi…或U∷=…TjVTi…的規(guī)則；Tj＜Ti當且僅當文法G中存在形如U∷=…TjV…的規(guī)則，其中V=>Ti…或V=>WTi…；Tj＞Ti當且僅當文法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ù)的引進二、算符文法三、算符優(yōu)先關(guān)系與算符優(yōu)先文法算符優(yōu)先關(guān)系算符優(yōu)先文法第五章語法分析----自底向上分析技術(shù)定義5.5

設(shè)有算符文法G，如果在它的任意兩個終結(jié)符號之間，算符優(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

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

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

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

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

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

算符優(yōu)先分析技術(shù)由于它的簡單直觀、所需存儲容量小、且速度快而被廣泛應(yīng)用于識別各類表達式，把while、do與if之類界限符也看作運算符(稱作廣義運算符)，給它們優(yōu)先數(shù)，則算符優(yōu)先分析技術(shù)可擴充到整個語言的處理。對于C等實際的程序設(shè)計語言，只需對文法稍加修改便可應(yīng)用算符優(yōu)先分析技術(shù)。算符優(yōu)先分析技術(shù)是一種行之有效、廣為應(yīng)用的分析技術(shù)。五、實際應(yīng)用中的算符優(yōu)先分析技術(shù)通常實際的編譯程序應(yīng)用算符優(yōu)先分析技術(shù)實現(xiàn)表達式的編譯時，使用的棧往往不是一個，而是兩個，即運算分量棧與運算符棧，分別用來存放還不能生成目標(歸約)的運算分量(標識符或常量之類終結(jié)符號)與運算符(其他終結(jié)符號)。算法框圖如下：第五章語法分析----自底向上分析技術(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、定義對于文法G[S],若S=>αβ,β∈Vt*,則稱α為規(guī)范前綴,又稱活前綴。若α是含句柄的活前綴，并且每個句柄是α的后綴，則α為可歸規(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ù)不同的分析表決定下一步的處理動作。對不同的文法，總控程序都一樣，只是分析表不同。分析表：是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)分析動作表：ACTION[S,y]指明當狀態(tài)S與向前看符號串y相匹配時所應(yīng)采取的動作。包括：移進、歸約、接受、出錯

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

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

分析步驟:

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

a.移進:當前輸入符號進符號棧,新的狀態(tài)進狀態(tài)棧,繼續(xù)掃描.

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

c.接受:

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

d.出錯:

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

分析步驟:

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

a.移進:當前輸入符號進符號棧,新的狀態(tài)進狀態(tài)棧,繼續(xù)掃描.

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

c.接受:

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

d.出錯:

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

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

定義5.14

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

完備項：圓點在整個右部之后的LR(0)項稱為完備項。

接受項：如果一個完備項呈Z→u.形，Z是識別符號。

歸約項：其余所有的完備項稱歸約項。

不完備項：不是完備項的項。

移入項：圓點之后是終結(jié)符號的不完備項。

待約項：圓點之后是非終結(jié)符號的不完備項。

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

(1)LR(0)項

(2)初始項

定義5.15

文法G［Z］的LR(0)項Z→.u稱為G的初始LR(0)項，簡稱初始項。

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

(1)LR(0)項

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

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

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

(4)項集

定義5.17由LR(0)項組成的集合稱LR(0)項集，簡稱項集。

后繼項集:

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

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

(5)項集的閉包

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

步驟1Si中每個項在CLOSURE(Si)中；

步驟2

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

步驟3

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

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

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

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

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

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

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

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

特別說明:

某一項集中,不同的項,其后繼符號相同時,后繼項集相同。

不同的項集中,若干個與前面對應(yī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ù)一、基本概念二、項集規(guī)范族和特征有窮狀態(tài)機一個文法G［Z］的LR(0)項集規(guī)范族的構(gòu)造步驟：

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

特別說明:

某一項集中,不同的項,其后繼符號相同時,后繼項集相同。

不同的項集中,若干個與前面對應(yī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ù)一、基本概念二、項集規(guī)范族和特征有窮狀態(tài)機文法的LR(0)項集規(guī)范族可以被抽象成一個有窮狀態(tài)機(FSM)，其步驟如下:步驟1

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

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

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

(CFSM)。

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

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

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

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

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

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

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

(v)凡不能由上述4個規(guī)則確定的分析表元素全置為報錯標志(空白)。

表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)造項集規(guī)范族和LR(0)分析表，并對輸入串

#aacbb#進行分析。

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

一、問題的提出二、簡單向前看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.歸約項

T→T.*F}移入項

S9:{E→E+T.歸約項

T→T.*F}移入項

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

定義5.20

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

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

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

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

三、SLR(1)文法

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

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

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

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

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

對輸入串＃i+i*i#進行分析。

*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

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

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

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

對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ù)

二、幾個基本概念

1、LR(1)項定義：在LR(0)項中放一個向前搜索符號a,成為形式:[A→α.β,a],其中a∈Follow(A),稱為LR(1)項。

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

當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ù)

二、幾個基本概念

3、LR(1)項集的閉包

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

步驟1Si中每個項在CLOSURE(Si)中；

步驟2

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

步驟3

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

特別說明:每一個LR(1)項與其后繼項有相同的向前搜索符號