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

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

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

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

{wcw|w是a和b的串}

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

: 終結(jié)符集合VN

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

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

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

expr

op

expr expr(expr)expr

expr expr

idop+ op

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

expr

op

expr expr(expr)expr

expr expr

idop+ op

*簡(jiǎn)化表示E

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

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

E+E|E

*

E|(E)|

E|id

E

E

(E)

(E+E)

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

3.1上下文無(wú)關(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上下文無(wú)關(guān)文法3.1.3分析樹EEEEE()EEE()EEE+EE()EEE+idEE()EEE+idid3.1上下文無(wú)關(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上下文無(wú)關(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ǔ)言和文法

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

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

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

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

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

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

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

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

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

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

語(yǔ)言和文法

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

語(yǔ)言和文法

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

語(yǔ)言和文法

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

a

A0|bA0|a

A1A1

b

A2A2

12開始a0abb

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

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

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

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

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

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

語(yǔ)言和文法把詞法分析從語(yǔ)法分析中分離出來(lái)的理由

簡(jiǎn)化設(shè)計(jì)

語(yǔ)言和文法把詞法分析從語(yǔ)法分析中分離出來(lái)的理由

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

語(yǔ)言和文法把詞法分析從語(yǔ)法分析中分離出來(lái)的理由

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

語(yǔ)言和文法把詞法分析從語(yǔ)法分析中分離出來(lái)的理由

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

語(yǔ)言和文法

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

(S)S|L(G)=配對(duì)的括號(hào)串的集合

語(yǔ)言和文法

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

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

語(yǔ)言和文法

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

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

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

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

語(yǔ)言和文法

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

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

語(yǔ)言和文法

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

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

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

1)的w=(x)y

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

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

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

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

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

id

*

id

*

(id+id)

語(yǔ)言和文法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

語(yǔ)言和文法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

語(yǔ)言和文法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)

語(yǔ)言和文法 expr

expr+term|term term

term

*factor|factor

factor

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

語(yǔ)言和文法3.2.5消除二義性stmt

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

elsestmt

語(yǔ)言和文法3.2.5消除二義性stmt

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

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

stmtifexprthenstmt

ifexprthenifexprthenstmtelsestmt

語(yǔ)言和文法3.2.5消除二義性stmt

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

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

stmtifexprthenstmt

ifexprthenifexprthenstmtelsestmt

stmtifexprthenstmtelsestmt

ifexprthenifexprthenstmtelsestmt

語(yǔ)言和文法

無(wú)二義的文法stmt

matched_stmt

|unmatched_stmtmatched_stmt

ifexprthenmatched_stmt

elsematched_stmt

|otherunmatched_stmt

ifexprthenstmt |ifexprthenmatched_stmt

elseunmatched_stmt

語(yǔ)言和文法3.2.6消除左遞歸文法左遞歸 A*Aa

語(yǔ)言和文法3.2.6消除左遞歸文法左遞歸 A*Aa

直接左遞歸 AAa|b

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

語(yǔ)言和文法3.2.6消除左遞歸文法左遞歸 A*Aa

直接左遞歸 AAa|b

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

bA A

aA|

語(yǔ)言和文法例

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

E

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

T

*

F|F （F

*

F...*

F） F

(E)|id

語(yǔ)言和文法例

算術(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

語(yǔ)言和文法非直接左遞歸 S

Aa|b

A

Ac|Sd|

語(yǔ)言和文法非直接左遞歸 S

Aa|b

A

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

Aa|b A

Aad|bd|

語(yǔ)言和文法非直接左遞歸 S

Aa|b

A

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

Aa|b A

Aad|bd|

再消除左遞歸

SAa|b A

bdA

|A

A

adA

|

語(yǔ)言和文法

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

1|2

語(yǔ)言和文法

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

1|2提左因子 A

A A

1|2

語(yǔ)言和文法例

懸空else的文法 stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other

語(yǔ)言和文法例

懸空else的文法 stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other 提左因子 stmt

ifexprthenstmt

optional_else_part |other optional_else_partelsestmt |

語(yǔ)言和文法

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

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

語(yǔ)言和文法

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

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

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

語(yǔ)言和文法

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

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

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

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

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

SaSa|bSb|c

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

SaSa|bSb|c

L2={anbmcmdn|n1,m1}

SaSd|aAd AbAc|bc

語(yǔ)言和文法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

語(yǔ)言和文法L3

={anbn|n

1}

SaSb|ab

語(yǔ)言和文法L3

={anbn|n

1}

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

語(yǔ)言和文法L3

={anbn|n

1}

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

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

語(yǔ)言和文法L3

={anbn|n

1}

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

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

設(shè)D讀完,

a,aa,

…,ak

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

…,sk

語(yǔ)言和文法L3

={anbn|n

1}

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

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

設(shè)D讀完,

a,aa,

…,ak

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

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

語(yǔ)言和文法L3

={anbn|n

1}

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

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

設(shè)D讀完,

a,aa,

…,ak

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

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

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

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

語(yǔ)言和文法

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

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

語(yǔ)言和文法

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

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

語(yǔ)言和文法

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

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

語(yǔ)言和文法

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

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

語(yǔ)言和文法

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

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

語(yǔ)言和文法

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

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

語(yǔ)言和文法

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

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

短語(yǔ)文法、上下文有關(guān)文法、上下文無(wú)關(guān)文法

語(yǔ)言和文法

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

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

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

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

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

cc

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

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

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

語(yǔ)言和文法例：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

語(yǔ)言和文法例：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

語(yǔ)言和文法例：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

語(yǔ)言和文法例：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

語(yǔ)言和文法例：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

語(yǔ)言和文法例：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)致語(yǔ)義工作推倒重來(lái)

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

文法 S

aCb C

cd|c

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

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

文法 S

aCb C

cd|c

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

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

)={a|

*a…,a

VT}

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

)={a|

*a…,a

VT} 特別是，

*時(shí)，規(guī)定

FIRST(

)

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

)={a|

*a…,a

VT} 特別是，

*時(shí)，規(guī)定

FIRST(

) 對(duì)A的任何兩個(gè)不同的選擇i

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

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

)={a|

*a…,a

VT} 特別是，

*時(shí)，規(guī)定

FIRST(

) 對(duì)A的任何兩個(gè)不同的選擇i

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

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

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

)={a|

*a…,a

VT} 特別是，

*時(shí)，規(guī)定

FIRST(

)FOLLOW(A)={a|S

*…Aa…，aVT}

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

)={a|

*a…,a

VT} 特別是，

*時(shí)，規(guī)定

FIRST(

)FOLLOW(A)={a|S

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

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

)FIRST()=；若

*

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

自上而下分析LL(1)文法 任何兩個(gè)產(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ù)測(cè)分析為每一個(gè)非終結(jié)符寫一個(gè)分析過程這些過程可能是遞歸的例： type

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

自上而下分析一個(gè)輔助過程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ù)測(cè)分析a+b$輸入預(yù)測(cè)分析程序分析表M輸出

XYZ$棧

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

入

符

號(hào)

id

+*

...EE

TE

E

E

+TE

T

T

FT

T

T

T

*FTF

F

id

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

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

*

id+id的動(dòng)作

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

$ET

id*id+id$

E

TE

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

*

id+id的動(dòng)作

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

$ET

id*id+id$

E

TE

$ETF

id*id+id$

T

FT

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

*

id+id的動(dòng)作

自上而下分析棧

輸

入

輸

出

$E

id*id+id$

$ET

id*id+id$

E

TE

$ETF

id*id+id$

T

FT

$ETid

id*id+id$

F

id

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

*

id+id的動(dòng)作

自上而下分析棧

輸

入

輸

出

$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ù)測(cè)分析器接受輸入id

*

id+id的動(dòng)作

自上而下分析棧

輸

入

輸

出

$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ù)測(cè)分析器接受輸入id

*

id+id的動(dòng)作

自上而下分析棧

輸

入

輸

出

$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ù)測(cè)分析器接受輸入id

*

id+id的動(dòng)作

自上而下分析棧

輸

入

輸

出

$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ù)測(cè)分析器接受輸入id

*

id+id的動(dòng)作

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

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

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

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

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

輸

入

符

號(hào)

other

b

else

...stmtstmt

other

e_part

e_part

elsestmte_part

expr

exprb

多重定義的條目

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

輸

入

符

號(hào)

other

b

else

...stmtstmt

other

e_part

e_part

elsestmtexpr

exprb

多重定義的條目

自上而下分析

預(yù)測(cè)分析的錯(cuò)誤恢復(fù)先對(duì)編譯器的錯(cuò)誤處理做一個(gè)概述

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

自上而下分析

預(yù)測(cè)分析的錯(cuò)誤恢復(fù)先對(duì)編譯器的錯(cuò)誤處理做一個(gè)概述

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

自上而下分析

預(yù)測(cè)分析的錯(cuò)誤恢復(fù)先對(duì)編譯器的錯(cuò)誤處理做一個(gè)概述

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

自上而下分析

預(yù)測(cè)分析的錯(cuò)誤恢復(fù)先對(duì)編譯器的錯(cuò)誤處理做一個(gè)概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

自上而下分析同步記號(hào)集合的選擇把FOLLOW(A)的所有終結(jié)符放入非終結(jié)符A的同步記號(hào)集合。把高層結(jié)構(gòu)的開始符號(hào)加到低層結(jié)構(gòu)的同步記號(hào)集合中。把FIRST(A)的終結(jié)符加入A的同步記號(hào)集合。如果非終結(jié)符可以產(chǎn)生空串，若出錯(cuò)時(shí)棧頂是這樣的非終結(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時(shí)的動(dòng)作序列來(lái)了解移進(jìn)歸約分析的工作方式。

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3$

自下而上分析棧

輸

入

動(dòng)

作

$id1

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

自下而上分析棧

輸

入

動(dòng)

作

$id1

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

$id1

*

id2+id3$

自下而上分析棧

輸

入

動(dòng)

作

$id1

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

$id1

*

id2+id3$按E

id歸約

自下而上分析棧

輸

入

動(dòng)

作

$id1

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

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$

自下而上分析棧

輸

入

動(dòng)

作

$id1

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

$id1

*

id2+id3$按E

id歸約

$E

*

id2+id3$移進(jìn)

自下而上分析棧

輸

入

動(dòng)

作

$id1

*id2+id3