自頂向下（Top-Down）語(yǔ)法分析第四講

基本思想

自頂向下預(yù)測(cè)分析

LL(1)

分析自頂向下語(yǔ)法分析

帶回溯的自頂向下分析

文法變換：消除左遞歸、提取左公因子

LL(1)

分析中的出錯(cuò)處理

LL(K)

文法的有關(guān)結(jié)論（選講）基本思想

核心問(wèn)題：識(shí)別（recognition）與解析（parsing）

對(duì)任意上下文無(wú)關(guān)文法G=(V

，T

，P，S)

和任意w

T*，是否有w

L(G)？若成立，則給出分析樹(shù)或（最左）推導(dǎo)步驟；否則，進(jìn)行報(bào)錯(cuò)處理。

兩種實(shí)現(xiàn)途徑自頂向下（top-down）分析自底向上（bottom-up）分析

語(yǔ)法分析

從文法開(kāi)始符號(hào)出發(fā)進(jìn)行推導(dǎo)；每一步推導(dǎo)都獲得文法的一個(gè)句型；直到產(chǎn)生出一個(gè)句子，恰好是所期望的終結(jié)符串每一步推導(dǎo)是對(duì)當(dāng)前句型中剩余的某個(gè)非終結(jié)符進(jìn)行擴(kuò)展，即用該非終結(jié)符的一個(gè)產(chǎn)生式的右部替換該非終結(jié)符如果不存在任何一個(gè)可以產(chǎn)生出所期望的終結(jié)符串的推導(dǎo)，則表明存在語(yǔ)法錯(cuò)誤

自頂向下分析思想基本思想

自頂向下分析舉例S（SAB）AB（AaA）

aAB（Bb）

aAb（AaA）

aaAb（AaA）

aaaAb（A

）

aaab文法G（S）:SABAaA|Bb|bB

單詞序列aaab

的一個(gè)自頂向下分析過(guò)程基本思想

兩類非確定性

在每一步推導(dǎo)中，選擇對(duì)哪一個(gè)非終結(jié)符、哪一個(gè)產(chǎn)生式都可能是非確定的

分析成功的結(jié)果：得到一個(gè)推導(dǎo)

一般方法帶回溯的自頂向下分析

舉例S（1）AB（2）

aAB（5）

aAbB（2）

aaAbB（2）

aaaAbB（3）

aaabB（回溯）……

復(fù)雜度很高失敗條件較復(fù)雜文法G（S）:（1）SAB（2）AaA（3）A

（4）Bb（5）BbB

單詞序列aaab

的一個(gè)自頂向下分析過(guò)程帶回溯的自頂向下分析

僅有產(chǎn)生式選擇是非確定的

在每一步推導(dǎo)中，總是對(duì)最左邊的非終結(jié)符進(jìn)行替換，但選擇哪一個(gè)產(chǎn)生式是非確定的分析成功的結(jié)果：得到一個(gè)最左推導(dǎo)

原理：每個(gè)合法的句子都存在至少一個(gè)起始于開(kāi)始符號(hào)的最左推導(dǎo)；一個(gè)終結(jié)符串，只要存在一個(gè)起始于開(kāi)始符號(hào)的最左推導(dǎo)，它就是一個(gè)合法的句子

從左向右掃描輸入單詞，失敗條件較簡(jiǎn)單

改進(jìn)的方法帶回溯的自頂向下分析

改進(jìn)的方法舉例S（1）AB（2）

aAB（3）

aB（回溯）

aAB（2）

aaAB（2）

aaaAB（3）

aaaB（5）

aaabB（回溯）

aaaB（4）

aaab（成功）文法G（S）:（1）SAB（2）AaA（3）A

（4）Bb（5）BbB

單詞序列aaab

的一個(gè)自頂向下分析過(guò)程帶回溯的自頂向下分析復(fù)雜度降低失敗條件簡(jiǎn)化

非終結(jié)符選擇和產(chǎn)生式選擇都是確定的在每一步推導(dǎo)中，總是對(duì)最左邊的非終結(jié)符進(jìn)行展開(kāi)，且選擇哪一個(gè)產(chǎn)生式是確定的，因此是一種無(wú)回溯的方法

從左向右掃描，可能向前查看（lookahead）

確定數(shù)目的單詞分析成功的結(jié)果：得到唯一的最左推導(dǎo)分析條件：對(duì)文法需要有一定的限制

確定的自頂向下分析自頂向下預(yù)測(cè)分析

舉例（向前查看2個(gè)單詞）S（1）AB（2）aAB（2）……

anAB（3）

anB（5）

anbB（5）……anbm-1B（4）

anbm

（成功）文法G（S）:（1）SAB（2）AaA（3）A

（4）Bb（5）BbB

單詞序列anbm（n0,m0）的預(yù)測(cè)分析過(guò)程只要向前查看2個(gè)單詞，就可預(yù)測(cè)分析L(G)中所有句子自頂向下預(yù)測(cè)分析

左遞歸帶來(lái)的問(wèn)題文法G（S）:（1）SSa（2）Sb

考慮下列文法識(shí)別ban

的分析過(guò)程S（1）Sa

（1）

Saa（1）

Saaa（1）……

San

（2）

ban但是：無(wú)論向前查看的單詞數(shù)確定為多少，都無(wú)法滿足預(yù)測(cè)分析L(G)中所有句子的需求需要向前查看n+2個(gè)單詞，才能確定這樣的推導(dǎo)序列自頂向下預(yù)測(cè)分析

要求文法不含左遞歸

例：直接左遞歸

可以通過(guò)文法變換消除左遞歸專門(mén)討論

例：間接左遞歸PPaPb……PAaAPb……自頂向下預(yù)測(cè)分析

左公因子帶來(lái)的問(wèn)題文法G（S）:SabAabBAaBb

如下文法需要向前查看3個(gè)單詞來(lái)預(yù)測(cè)分析

L(G)中的句子文法G（S）:SaAbaAcAaaA

對(duì)于如下文法無(wú)法確定需要向前查看多少個(gè)單詞來(lái)預(yù)測(cè)分析L(G)中的句子自頂向下預(yù)測(cè)分析

通常要求文法不含左公因子

可以通過(guò)文法變換消除左公因子專門(mén)討論自頂向下預(yù)測(cè)分析

應(yīng)用較普遍的自頂向下預(yù)測(cè)分析是

LL（1）分析

要求文法一定是LL（1）文法專門(mén)討論自頂向下預(yù)測(cè)分析

第一個(gè)“L”,

代表從左（Left）向右掃描單詞

第二個(gè)“L”,代表產(chǎn)生的是最左（Leftmost）推導(dǎo)

“1”代表向前查看（lookahead）一個(gè)單詞

LL（1）的含義LL（1）分析

要求文法是LL（1）的什么是LL（1）文法？先引入兩個(gè)重要概念

對(duì)文法的限制LL（1）分析

First集合

Follow集合

兩個(gè)重要概念LL（1）分析

定義

設(shè)G

=（VT，VN，P，S）是上下文無(wú)關(guān)文法對(duì)(VTVN)*，

First（）={a

*a,aVT,

(VT

VN)*,

或者

*ε時(shí)a=ε}

或者

First（）={a

lm*a,aVT,

(VT

VN)*,

或者

lm*ε時(shí)a=ε}

First

集合LL（1）分析

計(jì)算First

集合LL（1）分析對(duì)所有xVNVT{}

{vAuP,且v是u的后綴},則對(duì)xV{}，置First(x)={x}；對(duì)其它x，置First(x)=重復(fù)如下過(guò)程，直到所有First集合沒(méi)有變化為止：

(1)對(duì)于A

P，置First(A)=First(A){}.(2)對(duì)于Y1Y2…YK

{vAuP,且v是u的后綴},其中k1，YjVN

V（1jk）,若j:1ji-1(First(Yj))First(Yi),其中1ik

，則令

First(Y1Y2…YK)=

First(Yj){}

否則，若j:1jk(First(Yj)),則令

First(Y1Y2…YK)=

First(Yj).(3)若有AY1Y2…YK

P，則置First(A)=First(A)First(Y1Y2…YK).j=1ij=1k

例：計(jì)算First集合文法G（S）:（1）SAB（2）ADa（3）BcC（4）CaADC（5）DbFirst(a)={a}First(b)=First(c)={c}First()={}LL（1）分析First(S)={}First(A)={

}First(B)={}First(C)={

}First(D)={

}First(AB)={}First(Da)={}First(cC)={

}First(aADC)={

}

例：計(jì)算First集合(續(xù))文法G（S）:（1）SAB（2）ADa（3）BcC（4）CaADC（5）DbFirst(a)={a}First(b)=First(c)={c}First()={}LL（1）分析First(S)={}First(A)={}First(B)={}First(C)={}First(D)=

{,b}First(AB)={}First(Da)={}First(cC)={

}First(aADC)={

}

例：計(jì)算First集合(續(xù))文法G（S）:（1）SAB（2）ADa（3）BcC（4）CaADC（5）DbFirst(a)={a}First(b)=First(c)={c}First()={}LL（1）分析First(S)={}First(A)={}First(B)={}First(C)={}First(D)=

{,b}First(AB)={}First(Da)=

{a,b}First(cC)=

{c

}First(aADC)=

{a

}

例：計(jì)算First集合(續(xù))文法G（S）:（1）SAB（2）ADa（3）BcC（4）CaADC（5）DbFirst(a)={a}First(b)=First(c)={c}First()={}LL（1）分析First(S)={}First(A)={,a,b}First(B)=

{c}First(C)=

{a,}First(D)=

{,b}First(AB)={}First(Da)=

{a,b}First(cC)=

{c

}First(aADC)=

{a

}

例：計(jì)算First集合(續(xù))文法G（S）:（1）SAB（2）ADa（3）BcC（4）CaADC（5）DbFirst(a)={a}First(b)=First(c)={c}First()={}LL（1）分析First(S)={}First(A)={,a,b}First(B)=

{c}First(C)=

{a,}First(D)={,b}First(AB)=

{a,b,c}First(Da)=

{a,b}First(cC)={c}First(aADC)={a}

例：計(jì)算First集合(續(xù))文法G（S）:（1）SAB（2）ADa（3）BcC（4）CaADC（5）DbFirst(a)={a}First(b)=First(c)={c}First()={}LL（1）分析First(S)=

{a,b,c}First(A)={,a,b}First(B)={c}First(C)=

{a,}First(D)=

{,b}First(AB)=

{a,b,c}First(Da)={a,b}First(cC)={c}First(aADC)={a}

定義

設(shè)G

=（VT，VN，P，S）是上下文無(wú)關(guān)文法，對(duì)每個(gè)AVN，

Follow(A)={aS#*A#且aFirst(#)，

,

(VT

VN)*}

（#代表輸入單詞序列右邊的結(jié)束符）

Follow

集合LL（1）分析

計(jì)算Follow

集合置Follow(S)={#}，置所有其它的Follow集合為；重復(fù)如下步驟，直至所有Follow集不再變化為止：對(duì)于AαBβ

P，把

First(β){}加至

Follow(B);

若有First(β)，則把Follow(A)加至Follow(B)中．LL（1）分析

例：計(jì)算First和Follow集合文法G（S）:（1）SAB（2）ADa（3）BcC（4）CaADC（5）DbFirst(B)={c}First()={}First(a)={a}First(DC)={b,a,}First(C)={a,}Follow(S)={#}LL（1）分析Follow(A)={}Follow(B)={}Follow(C)={}Follow(D)={}

例：計(jì)算First和Follow集合文法G（S）:（1）SAB（2）ADa（3）BcC（4）CaADC（5）DbFirst(B)={c}First()={}First(a)={a}First(DC)={b,a,}First(C)={a,}LL（1）分析Follow(A)={c}Follow(B)={#}Follow(S)={#}Follow(A)={}Follow(B)={}Follow(C)={}Follow(D)={}

例：計(jì)算First和Follow集合文法G（S）:（1）SAB（2）ADa（3）BcC（4）CaADC（5）DbFirst(B)={c}First()={}First(a)={a}First(DC)={b,a,}First(C)={a,}LL（1）分析Follow(D)={a}Follow(S)={#}Follow(A)={c}Follow(B)={#}Follow(C)={}Follow(D)={}

例：計(jì)算First和Follow集合文法G（S）:（1）SAB（2）ADa（3）BcC（4）CaADC（5）DbFirst(B)={c}First()={}First(a)={a}First(DC)={b,a,}First(C)={a,}LL（1）分析Follow(C)={#}Follow(S)={#}Follow(A)={c}Follow(B)={#}Follow(C)={}Follow(D)={a}

例：計(jì)算First和Follow集合文法G（S）:（1）SAB（2）ADa（3）BcC（4）CaADC（5）DbFirst(B)={c}First()={}First(a)={a}First(DC)={b,a,}First(C)={a,}LL（1）分析Follow(A)={c,b,a,#}Follow(S)={#}Follow(A)={c}Follow(B)={#}Follow(C)={#}Follow(D)={a}Follow(D)={a,#}

例：計(jì)算First和Follow集合文法G（S）:（1）SAB（2）ADa（3）BcC（4）CaADC（5）DbFirst(B)={c}First()={}First(a)={a}First(DC)={b,a,}First(C)={a,}LL（1）分析Follow(S)={#}Follow(A)={c,b,a,#}Follow(B)={#}Follow(C)={#}Follow(D)={a,#}

定義：預(yù)測(cè)集合（PredictiveSet）

設(shè)G

=（VT，VN，P，S）是上下文無(wú)關(guān)文法。對(duì)任何產(chǎn)生式AαP，其預(yù)測(cè)集合PS(Aα)定義為：如果

first(α)，那么

PS(Aα)=first(α)；如果first(α)，那么

PS(Aα)=(first(α)–{})follow(A)

LL（1）分析

定義：LL（1）文法文法G是LL（1）文法，當(dāng)且僅當(dāng)對(duì)于G的每個(gè)非終結(jié)符A的任何兩個(gè)不同產(chǎn)生式Aαβ，下面的條件成立：

PS(Aα)

PS(Aβ)

=

LL（1）分析

舉例：驗(yàn)證如下文法G（S）不是LL（1）文法文法G（S）:（1）SAB（2）ADa（3）BcC（4）CaADC（5）DbPS(ADa)={b,a}PS(A)={c,b,a,#}PS(CaADC)={a}PS(C)={#}PS(Db)=PS(D)={a,#}LL（1）分析First(Da)={b,a}First()={}First(aADC)={a}First(b)=Follow(A)={c,b,a,#}Follow(C)={#}Follow(D)={a,#}PS(ADa)PS(A)

PS(CaADC)PS(C)=

PS(Db)PS(D)=

遞歸下降LL（1）分析程序每個(gè)非終結(jié)符對(duì)應(yīng)一個(gè)分析子程序LL（1）分析的實(shí)現(xiàn)

表驅(qū)動(dòng)LL（1）分析程序借助于預(yù)測(cè)分析表和一個(gè)下推棧LL（1）分析

工作原理每個(gè)非終結(jié)符都對(duì)應(yīng)一個(gè)子程序。該子程序的行為根據(jù)語(yǔ)法描述來(lái)明確：根據(jù)下一個(gè)輸入符號(hào)來(lái)確定按照哪一個(gè)產(chǎn)生式進(jìn)行處理，再根據(jù)該產(chǎn)生式的右端，每遇到一個(gè)終結(jié)符，則判斷當(dāng)前讀入的單詞是否與該終結(jié)符相匹配，若匹配，再讀取下一個(gè)單詞繼續(xù)分析；不匹配，則進(jìn)行出錯(cuò)處理每遇到一個(gè)非終結(jié)符，則調(diào)用相應(yīng)的子程序

遞歸下降LL(1)分析程序遞歸下降LL（1）分析程序

例對(duì)于下列關(guān)于function的唯一產(chǎn)生式

<function>

FUNCID(<parameter_list>)<statement>

（<function>，<parameter_list>，和

<statement>是非終結(jié)符）

非終結(jié)符對(duì)應(yīng)的遞歸下降子程序voidParseFunction(){MatchToken(T_FUNC);//匹配FUNCMatchToken(T_ID);//匹配IDMatchToken(T_LPAREN);//匹配（

ParseParameterList();MatchToken(T_RPAREN);//匹配）

ParseStatement();}遞歸下降LL（1）分析程序

例續(xù)上頁(yè)

非終結(jié)符對(duì)應(yīng)的遞歸下降子程序voidMatchToken(intexpected){if(lookahead!=expected)//判別當(dāng)前單詞是否與

{//期望的終結(jié)符匹配

printf("syntaxerror\n");exit(0);}else//若匹配,消費(fèi)掉當(dāng)前單詞并讀入下一個(gè)

lookahead=getToken();//調(diào)用詞法分析程序}遞歸下降LL（1）分析程序

例對(duì)于下列文法G(S):

SAaS

BbSdAaB

c

遞歸下降LL(1)分析程序舉例PS(SAaS)={a}PS(SBbS)={c,b}PS(Sd)=ttnrhnnPS(Aa)={a}PS(B)=PS(Bc)={c}First（AaS）={a}First（BbS）={c,b}First（d）=rvzjbtdFirst（a）={a}First（）={}First（c）={c}Follow（S）={#}Follow（A）={a}Follow（B）=遞歸下降LL（1）分析程序PS(SAaS)，PS(SBbS)以及PS(Sd)互不相交，PS(B)和PS(Sd)互不相交，所以，G(S)是LL(1)文法

一般結(jié)構(gòu)

設(shè)A的產(chǎn)生式:

A

u1u2...un,

相對(duì)于非終結(jié)符A

的遞歸下降子程序

ParseA

的一般結(jié)

構(gòu)如右圖所示

非終結(jié)符對(duì)應(yīng)的遞歸下降子程序voidParseA(){switch(lookahead){casePS(Au1):/*codetorecognizeu1*/break;casePS(Au2):/*codetorecognizeu2*/break;...casePS(Aun):/*codetorecognizeun*/break;default:printf("syntaxerror\n");exit(0);}}遞歸下降LL（1）分析程序

接上例針對(duì)文法G(S)構(gòu)造的遞歸下降分析程序voidParseS(){switch(lookahead)

{casea:ParseA();MatchToken(a);ParseS();break;G(S):SAaS

BbSdAaB

cPS(SAaS)={a}PS(SBbS)={c,b}PS(Sd)=jtznx7zcaseb,c:ParseB();MatchToken(b);ParseS();break;cased:MatchToken(d);break;default:printf("syntaxerror\n")exit(0);}}遞歸下降LL（1）分析程序

接上例針對(duì)文法G(S)

構(gòu)造的遞歸下降分析程序voidParseA(){if(lookahead==a)

{MatchToken(a);}else{printf("syntaxerror\n”);exit(0);}}PS(Aa)={a}PS(B)=PS(Bc)={c}voidParseB(){if(lookahead==c)

{MatchToken(c);}elseif(lookahead==b){}

else{printf("syntaxerror\n”);exit(0);}}G(S):SAaS

BbSdAaB

c遞歸下降LL（1）分析程序

實(shí)際應(yīng)用中的推廣

上面只討論了根據(jù)普通文法構(gòu)造遞歸下降分析程序。實(shí)際上，也可以將產(chǎn)生式右端擴(kuò)展為更復(fù)雜的描述表達(dá)式，即除了文法符號(hào)之間的連接運(yùn)算之外，還可以有選擇、重復(fù)、任選以及優(yōu)先括號(hào)等運(yùn)算（如EBNF范式中的運(yùn)算），以使語(yǔ)法描述更加簡(jiǎn)潔，分析程序更加高效（比較：若將其展開(kāi)為普通文法，則需要引入多個(gè)非終結(jié)符，增加多個(gè)對(duì)應(yīng)的子程序）。

X1|X1|…|Xm多個(gè)成分之間的選擇

{X}

成分X的重復(fù)（0到多次）

[X]

成分X的任選（0或1次）

(X)

成分X優(yōu)先遞歸下降LL（1）分析程序

實(shí)際應(yīng)用中的推廣

將產(chǎn)生式右端擴(kuò)展后，同樣要求它的

First

集合，以適應(yīng)遞歸下降分析程序的構(gòu)造方法。

First（X1|X2|…|Xm）=First（X1）

…First（Xm）

First（{X}）=First（X）

{}First（[X]）=

First（X）

{}First（(X)）=

First（X）遞歸下降LL（1）分析程序

實(shí)際應(yīng)用中的推廣

將產(chǎn)生式右端擴(kuò)展后，子程序的處理過(guò)程中需要針對(duì)不同運(yùn)算選擇不同的語(yǔ)句形式（普通文法只有連接運(yùn)算，所以只對(duì)應(yīng)順序語(yǔ)句）。

X1|X2|…|Xm

對(duì)應(yīng)選擇語(yǔ)句

{X}對(duì)應(yīng)循環(huán)語(yǔ)句

[X]對(duì)應(yīng)If-Then語(yǔ)句

(X)對(duì)應(yīng)復(fù)合語(yǔ)句

可參考PL/0編譯器的語(yǔ)法分析程序遞歸下降LL（1）分析程序

工作原理

利用預(yù)測(cè)分析表和一個(gè)下推棧實(shí)現(xiàn)初始時(shí)，下推棧只包含#；首先將文法開(kāi)始符號(hào)入棧；之后依如下步驟：（1）若棧頂為終結(jié)符，則判斷當(dāng)前讀入的單詞是否與該終結(jié)符相匹配，若匹配，再讀取下一單詞繼續(xù)分析；不匹配，則進(jìn)行出錯(cuò)處理；（2）若棧頂為非終結(jié)符，則根據(jù)該非終結(jié)符和當(dāng)前輸入單詞查預(yù)測(cè)分析表，若相應(yīng)表項(xiàng)中是產(chǎn)生式（唯一的），則將此非終結(jié)符出棧，并把產(chǎn)生式右部符號(hào)從右至左入棧；若表項(xiàng)為空，則進(jìn)行出錯(cuò)處理；（3）重復(fù)（1）和（2），直到棧頂為#同時(shí)輸入也遇到結(jié)束符#

時(shí)，分析結(jié)束

表驅(qū)動(dòng)LL(1)分析程序表驅(qū)動(dòng)LL（1）分析程序

表驅(qū)動(dòng)分析程序需要的二維表M

表的每一行A

對(duì)應(yīng)一個(gè)非終結(jié)符

表的每一列a對(duì)應(yīng)某個(gè)終結(jié)符或輸入結(jié)束符#

表中的項(xiàng)M(A,a)表示棧頂為A，下一個(gè)輸入符號(hào)為a時(shí)，可選的產(chǎn)生式集合

對(duì)于LL（1）文法，可以構(gòu)造出一個(gè)M(A,a)

最多只包含一個(gè)產(chǎn)生式的預(yù)測(cè)分析表，可稱之為

LL（1）分析表

M(A,a)

不含產(chǎn)生式時(shí)，對(duì)應(yīng)一個(gè)出錯(cuò)位置

預(yù)測(cè)分析表表驅(qū)動(dòng)LL（1）分析程序

預(yù)測(cè)分析表的構(gòu)造算法對(duì)文法G

的每個(gè)產(chǎn)生式A執(zhí)行如下步驟：

對(duì)每個(gè)aPS(A)，將A加入M[A,a]把所有無(wú)定義的

M[A,a]標(biāo)上“出錯(cuò)標(biāo)志”可以證明:一個(gè)文法G

的預(yù)測(cè)分析表不含多重入口，當(dāng)且僅當(dāng)該文法是LL(1)的表驅(qū)動(dòng)LL（1）分析程序

預(yù)測(cè)分析表的構(gòu)造舉例

對(duì)于下列文法G(S)：

SAaS

BbSdAaB

c可構(gòu)造如下預(yù)測(cè)分析表：SAaSSBbSSdAaBBcSBbS表驅(qū)動(dòng)LL（1）分析程序PS(SAaS)={a}PS(SBbS)={c,b}PS(Sd)=hxzjdpvPS(Aa)={a}PS(B)=PS(Bc)={c}

表驅(qū)動(dòng)預(yù)測(cè)分析程序分析算法

初始時(shí)‘#’入棧，然后文法開(kāi)始符號(hào)入棧；首個(gè)輸入符號(hào)讀進(jìn)a；

flag=TRUE；

while(flag)do{

棧頂符號(hào)出棧并放在X中；

if(XVT){if(X==a)

把下一個(gè)輸入符號(hào)讀進(jìn)a;

elseERROR;}elseif(X==‘#’）{if(a==‘#’)flag=FALSE;elseERROR;}elseif(M[X,a]=={XX1X2…Xk})Xk,XK-1,…,X1依次進(jìn)棧;

elseERROR;}/*分析成功，過(guò)程完畢*／表驅(qū)動(dòng)LL（1）分析程序

表驅(qū)動(dòng)預(yù)測(cè)分析過(guò)程舉例

對(duì)于下列文法G(S)：

SAaS

BbSdAaB

c

分析輸入串a(chǎn)abd的過(guò)程：#S剩余的輸入串

aabd#SAaSSBbSSdAaBBcSBbS表驅(qū)動(dòng)LL（1）分析程序

表驅(qū)動(dòng)預(yù)測(cè)分析過(guò)程舉例

對(duì)于下列文法G(S)：

SAaS

BbSdAaB

c

分析輸入串a(chǎn)abd的過(guò)程：#S剩余的輸入串

aabd#aASAaSSBbSSdAaBBcSBbS表驅(qū)動(dòng)LL（1）分析程序

表驅(qū)動(dòng)預(yù)測(cè)分析過(guò)程舉例

對(duì)于下列文法G(S)：

SAaS

BbSdAaB

c

分析輸入串a(chǎn)abd的過(guò)程：#S剩余的輸入串

aabd#aaSAaSSBbSSdAaBBcSBbS表驅(qū)動(dòng)LL（1）分析程序

表驅(qū)動(dòng)預(yù)測(cè)分析過(guò)程舉例

對(duì)于下列文法G(S)：

SAaS

BbSdAaB

c

分析輸入串a(chǎn)abd的過(guò)程：#S剩余的輸入串

abd#aSAaSSBbSSdAaBBcSBbS表驅(qū)動(dòng)LL（1）分析程序

表驅(qū)動(dòng)預(yù)測(cè)分析過(guò)程舉例

對(duì)于下列文法G(S)：

SAaS

BbSdAaB

c

分析輸入串a(chǎn)abd的過(guò)程：#S剩余的輸入串

bd#SAaSSBbSSdAaBBcSBbS表驅(qū)動(dòng)LL（1）分析程序

表驅(qū)動(dòng)預(yù)測(cè)分析過(guò)程舉例

對(duì)于下列文法G(S)：

SAaS

BbSdAaB

c

分析輸入串a(chǎn)abd的過(guò)程：#剩余的輸入串

bd#SbBSAaSSBbSSdAaBBcSBbS表驅(qū)動(dòng)LL（1）分析程序

表驅(qū)動(dòng)預(yù)測(cè)分析過(guò)程舉例

對(duì)于下列文法G(S)：

SAaS

BbSdAaB

c

分析輸入串a(chǎn)abd的過(guò)程：#剩余的輸入串

bd#SbSAaSSBbSSdAaBBcSBbS表驅(qū)動(dòng)LL（1）分析程序

表驅(qū)動(dòng)預(yù)測(cè)分析過(guò)程舉例

對(duì)于下列文法G(S)：

SAaS

BbSdAaB

c

分析輸入串a(chǎn)abd的過(guò)程：#剩余的輸入串

d#SSAaSSBbSSdAaBBcSBbS表驅(qū)動(dòng)LL（1）分析程序

表驅(qū)動(dòng)預(yù)測(cè)分析過(guò)程舉例

對(duì)于下列文法G(S)：

SAaS

BbSdAaB

c

分析輸入串a(chǎn)abd的過(guò)程：#剩余的輸入串

d#dSAaSSBbSSdAaBBcSBbS表驅(qū)動(dòng)LL（1）分析程序

表驅(qū)動(dòng)預(yù)測(cè)分析過(guò)程舉例

對(duì)于下列文法G(S)：

SAaS

BbSdAaB

c

分析輸入串a(chǎn)abd的過(guò)程：#剩余的輸入串

#SAaSSBbSSdAaBBcSBbS表驅(qū)動(dòng)LL（1）分析程序

LL(1)文法通常不含左遞歸和左公因子許多文法在消除左遞歸和提取左公因子后可以變換為L(zhǎng)L(1)文法

但不含左遞歸和左公因子的文法不一定都是

LL(1)文法

文法變換：消除左遞歸、提取左公因子文法變換文法變換：消除左遞歸

左遞歸消除規(guī)則消除直接左遞歸對(duì)形如

PPαβ

的產(chǎn)生式，其中α非，β不以P打頭，可改寫(xiě)為：

P

βQQ

αQ

其中Q為新增加的非終結(jié)符文法變換：消除左遞歸

左遞歸消除規(guī)則消除直接左遞歸對(duì)更一般的形如

PPα1Pα2…Pαmβ1β2…βn

的一組產(chǎn)生式，其中αi（1im）不為，βj（1jn）

不以P打頭，可改寫(xiě)為：

Pβ1Qβ2Q…βnQQ

α1Qα2Q…αmQ

其中Q為新增加的非終結(jié)符文法變換：消除左遞歸

左遞歸消除舉例原文法G[E]:EETTTTFFF(E)a消除左遞歸后的文法

G’[E]:(1)ETE’(2)E’

TE’(3)E’

(4)TFT’(5)T’

FT’(6)T’

(7)F→(E)(8)F→a文法變換：消除左遞歸

左遞歸消除規(guī)則消除一般左遞歸

對(duì)無(wú)回路(A

A)、無(wú)-產(chǎn)生式的文法，通過(guò)下列步驟可消除一般左遞歸（包括直接和間接左遞歸）：（1）以某種順序?qū)⑽姆ǚ墙K結(jié)符排列A1,A2…An

（2）fori=1,ndo{forj=1,i-1do{

用Ai

1r2r…kr反復(fù)替代形如AiAjr的規(guī)則,

其中Aj

1

2…k是關(guān)于Aj的全部產(chǎn)生式;}

消除Ai規(guī)則的直接左遞歸;

}

（3）化簡(jiǎn)由（2）得到的文法文法變換：消除左遞歸

左遞歸消除舉例原文法G[S]:SPQaPQSbQSPc非終結(jié)符排序?yàn)镾、P、Q，按造消除一般左遞歸的方法，進(jìn)行如下變換:QSPc結(jié)果：SPQaPQSbQbQPRaPRcRRSQPRQPQPaPcQQSQPbQP

aPcQbQPRaPRcRRSQPR文法變換：消除左遞歸

左遞歸消除舉例

原文法G[S]:SPQaPQSbQSPc

按造非終結(jié)符的另一種排序Q、P、S，依消除一般左遞歸的方法，進(jìn)行如下變換:PQSb結(jié)果ScSQRbQRaRPSPScSbQSPcRPSQR

PSPScSbSPQaSSPSQcSQbQaScSQRbQRaRRPSQR

文法變換：提取左公因子

提取左公因子規(guī)則

對(duì)形如

P

αβαγ

的一對(duì)產(chǎn)生式，可用如下三個(gè)產(chǎn)生式替換：

P

αQQ

β

γ

其中Q為新增加的未出現(xiàn)過(guò)的非終結(jié)符文法變換：提取左公因子

提取左公因子規(guī)則

一般含有左公因子的產(chǎn)生式形如

P

αβ1αβ2…αβm

γ1γ

2…γn

其中，每個(gè)γ不以α開(kāi)頭.提取左公共因子，產(chǎn)生式改寫(xiě)成：

P

αQγ1γ

2…γn

Q

β1β2…βm文法變換：提取左公因子

對(duì)文法G(S):

S

ifCtS

ifCtSeSCb

提取左公因子后，可改寫(xiě)為文法G’(S)：

S

ifCtSAAeS

Cb

提取左公因子舉例文法變換

舉例：許多文法在消除左遞歸和提取左公因子后可以變換為L(zhǎng)L(1)文法可驗(yàn)證如下文法

G[E]是LL(1)文法:(1)ETE’(2)E’

TE’(3)E’

(4)TFT’(5)T’

FT’(6)T’

(7)F→(E)(8)F→a文法變換

舉例：不含左遞歸和左公因子的文法不一定是LL(1)文法First集

Follow集ifCtSA:{if}S:{#,e}eS:{e}A:{#,e}bC:{t}M[A,e]={A→eS，A→}S

ifCtS

ifCtSeSCb提取左公因子后：

S

ifCtSAAeS

Cb文法變換

問(wèn)題探討某些非LL(1)的文法也可采用LL(1)分析方法M[A,e]={AeS，

A

}S

ifCtS

ifCtSeSCb提取左公因子后：

S

ifCtSAAeS

優(yōu)先使用預(yù)測(cè)分析中的出錯(cuò)處理

錯(cuò)誤處理的原則盡可能準(zhǔn)確指出錯(cuò)誤位置和錯(cuò)誤屬性盡可能進(jìn)行校正預(yù)測(cè)分析中的出錯(cuò)處理

遞歸下降LL(1)分析中的出錯(cuò)處理介紹一種短語(yǔ)層錯(cuò)誤恢復(fù)技術(shù)表驅(qū)動(dòng)LL(1)分析中的出錯(cuò)處理

介紹一種簡(jiǎn)單的應(yīng)急錯(cuò)誤恢復(fù)技術(shù)

預(yù)測(cè)分析中的出錯(cuò)處理

出錯(cuò)報(bào)告（errorr