第四章文法與語(yǔ)法分析語(yǔ)法分析概述文法和文法分析進(jìn)行語(yǔ)法分析的幾種方法1.語(yǔ)法分析概述語(yǔ)法分析器和識(shí)別器語(yǔ)法分析的功能語(yǔ)法錯(cuò)誤類別語(yǔ)法錯(cuò)誤的處理

語(yǔ)法分析器和識(shí)別器語(yǔ)法分析器的功能：語(yǔ)法錯(cuò)誤類別程序的開(kāi)始符，語(yǔ)句（表達(dá)式）的開(kāi)始符（后繼符）錯(cuò)

標(biāo)識(shí)符（常量）錯(cuò)：該出現(xiàn)時(shí)未出現(xiàn)

括號(hào)類錯(cuò)誤：不匹配

分隔符錯(cuò)：assignment;

Token/TokenListParser語(yǔ)法樹(shù)/語(yǔ)法錯(cuò)誤信息

語(yǔ)法錯(cuò)誤處理

要求：報(bào)告錯(cuò)誤出現(xiàn)的位置修復(fù)錯(cuò)誤并繼續(xù)檢查后續(xù)部分執(zhí)行開(kāi)銷不應(yīng)太大

修改策略：插入/刪除/修改應(yīng)急方式恢復(fù):

定義同步符號(hào)集合(分隔符，end,某些語(yǔ)句頭符，else等)發(fā)現(xiàn)錯(cuò)誤時(shí)，跳過(guò)一些Token，直到找到某個(gè)同步符號(hào)，再繼續(xù)進(jìn)行分析。同步符號(hào)保證接下來(lái)的分析是從正確的頭位置開(kāi)始。2.文法和文法分析

文法能清晰地描述程序設(shè)計(jì)語(yǔ)言的語(yǔ)法構(gòu)成易于理解。文法能自動(dòng)地構(gòu)造有效的語(yǔ)法分析器，檢查源程序是否符合語(yǔ)言規(guī)定地語(yǔ)法形式。文法定義可以了解程序設(shè)計(jì)語(yǔ)言的結(jié)構(gòu)，有利于將源程序轉(zhuǎn)化為目標(biāo)代碼，以及檢查出語(yǔ)法錯(cuò)誤?；谖姆▽?shí)現(xiàn)的語(yǔ)言易于擴(kuò)展文法的定義文法G定義為四元組(VT,VN,S,P)VT是有限的終極符集合VN是有限的非終極符集合S是開(kāi)始符，S

VNP是產(chǎn)生式的集合，且具有下面的形式：

，其中，(VT

VN)*文法的分類

O型文法:

也稱為短語(yǔ)文法，其產(chǎn)生式具有形式:

→

，其中

,

(VT

VN)*，并且

至少含一個(gè)非終極符

。

1型文法:

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

|

|

|(S→

例外，但S不得出現(xiàn)于產(chǎn)生式右部)。

2型文法:

也稱為上下文無(wú)關(guān)文法。它是1型文法的特例，即要求產(chǎn)生式左部是一個(gè)非終極符:A→

。

3型文法:

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

其中A,B

VN

，a

VT

。

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

VNP是產(chǎn)生式的集合，且具有下面的形式：

AX1X2…Xn其中A

VN，Xi

(VT

VN)，右部可空。推導(dǎo)：如果A

是一個(gè)產(chǎn)生式，則有A,其中

表示一步推導(dǎo)(用A→)。這時(shí)稱

是由

A直接推導(dǎo)的。的含義是，使用一條規(guī)則，代替左邊的某個(gè)符號(hào)，產(chǎn)生右端的符號(hào)串

+

:表示

通過(guò)一步或多步可推導(dǎo)出

*:表示

通過(guò)0步或多步可推導(dǎo)出

句型：如果有S

*

，則稱符號(hào)串

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

句子：如果

只包含終極符，則稱

為CFG的句子，其中S是文法的開(kāi)始符

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

+u,u

VT*}。文法G所定義的語(yǔ)言是其開(kāi)始符所能推導(dǎo)的所有終極符號(hào)串(句子)的集合。

最左（右）推導(dǎo)：如果進(jìn)行推導(dǎo)時(shí)選擇的是句型中的最左(右）非終極符，則稱這種推導(dǎo)為最左(右)推導(dǎo)，并用符號(hào)

lm（

rm）表示最左（右）推導(dǎo)。左（右）句型：用最左推導(dǎo)方式導(dǎo)出的句型，稱為左句型，而用最右推導(dǎo)方式導(dǎo)出的句型，稱為右句型(規(guī)范句型)。結(jié)論：每個(gè)句子都有相應(yīng)的最右和最左推導(dǎo)（但對(duì)句型此結(jié)論不成立）語(yǔ)法分析樹(shù)與二義性語(yǔ)法分析樹(shù)(簡(jiǎn)稱分析樹(shù))用來(lái)描述句型的結(jié)構(gòu)，是句型推導(dǎo)的一種樹(shù)型表示。文法G=(VN,VT,S,P)，則稱滿足下面條件的樹(shù)為G的一棵分析樹(shù)： 1.每個(gè)結(jié)點(diǎn)都有G的一個(gè)文法符號(hào)，并且根結(jié)點(diǎn)標(biāo)有初始符S，非葉結(jié)點(diǎn)標(biāo)有非終極符，葉結(jié)點(diǎn)標(biāo)有終極符或非終極符或

。2.如果一個(gè)非葉結(jié)點(diǎn)A有n個(gè)兒子結(jié)點(diǎn)(從左到右）為

X1,X2,...,Xn，則G一定有產(chǎn)生式A→X1X2...Xn。線性推導(dǎo)：我們稱用

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

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

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

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

stmtmatched_stmt|unmatched_stmtmatched_stmtifEthenmatched_stmtelsematched_stmt|otherunmatched_stmtifEthenstmt|ifEthenmatched_stmt

elseunmatched_stmt有關(guān)文法實(shí)用中的一些說(shuō)明有關(guān)文法的實(shí)用限制

?

有害規(guī)則UU

?

多余規(guī)則{不可到達(dá)的，不可終止的}上下文無(wú)關(guān)文法中的

規(guī)則A

文法G[s]:SBe

BCeBAfAAeAe

CCf

CC

Df求能推出

的非終極符

S_Lambda={Aj|Aj

PSet};

對(duì)pPset：Ap

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

重復(fù)第二步，直至S_Lambda收斂為止消除空產(chǎn)生式算法S_Lambda={Aj|Aj

+

};刪除所有的空產(chǎn)生式和只能導(dǎo)出空串的非終極符。對(duì)剩余的每個(gè)產(chǎn)生式P：AC1C2…Cp

如果有Ci，因?yàn)閯h除了所有的空產(chǎn)生式，需要擴(kuò)充一些產(chǎn)生式AC1…Ci-1Ci+1…Cp。重復(fù)上述過(guò)程直至不出現(xiàn)新的產(chǎn)生式為止。句型分析的有關(guān)問(wèn)題短語(yǔ)：設(shè)S是文法的開(kāi)始符，

是句型(即有S

*

），如果滿足條件：

S

*

A

A

+

則稱

是句型

的一個(gè)短語(yǔ)。

直接短語(yǔ)（簡(jiǎn)單短語(yǔ)）：如果滿足條件：

S

*

A

A

則稱

是句型

的一個(gè)簡(jiǎn)單短語(yǔ)。

句柄：一個(gè)句型可能有多個(gè)簡(jiǎn)單短語(yǔ)，其中最左的簡(jiǎn)單短語(yǔ)稱之為句柄。

文法G:ET|E+TTF|T*FF(E)|i(T+i)*i+F是G的一個(gè)句型。其推導(dǎo)過(guò)程如下：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短語(yǔ)有8個(gè)：1.(T+i)*i+F2.(T+i)*i3.(T+i)4.T+i5.T6.第一個(gè)i7.第二個(gè)i8.F簡(jiǎn)單短語(yǔ)有4個(gè)：

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

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

)

={a

VT|

*a......}

(if

*

then{

}else

)

可以根據(jù)當(dāng)前的輸入符號(hào)是屬于哪個(gè)產(chǎn)生式右部的首符集而決定選擇相應(yīng)產(chǎn)生式進(jìn)行推導(dǎo)。

文法G3[S]:SaA|dAbAS|輸入串W=abd。自頂向下的推導(dǎo)過(guò)程為:S

aA

abAS

abS

abd相應(yīng)的語(yǔ)法樹(shù)為：SaAbAS

dFollow集的定義設(shè)G=(VT，VN，S，P)是上下文無(wú)關(guān)文法，AVN，S是開(kāi)始符號(hào)Follow(A)={a

VT|S

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

(ifS

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

)當(dāng)文法中存在形如：A,A的產(chǎn)生式，并且

，

不同時(shí)推出時(shí)，如果滿足

First()(First()Follow(A))=時(shí)，對(duì)于非終極符A的替換仍可唯一的確定候選產(chǎn)生式。三個(gè)集合的定義

First(

)

={a

VT|

*a......}

(if

*

then{

}else

)

Follow(A) ={a

VT|S

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

(ifS

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

)

Predict(A→

) =First(

)，當(dāng)

First(

) =First(

)-{

}

Follow(A)，當(dāng)

First(

)

三個(gè)集合的定義

First(

)

={a

VT|

*a......}

(if

*

then{

}else

)

Follow(A) ={a

VT|S

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

(ifS

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

)

Predict(A→

) =First(

)，當(dāng)

First(

) =First(

)-{

}

Follow(A)，當(dāng)

First(

)

計(jì)算First(X)集對(duì)每一文法符號(hào)X計(jì)算First(X)若XVT,First(X)={X}若XVN則

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

，且Y1,Y2,…,YiVN

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

中。計(jì)算First(

)集若符號(hào)串

=X1X2…Xn，當(dāng)X1,X2,…Xi-1*，Xi不能

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

對(duì)所有A

VN，令Follow(A):={}；對(duì)開(kāi)始符

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

2:

若有產(chǎn)生式A→xBy，如果

First(y)則：

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

})

Follow(A)

否則

Follow(B):=First(y)

3:重復(fù)2和3，直至對(duì)所有A

VN，F(xiàn)ollow(A)收斂為止。計(jì)算Predict集Predict(A→

)=First(

)，當(dāng)First(

)不含

=First(

)-{

}

Follow(A)，當(dāng)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))={(}語(yǔ)法分析方法的分類

自頂向下分析方法

遞歸子程序法

LL分析方法

自底向上分析方法

優(yōu)先關(guān)系法

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

從文法開(kāi)始符出發(fā)試圖推導(dǎo)出所給的終極符串。例G[z]:[1]ZaBd[2]Bd[3]Bc[4]BbB

對(duì)給定的終極符串a(chǎn)bcd，推導(dǎo)過(guò)程：

Z

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

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

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

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

對(duì)給定的終極符串a(chǎn)bcd，歸約過(guò)程：abcd

[3]abBd

[4]aBd

[3]

Z

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

pA

pcAd

pccAdd

pccadd相應(yīng)的語(yǔ)法樹(shù)為：pAcAdcAdaS文法G2[s]:SAp|BqAa|cABb|dB輸入串W=ccap。自頂向下的推導(dǎo)過(guò)程為:S

Ap

cAp

ccAp

ccap相應(yīng)的語(yǔ)法樹(shù)為：SApcAcAa自頂向下分析——遞歸下降法遞歸下降法(Recursive-DescentParsing)對(duì)每個(gè)非終極符按其產(chǎn)生式結(jié)構(gòu)產(chǎn)生相應(yīng)語(yǔ)法分析子程序. 終極符產(chǎn)生匹配命令非終極符則產(chǎn)生調(diào)用命令文法遞歸相應(yīng)子程序也遞歸，所以稱這種方法為遞歸子程序方法或遞歸下降法。例：Stm→while

Exp

do

Stm

則對(duì)應(yīng)產(chǎn)生式右部的語(yǔ)法分析程序部分如下：begin

Match($while)；

Exp；

Match($do)；

Stm

endwhile

x>y

do

ifx>zthenx:=x+yelsex:=y

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

當(dāng)產(chǎn)生式中形如:A

1|2|…|n

則按下面的方法編寫(xiě)子程序A：

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

(

n)elseerr()end

其中對(duì)

i=X1X2…Xn，(

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

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

如果X=,(

)=skip(空語(yǔ)句)假設(shè)有文法

Z→

aBa B→

bB|

c則相應(yīng)的遞歸子程序可如下：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)=

，當(dāng)k

j

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

被選擇的條件是：當(dāng)前的輸入符屬于predict(A→)。至多一個(gè)產(chǎn)生式被選擇的條件是：predict(A→

k)

predict(A→

j)=

，當(dāng)k

j文法的等價(jià)變換某個(gè)非終極符A有如下的兩個(gè)產(chǎn)生式：A→

，A→

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

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

1|2|…|n|

表示不以

開(kāi)頭的字符串。2.引進(jìn)非終極符A’，使產(chǎn)生式替換為：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替換

提因子

引進(jìn)A’

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

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

對(duì)直接左遞歸形如：

A

A|

消除左遞歸為：

AA

A

A

|

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

AB|BA|b

消除左遞歸：轉(zhuǎn)為直接左遞歸形式：

AA|b|或者BB||b

按照直接左遞歸方式消除。去掉多余的產(chǎn)生式例：[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]與原文法等價(jià)LL分析方法—自頂向下分析LL(1)是LL(k)的特例,其中的k則表示向前看k個(gè)符號(hào)。LL(1)方法和遞歸下降法屬于同一級(jí)別的自頂向下分析法，但有一些區(qū)別.

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

和A→

，都要滿足下面條件：

Predict(A→

)

Predict(A→

)=

滿足這一條件的文法稱為L(zhǎng)L(1)文法。

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

VT→P

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

若t

Predict(A→

) T(A,t)=Error否則其中P表示所有產(chǎn)生式的集合LL(1)分析的驅(qū)動(dòng)器StackInputa

棧為空情形的處理

X

VT情形的處理

X

VN情形的處理

XLL[1]分析表LL_Driver [1] 初始化：Stack:=empty；Push(S)； [2] 讀下一個(gè)輸入符：Read(a)； [3]若當(dāng)前格局是(empty,#)，則成功結(jié)束；否則轉(zhuǎn)下； [4]設(shè)當(dāng)前格局為（.....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分析實(shí)例文法G:

ETE’[1]E’+TE’[2]|[3]TFT’[4]T’*FT’[5]|[6]Fid[7]|(E)[8]符號(hào)串i+i*i#的LL[1]分析過(guò)程：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語(yǔ)句BL語(yǔ)言{[i]j|i>=j>=0}不是LL文法條件語(yǔ)句的產(chǎn)生式是無(wú)法變換成LL[1]型產(chǎn)生式的。自底向上分析－LR分析概述自底向上分析的思想和主要問(wèn)題幾種LR分析方法：LR(0)SLR(1)LR(1)LALR(1)主要內(nèi)容：LR的幾個(gè)基本概念線性正則式的狀態(tài)機(jī)LRSM短語(yǔ)：設(shè)S是文法的開(kāi)始符，

是句型(即有S

*

），如果滿足條件：

S

*

A

A

+

則稱

是句型

的一個(gè)短語(yǔ)。直接短語(yǔ)（簡(jiǎn)單短語(yǔ)）：如果滿足條件：

S

*

A

A

則稱

是句型

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

(T+i)*i+F

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

T,第一個(gè)i,第二個(gè)i,F句柄：T規(guī)范句型：用最右推導(dǎo)導(dǎo)出的句型(也稱右句型）。規(guī)范前綴：若存在規(guī)范句型

，且

是終極符串或空串，則稱

為規(guī)范前綴。規(guī)范活前綴：若規(guī)范前綴

不含句柄或含一個(gè)句柄并且具有形式

=

(

是句柄)，則稱規(guī)范前綴

為規(guī)范活前綴(簡(jiǎn)稱活前綴）。歸約規(guī)范活前綴：若活前綴

是含句柄的活前綴，即有

=

，且

是句柄，則稱活前綴

為歸約規(guī)范活前綴（簡(jiǎn)稱歸約活前綴）。

例：SaAcBe[1]Ab[2]AAb[3]Bd[4]輸入流：abbcde。規(guī)范推導(dǎo)過(guò)程為：

逆過(guò)程:(分析棧，輸入流)(-,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]活前綴的描述性定義：形成可歸前綴之前，包括可歸前綴在內(nèi)所有規(guī)范句型的前綴都稱為活前綴。活前綴為一個(gè)或若干規(guī)范句型的前綴。在規(guī)范歸約過(guò)程中的任何時(shí)刻已分析過(guò)的部分，即在分析棧（符號(hào)棧）中的符號(hào)串均為規(guī)范句型的活前綴，表明輸入串的已被分析過(guò)的部分是該文法某規(guī)范句型的一個(gè)正確部分。線性正則式狀態(tài)機(jī)－LRSM線性正則式：不含*符號(hào)的正則表達(dá)式LRSM：(LinearRegularStatesMachine)(1)從LRSM可構(gòu)造出恰好接受給定所有正則式的確定自動(dòng)機(jī)DA；(2)從LRSM的終止?fàn)顟B(tài)可判定接受的是哪個(gè)正則式；(3)從LRSM的狀態(tài)可判定一個(gè)正則式是不是另一正則式的前綴。項(xiàng)目：假設(shè)

[P]是一個(gè)正則式，則我們稱形如

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

：

SubItems(IS,X)={

X

[P]|

X

[P]

IS,X

SymbSet}簡(jiǎn)記為IS(X)

假設(shè)有線性正則項(xiàng)集: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的構(gòu)造給定正則式集{

1,2,…n}：■構(gòu)造初始項(xiàng)目集IS0={

1[1],...,

n[n]}，并給IS0標(biāo)上NO(表示未處理）?！鰪囊褬?gòu)造的LRSM部分圖選擇被標(biāo)為NO的任一項(xiàng)目集ISi，并做下面動(dòng)作：[1]對(duì)每個(gè)符號(hào)X

SymbSet：若ISiX非空，給ISiX標(biāo)上NO，并在ISi和ISiX之間畫(huà)有向X邊:ISi

→

ISiX。[2]給ISi標(biāo)上OK。■

重復(fù)上述步驟二，直至在LRSM中沒(méi)有被標(biāo)記為NO的狀態(tài)（項(xiàng)目集）結(jié)點(diǎn)為止。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的轉(zhuǎn)換例LRSM的性質(zhì)展望符：Lookup(S)有效前綴集

Prefix(S)狀態(tài)Si中的項(xiàng)目?[P]表示

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

表示待輸入部分?？蓸?gòu)造接受給定正則式集合的DA嚴(yán)格前綴：某狀態(tài)中既含有定位點(diǎn)在尾處的項(xiàng)目又含有定位點(diǎn)不在尾處的項(xiàng)目，則一個(gè)正則式是另一個(gè)正則式的嚴(yán)格前綴。派生定理開(kāi)始符產(chǎn)生式的右部是歸約活前綴。如果

A

是歸約活前綴，且A→

是產(chǎn)生式，則

也是歸約活前綴。任何歸約活前綴，都可按上述方式被派生。設(shè)文法開(kāi)始符的產(chǎn)生式是：S→

1|2|…|n

RPSG={

1,…,n}

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

A→Abb[2]

A→b[3]

可歸前綴集：

aAcaAbbabLR(0)項(xiàng)目：若A→

是產(chǎn)生式，則稱A→

為L(zhǎng)R(0)項(xiàng)目(簡(jiǎn)稱項(xiàng)目），也寫(xiě)作

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

為IS關(guān)于X的投影集：

IS(X)={A→

X

|A→

X

IS,X

(VT

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

CLOSURE(IS)=IS

{A→

|Y→

A

CLOSURE(IS)A→

是產(chǎn)生式}

兩個(gè)重要的性質(zhì)歸約活前綴的性質(zhì)：若

A是歸約活前綴，A→

是產(chǎn)生式，則

也是歸約活前綴?；钋熬Y狀態(tài)機(jī)性質(zhì)：若有

Prefix(ISi)，且A→

ISi，則

是歸約活前綴。若有

Prefix(ISi)，Y→

A

ISi，則根據(jù)性質(zhì)2—(活前綴狀態(tài)機(jī)的性質(zhì)），

A

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

A→

是A的產(chǎn)生式，則

也是歸約活前綴。構(gòu)造LRSM的思想：如果在狀態(tài)項(xiàng)目集ISi中有項(xiàng)目A→

B

，且B→

是B的產(chǎn)生式，則在ISi中增加項(xiàng)目B→

；對(duì)于ISi這個(gè)過(guò)程繼續(xù)到不可再擴(kuò)充為止。

構(gòu)造LR(0)活前綴狀態(tài)機(jī)LRSM的算法要點(diǎn)：

構(gòu)造初始狀態(tài)IS0：IS0=CLOSURE({Z→

S})，并給IS0標(biāo)上NO。從已構(gòu)造的LRSM部分圖選擇被標(biāo)為NO的任一狀態(tài)IS，并做

[1]對(duì)每個(gè)符號(hào)X

VT

VN，做下面動(dòng)作：

1)令I(lǐng)Sj=CLOSURE(IS(X))，若非空。2)若在LRSM部分圖中已有ISk與ISj有相同項(xiàng)目集，則令m=k；否則構(gòu)造ISj的狀態(tài)點(diǎn)ISj，并給ISj標(biāo)上NO，同時(shí)令m=j。3)在IS和ISm之間畫(huà)有向X邊：IS

ISm。

[2]給IS標(biāo)上OK。重復(fù)上一步驟，直至沒(méi)有被標(biāo)記為NO的狀態(tài)結(jié)點(diǎn)為止。x例：構(gòu)造LR(0)狀態(tài)機(jī)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中的每個(gè)狀態(tài)將對(duì)應(yīng)一個(gè)飽和項(xiàng)目集：

（1）其中一部分是由先驅(qū)狀態(tài)分出來(lái)(稱為基本項(xiàng)目)；（2）一部分則是由基本項(xiàng)目擴(kuò)展出來(lái)的(稱為擴(kuò)展項(xiàng)目或派生項(xiàng)目)。派生部分項(xiàng)目的特點(diǎn)是其中的“

”出現(xiàn)在產(chǎn)生式右部的最左側(cè)。形如A→?[P]的項(xiàng)目稱為歸約型項(xiàng)目形如A→

?[P]的項(xiàng)目稱為移入型項(xiàng)目

移入－歸約沖突

歸約－歸約沖突

LRSM不能直接用于LR分析

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

a

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

a

]；[A→

]（3）移入/歸約后的轉(zhuǎn)向狀態(tài)信息#X1X2…Xk…XtSi0Si1Si2…Sik…Sitaiai+1…an#移入動(dòng)作：設(shè)Sit的ai輸入邊所指向的狀態(tài)為S*#X1X2…Xk…XtSi0Si1Si2…Sik…SitaiS*歸約動(dòng)作：設(shè)按A→Xk+1Xk+2…Xt進(jìn)行歸約，則首先歸約為ASik的A輸出邊所指向的狀態(tài)設(shè)為S*，則格局變?yōu)椋?X1X2…XkSi0Si1Si2…SikAS*設(shè)當(dāng)前格局是：#X1X2…XkSi0Si1Si2…SikA

LRSM給出了所有的可歸活前綴LRSM中的每個(gè)狀態(tài)將對(duì)應(yīng)一個(gè)飽和項(xiàng)目集：

（1）其中一部分是由先驅(qū)狀態(tài)分出來(lái)(稱為基本項(xiàng)目)；（2）一部分則是由基本項(xiàng)目擴(kuò)展出來(lái)的(稱為擴(kuò)展項(xiàng)目或派生項(xiàng)目)。派生部分項(xiàng)目的特點(diǎn)是其中的“

”出現(xiàn)在產(chǎn)生式右部的最左側(cè)。形如A→?[P]的項(xiàng)目稱為歸約型項(xiàng)目形如A→

?[P]的項(xiàng)目稱為移入型項(xiàng)目移入－歸約沖突歸約－歸約沖突

LRSM不能直接用于LR分析

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

a

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

a

]；[A→

]（3）移入/歸約后的轉(zhuǎn)向狀態(tài)信息#X1X2…Xk…XtSi0Si1Si2…Sik…Sitaiai+1…an#移入動(dòng)作：設(shè)Sit的ai輸入邊所指向的狀態(tài)為S*#X1X2…Xk…XtSi0Si1Si2…Sik…SitaiS*歸約動(dòng)作：設(shè)按A→Xk+1Xk+2…Xt進(jìn)行歸約，則首先歸約為ASik的A輸出邊所指向的狀態(tài)設(shè)為S*，則格局變?yōu)椋?X1X2…XkSi0Si1Si2…SikAS*設(shè)當(dāng)前格局是：#X1X2…XkSi0Si1Si2…SikALR分析模型OutputStack#an…ai…a1LR分析驅(qū)動(dòng)器gotoactionInputStXt……LR分析表Action矩陣：行代表狀態(tài)，列代表輸入符，而矩陣元素則表示相應(yīng)的分析動(dòng)作：

Shift/Reduce?/Accept/Error

GoTo矩陣：行代表狀態(tài)，而列則代表語(yǔ)法符號(hào)（非終極符，終極符），而矩陣元素則表示歸約后的轉(zhuǎn)向狀態(tài)。LR(0)投影函數(shù)

0

動(dòng)作集:{Shift,Reduce1,Reduce2,...}投影函數(shù)0：StateSet→2

0(S)={Reducej|B→

S,且B→

是產(chǎn)生式j(luò)}∪(if(存在X→

a

S且a

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

0(S)|=1，即

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

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

0(S)={Reducej}，則表示S只含一個(gè)[j]歸約項(xiàng)目。每個(gè)狀態(tài)的移入/歸約動(dòng)作的確定沒(méi)有沖突，而且不依賴于輸入符號(hào)。Action表的構(gòu)造Action(S)=Shift.......當(dāng)

0(S)=ShiftAction(S)=Reducej...當(dāng)

0(S)=Reducej （j不是拓廣產(chǎn)生式號(hào)）Action(S)=Accept....當(dāng)

0(S)=Reducej（j是拓廣產(chǎn)生式號(hào)）Action(S)=Error...………當(dāng)

0(S)=

Action(

)=Error.………是特別引進(jìn)的錯(cuò)誤狀態(tài)標(biāo)記

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

，當(dāng)LRSM0中有SS

GoTo(S,X)=

，否則XLR(0)分析例文法如下： S→E# E→E+T|T T→id|(E)#+id()ETS0S5S6S1S9S1S2S3S2S3S5S6S4S4S5S6S5S6S7S9S7S3S8S8S9GoTo表ShiftShiftAcceptShiftReduce2Reduce4ShiftShiftReduce5Reduce3ActionLR(0)驅(qū)動(dòng)程序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)分析實(shí)例狀態(tài)棧符號(hào)棧輸入串ActionGoto0id+id#shift505id+id#reduce4909T+id#reduce3101E+id#shift3013E+id#shift50135E+id#reduce440134E+T#reduce2101E#shift2012E#accept

id+id#LR(0)分析方法的不足LR(0)方法對(duì)文法的要求嚴(yán)格。LR(0)方法容易出現(xiàn)沖突狀態(tài)。一個(gè)文法例: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如果某個(gè)狀態(tài)有如下項(xiàng)目集：{A→

,B→

,D→

d

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

歸約，則當(dāng)前輸入符應(yīng)在A的Follow集中若用B→

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

1，…，An→

n，B1→

1

a1r1，…，Bn→

n

anrn}

Follow(A1)…Follow(An)

{a1,…,an}=

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

1定義如下：

1：StateSet

(VT∪{#})

→2

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

S,a

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

a

S且a

VTthen{Shift})如果LRSM0中的每個(gè)狀態(tài)S，對(duì)任意

a

VT，使得|

1(S,a)|

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

SLR(1)__Action表的構(gòu)造若

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表的構(gòu)造GoTo(S,X)=S

，

當(dāng)LRSM0中有SS

GoTo(S,X)=error，否則

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

Action

(S,a)=Shifti,當(dāng)Action

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

(S,X)=Si,當(dāng)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→