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

編譯原理Principles

of

Compilers第四章語法分析4.1概述語法分析輸入：為單詞的序列任務(wù)：判斷單詞的序列是否滿足一個上下文無關(guān)文法輸出：一個與單詞序列匹配的語法樹語法分析的一般方法利用一個棧表示識別的狀態(tài)根據(jù)語法樹的生成方式分為自上而下與自下而上的兩種策略4.2

CFG與PDA上下文無關(guān)文法CFG

(

Context-free

Grammar

)產(chǎn)生式的形式為A

，其中A

VN上下文無關(guān)語言CFL

(

Context-free

Language

)一個語言是CFL，當(dāng)且僅當(dāng)存在CFG描述它。4.2

CFG與PDA下推自動機PDA

(

Push

Down

Automata

)帶一個棧的有窮狀態(tài)自動機PDA讀入一個符號，在做狀態(tài)遷移的同時還能夠?qū)＿M行操作是棧式程序的抽象模型CFG與PDA的等價性一個語言是CFL，當(dāng)且僅當(dāng)存在一臺PDA識別它4.2

CFG與PDA下推自動機的應(yīng)用–

例：只使用一個棧與一個狀態(tài)變量，識別語言L

={0n1n

|

n0}算法描述令狀態(tài)變量s=0，從左向右讀入符號，重復(fù)以下如動果作空：棧則ERROR如果s==0，那么如果a為0，則壓入0如果a為1，則彈出一個0，且令如s果=1空棧則ERROR如果s==1，那么如果a為0，則ERROR如果a為1，則彈出一個0如果輸入結(jié)束，那么s==1則接受，否則拒絕。而且棧為空棧4.2

CFG與PDA下推自動機的形式定義一個PDA

M=(Q,

S, ,

q0,

d,

F)，其中：Q為狀態(tài)集為字符集為棧字符集q0

Q為初始狀態(tài)F

Q為接受狀態(tài)集：QP(

Q)，={4.2

CFG與PDAPDA的語言–一個PDA

M=(Q,S,,

q0,

d,

F)接受串

，如果

能夠?qū)懗?=

a1a2…am，ai

，并且存在M的一個狀02…

m，使得：態(tài)序列s0s1…sm與一個棧的串序列s0

=

q0，

0

=，*0

i

m(

(si+1,

b)

(si,

ai+1,

c)

)，其中

i

=

c=

b

，b,

csm

F–M的語言為所有M接受的串的集合4.3自上而下的分析方法一般策略給定一個文法G，判斷一個串a(chǎn)是否屬于G的語言。自上而下的分析方法試圖從文法的開始符號推導(dǎo)出目標串a(chǎn)，如果成功則認為a屬于G的語言。由于該推導(dǎo)過程正好表示對應(yīng)語法樹從上到下的生成過程，因此稱之為自上而下的分析方法。4.3自上而下的分析方法文法G[S]:–

S

0S1

|分析過程令輸入串a(chǎn)=0011分析過程即從S開始試圖推導(dǎo)出0011S

0S1

00S1100110S10

S

1語法樹S4.3.1基于PDA的分析算法基本思想利用PDA的棧來存儲推導(dǎo)的中間結(jié)果。利用PDA的非確定性來“猜測”所有可能的推導(dǎo)。采用最左推導(dǎo)，及時將推導(dǎo)產(chǎn)生出來的最左終結(jié)符與輸入匹配4.3.1基于PDA的分析算法構(gòu)造思想–

給定文法G=(VN,VT,P,S)，構(gòu)造PDA

M=(Q,S,

,q0,d,F)，使M恰好接受G的語言。PDA的分析算法向棧中壓入$S。如果棧頂符號為非終結(jié)符A，則非確定性地用A的所有產(chǎn)生式的右 部替換棧頂?shù)腁。如果棧頂符號為終結(jié)符a，則與輸入符號匹配，如果成功則從棧頂 彈出a，否則該分支進入無定義狀態(tài)（終止）。如果棧頂符號為$，而且輸入符號為$（輸入結(jié)束），則接受，否 則該分支進入無定義狀態(tài)。重復(fù)2,3,4。4.3.1基于PDA的分析算法PDA的構(gòu)造方法給定文法G[S]:S

0S1

|

01構(gòu)造步驟構(gòu)造初始遷移為每一條產(chǎn)生式構(gòu)造對應(yīng)的遷移為每一個終結(jié)符的匹配構(gòu)造對應(yīng)的遷移構(gòu)造猜測成功的遷移2,$S,

S

1S0,

S

103$,

$10,

01,

14.3.1基于PDA的分析算法S$20011$20S1$201$0011$0011$2S1$1$2011$011$2011$0S11$2011$011$211$S11$$2$3211$0S111$接受211$0111$4.3.1基于PDA的分析算法算法特點通用性好抽象層次高算法效率低4.3.2左遞歸的消除直接左遞歸的消除產(chǎn)生式P

P

|改寫為：P

P’，P’P’

|m

|

1

|

2

|

…

|n一般形式的直接左遞歸–

P

P

1

|

P

2

|

…

|

P–改寫為：PP’1P’

|1P’

|2P’

|

…

|

nP’2P’

|

…

|

mP’

|4.3.2左遞歸的消除間接左遞歸S

Qc

|

cQ

Rb

|

bR

Sa

|

a間接左遞歸產(chǎn)生的原因推導(dǎo)串的首個非終結(jié)符存在環(huán)路消除方法：打破可能存在的環(huán)路4.3.2左遞歸的消除間接左遞歸的消除算法將文法中所有非終結(jié)符排列為P1,P2,…,Pnfor

i

:=

1

to

n

dofor

j

:=

1

to

i

–

1

do將形如Pi1|Pj

的產(chǎn)生式改寫為：Pi2k，其中Pj1

||

…

|2

|

…

|

k；消除Pi的直接左遞歸；nextnext4.3.3

LL(k)分析方法概述

向前查看k個符號，以協(xié)助選擇正確的產(chǎn)生式進行推導(dǎo)，從而避免回溯

如果對某一文法不能避免回溯，則LL(k)無法分析該文法LL(1)與LL(2)是最常見的LL分析方法4.3.3

LL(k)分析方法LL(1)算法基本思想將文法的開始符號S壓入棧中從左向右讀輸入符號，重復(fù)以下如果棧頂元素為終結(jié)符，則用與輸入符號a匹配，匹配成功則彈出一個符號，否則ERROR如果棧頂元素為非終結(jié)符A，輸入符號為a，則選擇一條能夠產(chǎn)生首字符a的產(chǎn)生式進行推導(dǎo)，用產(chǎn)生式的右部替換棧中的A空棧，則判斷輸入是否結(jié)束，如果結(jié)束則接受，否則ERROR4.3.3

LL(k)分析方法產(chǎn)生式首字符的判斷方法–利用FIRST函數(shù)以及FOLLOW函數(shù)進行判斷FIRST函數(shù)(VN

VT)*FIRST(*)

=

{

a

|，iff*

a

,

a

VT,FIRST(

)(VNFOLLOW函數(shù)–

FOLLOW(A)

=

{

a

|

SVT)*

}–

如果S

*

A，則令$*

Aa

,

a

VT,

,FOLLOW(A)4.3.3

LL(k)分析方法產(chǎn)生式的選擇方法–假設(shè)棧頂元素為A，輸入符號為a，A1

|

2

|

…|ni如果a

FIRST(

i)

，那么選擇如果i*

(FIRST(

i))，且aFOLLOW(A)，那么選擇i4.3.3

LL(k)分析方法4.3.3

LL(k)分析方法4.3.3

LL(k)分析方法FOLLOW函數(shù)的構(gòu)造計算非終結(jié)符A的FOLLOW(A)，應(yīng)用以下規(guī)則，直到結(jié)果集合不能再增加為止：如果A

=

S，那么令$

FOLLOW(A)如果B

A，那么令FIRST( )

\

{

}如果B

A，或者B

A

，其中FOLLOW(A)FIRST(

)，那么令FOLLOW(B)

FOLLOW(A)4.3.3

LL(k)分析方法預(yù)測分析表FIRST與FOLLOW函數(shù)的計算需要消耗時間，因此需要根據(jù)所有可能，預(yù)先計算出產(chǎn)生式的選擇考慮所有可能的棧頂元素A與輸入符號a構(gòu)造方法構(gòu)造二維分析表M–

如果有產(chǎn)生式A

，且終結(jié)符aFIRST(

)，則將A–如果放入M[A,a]FIRST()

，且b

FOLLOW(A)則將A放入M[A,b]4.3.3

LL(k)分析方法例：表達式文法E E

+

T

|

TT T

*

F

|

FF

(E)

|

i消除左遞歸：E

TE’E’

+TE’

|T

FT’T’

*FT’

|F

(E)

|

iFIRST：FIRST(E)

=

{(,

i}FIRST(E’)

=

{+,

e}FIRST(T)

=

{(,

i}FIRST(T’)

=

{*,

e}FIRST(F)

=

{(,

i

}FOLLOW：FOLLOW(E)

=

{),

$}FOLLOW(E’)

=

{),

$}FOLLOW(T)

=

{+,

),

$}FOLLOW(T’)

=

{+,

),

$}FOLLOW(F)

=

{+,

*,

),

$}4.3.3

LL(k)分析方法LL(1)分析能力的限制–對任意的非終結(jié)符A，A1

i,j

n((FIRST(1

|

2

|…|

n，滿足：i)

FIRST(

j))

i

=

j)(i*

)

j

i(FOLLOW(A)

FIRST(j)

=

)4.4遞歸下降分析方法遞歸下降分析器(Recursive

Descent

Parser)自頂向下分析器(Top-down

Parser)；可以用來分析LL(k)文法；同樣存在左遞歸問題。4.4遞歸下降分析方法遞歸下降分析器設(shè)計每一個非終結(jié)符對應(yīng)一個分析函數(shù)；產(chǎn)生式右部的非終結(jié)符對應(yīng)一次對分析函數(shù)的調(diào)用；產(chǎn)生式右部的終結(jié)符對應(yīng)一次輸入的匹配動作；多條產(chǎn)生式對應(yīng)分析器中的if-then-else。4.4遞歸下降分析方法void

E()

{if

(token

==

‘i‘

||

token

==

‘(‘)

{T();

E1();}

elseerror();}void

E1()

{if

(token

==

‘+’)

{token

=

nextToken();T();

E1();}

else

if

(token

==

‘)’

||

token

==

‘$’);elseerror();}void

T()

{if

(token

==

‘i‘

||

token

==

‘(‘)

{F();

T1();}

elseerror();}void

T1()

{if

(token

==

‘*’)

{token

=

nextToken();F();

T1();}

else

if

(token

==

‘)’

||

token

==

‘$’||

token

==

‘+’);elseerror();}void

F()

{if

(token

==

‘(‘)

{token

==

nextToken();E();if

(token

==

‘)’)token

=

nextToken();elseerror();}

else

if

(token

==

‘i‘)token

=

nextToken();elseerror();}4.5

LR分析方法移入與歸約與LL(k)分析方法中的匹配與推導(dǎo)動作相對應(yīng)移入動作將輸入的符號壓入分析棧中歸約動作推導(dǎo)的逆過程將棧頂?shù)漠a(chǎn)生式右部彈出，壓入產(chǎn)生式的左部4.5

LR分析方法自下而上的分析方法從輸入串開始，試圖歸約到文法識別（開始）符號的分析方法一般策略利用一個棧保存歸約的中間結(jié)果從左向右讀輸入串

如果棧內(nèi)存在可歸約的串，則歸約，否則移入當(dāng)前的輸入符號

如果輸入結(jié)束，而且棧內(nèi)只剩下文法的識別符號，則接受該輸入，否則拒絕。4.5.1基于PDA的分析方法PDA分析方法的基本思路利用非確定性，隨時猜測棧頂是否出現(xiàn)了某個產(chǎn)生式的右部的串，同時猜測是否可以壓入當(dāng)前的輸入符號猜測的過程：非確定性的選擇一條產(chǎn)生式，按照逆序彈出棧內(nèi)對應(yīng)的符號隨時猜測輸入是否結(jié)束4.5.1基于PDA的分析方法例：文法S

0S1

|改寫文法，增加一條產(chǎn)生式：S’

S非確定性地選擇：移入當(dāng)前輸入的符號

選擇一條產(chǎn)生式進行歸約4.5.1基于PDA的分析方法PDA分析方法的缺點非確定性帶來的效率問題如何解決非確定性？選擇“正確”的產(chǎn)生式進行歸約，如果沒有“正確”的產(chǎn)生式，則移入輸入的符號所謂“正確”的產(chǎn)生式被稱為句柄(handle)4.5.2

LR(0)分析方法LR(k)方法的基本思路–判斷棧頂是否出現(xiàn)了句柄，如果有句柄則歸約，否則移入。句柄的定義：–如果文法G中存在產(chǎn)生式AT，而且S，其中

V

*，則稱

為句型*

A的句柄。簡單的說，句柄代表最后一次最右直接推導(dǎo)（最左歸約）如何判斷句柄？判斷句柄需要對整個輸入串進行分析，畫出語法樹4.5.2

LR(0)分析方法LR(0)方法的基本思路只要產(chǎn)生式的右部出現(xiàn)在棧頂，則認為它是句柄；構(gòu)造一個FA

H，識別所有的活前綴以及產(chǎn)生式的右部；模擬FA

H的運行，如果FA

H到達接受狀態(tài)，則歸約，否則移入。LR(0)項目FA

H的狀態(tài)稱為一個LR(0)項目，其一般形式為A，表示句柄的識別狀態(tài)，其中

已經(jīng)輸入到H中，H期待

的繼續(xù)輸入。4.5.2

LR(0)分析方法FA

H的運行方式–所有進棧的符號被看作H的輸入符號，包括句柄歸約得到的非終結(jié)符；–

如果當(dāng)前項目為A遷移到項目A

XX

，X

VN

VT，那么接收輸入X后；–

如果當(dāng)前項目為A

B

，B那么H可以通過空轉(zhuǎn)移到項目BVN，而且B1，B1|

2|…|

n，2，…

Bn–如果當(dāng)前項目為A，那么將歸約為A，H退回到原先準備接收A的狀態(tài)，而且將A輸入到H中。DFA

H的構(gòu)造–從初始項目開始構(gòu)造確定化的FA

H。4.5.2

LR(0)分析方法FA

H的運行方式AXX……XAX……4.5.2

LR(0)分析方法FA

H的運行方式AB……4.5.2

LR(0)分析方法FA

H的運行方式AB……B4.5.2

LR(0)分析方法FA

H的運行方式AB……B4.5.2

LR(0)分析方法FA

H的運行方式AB…B…4.5.2

LR(0)分析方法FA

H的運行方式……AB…4.5.2

LR(0)分析方法FA

H的運行方式……ABB…4.5.2

LR(0)分析方法FA

H的運行方式……ABB…B4.5.2

LR(0)分析方法FA

H的運行方式……ABB…B4.5.2

LR(0)分析方法FA

H的運行方式……ABB…BAB4.5.2

LR(0)分析方法DFA

H的構(gòu)造構(gòu)造NFA的初始狀態(tài)（項目）S’

S對NFA的初始狀態(tài)做閉包（

-Closure），求DFAH的初始狀態(tài)（初始項目集）由DFA

H的一個狀態(tài)中的項目求出一個新項目，再求

-Closure得到新狀態(tài)反復(fù)以上直到不能求出新狀態(tài)為止的狀態(tài)（歸–DHA

H的接受狀態(tài)：包含項目A約項目）4.5.2

LR(0)分析方法例–

1.

S’

E2.

E

aB3.

E

bA4.

A

cA5.

A

d6.

B

cB7.

B

d4.5.2

LR(0)分析方法XLR(0)分析方法中的沖突項目類型：歸約項目，形如A移入項目，形如A歸約與歸約的沖突一個狀態(tài)（項目集）中包含多個歸約項目移入與歸約的沖突一個狀態(tài)中同時包含歸約項目與移入項目4.5.2

LR(0)分析方法LR(0)分析器的運行1.壓入初始狀態(tài)：-Closure(S’

S)；如果棧頂狀態(tài)為歸約項目，則歸約，否則：如果當(dāng)前狀態(tài)接受輸入符號，則移入當(dāng)前輸入符號；否則報錯；如果S被歸約為S’，且輸入結(jié)束，則接受輸入串，否則報錯；Goto

2。4.5.2

LR(0)分析方法預(yù)測分析表ab$I0s2s3I1r1r1r1I2s0I3r2r2r2ABEs1s14.5.2

LR(0)分析方法LR(0)分析預(yù)測分析表的生成歸約狀態(tài)i:

A

[m]在第i行的所有單元格上填上rmX

,

j:

AX移入狀態(tài)i:A在第i行第X列填上sj其它空白處為錯誤4.5.3

SLR(1)分析方法例E E

+

T

|

TT T

*

F

|

FF

(E)

|

i4.5.3

SLR(1)分析方法SLR(1)方法的基本思路–在某一個產(chǎn)生式右部出現(xiàn)時，在輸入中向前看一個符號，以輔助句柄的判斷；–如果輸入符號為a，產(chǎn)生式A么當(dāng)a

FOLLOW(A)的時候，認為出現(xiàn)在棧頂，那為句柄。4.5.4

LR(1)分析方法SLR(1)的局限：