第四章文法與語法分析語法分析概述文法和文法分析進行語法分析的幾種方法1.語法分析概述語法分析器和識別器語法分析的功能語法錯誤類別語法錯誤的處理

語法分析器和識別器語法分析器的功能：語法錯誤類別程序的開始符，語句（表達式）的開始符（后繼符）錯

標識符（常量）錯：該出現時未出現

括號類錯誤：不匹配

分隔符錯：assignment;

Token/TokenListParser語法樹/語法錯誤信息

語法錯誤處理

要求：報告錯誤出現的位置修復錯誤并繼續檢查后續部分執行開銷不應太大

修改策略：插入/刪除/修改應急方式恢復:

定義同步符號集合(分隔符，end,某些語句頭符，else等)發現錯誤時，跳過一些Token，直到找到某個同步符號，再繼續進行分析。同步符號保證接下來的分析是從正確的頭位置開始。2.文法和文法分析

文法能清晰地描述程序設計語言的語法構成易于理解。文法能自動地構造有效的語法分析器，檢查源程序是否符合語言規定地語法形式。文法定義可以了解程序設計語言的結構，有利于將源程序轉化為目標代碼，以及檢查出語法錯誤。基于文法實現的語言易于擴展文法的定義文法G定義為四元組(VT,VN,S,P)VT是有限的終極符集合VN是有限的非終極符集合S是開始符，S

VNP是產生式的集合，且具有下面的形式：

，其中，(VT

VN)*文法的分類

O型文法:

也稱為短語文法，其產生式具有形式:

→

，其中

,

(VT

VN)*，并且

至少含一個非終極符

。

1型文法:

也稱為上下文有關文法。它是0型文法的特例，即要求|

|

|

|(S→

例外，但S不得出現于產生式右部)。

2型文法:

也稱為上下文無關文法。它是1型文法的特例，即要求產生式左部是一個非終極符:A→

。

3型文法:

也稱為正則文法。它是2型文法的特例，即其產生式的右部至多有兩個符號，而且具有下面形式之一:A→a，A→aB

其中A,B

VN

，a

VT

。

上下文無關文法（CFG）定義為四元組(VT,VN,S,P)VT是有限的終極符集合VN是有限的非終極符集合S是開始符，S

VNP是產生式的集合，且具有下面的形式：

AX1X2…Xn其中A

VN，Xi

(VT

VN)，右部可空。推導：如果A

是一個產生式，則有A,其中

表示一步推導(用A→)。這時稱

是由

A直接推導的。的含義是，使用一條規則，代替左邊的某個符號，產生右端的符號串

+

:表示

通過一步或多步可推導出

*:表示

通過0步或多步可推導出

句型：如果有S

*

，則稱符號串

為CFG的句型。我們用SF(G)表示文法G的所有句型的集合

句子：如果

只包含終極符，則稱

為CFG的句子，其中S是文法的開始符

語言：L(G)={u|S

+u,u

VT*}。文法G所定義的語言是其開始符所能推導的所有終極符號串(句子)的集合。

最左（右）推導：如果進行推導時選擇的是句型中的最左(右）非終極符，則稱這種推導為最左(右)推導，并用符號

lm（

rm）表示最左（右）推導。左（右）句型：用最左推導方式導出的句型，稱為左句型，而用最右推導方式導出的句型，稱為右句型(規范句型)。結論：每個句子都有相應的最右和最左推導（但對句型此結論不成立）語法分析樹與二義性語法分析樹(簡稱分析樹)用來描述句型的結構，是句型推導的一種樹型表示。文法G=(VN,VT,S,P)，則稱滿足下面條件的樹為G的一棵分析樹： 1.每個結點都有G的一個文法符號，并且根結點標有初始符S，非葉結點標有非終極符，葉結點標有終極符或非終極符或

。2.如果一個非葉結點A有n個兒子結點(從左到右）為

X1,X2,...,Xn，則G一定有產生式A→X1X2...Xn。線性推導：我們稱用

符號進行的推導為線性推導。樹型推導與線性推導的不同：線性推導指明了推導的順序，而樹型推導則沒有指明推導的順序。因此，句型一般只有一棵分析樹(如果無二義性)，而線性推導則可很多。二義性文法文法G=({+,*,I,(,)},{E},E,P),其中P為：EiEE+EEE*EE(E)E+EEE*Eii推導1的語法樹EE*EE+Eii推導2的語法樹句型i*i+i:推導1:EE+EE*E+Ei*E+Ei*i+Ei*i+i推導1:EE*E

i*Ei*E+Ei*i+Ei*i+iii

<Stm>→if<Exp>then<Stm>else<Stm> <Stm>→if<Exp>then<Stm> <Stm>→......假設有條件語句ife1thenife2thens1elses2則可有下圖所示的兩棵不同的語法分析樹：

if語句的二義性ififthen<Stm><Stm><Stm><Stm>elsethen<Exp><Exp>e1e2S1S2<Stm><Stm><Stm><Stm>elsethenifthenif<Exp><Exp>e1e2S1S1文法二義性的消除二義性文法的判定是遞歸不可解的消除二義性的方法：1.設置一規則，該規則可在產生二義性的情況下，指出哪一個分析樹是正確的2.將文法改變成一個強制正確分析樹的構造格式定義表達式的無二義性文法ETEE+TTFTT*FF(E)FiET|E+TTF|T*FF(E)|iIf語句的無二義性文法定義

stmtmatched_stmt|unmatched_stmtmatched_stmtifEthenmatched_stmtelsematched_stmt|otherunmatched_stmtifEthenstmt|ifEthenmatched_stmt

elseunmatched_stmt有關文法實用中的一些說明有關文法的實用限制

?

有害規則UU

?

多余規則{不可到達的，不可終止的}上下文無關文法中的

規則A

文法G[s]:SBe

BCeBAfAAeAe

CCf

CC

Df求能推出

的非終極符

S_Lambda={Aj|Aj

PSet};

對pPset：Ap

X1…Xn,如果XiS_Lambda,0in，則S_Lambda=S_Lambda{Ap}

重復第二步，直至S_Lambda收斂為止消除空產生式算法S_Lambda={Aj|Aj

+

};刪除所有的空產生式和只能導出空串的非終極符。對剩余的每個產生式P：AC1C2…Cp

如果有Ci，因為刪除了所有的空產生式，需要擴充一些產生式AC1…Ci-1Ci+1…Cp。重復上述過程直至不出現新的產生式為止。句型分析的有關問題短語：設S是文法的開始符，

是句型(即有S

*

），如果滿足條件：

S

*

A

A

+

則稱

是句型

的一個短語。

直接短語（簡單短語）：如果滿足條件：

S

*

A

A

則稱

是句型

的一個簡單短語。

句柄：一個句型可能有多個簡單短語，其中最左的簡單短語稱之為句柄。

文法G:ET|E+TTF|T*FF(E)|i(T+i)*i+F是G的一個句型。其推導過程如下：EE+TT+TT*F+TF*F+T(E)*F+T(E+T)*F+T(T+T)*F+T(T+F)*F+T(T+i)*i+F短語有8個：1.(T+i)*i+F2.(T+i)*i3.(T+i)4.T+i5.T6.第一個i7.第二個i8.F簡單短語有4個：

T,第一個i,第二個i,F句柄有1個：T一個有用的定理定義1：由某一結點及其所屬分支組成的部分樹稱為原樹的一棵子樹。定義2：只有單層分支的子樹稱為簡單子樹。定理1：1.每個句型都有一棵語法樹，每個語法樹的葉組成一句型。2.每棵子樹的葉組成短語，每棵簡單子樹的葉組成簡單短語，最左簡單子樹的葉組成句柄。3.用語法樹可證明每個句子都有一規范推導。短語有8個：1.(T+i)*i+F2.(T+i)*i3.(T+i)4.T+i5.T6.第一個i7.第二個i8.F簡單短語有4個：

T,第一個i,第二個i,F句柄有1個：TEE+TTT*FiF(E)E+TTiFF文法G:ET|E+TTF|T*FF(E)|ii(1)*i(2)+i(3)是G的一個句子，（1）畫出該句子的語法分析樹（2）給出該句子的最左推導和最右推導（3）找出該句子的所有短語，簡單短語，句柄First集的定義設G=(VT，VN，S，P)是上下文無關文法First(

)

={a

VT|

*a......}

(if

*

then{

}else

)

可以根據當前的輸入符號是屬于哪個產生式右部的首符集而決定選擇相應產生式進行推導。

文法G3[S]:SaA|dAbAS|輸入串W=abd。自頂向下的推導過程為:S

aA

abAS

abS

abd相應的語法樹為：SaAbAS

dFollow集的定義設G=(VT，VN，S，P)是上下文無關文法，AVN，S是開始符號Follow(A)={a

VT|S

+....Aa.....}

(ifS

*......Athen{#}else

)當文法中存在形如：A,A的產生式，并且

，

不同時推出時，如果滿足

First()(First()Follow(A))=時，對于非終極符A的替換仍可唯一的確定候選產生式。三個集合的定義

First(

)

={a

VT|

*a......}

(if

*

then{

}else

)

Follow(A) ={a

VT|S

+....Aa.....}

(ifS

*......Athen{#}else

)

Predict(A→

) =First(

)，當

First(

) =First(

)-{

}

Follow(A)，當

First(

)

三個集合的定義

First(

)

={a

VT|

*a......}

(if

*

then{

}else

)

Follow(A) ={a

VT|S

+....Aa.....}

(ifS

*......Athen{#}else

)

Predict(A→

) =First(

)，當

First(

) =First(

)-{

}

Follow(A)，當

First(

)

計算First(X)集對每一文法符號X計算First(X)若XVT,First(X)={X}若XVN則

First(X)={a|Xa…PSet,aVT}若XVN,且有產生式X,則{}First(X)若XVN,有產生式XY1Y2…Yn

，且Y1,Y2,…,YiVN

當Y1,Y2,…,Yi-1*，則First(Y1)-{},First(Y2)-{},…First(Yi-1)-{},First(Yi)都包含在First(X)中。當Yi*(i=1,2,…n),將{}并入First(X)

中。計算First(

)集若符號串

=X1X2…Xn，當X1,X2,…Xi-1*，Xi不能

*，則First()=1i-1(First(Xj)-{})First(Xi)若所有Xi都能*，則First()=1nFirst(Xj)計算Follow集1:

對所有A

VN，令Follow(A):={}；對開始符

S,令Follow(S):={#}；

2:

若有產生式A→xBy，如果

First(y)則：

Follow(B):=(First(y)－{

})

Follow(A)

否則

Follow(B):=First(y)

3:重復2和3，直至對所有A

VN，Follow(A)收斂為止。計算Predict集Predict(A→

)=First(

)，當First(

)不含

=First(

)-{

}

Follow(A)，當First(

)含

ETE’E’+TE’|TFT’T’

*FT’|Fid|(E)

Predict(ETE’)=first(TE’)={id,(}Predict(E’+TE’)=first(+TE’)={+}Predict(E’)=follow(E’)={),#}Predict(TFT’)=first(FT’)={id,(}Predict(T’*FT’)=first(*FT’)={*}Predict(T’)=follow(T’)={+,),#}Predict(Fid)=first(id)={id}Predict(F(E))=first((E))={(}語法分析方法的分類

自頂向下分析方法

遞歸子程序法

LL分析方法

自底向上分析方法

優先關系法

LR分析方法自頂向下分析概述

從文法開始符出發試圖推導出所給的終極符串。例G[z]:[1]ZaBd[2]Bd[3]Bc[4]BbB

對給定的終極符串abcd，推導過程：

Z

[1]aBd[4]abBd[3]abcd

aBd#abcd# MatchBd#bcd# DerivationbBd#bcd# MatchBd#cd# Derivationcd#cd# Matchd#d# Match##Success自頂向下的語法分析過程【Sf,Rest,Action(D/M/S/E)】

Z#abcd#Derivation自底向上分析概述

從終極符串出發歸約（reduce）出文法的開始符。例G[z]:[1]ZaBd[2]Bd[3]Bc[4]BbB

對給定的終極符串abcd，歸約過程：abcd

[3]abBd

[4]aBd

[3]

Z

#abcd#Shift#abcd#Shift#abcd#Reduce[3]#abBd#Reduce[4]#aBd#Shift#aBd#Reduce[1]#Z#Success自底向上的語法分析過程【AnalysisST,Input,Action(S/R/E/S)】#abcd#Shift文法G1[S]:SpA|qBAcAd|a輸入串W=pccadd。自頂向下的推導過程為:S

pA

pcAd

pccAdd

pccadd相應的語法樹為：pAcAdcAdaS文法G2[s]:SAp|BqAa|cABb|dB輸入串W=ccap。自頂向下的推導過程為:S

Ap

cAp

ccAp

ccap相應的語法樹為：SApcAcAa自頂向下分析——遞歸下降法遞歸下降法(Recursive-DescentParsing)對每個非終極符按其產生式結構產生相應語法分析子程序. 終極符產生匹配命令非終極符則產生調用命令文法遞歸相應子程序也遞歸，所以稱這種方法為遞歸子程序方法或遞歸下降法。例：Stm→while

Exp

do

Stm

則對應產生式右部的語法分析程序部分如下：begin

Match($while)；

Exp；

Match($do)；

Stm

endwhile

x>y

do

ifx>zthenx:=x+yelsex:=y

BeginMatch($while);Exp;Match($do);StmEnd

當產生式中形如:A

1|2|…|n

則按下面的方法編寫子程序A：

procedureA()beginiftokenPredict(A1)then(1)elseiftokenPredict(A2)then(2)else……iftokenPredict(An)then

(

n)elseerr()end

其中對

i=X1X2…Xn，(

i)=’(X1);’(X2);…;’(Xn);如果XVN，’(X)=X

如果XVT，’(X)=Match(X)

如果X=,(

)=skip(空語句)假設有文法

Z→

aBa B→

bB|

c則相應的遞歸子程序可如下：procedureZ()begin

iftoken=athen

Match(a)；B；

Match(a)

else

err()end;procedureB()begin

iftoken=bthen

Match(b);B;

else

iftoken=c

then

Match(c);

else

err()end;主程序：BeginReadToken;

Z

endReadTokenReadToken遞歸子程序方法的條件：(1)predict(A→

k)

predict(A→

j)=

，當k

j

(2)任一非終極符A都不是左遞歸的。產生式A→

被選擇的條件是：當前的輸入符屬于predict(A→)。至多一個產生式被選擇的條件是：predict(A→

k)

predict(A→

j)=

，當k

j文法的等價變換某個非終極符A有如下的兩個產生式：A→

，A→

(即有左公共前綴)某個非終極符A有直接左遞歸產生式：A→A

|......消除左公共前綴消除左遞歸消除公共前綴變換步驟：產生式形如：A

1|2|…|n|

表示不以

開頭的字符串。2.引進非終極符A’，使產生式替換為：AA

|

A

1|2|…|nStm→id:=ExpStm→id(ExpL)ExpL→Exp

ExpL→Exp,ExpL

Stm→idStm

Stm

→:=Exp

Stm

→(ExpL)

ExpL→Exp

ExpL

ExpL

→,ExpExpL

ExpL

→

消除公共前綴的例子消除公共前綴的例子2AadABcBaABbBAadAaAcAbBcBaABbBAa(d|Ac)AbBcBaABbBAaA

A

dA

AcAbBcBaABbB替換

提因子

引進A’

左遞歸一個文法含有下列形式的產生式時（1）AAAVN,V*（2）ABBAA,BVN,,V*其中（1）為直接左遞歸，（2）為間接左遞歸，因此文法中只要有A

+A…，則稱文法為左遞歸的。消除左遞歸

對直接左遞歸形如：

A

A|

消除左遞歸為：

AA

A

A

|

消除左遞歸間接左遞歸形如：

AB|BA|b

消除左遞歸：轉為直接左遞歸形式：

AA|b|或者BB||b

按照直接左遞歸方式消除。去掉多余的產生式例：[1]A→B1|a[2]B→C2|b[3]C→A3|cA

B

1

C

2

1

A

3

2

1

[3]

C→(B

1|a)

3|c

[3]

C→C

2

1

3|b

1

3|a

3|c

[4]C→(b

1

3|a

3|c)C

[5]C

→

2

1

3C

|

[1],[2],[4],[5]與原文法等價LL分析方法—自頂向下分析LL(1)是LL(k)的特例,其中的k則表示向前看k個符號。LL(1)方法和遞歸下降法屬于同一級別的自頂向下分析法，但有一些區別.

遞歸下降法對每個非終極符產生子程序，而LL(1)方法則產生LL分析表；遞歸下降法能判斷每個產生式的結束，而LL(1)方法則不能；遞歸下降法分析法不用符號棧，而LL(1)方法則用符號棧。LL(1)分析方法的條件對于任一非終極符A，其任意兩個產生式A→

和A→

，都要滿足下面條件：

Predict(A→

)

Predict(A→

)=

滿足這一條件的文法稱為LL(1)文法。

LL(1)分析例文法G[A]:AaBc[1]Bd[2]|bB[3]輸入串：abbdc分析過程：(A,abbdc)1(cBa,abbdc)(cB,bbdc)3(cBb,bbdc)(cB,bdc)3(cBb,bdc)(cB,dc)2(cd,dc)(c,c)(,)LL(1)分析的動作替換：當X1VN時選相應候選式去替換X1。匹配：當X1VT時它與Y1進行匹配，其結果可能成功，也可能失敗，如果成功則去掉X1和Y1，否則報錯。接受：當格局為（空，空）時報分析成功。報錯：出錯后，停止分析。LL(1)分析表T：VN

VT→P

{Error} T(A,t)=A→

若t

Predict(A→

) T(A,t)=Error否則其中P表示所有產生式的集合LL(1)分析的驅動器StackInputa

棧為空情形的處理

X

VT情形的處理

X

VN情形的處理

XLL[1]分析表LL_Driver [1] 初始化：Stack:=empty；Push(S)； [2] 讀下一個輸入符：Read(a)； [3]若當前格局是(empty,#)，則成功結束；否則轉下； [4]設當前格局為（.....X,a.....)，則

若X

VT&X=a則{Pop(1)；Read(a)；goto[3]}

若X

VT&X

a則Error；

若X

VN，則：

ifT(X,a)=X→Y1Y2Yn

then{Pop(1)；Push(Yn,.....,Y1)；goto[3]}elseErrorLL分析實例文法G:

ETE’[1]E’+TE’[2]|[3]TFT’[4]T’*FT’[5]|[6]Fid[7]|(E)[8]符號串i+i*i#的LL[1]分析過程：Predict([1])=first(TE’)={id,(}Predict([2])=first(+TE’)={+}Predict([3])=follow(E’)={),#}Predict([4])=first(FT’)={id,(}Predict([5])=first(*FT’)={*}Predict([6])=follow(T’)={+,),#}Predict([7])=first(id)={id}Predict([8])=first((E))={(}分析棧S輸入流T矩陣元素#Ei+i*i#LL[E,i]=[1]#E’Ti+i*i#LL[T,i]=[4]#E’T’Fi+i*i#LL[F,i]=[7]#E’T’ii+i*i#Match#E’T’+i*i#LL[T’,+]=[6]#E’+i*i#LL[E’,+]=[2]#E’T++i*i#Match#E’Ti*i#LL[T,i]=[4]#E’T’Fi*i#LL[F,i]=[7]#E’T’ii*i#Match#E’T’*i#LL[T’,*]=[5]#E’T’F**i#Match#E’T’Fi#LL[F,i]=[7]#E’T’ii#Match#E’T’#LL[T’,#]=[6]#E’#LL[E’,#]=[3]##okIf-then-else語句BL語言{[i]j|i>=j>=0}不是LL文法條件語句的產生式是無法變換成LL[1]型產生式的。自底向上分析－LR分析概述自底向上分析的思想和主要問題幾種LR分析方法：LR(0)SLR(1)LR(1)LALR(1)主要內容：LR的幾個基本概念線性正則式的狀態機LRSM短語：設S是文法的開始符，

是句型(即有S

*

），如果滿足條件：

S

*

A

A

+

則稱

是句型

的一個短語。直接短語（簡單短語）：如果滿足條件：

S

*

A

A

則稱

是句型

的一個簡單短語。句柄：一個句型可能有多個簡單短語，其中最左的簡單短語稱之為句柄。一個有用的定理定義：由某一結點及其所屬分支組成的部分樹稱為原樹的一顆子樹。只有單層分支的子樹稱為簡單子樹。定理：1.每個句型都有一顆語法樹，每個語法樹的葉組成一句型。2.每棵子樹的葉組成短語，每顆簡單子樹的葉組成簡單短語，最左簡單子樹的葉組成句柄。句型:

(T+i)*i+F

EE+TTT*FiF(E)E+TTiFF短語：1.(T+i)*i+F2.(T+i)*i3.(T+i)4.T+i5.T6.第一個i7.第二個i8.F簡單短語：

T,第一個i,第二個i,F句柄：T規范句型：用最右推導導出的句型(也稱右句型）。規范前綴：若存在規范句型

，且

是終極符串或空串，則稱

為規范前綴。規范活前綴：若規范前綴

不含句柄或含一個句柄并且具有形式

=

(

是句柄)，則稱規范前綴

為規范活前綴(簡稱活前綴）。歸約規范活前綴：若活前綴

是含句柄的活前綴，即有

=

，且

是句柄，則稱活前綴

為歸約規范活前綴（簡稱歸約活前綴）。

例：SaAcBe[1]Ab[2]AAb[3]Bd[4]輸入流：abbcde。規范推導過程為：

逆過程:(分析棧，輸入流)(-,abbcde)(a,bbcde)(ab,bcde)(aA,bcde)(aAb,cde)(aA,cde)(aAc,de)(aAcd,e)(aAcB,e)(aAcBe,-)(S,-)S

aAcBe[1]

aAcd[4]e[1]

aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]活前綴的描述性定義：形成可歸前綴之前，包括可歸前綴在內所有規范句型的前綴都稱為活前綴。活前綴為一個或若干規范句型的前綴。在規范歸約過程中的任何時刻已分析過的部分，即在分析棧（符號棧）中的符號串均為規范句型的活前綴，表明輸入串的已被分析過的部分是該文法某規范句型的一個正確部分。線性正則式狀態機－LRSM線性正則式：不含*符號的正則表達式LRSM：(LinearRegularStatesMachine)(1)從LRSM可構造出恰好接受給定所有正則式的確定自動機DA；(2)從LRSM的終止狀態可判定接受的是哪個正則式；(3)從LRSM的狀態可判定一個正則式是不是另一正則式的前綴。項目：假設

[P]是一個正則式，則我們稱形如

[P]的表示為項目，其中P是正則式編號。其中黑點可出現于任何位置上。項目集：用IS表示IS(X)

：

SubItems(IS,X)={

X

[P]|

X

[P]

IS,X

SymbSet}簡記為IS(X)

假設有線性正則項集:IS={

abd[1],

abc[2],

bc[3],de

[4],de

c[5]},

則有：IS(a)={a

bd[1],a

bc[2]}IS(b) ={b

c[3]}IS(c)={dec

[4]}線性正則式到LRSM的構造給定正則式集{

1,2,…n}：■構造初始項目集IS0={

1[1],...,

n[n]}，并給IS0標上NO(表示未處理）。■從已構造的LRSM部分圖選擇被標為NO的任一項目集ISi，并做下面動作：[1]對每個符號X

SymbSet：若ISiX非空，給ISiX標上NO，并在ISi和ISiX之間畫有向X邊:ISi

→

ISiX。[2]給ISi標上OK。■

重復上述步驟二，直至在LRSM中沒有被標記為NO的狀態（項目集）結點為止。abdcdbecd?abc[1]?abd[2]?ad[3]?bec[4]?bed[5]S0a?bc[1]a?bd[2]a?d[3]S1=S0aab?c[1]ab?d[2]S3b?ec[4]b?ed[5]S2be?c[4]be?d[5]S5abc?[1]S6abd?[2]S7ad?[3]S4bec?[4]S8bed?[5]S9正則式到LRSM的轉換例LRSM的性質展望符：Lookup(S)有效前綴集

Prefix(S)狀態Si中的項目?[P]表示

部分已被輸入，而且是Si的前綴的后綴，

表示待輸入部分。可構造接受給定正則式集合的DA嚴格前綴：某狀態中既含有定位點在尾處的項目又含有定位點不在尾處的項目，則一個正則式是另一個正則式的嚴格前綴。派生定理開始符產生式的右部是歸約活前綴。如果

A

是歸約活前綴，且A→

是產生式，則

也是歸約活前綴。任何歸約活前綴，都可按上述方式被派生。設文法開始符的產生式是：S→

1|2|…|n

RPSG={

1,…,n}

{|ARPSG,A→P}例有文法G[s]: S→aAc[1]

A→Abb[2]

A→b[3]

可歸前綴集：

aAcaAbbabLR(0)項目：若A→

是產生式，則稱A→

為LR(0)項目(簡稱項目），也寫作

[p]形式。項目集的投影：假設IS是LR(0)項目集，則稱下面IS(X)

為IS關于X的投影集：

IS(X)={A→

X

|A→

X

IS,X

(VT

VN)}.項目集的閉包：假設IS是LR(0)項目集，則稱下面CLOSURE(IS)為IS的閉包集：

CLOSURE(IS)=IS

{A→

|Y→

A

CLOSURE(IS)A→

是產生式}

兩個重要的性質歸約活前綴的性質：若

A是歸約活前綴，A→

是產生式，則

也是歸約活前綴。活前綴狀態機性質：若有

Prefix(ISi)，且A→

ISi，則

是歸約活前綴。若有

Prefix(ISi)，Y→

A

ISi，則根據性質2—(活前綴狀態機的性質），

A

是歸約活前綴。再根據派生原理，若

A→

是A的產生式，則

也是歸約活前綴。構造LRSM的思想：如果在狀態項目集ISi中有項目A→

B

，且B→

是B的產生式，則在ISi中增加項目B→

；對于ISi這個過程繼續到不可再擴充為止。

構造LR(0)活前綴狀態機LRSM的算法要點：

構造初始狀態IS0：IS0=CLOSURE({Z→

S})，并給IS0標上NO。從已構造的LRSM部分圖選擇被標為NO的任一狀態IS，并做

[1]對每個符號X

VT

VN，做下面動作：

1)令ISj=CLOSURE(IS(X))，若非空。2)若在LRSM部分圖中已有ISk與ISj有相同項目集，則令m=k；否則構造ISj的狀態點ISj，并給ISj標上NO，同時令m=j。3)在IS和ISm之間畫有向X邊：IS

ISm。

[2]給IS標上OK。重復上一步驟，直至沒有被標記為NO的狀態結點為止。x例：構造LR(0)狀態機SE＃EE+TETTidT(E)0

S→

E＃E→

E+TE→

TT→

idT→

(E)1

S→E

＃E→E

+T

5

T→id

3

E→E+

TT→

idT→

(E)

4

E→E+T

9

E→T

6

T→(

E)E→

E+TE→

TT→

idT→

(E)7

T→(E

)E→E

+T

8

T→(E)

TT(idETid)E+id((GE的LRSM+2

S→E＃

＃LRSM給出了所有的可歸活前綴LRSM中的每個狀態將對應一個飽和項目集：

（1）其中一部分是由先驅狀態分出來(稱為基本項目)；（2）一部分則是由基本項目擴展出來的(稱為擴展項目或派生項目)。派生部分項目的特點是其中的“

”出現在產生式右部的最左側。形如A→?[P]的項目稱為歸約型項目形如A→

?[P]的項目稱為移入型項目

移入－歸約沖突

歸約－歸約沖突

LRSM不能直接用于LR分析

LRSM提供的信息：（1）合法性檢查信息[A→

a

]（2）移入/歸約信息[A→

a

]；[A→

]（3）移入/歸約后的轉向狀態信息#X1X2…Xk…XtSi0Si1Si2…Sik…Sitaiai+1…an#移入動作：設Sit的ai輸入邊所指向的狀態為S*#X1X2…Xk…XtSi0Si1Si2…Sik…SitaiS*歸約動作：設按A→Xk+1Xk+2…Xt進行歸約，則首先歸約為ASik的A輸出邊所指向的狀態設為S*，則格局變為：#X1X2…XkSi0Si1Si2…SikAS*設當前格局是：#X1X2…XkSi0Si1Si2…SikA

LRSM給出了所有的可歸活前綴LRSM中的每個狀態將對應一個飽和項目集：

（1）其中一部分是由先驅狀態分出來(稱為基本項目)；（2）一部分則是由基本項目擴展出來的(稱為擴展項目或派生項目)。派生部分項目的特點是其中的“

”出現在產生式右部的最左側。形如A→?[P]的項目稱為歸約型項目形如A→

?[P]的項目稱為移入型項目移入－歸約沖突歸約－歸約沖突

LRSM不能直接用于LR分析

LRSM提供的信息：（1）合法性檢查信息[A→

a

]（2）移入/歸約信息[A→

a

]；[A→

]（3）移入/歸約后的轉向狀態信息#X1X2…Xk…XtSi0Si1Si2…Sik…Sitaiai+1…an#移入動作：設Sit的ai輸入邊所指向的狀態為S*#X1X2…Xk…XtSi0Si1Si2…Sik…SitaiS*歸約動作：設按A→Xk+1Xk+2…Xt進行歸約，則首先歸約為ASik的A輸出邊所指向的狀態設為S*，則格局變為：#X1X2…XkSi0Si1Si2…SikAS*設當前格局是：#X1X2…XkSi0Si1Si2…SikALR分析模型OutputStack#an…ai…a1LR分析驅動器gotoactionInputStXt……LR分析表Action矩陣：行代表狀態，列代表輸入符，而矩陣元素則表示相應的分析動作：

Shift/Reduce?/Accept/Error

GoTo矩陣：行代表狀態，而列則代表語法符號（非終極符，終極符），而矩陣元素則表示歸約后的轉向狀態。LR(0)投影函數

0

動作集:{Shift,Reduce1,Reduce2,...}投影函數0：StateSet→2

0(S)={Reducej|B→

S,且B→

是產生式j}∪(if(存在X→

a

S且a

VT)then{Shift})LR(0)文法如果其LRSM0的每個狀態S都有|

0(S)|=1，即

0(S)只包含一個元素，我們稱文法G是LR(0)文法。若

0(S)={Shift}，則表示S只含移入項目若

0(S)={Reducej}，則表示S只含一個[j]歸約項目。每個狀態的移入/歸約動作的確定沒有沖突，而且不依賴于輸入符號。Action表的構造Action(S)=Shift.......當

0(S)=ShiftAction(S)=Reducej...當

0(S)=Reducej （j不是拓廣產生式號）Action(S)=Accept....當

0(S)=Reducej（j是拓廣產生式號）Action(S)=Error...………當

0(S)=

Action(

)=Error.………是特別引進的錯誤狀態標記

GOTO表的構造GoTo(S,X)=S

，當LRSM0中有SS

GoTo(S,X)=

，否則XLR(0)分析例文法如下： S→E# E→E+T|T T→id|(E)#+id()ETS0S5S6S1S9S1S2S3S2S3S5S6S4S4S5S6S5S6S7S9S7S3S8S8S9GoTo表ShiftShiftAcceptShiftReduce2Reduce4ShiftShiftReduce5Reduce3ActionLR(0)驅動程序1：Push(S0)；2：Scan(a)；3：S:=TopOf(StateStack)；4：caseAction(S)of

Error

ErrorProcess；

Accept

Finish；

Shift

{Push(GoTo(S,a))；goto2}

Reducej

{Pop(JJ)；Push(GoTo(S-JJ,Lj))；goto3} endLR(0)分析實例狀態棧符號棧輸入串ActionGoto0id+id#shift505id+id#reduce4909T+id#reduce3101E+id#shift3013E+id#shift50135E+id#reduce440134E+T#reduce2101E#shift2012E#accept

id+id#LR(0)分析方法的不足LR(0)方法對文法的要求嚴格。LR(0)方法容易出現沖突狀態。一個文法例:GE:S→E#[1] E→E+T[2] E→T[3] T→T

P[4] T→P[5] P→id[6] P→(E)[7]

圖

G

E

的LRSM0+EPid#+Pid(TTid(

idE(P)

4

E→T

T→T

P7

P→id

5

E→E+

T

T→T

P

T→P

P→id

P→(E)

3

T→P

4

S→E

#

E→E+T

1S→

E#[1]

E→E+T[2]E→T[3]T→T

P[4]T→P[5]P→id[6]P→(E)[7]0T→T

P

P→id

P→(E)8

T→T*P

9

E→E+T

T→T

P

11

P→(E

)

E→E+T

12

P→(E)

10P(T

P→(

E)

E→E+T

E→T

T→T

P

T→P

P→id

P→(E)

678

S→E#

2如果某個狀態有如下項目集：{A→

,B→

,D→

d

}，則存在著歸約-歸約，歸約-移入沖突若用A→

歸約，則當前輸入符應在A的Follow集中若用B→

歸約，則當前輸入符應在B的Follow集若移入，則當前輸入符應為d。SLR(1)分析條件LRSM0中存在著狀態{A1→

1，…，An→

n，B1→

1

a1r1，…，Bn→

n

anrn}

Follow(A1)…Follow(An)

{a1,…,an}=

SLR(1)文法的定義SLR(1)文法的投影函數

1定義如下：

1：StateSet

(VT∪{#})

→2

1(S,a)={Reducej|B→

S,a

Follow(B),B→P}∪(if存在X→

a

S且a

VTthen{Shift})如果LRSM0中的每個狀態S，對任意

a

VT，使得|

1(S,a)|

1，則稱相應文法為SLR(1)文法。

SLR(1)__Action表的構造若

1(S,#)={Shift}Action(S,#)=Accept若

1(S,a)={Shift}且a

#Action(S,a)=Shift若

1(S,a)={Reducej}Action(S,a)=Reducej若

1(S,a)=

Action(S,a)=Error SLR(1)__GoTo表的構造GoTo(S,X)=S

，

當LRSM0中有SS

GoTo(S,X)=error，否則

合并的SLR(1)分析表，合并方法:

Action

(S,a)=Shifti,當Action

(S,a)=Shift且GoTo(S,a)=SiGoTo

(S,X)=Si,當GoTo(S,X)=Si

且X

VNX

圖

G

E

的LRSM0+EPid#+Pid(TTid(

idE(P)

4

E→T

T→T

P7

P→id

5

E→E+

T

T→T

P

T→P

P→id

P→(E)

3

T→P

4

S→E

#

E→E+T

1S→

E#[1]

E→E+T[2]E→T[3]T→T

P[4]T→P[5]P→id[6]P→(E)[7]0T→T

P

P→