中國科學(xué)技術(shù)大學(xué)陳意云編譯原理全套參考資料陳意云編譯原理全套參考資料chapter3

第三章語法分析詞法分析器記號取下一個記號源程序分析樹前端的其余部分分析器分析樹符號表本章內(nèi)容上下文無關(guān)文法自上而下分析和自下而上分析圍繞分析器的自動生成展開3.1上下文無關(guān)文法3.1.1上下文無關(guān)文法的定義

正規(guī)式來定義一些簡單的語言，能表示給定結(jié)構(gòu)的固定次數(shù)的重復(fù)或者沒有指定次數(shù)的重復(fù)。

例：a(ba)5,a(ba)*正規(guī)式不能用于描述配對或嵌套的結(jié)構(gòu) 例：配對括號串的集合

{wcw|w是a和b的串}

3.1上下文無關(guān)文法上下文無關(guān)文法是四元組（VT,VN,S,P）VT

: 終結(jié)符集合VN

: 非終結(jié)符集合S: 開始符號P

: 產(chǎn)生式集合，產(chǎn)生式形式:A

例({id,+,*,,(,)},{expr,op},expr,P)expr

expr

op

expr expr(expr)expr

expr expr

idop+ op

*3.1上下文無關(guān)文法例({id,+,*,,(,)},{expr,op},expr,P)expr

expr

op

expr expr(expr)expr

expr expr

idop+ op

*簡化表示E

EAE|(E)|E|idA+|*3.1上下文無關(guān)文法

推導(dǎo)把產(chǎn)生式看成重寫規(guī)則，把符號串中的非終結(jié)符用其產(chǎn)生式右部的串來代替。例 E

E+E|E

*

E|(E)|

E|id

E

E

(E)

(E+E)

(id+E)(id+id)概念 上下文無關(guān)語言、等價的文法、句型記號S*、S+w

3.1上下文無關(guān)文法E

E+E|E

*

E|(E)|

E|id

最左推導(dǎo) E lm

Elm

(E)lm

(E+E)

lm

(id+E)lm(id+id)最右推導(dǎo)（規(guī)范推導(dǎo)） E rm

Erm

(E)rm

(E+E)

rm

(E+id)rm(id+id)3.1上下文無關(guān)文法3.1.3分析樹EEEEE()EEE()EEE+EE()EEE+idEE()EEE+idid3.1上下文無關(guān)文法3.1.3二義性E

E*E

E

E+Eid*E

E

*

E+E

id*

E+E id*

E+E

id*id+E id*id+Eid*id+id id*id+id3.1上下文無關(guān)文法3.1.3二義性E

E*E

E

E+Eid*E

E

*

E+E

id*

E+E id*

E+E

id*id+E id*id+Eid*id+id id*id+idEEE*+EEidididEEidE*+EEidid

語言和文法

語言和文法文法的優(yōu)點(diǎn)

文法給出了精確的，易于理解的語法說明

語言和文法文法的優(yōu)點(diǎn)

文法給出了精確的，易于理解的語法說明自動產(chǎn)生高效的分析器

語言和文法文法的優(yōu)點(diǎn)

文法給出了精確的，易于理解的語法說明自動產(chǎn)生高效的分析器可以給語言定義出層次結(jié)構(gòu)

語言和文法文法的優(yōu)點(diǎn)

文法給出了精確的，易于理解的語法說明自動產(chǎn)生高效的分析器可以給語言定義出層次結(jié)構(gòu)以文法為基礎(chǔ)的語言的實(shí)現(xiàn)便于語言的修改

語言和文法文法的優(yōu)點(diǎn)

文法給出了精確的，易于理解的語法說明自動產(chǎn)生高效的分析器可以給語言定義出層次結(jié)構(gòu)以文法為基礎(chǔ)的語言的實(shí)現(xiàn)便于語言的修改文法的問題文法只能描述編程語言的大部分語法

語言和文法

正規(guī)式和上下文無關(guān)文法的比較正規(guī)式(a|b)*ab

語言和文法

正規(guī)式和上下文無關(guān)文法的比較正規(guī)式(a|b)*ab12開始a0abb

語言和文法

正規(guī)式和上下文無關(guān)文法的比較正規(guī)式(a|b)*ab文法A0

a

A0|bA0|a

A1A1

b

A2A2

12開始a0abb

語言和文法3.2.2分離詞法分析器理由為什么要用正規(guī)式定義詞法

詞法規(guī)則非常簡單，不必用上下文無關(guān)文法。

語言和文法3.2.2分離詞法分析器理由為什么要用正規(guī)式定義詞法

詞法規(guī)則非常簡單，不必用上下文無關(guān)文法。對于詞法記號，正規(guī)式描述簡潔且易于理解。

語言和文法3.2.2分離詞法分析器理由為什么要用正規(guī)式定義詞法

詞法規(guī)則非常簡單，不必用上下文無關(guān)文法。對于詞法記號，正規(guī)式描述簡潔且易于理解。從正規(guī)式構(gòu)造出的詞法分析器效率高。

語言和文法把詞法分析從語法分析中分離出來的理由

簡化設(shè)計

語言和文法把詞法分析從語法分析中分離出來的理由

簡化設(shè)計編譯器的效率會改進(jìn)

語言和文法把詞法分析從語法分析中分離出來的理由

簡化設(shè)計編譯器的效率會改進(jìn)編譯器的可移植性加強(qiáng)

語言和文法把詞法分析從語法分析中分離出來的理由

簡化設(shè)計編譯器的效率會改進(jìn)編譯器的可移植性加強(qiáng)便于編譯器前端的模塊劃分

語言和文法

驗(yàn)證文法產(chǎn)生的語言G:S

(S)S|L(G)=配對的括號串的集合

語言和文法

驗(yàn)證文法產(chǎn)生的語言G:S

(S)S|L(G)=配對的括號串的集合按推導(dǎo)步數(shù)進(jìn)行歸納：推出的是配對括號串

語言和文法

驗(yàn)證文法產(chǎn)生的語言G:S

(S)S|L(G)=配對的括號串的集合按推導(dǎo)步數(shù)進(jìn)行歸納：推出的是配對括號串歸納基礎(chǔ)：S

歸納假設(shè)：少于n步的推導(dǎo)都產(chǎn)生配對的括號串歸納步驟：n步的最左推導(dǎo)如下：

S(S)S*(x)S*(x)y

語言和文法

驗(yàn)證文法產(chǎn)生的語言G:S

(S)S|L(G)=配對的括號串的集合按串長進(jìn)行歸納：配對括號串可由S推出

語言和文法

驗(yàn)證文法產(chǎn)生的語言G:S

(S)S|L(G)=配對的括號串的集合按串長進(jìn)行歸納：配對括號串可由S推出歸納基礎(chǔ)：S

歸納假設(shè)：長度小于2n的都可以從S推導(dǎo)出來歸納步驟：考慮長度為2n(n

1)的w=(x)y

S(S)S*(x)S*(x)y

語言和文法3.2.4適當(dāng)?shù)谋磉_(dá)式文法用一種層次觀點(diǎn)看待表達(dá)式

id*id*(id+id)+id*id+id

語言和文法3.2.4適當(dāng)?shù)谋磉_(dá)式文法用一種層次觀點(diǎn)看待表達(dá)式

id*id*(id+id)+id*id+id

id

*

id

*

(id+id)

語言和文法3.2.4適當(dāng)?shù)谋磉_(dá)式文法用一種層次觀點(diǎn)看待表達(dá)式

id*id*(id+id)+id*id+id

id

*

id

*

(id+id)

文法 expr

expr+term|term

語言和文法3.2.4適當(dāng)?shù)谋磉_(dá)式文法用一種層次觀點(diǎn)看待表達(dá)式

id*id*(id+id)+id*id+id

id

*

id

*

(id+id)

文法 expr

expr+term|term term

term

*factor|factor

語言和文法3.2.4適當(dāng)?shù)谋磉_(dá)式文法用一種層次觀點(diǎn)看待表達(dá)式

id*id*(id+id)+id*id+id

id

*

id

*

(id+id)

文法 expr

expr+term|term term

term

*factor|factor

factor

id|(expr)

語言和文法 expr

expr+term|term term

term

*factor|factor

factor

id|(expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid*id*id和id+id*id的分析樹

語言和文法3.2.5消除二義性stmt

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

elsestmt

語言和文法3.2.5消除二義性stmt

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

elsestmt兩個最左推導(dǎo)：

stmtifexprthenstmt

ifexprthenifexprthenstmtelsestmt

語言和文法3.2.5消除二義性stmt

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

elsestmt兩個最左推導(dǎo)：

stmtifexprthenstmt

ifexprthenifexprthenstmtelsestmt

stmtifexprthenstmtelsestmt

ifexprthenifexprthenstmtelsestmt

語言和文法

無二義的文法stmt

matched_stmt

|unmatched_stmtmatched_stmt

ifexprthenmatched_stmt

elsematched_stmt

|otherunmatched_stmt

ifexprthenstmt |ifexprthenmatched_stmt

elseunmatched_stmt

語言和文法3.2.6消除左遞歸文法左遞歸 A*Aa

語言和文法3.2.6消除左遞歸文法左遞歸 A*Aa

直接左遞歸 AAa|b

串的特點(diǎn) ba...a

語言和文法3.2.6消除左遞歸文法左遞歸 A*Aa

直接左遞歸 AAa|b

串的特點(diǎn) ba...a消除直接左遞歸 A

bA A

aA|

語言和文法例

算術(shù)表達(dá)文法

E

E+T|T （T+T...+T） T

T

*

F|F （F

*

F...*

F） F

(E)|id

語言和文法例

算術(shù)表達(dá)文法

E

E+T|T （T+T...+T） T

T

*

F|F （F

*

F...*

F） F

(E)|id消除左遞歸后文法 E

TE E

+TE

| T

FT

T

*

FT

|

F

(E)|id

語言和文法非直接左遞歸 S

Aa|b

A

Ac|Sd|

語言和文法非直接左遞歸 S

Aa|b

A

Sd|先變換成直接左遞歸 S

Aa|b A

Aad|bd|

語言和文法非直接左遞歸 S

Aa|b

A

Sd|先變換成直接左遞歸 S

Aa|b A

Aad|bd|

再消除左遞歸

SAa|b A

bdA

|A

A

adA

|

語言和文法

提左因子有左因子的文法 A

1|2

語言和文法

提左因子有左因子的文法 A

1|2提左因子 A

A A

1|2

語言和文法例

懸空else的文法 stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other

語言和文法例

懸空else的文法 stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other 提左因子 stmt

ifexprthenstmt

optional_else_part |other optional_else_partelsestmt |

語言和文法

非上下文無關(guān)的語言結(jié)構(gòu)L1={wcw|w屬于(a|b)*}

標(biāo)識符的聲明應(yīng)先于其引用的抽象

語言和文法

非上下文無關(guān)的語言結(jié)構(gòu)L1={wcw|w屬于(a|b)*}

標(biāo)識符的聲明應(yīng)先于其引用的抽象

L2={anbmcndm|n0,m0}形參個數(shù)和實(shí)參個數(shù)應(yīng)該相同的抽象

語言和文法

非上下文無關(guān)的語言結(jié)構(gòu)L1={wcw|w屬于(a|b)*}

標(biāo)識符的聲明應(yīng)先于其引用的抽象

L2={anbmcndm|n0,m0}形參個數(shù)和實(shí)參個數(shù)應(yīng)該相同的抽象

L3={anbncn|n0}早先排版描述的一個現(xiàn)象的抽象

語言和文法L1={wcwR|w(a|b)*}

SaSa|bSb|c

語言和文法L1={wcwR|w(a|b)*}

SaSa|bSb|c

L2={anbmcmdn|n1,m1}

SaSd|aAd AbAc|bc

語言和文法L1={wcwR|w(a|b)*}

SaSa|bSb|c

L2={anbmcmdn|n1,m1}

SaSd|aAd AbAc|bcL

2={anbncmdm|n1，m1} SAB AaAb|ab

BcBd|cd

語言和文法L3

={anbn|n

1}

SaSb|ab

語言和文法L3

={anbn|n

1}

SaSb|abL3是不能用正規(guī)式描述的語言的一個范例

語言和文法L3

={anbn|n

1}

SaSb|abL3是不能用正規(guī)式描述的語言的一個范例

若存在接受L3的DFAD，狀態(tài)數(shù)為k個。

語言和文法L3

={anbn|n

1}

SaSb|abL3是不能用正規(guī)式描述的語言的一個范例

若存在接受L3的DFAD，狀態(tài)數(shù)為k個。

設(shè)D讀完,

a,aa,

…,ak

分別到達(dá)狀態(tài)s0,s1,

…,sk

語言和文法L3

={anbn|n

1}

SaSb|abL3是不能用正規(guī)式描述的語言的一個范例

若存在接受L3的DFAD，狀態(tài)數(shù)為k個。

設(shè)D讀完,

a,aa,

…,ak

分別到達(dá)狀態(tài)s0,s1,

…,sk至少有兩個狀態(tài)相同，例如是si和sj，則ajbi屬于L3

語言和文法L3

={anbn|n

1}

SaSb|abL3是不能用正規(guī)式描述的語言的一個范例

若存在接受L3的DFAD，狀態(tài)數(shù)為k個。

設(shè)D讀完,

a,aa,

…,ak

分別到達(dá)狀態(tài)s0,s1,

…,sk至少有兩個狀態(tài)相同，例如是si和sj，則ajbi屬于L3

si…。。。fs0標(biāo)記為ai的路徑標(biāo)記為bi的路徑標(biāo)記為aj

i的路徑…。。?！?。。

語言和文法

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||1

語言和文法

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||1短語文法

語言和文法

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外短語文法

語言和文法

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外短語文法、上下文有關(guān)文法

語言和文法

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*短語文法、上下文有關(guān)文法

語言和文法

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*短語文法、上下文有關(guān)文法、上下文無關(guān)文法

語言和文法

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*3型文法：AaB或Aa，A,BVN,aVT

短語文法、上下文有關(guān)文法、上下文無關(guān)文法

語言和文法

形式語言鳥瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*3型文法：AaB或Aa，A,BVN,aVT

短語文法、上下文有關(guān)文法、上下文無關(guān)文法、正規(guī)文法

語言和文法例：L3＝{anbncn|n1}的上下文有關(guān)文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

cc

語言和文法例：L3＝{anbncn|n1}的上下文有關(guān)文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推導(dǎo)過程如下：S*an-1S(BC)n1

語言和文法例：L3＝{anbncn|n1}的上下文有關(guān)文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推導(dǎo)過程如下：S*an-1S(BC)n1S+an(BC)n

語言和文法例：L3＝{anbncn|n1}的上下文有關(guān)文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推導(dǎo)過程如下：S*an-1S(BC)n1S+an(BC)n

S+anBnCn

語言和文法例：L3＝{anbncn|n1}的上下文有關(guān)文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推導(dǎo)過程如下：S*an-1S(BC)n1S+an(BC)n

S+anBnCnS+anbBn1Cn

語言和文法例：L3＝{anbncn|n1}的上下文有關(guān)文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推導(dǎo)過程如下：S*an-1S(BC)n1S+an(BC)n

S+anBnCnS+anbBn1CnS+anbnCn

語言和文法例：L3＝{anbncn|n1}的上下文有關(guān)文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推導(dǎo)過程如下：S*an-1S(BC)n1S+an(BC)n

S+anBnCnS+anbBn1CnS+anbnCn

S+anbncCn-1

語言和文法例：L3＝{anbncn|n1}的上下文有關(guān)文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推導(dǎo)過程如下：S*an-1S(BC)n1S+an(BC)n

S+anBnCnS+anbBn1CnS+anbnCn

S+anbncCn-1S+anbncn

自上而下分析3.3.1自上而下分析的一般方法例：

文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹

自上而下分析3.3.1自上而下分析的一般方法例：

文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SaCb

自上而下分析3.3.1自上而下分析的一般方法例：

文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SSaCbaCbcd

自上而下分析3.3.1自上而下分析的一般方法例：

文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SSSaCbaaCCbbcdc

自上而下分析3.3.1自上而下分析的一般方法例：

文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SSSaCbaaCCbbcdc 不能處理左遞歸

自上而下分析3.3.1自上而下分析的一般方法例：

文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SSSaCbaaCCbbcdc 不能處理左遞歸、復(fù)雜的回溯技術(shù)

自上而下分析3.3.1自上而下分析的一般方法例：

文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SSSaCbaaCCbbcdc 不能處理左遞歸、復(fù)雜的回溯技術(shù)、回溯導(dǎo)致語義工作推倒重來

自上而下分析3.3.1自上而下分析的一般方法例：

文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SSSaCbaaCCbbcdc 不能處理左遞歸、復(fù)雜的回溯技術(shù)、回溯導(dǎo)致語義工作推倒重來、難以報告出錯的確切位置

自上而下分析3.3.1自上而下分析的一般方法例：

文法 S

aCb C

cd|c

為輸入串w=acb建立分析樹SSSaCbaaCCbbcdc 不能處理左遞歸、復(fù)雜的回溯技術(shù)、回溯導(dǎo)致語義工作推倒重來、難以報告出錯的確切位置、效率低

自上而下分析3.3.2LL(1)文法對文法加什么樣的限制可以保證沒有回溯？先定義兩個和文法有關(guān)的函數(shù)FIRST(

)={a|

*a…,a

VT}

自上而下分析3.3.2LL(1)文法對文法加什么樣的限制可以保證沒有回溯？先定義兩個和文法有關(guān)的函數(shù)FIRST(

)={a|

*a…,a

VT} 特別是，

*時，規(guī)定

FIRST(

)

自上而下分析3.3.2LL(1)文法對文法加什么樣的限制可以保證沒有回溯？先定義兩個和文法有關(guān)的函數(shù)FIRST(

)={a|

*a…,a

VT} 特別是，

*時，規(guī)定

FIRST(

) 對A的任何兩個不同的選擇i

和j，希望有 FIRST(i)FIRST(j)=

自上而下分析3.3.2LL(1)文法對文法加什么樣的限制可以保證沒有回溯？先定義兩個和文法有關(guān)的函數(shù)FIRST(

)={a|

*a…,a

VT} 特別是，

*時，規(guī)定

FIRST(

) 對A的任何兩個不同的選擇i

和j，希望有 FIRST(i)FIRST(j)=

但有一個前提，F(xiàn)IRST(i)和FIRST(j)都不含

自上而下分析3.3.2LL(1)文法對文法加什么樣的限制可以保證沒有回溯？先定義兩個和文法有關(guān)的函數(shù)FIRST(

)={a|

*a…,a

VT} 特別是，

*時，規(guī)定

FIRST(

)FOLLOW(A)={a|S

*…Aa…，aVT}

自上而下分析3.3.2LL(1)文法對文法加什么樣的限制可以保證沒有回溯？先定義兩個和文法有關(guān)的函數(shù)FIRST(

)={a|

*a…,a

VT} 特別是，

*時，規(guī)定

FIRST(

)FOLLOW(A)={a|S

*…Aa…，aVT} 如果A是某個句型的最右符號，那么$屬于FOLLOW(A)

自上而下分析LL(1)文法 任何兩個產(chǎn)生式A|都滿足下列條件：FIRST(

)FIRST()=；若

*

，那么FIRST()FOLLOW(A)=。

自上而下分析LL(1)文法 任何兩個產(chǎn)生式A|都滿足下列條件：FIRST(

)FIRST()=；若

*

，那么FIRST()FOLLOW(A)=。LL(1)文法有一些明顯的性質(zhì)沒有公共左因子不是二義的不含左遞歸

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|id

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}FOLLOW(E)=FOLLOW(E)={),$}

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}FOLLOW(E)=FOLLOW(E)={),$}FOLLOW(T)=FOLLOW(T)={+,),$}

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}FOLLOW(E)=FOLLOW(E)={),$}FOLLOW(T)=FOLLOW(T)={+,),$}FOLLOW(F)={+,*,),$}

自上而下分析3.3.3遞歸下降的預(yù)測分析為每一個非終結(jié)符寫一個分析過程這些過程可能是遞歸的例： type

simple |id |array[simple]oftype simpleinteger |char |numdotdotnum

自上而下分析一個輔助過程procedurematch(t:token);begin iflookahead=tthen lookahead:=nexttoken() elseerror()end;

自上而下分析proccduretype;begin iflookaheadin{integer,char,num}then simple() elseiflookahead=thenbegin match();match(id) end elseiflookahead=arraythenbegin match(array);match([);simple(); match(]);match(of);type() end elseerror()end;type

simple |id |array[simple]oftype

自上而下分析proceduresimple;begin iflookahead=integerthen match(integer) elseiflookahead=charthen match(char) elseiflookahead=numthenbegin match(num);match(dotdot);match(num) end elseerror()end;simpleinteger |char |numdotdotnum

自上而下分析3.3.4非遞歸的預(yù)測分析a+b$輸入預(yù)測分析程序分析表M輸出

XYZ$棧

自上而下分析非終結(jié)符輸

入

符

號

id

+*

...EE

TE

E

E

+TE

T

T

FT

T

T

T

*FTF

F

id

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

預(yù)測分析器接受輸入id

*

id+id的動作

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

$ET

id*id+id$

E

TE

預(yù)測分析器接受輸入id

*

id+id的動作

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

$ET

id*id+id$

E

TE

$ETF

id*id+id$

T

FT

預(yù)測分析器接受輸入id

*

id+id的動作

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

$ET

id*id+id$

E

TE

$ETF

id*id+id$

T

FT

$ETid

id*id+id$

F

id

預(yù)測分析器接受輸入id

*

id+id的動作

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

$ET

id*id+id$

E

TE

$ETF

id*id+id$

T

FT

$ETid

id*id+id$

F

id

$ET

*

id+id$

預(yù)測分析器接受輸入id

*

id+id的動作

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

$ET

id*id+id$

E

TE

$ETF

id*id+id$

T

FT

$ETid

id*id+id$

F

id

$ET

*

id+id$

$ETF*

*

id+id$

T

*FT

預(yù)測分析器接受輸入id

*

id+id的動作

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

$ET

id*id+id$

E

TE

$ETF

id*id+id$

T

FT

$ETid

id*id+id$

F

id

$ET

*

id+id$

$ETF*

*

id+id$

T

*FT

$ETF

id+id$

預(yù)測分析器接受輸入id

*

id+id的動作

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

$ET

id*id+id$

E

TE

$ETF

id*id+id$

T

FT

$ETid

id*id+id$

F

id

$ET

*

id+id$

$ETF*

*

id+id$

T

*FT

$ETF

id+id$

$ETid

id+id$

F

id

預(yù)測分析器接受輸入id

*

id+id的動作

自上而下分析3.3.5構(gòu)造預(yù)測分析表（1）對文法的每個產(chǎn)生式A

，執(zhí)行(2)和(3)。（2）對FIRST()的每個終結(jié)符a，把A

加入M[A,a]。（3）如果在FIRST()中，對FOLLOW(A)的每個終結(jié)符b（包括$）,把A

加入M[A,b]。（4）M的其它沒有定義的條目都是error。

自上而下分析非終結(jié)符

輸

入

符

號

other

b

else

...stmtstmt

other

e_part

e_part

elsestmte_part

expr

exprb

多重定義的條目

自上而下分析非終結(jié)符

輸

入

符

號

other

b

else

...stmtstmt

other

e_part

e_part

elsestmtexpr

exprb

多重定義的條目

自上而下分析

預(yù)測分析的錯誤恢復(fù)先對編譯器的錯誤處理做一個概述

詞法錯誤，如標(biāo)識符、關(guān)鍵字或算符的拼寫錯

自上而下分析

預(yù)測分析的錯誤恢復(fù)先對編譯器的錯誤處理做一個概述

詞法錯誤，如標(biāo)識符、關(guān)鍵字或算符的拼寫錯語法錯誤，如算術(shù)表達(dá)式的括號不配對

自上而下分析

預(yù)測分析的錯誤恢復(fù)先對編譯器的錯誤處理做一個概述

詞法錯誤，如標(biāo)識符、關(guān)鍵字或算符的拼寫錯語法錯誤，如算術(shù)表達(dá)式的括號不配對語義錯誤，如算符作用于不相容的運(yùn)算對象

自上而下分析

預(yù)測分析的錯誤恢復(fù)先對編譯器的錯誤處理做一個概述

詞法錯誤，如標(biāo)識符、關(guān)鍵字或算符的拼寫錯語法錯誤，如算術(shù)表達(dá)式的括號不配對語義錯誤，如算符作用于不相容的運(yùn)算對象邏輯錯誤，如無窮的遞歸調(diào)用

自上而下分析分析器對錯誤處理的基本目標(biāo)清楚而準(zhǔn)確地報告錯誤的出現(xiàn)

自上而下分析分析器對錯誤處理的基本目標(biāo)清楚而準(zhǔn)確地報告錯誤的出現(xiàn)迅速地從每個錯誤中恢復(fù)過來，以便診斷后面的錯誤，并盡量少出現(xiàn)偽錯誤

自上而下分析分析器對錯誤處理的基本目標(biāo)清楚而準(zhǔn)確地報告錯誤的出現(xiàn)迅速地從每個錯誤中恢復(fù)過來，以便診斷后面的錯誤，并盡量少出現(xiàn)偽錯誤

它不應(yīng)該使正確程序的處理速度降低太多

自上而下分析非遞歸預(yù)測分析在什么場合下發(fā)現(xiàn)錯誤棧頂?shù)慕K結(jié)符和下一個輸入符號不匹配棧頂是非終結(jié)符A，輸入符號是a，而M[A,a]是空白

自上而下分析非遞歸預(yù)測分析：采用緊急方式的錯誤恢復(fù) 發(fā)現(xiàn)錯誤時，分析器每次拋棄一個輸入記號，直到輸入記號屬于某個指定的同步記號集合為止。

自上而下分析非遞歸預(yù)測分析：采用緊急方式的錯誤恢復(fù) 發(fā)現(xiàn)錯誤時，分析器每次拋棄一個輸入記號，直到輸入記號屬于某個指定的同步記號集合為止。同步 詞法分析器當(dāng)前提供的記號流能構(gòu)成的語法結(jié)構(gòu)，正是語法分析器所期望的。

自上而下分析同步記號集合的選擇把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號集合。

自上而下分析同步記號集合的選擇把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號集合。 ifexprthen （then是expr的一個同步記號）

自上而下分析同步記號集合的選擇把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號集合。把高層結(jié)構(gòu)的開始符號加到低層結(jié)構(gòu)的同步記號集合中。

自上而下分析同步記號集合的選擇把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號集合。把高層結(jié)構(gòu)的開始符號加到低層結(jié)構(gòu)的同步記號集合中。

a:=expr;if… （語句的開始符號作為表達(dá)式的同步符號，以免遺漏分號時忽略一大段程序。）

自上而下分析同步記號集合的選擇把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號集合。把高層結(jié)構(gòu)的開始符號加到低層結(jié)構(gòu)的同步記號集合中。把FIRST(A)的終結(jié)符加入A的同步記號集合。

自上而下分析同步記號集合的選擇把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號集合。把高層結(jié)構(gòu)的開始符號加到低層結(jié)構(gòu)的同步記號集合中。把FIRST(A)的終結(jié)符加入A的同步記號集合。如果非終結(jié)符可以產(chǎn)生空串，若出錯時棧頂是這樣的非終結(jié)符，則可以使用產(chǎn)生空串的產(chǎn)生式。

自上而下分析同步記號集合的選擇把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號集合。把高層結(jié)構(gòu)的開始符號加到低層結(jié)構(gòu)的同步記號集合中。把FIRST(A)的終結(jié)符加入A的同步記號集合。如果非終結(jié)符可以產(chǎn)生空串，若出錯時棧頂是這樣的非終結(jié)符，則可以使用產(chǎn)生空串的產(chǎn)生式。如果終結(jié)符在棧頂而不能匹配，彈出此終結(jié)符。

自下而上分析

歸約例 S

aABe

A

Abc|b B

d

自下而上分析

歸約例 S

aABe

A

Abc|b B

dabbcde

自下而上分析

歸約例 S

aABe

A

Abc|b B

dabbcdeaAbcde

自下而上分析

歸約例 S

aABe

A

Abc|b B

dabbcdeaAbcdeaAde

自下而上分析

歸約例 S

aABe

A

Abc|b B

dabbcdeaAbcdeaAdeaABe

自下而上分析

歸約例 S

aABe

A

Abc|b B

dabbcdeaAbcdeaAdeaABeS

自下而上分析

歸約例 S

aABe

A

Abc|b B

dabbcdeaAbcdeaAdeaABeSSrmaABermaAdermaAbcdermabbcde

自下而上分析

句柄 句型的句柄是和某產(chǎn)生式右部匹配的子串，并且，把它歸約成該產(chǎn)生式左部的非終結(jié)符代表了最右推導(dǎo)過程的逆過程的一步。

自下而上分析

句柄 句型的句柄是和某產(chǎn)生式右部匹配的子串，并且，把它歸約成該產(chǎn)生式左部的非終結(jié)符代表了最右推導(dǎo)過程的逆過程的一步。

S

aABe

A

Abc|b B

dSrmaABe

rmaAdermaAbcdermabbcde

自下而上分析

句柄 句型的句柄是和某產(chǎn)生式右部匹配的子串，并且，把它歸約成該產(chǎn)生式左部的非終結(jié)符代表了最右推導(dǎo)過程的逆過程的一步。

S

aABe

A

Abc|b B

dSrmaABe

rmaAdermaAbcdermabbcde句柄的右邊僅含終結(jié)符。

自下而上分析

句柄 句型的句柄是和某產(chǎn)生式右部匹配的子串，并且，把它歸約成該產(chǎn)生式左部的非終結(jié)符代表了最右推導(dǎo)過程的逆過程的一步。

S

aABe

A

Abc|b B

dSrmaABe

rmaAdermaAbcdermabbcde句柄的右邊僅含終結(jié)符。如果文法二義，那么句柄可能不唯一。

自下而上分析例 EE+E|E*E|(E)|id

自下而上分析例 EE+E|E*E|(E)|idErmE*ErmE*

E+ErmE*E+id3 rmE*

id2+id3

rm

id1

*id2+id3

自下而上分析例 EE+E|E*E|(E)|idErmE*E E

rmE+ErmE*

E+E rmE+id3rmE*E+id3 rmE*E

+id3rmE*

id2+id3

rmE*

id2+id3

rm

id1

*id2+id3

rm

id1

*id2+id3

在句型E*E+id3中，句柄不唯一。

自下而上分析3.4.3用棧實(shí)現(xiàn)移進(jìn)歸約分析先通過 移進(jìn)歸約分析器在分析輸入串id1

*id2+id3時的動作序列來了解移進(jìn)歸約分析的工作方式。

自下而上分析棧

輸

入

動

作

$id1

*id2+id3$

自下而上分析棧

輸

入

動

作

$id1

*id2+id3$移進(jìn)

自下而上分析棧

輸

入

動

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$

自下而上分析棧

輸

入

動

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

自下而上分析棧

輸

入

動

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$

自下而上分析棧

輸

入

動

作

$id1

*id2+id3$移進(jìn)

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

自下而上分析棧

輸

入

動

作

$id1

*id2+id3