編譯原理課件：第四章 語法分析2

詞法單元：記號名、屬性、詞素、模式正則表達式、正則定義狀態(tài)轉(zhuǎn)換圖有限自動機不確定有限自動機（NFA）確定有限自動機（DFA）正則式NFADFA最簡DFA正則式DFALex工具第三章復(fù)習(xí)期中考試

11月19日：15:00~17:00

文思209、2082編譯原理第四章語法分析第四章語法分析本章內(nèi)容上下文無關(guān)文法自上而下分析和自下而上分析圍繞分析器的自動生成展開詞法分析器記號取下一個記號源程序分析樹前端的其余部分分析器中間表示符號表4.1上下文無關(guān)文法4.1.1上下文無關(guān)文法的定義正則式能定義一些簡單的語言，能表示給定結(jié)構(gòu)的固定次數(shù)的重復(fù)或者沒有指定次數(shù)的重復(fù) 例：a(ba)5,a(ba)*正則式不能用于描述配對或嵌套的結(jié)構(gòu) 例1：配對括號串的集合 例2：{wcw|w是a和b的串}

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

: 終結(jié)符集合VN

: 非終結(jié)符集合S: 開始符號，非終結(jié)符中的一個P

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

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

expr

op

expr expr(expr)expr

expr expr

idop+ op

4.1上下文無關(guān)文法簡化表示expr

expr

op

expr |

(expr)|

expr|idop+|簡化表示E

EAE|(E)|E|idA+|4.1上下文無關(guān)文法文法書寫上的約定終結(jié)符字母表中的小寫字母，如a，b，c黑體串，如id,while數(shù)字0,1,…,9標點符號，如括號，逗號等運算符號，如+,-等非終結(jié)符字母表中的大寫字母，如A,B,C字母S，并且通常代表開始符號小寫字母的名字（斜體），如expr,stmt4.1上下文無關(guān)文法文法書寫上的約定字母表中后面的大寫字母，如X，Y，Z，可以是終結(jié)符或非終結(jié)符字母表中后面的小寫字母，如u，v

…z可代表終結(jié)符號串小寫希臘字母，如a，b，可代表文法的符號串對于Aa1，Aa2，...

Aan可以寫成

Aa1|a2|…

|an4.1上下文無關(guān)文法4.1.2

推導(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)概念 S*、S+w

，于是**

b，且b

γ,則*

γ

4.1上下文無關(guān)文法4.1.2

推導(dǎo)概念 上下文無關(guān)語言A→γ,且a、b是任意符號串，則aAb

aγb由上下文無關(guān)文法生成的語言是上下文無關(guān)語言等價的文法如果兩個文法產(chǎn)生同樣的語言，則兩個文法等價句型文法G的開始符為S，S*，可能含有非終結(jié)符，則叫做文法G的句型。4.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) E rm

Erm

(E)rm

(E+E)

rm

(E+id)rm(id+id)4.1上下文無關(guān)文法4.1.3分析樹例E

E+E|E

E|(E)|

E|idEE()EEE+idid4.1上下文無關(guān)文法4.1.4二義性 E

E

E

E

E+E idE

E

E+E

id

E+E id

E+E

idid+E idid+E idid+id idid+id 兩個不同的最左推導(dǎo)4.1上下文無關(guān)文法4.1.4二義性 E

E

E

E

E+E idE

E

E+E

id

E+E id

E+E

idid+E idid+E idid+id idid+id 兩棵不同的語法樹EEE*+EEidididEEidE*+EEidid4.2語言和文法文法的優(yōu)點

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

語言和文法4.2.1

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

a

A0|bA0|a

A1A1

b

A2A2

12開始a0abb4.2

語言和文法4.2.2分離詞法分析器理由為什么要用正則式定義詞法

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

語言和文法從軟件工程角度看，詞法分析和語法分析的分離有如下好處簡化設(shè)計編譯器的效率會改進編譯器的可移植性加強便于編譯器前端的模塊劃分4.2

語言和文法能否把詞法分析并入到語法分析中，直接從字符流進行語法分析若把詞法分析和語法分析合在一起，則必須將語言的注解和空白的規(guī)則反映在文法中，文法將大大復(fù)雜注解和空白由自己來處理的分析器，比注解和空格已由詞法分析器刪除的分析器要復(fù)雜得多4.2

語言和文法4.2.3

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

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

語言和文法4.2.3

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

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

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

S(S)S*(x)S*(x)y4.2

語言和文法4.2.3

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

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

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

1)的w=(x)y

S(S)S*(x)S*(x)y4.2

語言和文法4.2.4適當?shù)谋磉_式文法用一種層次觀點看待表達式 idid(id+id)+idid+id4.2

語言和文法4.2.4適當?shù)谋磉_式文法用一種層次觀點看待表達式

idid(id+id)+idid+id

id

id

(id+id)

文法 expr

expr+term|term term

term

factor|factor

factor

id|(expr)4.2

語言和文法expr

expr+term|termterm

term

factor|factor

factor

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

ididid分析樹

4.2

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

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

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

stmtifexprthenstmt

ifexprthenifexprthenstmtelsestmt

stmtifexprthenstmtelsestmt

ifexprthenifexprthenstmtelsestmt

4.2

語言和文法

無二義的文法stmt

matched_stmt

|unmatched_stmtmatched_stmt

ifexprthenmatched_stmt

elsematched_stmt

|otherunmatched_stmt

ifexprthenstmt |ifexprthenmatched_stmt

elseunmatched_stmt上節(jié)復(fù)習(xí)上下文無關(guān)文法是四元組（VT,VN,S,P）VT

: 終結(jié)符集合VN

: 非終結(jié)符集合S: 開始符號，非終結(jié)符中的一個P

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

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

expr

op

expr expr(expr)expr

expr expr

idop+ op

上節(jié)復(fù)習(xí)例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) E rm

Erm

(E)rm

(E+E)

rm

(E+id)rm(id+id)上節(jié)復(fù)習(xí)二義性 E

E

E

E

E+E idE

E

E+E

id

E+E id

E+E

idid+E idid+E idid+id idid+id 兩棵不同的語法樹EEE*+EEidididEEidE*+EEidid上節(jié)復(fù)習(xí)正則式和上下文無關(guān)文法的比較正則式(a|b)*ab文法A0

a

A0|bA0|a

A1A1

b

A2A2

12開始a0abb4.2

語言和文法4.2.6消除左遞歸消除左遞歸AA

α|βAβRRαR|ε4.2

語言和文法4.2.6消除左遞歸文法左遞歸 A+Aa

直接左遞歸 AAa|b

串的特點 ba...a消除直接左遞歸 A

bA A

aA|

4.2

語言和文法例

算術(shù)表達文法

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)|id4.2

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

Aa|b

A

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

Aa|b A

Aad|bd|

再消除左遞歸

SAa|b A

bdA

|A A

adA

|4.2

語言和文法4.2.7

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

1|2提左因子 A

A A

1|2

4.2

語言和文法例

懸空else的文法 stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other 提左因子

stmt

ifexprthenstmt

optional_else_part |other

optional_else_partelsestmt |4.2

語言和文法4.2.8

非上下文無關(guān)的語言構(gòu)造L1={wcw|w屬于(a|b)*}標識符的聲明應(yīng)先于其引用的抽象

L2={anbmcndm|n

0,m

0}形參個數(shù)和實參個數(shù)應(yīng)該相同的抽象

L3={anbncn|n

0}早先排版描述的一個現(xiàn)象的抽象

b

e

g

i

n：5個字母鍵，5個回退鍵，5個下劃線鍵4.2

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

SaSa|bSb|c

L2={anbmcmdn|n

1,m

1}

SaSd|aAd AbAc|bcL

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

BcBd|cd4.2

語言和文法L3

={anbn|n

1}

SaSb|abL3是不能用正則式描述的語言的一個范例

若存在接受L3的DFAD，狀態(tài)數(shù)為k個設(shè)D讀完,

a,aa,

…,ak

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

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

si…fs0標記為ai的路徑標記為bi的路徑標記為aji的路徑…

…4.2

語言和文法4.2.9

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

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

語言和文法4.2.9

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

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

語言和文法4.2.9

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

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

語言和文法4.2.9

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

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

語言和文法4.2.9

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

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

語言和文法4.2.9

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

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

語言和文法4.2.9

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

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