語法分析(共99張PPT)

第四章語法分析1第一頁，共99頁。4.5自底向上分析移進歸約分析法(Shift-reduceparsing)一般的移進歸約法－LRparsingLR(0)SLRLR(1)LALR自動的語法分析器的生成器（YACC）2第二頁，共99頁。4.5.1歸約例考慮文法S

aABe

A

Abc|bB

d句子abbcde的歸約步驟如下：abbcdeaAbcdeaAdeaABeS對應最右推導的逆過程：S

rm

aABe

rm

aAde

rm

aAbcde

rm

abbcdeSaABedAb

cb3第三頁，共99頁。句柄(handles)句柄是最左直接短語。右句型的句柄是產(chǎn)生式A和中的子串，且用A

代替得到的仍是右句型i.e.Aisahandleofwatthelocationimmediatelyaftertheendof,if:句柄的右邊僅含終結符。SAw4第四頁，共99頁。短語和句柄設有上下文無關文法G=(VT,VN,S,P)，串是文法G的句型，若有A+，且串A也是文法G的句型，則稱是句型中關于非終結符號A的短語。若A

，則稱為直接短語。最左直接短語稱為句柄(handle)。5第五頁，共99頁。ExampleS

aABe

aAdeaAbcdeabbcde考慮文法S

aABe

A

Abc|bB

dItfollowsthat:

Ab

isahandleofabbcdeinlocation2.rmrmrmrmSaABedAb

cb6第六頁，共99頁。ExampleS

aABe

aAdeaAbcdeabbcdeItfollowsthat:

AAbc

isahandleofaAbcdeinlocation2.rmrmrmrmSaABedAb

c考慮文法S

aABe

A

Abc|bB

d7第七頁，共99頁。ExampleS

aABe

aAdeaAbcdeabbcdeItfollowsthat:

Bd

isahandleofaAdeinlocation3.rmrmrmrmSaABed考慮文法S

aABe

A

Abc|bB

d8第八頁，共99頁。ExampleS

aABe

aAdeaAbcdeabbcdeItfollowsthat:S

aABe

isahandleofaABe

inlocation1.rmrmrmrmSaABe考慮文法S

aABe

A

Abc|bB

d9第九頁，共99頁。

例4.22 E

E+E|E*E|(E)|id如果文法二義，那么句柄可能不唯一。在句型E+E*id3中，句柄不唯一。E

rmE+E

rm

E+E*E

rm

E+E*id3

rm

E+id2*id3

rm

id1+id2*id3E

rmE*E

rm

E*id3

rm

E+E*id3rm

E+id2*id3

rm

id1+id2*id3

10第十頁，共99頁。4.5.2句柄剪枝(HandlePruning)Arightmostderivationinreversecanbeobtainedby“handle-pruning.”從被分析的終結符號串w開始，如果w是文法的句子，那么記w=n，其中n是最右推導的第n步句型：構造最右推導的逆過程，在n中找句柄進行歸約得到右句型n-1。11第十一頁，共99頁。例右句型句柄歸約產(chǎn)生式id1

＋id2*id3E

＋id2*id3E

＋E*id3E

＋E*E

E

＋EEid1id2id3E*EE+E

E

id

E

id

E

id

E

E*E

E

E+E12第十二頁，共99頁。分析過程的特點從輸入串的開頭依次讀入(移進)單詞。一旦發(fā)現(xiàn)可歸約串(在上例中是句柄)就立即歸約。根據(jù)句柄對分析樹進行修剪子樹，剪去子樹的葉子。若最終能歸約成文法的開始符號，則分析成功。由于總是將句型的最左邊的可歸約串替換成非終結符號，該歸約方法通常得到是最右推導的逆過程。13第十三頁，共99頁。4.5.3用棧實現(xiàn)移進歸約分析必須解決兩個問題確定右句型中將要歸約的子串（句柄）如何確定選擇哪一個產(chǎn)生式一般方法用棧保存文法符號輸入緩沖區(qū)存放待分析的串移進(shift)輸入符號入棧，直至棧頂出現(xiàn)句柄歸約(reduce)句柄，用產(chǎn)生式左部的非終結符替代棧中的句柄14第十四頁，共99頁。棧輸入

動作

$id1+id2*id3$移進

$id1

+id2*id3$按E

id歸約

$E

+id2*id3$移進

$E+

id2*id3$移進

$E+id2

*id3$按E

id歸約

$E+E

*id3$移進

$E+E*

id3$移進

$E+E*id3

$按E

id歸約

$E+E*E

$按E

E*E歸約

$E+E

$按E

E+E歸約

$E

$接受例15第十五頁，共99頁。初始狀態(tài)格局

棧 輸入

$ w$接受狀態(tài)格局 棧 輸入

$S $16第十六頁，共99頁。動作有四種動作移進：把下一個輸入符號移進棧頂歸約：在棧中確定句柄，選擇正確的非終結符替代句柄接受報錯17第十七頁，共99頁。句柄總會出現(xiàn)在棧頂，而不會在棧的里面。考察任意最右推導中連續(xù)兩步的可能形式：18第十八頁，共99頁。假設當前狀態(tài)格局為：

棧 輸入

$

yz$把句柄歸約為B，達到狀態(tài)格局： 棧 輸入

$B

yz$移進y入棧中，達到格局： 棧 輸入

$By

z$棧頂形成句柄By，歸約為A，達到狀態(tài)格局： 棧 輸入

$A

z$SAzBy19第十九頁，共99頁。假設當前狀態(tài)格局為：

棧 輸入

$

xyz$把句柄歸約為B，達到狀態(tài)格局： 棧 輸入

$B

xyz$移進x,y入棧中，達到格局： 棧 輸入

$Bxy

z$棧頂句柄y歸約為A，達到狀態(tài)格局： 棧 輸入

$Bx

z$SzBxAy20第二十頁，共99頁。4.5.4活前綴(Viableprefix)出現(xiàn)在移進歸約分析器棧中的右句型的前綴集合稱為活前綴?；钋熬Y是右句型的前綴，不含右句柄之后的任何符號?；钋熬Y后加上終結符可以得到右句型。只有輸入串中已分析過的那部分能歸約成活前綴，就沒有語法錯誤。21第二十一頁，共99頁。4.5.5沖突(Conflicts)如果形成這樣的格局：根據(jù)棧中的內(nèi)容和下一個輸入符號不能決定是移進還是歸約（移進歸約沖突），或不能決定用那一條產(chǎn)生式進行歸約（歸約歸約沖突）。22第二十二頁，共99頁。移進歸約沖突例stmt

ifexpr

thenstmt |ifexpr

thenstmt

elsestmt |other存在移進歸約沖突。一般地，任何二義性文法都不是LR(k)文法。假設當前狀態(tài)格局為：

棧 輸入

…if

expr

then

stmt

else…$23第二十三頁，共99頁。歸約歸約沖突例4.26關于過程調(diào)用和數(shù)組引用的下標的文法stmt

id(parameter_list)|expr:=exprparameter_list

parameter_list,parameter|parameterparameter

idexpr

id(expr_list)|idexpr_list

expr_list,expr|expr24第二十四頁，共99頁。例4.26關于過程調(diào)用和數(shù)組引用的下標的文法考察輸入串A(I,J)，對應記號流形式id(id,id)。

假設當前狀態(tài)格局為：

棧 輸入

…id(id

,id…$Reduce/ReduceConflict…whattodo?

(itreallydependsonwhatisA,anarray?oraprocedure?25第二十五頁，共99頁。4.6LR語法分析器本節(jié)介紹LR(k)分析技術“L”：left-to-rightscanning自左向右掃描“R”：rightmostderivationinreverse最右推導的逆“k”

：thenumberofinputsymbolsoflookahead，when(k)isomitted,kisassumedtobe126第二十六頁，共99頁。LR分析器的特點通用適用面廣效率高27第二十七頁，共99頁。LR分析器的特點通用一般的移進歸約法適用面廣適合大多數(shù)的上下文無關文法效率高實用28第二十八頁，共99頁。4.6.2LR(0)項目（Item）在產(chǎn)生式右部加上‘·’，表示分析過程中的狀態(tài),指示產(chǎn)生式右部符號已經(jīng)被識別了多少‘·’之前的子串已經(jīng)出現(xiàn)在棧中‘·’之后的子串是下一步將看到的在文法產(chǎn)生式右部某個位置標有‘·’的產(chǎn)生式，稱為文法的一個LR(0)項目。形如A·

的項目稱為歸約項目；形如A·B

的項目稱為待約項目(基本項目)；形如A·a

的項目稱為移進項目。29第二十九頁，共99頁。LR(0)項目例如，產(chǎn)生式AXYZ對應四個項目：A·XYZAX·YZAXY·ZAXYZ·注意，產(chǎn)生式A只對應一個項目：A·30第三十頁，共99頁。FOLLOW(E)={$,+,)}E+T*F可行前綴是一個右句型的前綴，且該前綴沒有越過該句型的句柄的右端。若I是文法G的一個LR(0)項目集，X是G中的文法符號，定義轉移函數(shù)

goto(I,X)=closure(J)functiongoto(I,X)“R”：rightmostderivationinreverse最右推導的逆|other第六十五頁，共99頁。移進之后(s0s1s2…sms,ai+1…an$)若項目集I={[EE·],[EE·+T]}，計算goto(I,+)得到以下項目集：

EE+·TI6:=goto(I1,+)closure(I)僅包含上述兩條規(guī)則確定的LR(0)項目。構造最右推導的逆過程，在n中找句柄進行歸約得到右句型n-1。+id2*id3$從DFA構造SLR分析表end

elseifaction[s,a]=“reduceA”thenbegin

從棧頂彈出||個符號；LR(0)項目集族對文法G，構造一個有限自動機，它能識別G的所有活前綴。在這個基礎上，把自動機轉變成LR分析表。NFA/DFA首先構造一個NFA，它能識別G的所有活前綴。NFA的狀態(tài)是下面定義的一個“項目”。31第三十一頁，共99頁。增廣文法對文法G[S]增加S’

SS’S·

是唯一動作為accept的狀態(tài)。

32第三十二頁，共99頁。閉包運算closure項目閉包：設I是文法G的一個LR(0)項目集合，I的項目閉包closure(I)定義如下：Iclosure(I)若項目A·Bclosure(I)，且B

是G的產(chǎn)生式，則項目B·closure(I)closure(I)僅包含上述兩條規(guī)則確定的LR(0)項目。33第三十三頁，共99頁。functionclosure(I)begin

j:=I;

repeat

foreachA·BinJandeachproduction

BofGsuchthatB·isnotinJdoADDB·toJ

untilnomoreitemscanbeaddedtoJ

return

Jendclosure的計算34第三十四頁，共99頁。E'

EE

E

+

T|TTT

*

F|FF(

E

)|id如果I

是項目集合[E'

·E]，那么closure(I)包括下列項目：E'

·EE

·E+T

E

·TT·T*F

T·FF·(E)F·id例4.26考慮拓廣的表達式文法：35第三十五頁，共99頁。核心項目和非核心項目可以把項目集中的項目分為兩類：核心項目(Kernelitems)：初始項S'

·S和所有點不在左端的項目非核心項目(Non-kernelitems)：點在左端的非初始項目非核心項目可以通過求核心項目集的閉包得到。36第三十六頁，共99頁。轉移函數(shù)goto若I是文法G的一個LR(0)項目集，X是G中的文法符號，定義轉移函數(shù)

goto(I,X)=closure(J)

其中

J={AX·|A·XI}項目AX·稱為項目A·X的后繼。如果I是對某個活前綴的有效項目集，那么goto(I,X)是對活前綴X的有效項目集。37第三十七頁，共99頁。例若項目集I={[E

E·],[EE·+T]}，計算goto(I,+)得到以下項目集：

EE+·

T

T·

T*F

T·

F

F·(E)

F·

id

38第三十八頁，共99頁。function

goto(I,X)beginletJbethesetofitems[AX·]suchthat[A·X]isinI;

return

closure(J)end

goto的計算39第三十九頁，共99頁。procedure

items(G')begin

C:={closure[S'·

S]}repeatfor

C

的每個項目集I

和每個文法符號X

若goto(I,X)isnotemptyandnotinC doaddgoto(I,X)toCuntilnomoresetsofitemscanbeaddedtoCendThesets-of-Itemsconstruction

構造LR(0)項目集規(guī)范族40第四十頁，共99頁。例4.28設文法G的產(chǎn)生式為拓廣文法G：E'

EE

E

+

T|TTT

*

F|FF(

E

)|id的LR(0)項目集規(guī)范族為：41第四十一頁，共99頁。構造LR(0)項目集規(guī)范族

I0:

E·E

(核心項目) E·E+T E·T (非核心項目，

T·T

F 通過對核心項目求閉包

T·F 而獲得) F·(E) F·id42第四十二頁，共99頁。I0: I1:=goto(I0,E)

E·E

EE· E·E+T EE·+T E·T T·T

F I2:=goto(I0,T) T·F E

T·

F·(E) TT·

F

F·id I3:=goto(I0,F)

TF·43第四十三頁，共99頁。I4:=goto(I0,(

) F(·E) E·E+T E·T T·T

F T·F F·(E) F·id

I5:=goto(I0,id

)

F

id·I6

:=goto(I1,+

)

EE+·T T·TF

T·F

F·(E)

F·id

44第四十四頁，共99頁。I7

:=goto(I2,*

)

TT*·

F

F·(E)

F·idI8:=goto(I4,E)

F(E·)EE·

+T

I9

:=goto(I1,+

)

EE+T· TT·

*FI10

:

TT*F·I11:

F(E)·45第四十五頁，共99頁。文法的LR(0)項目集規(guī)范族I0: E·

E

E·

E+T

E·

T

T·

T*F

T·

F

F·(E)

F·

idI1:

EE·

EE·

+TI2: ET· TT·

*FI3: TF·I4: F(·

E)

E·

E+T

E·

T

T·

T*F

T·

F

F·(E)

F·

idI5:

Fid·

I6: EE+·

T T·

T*F T·

F

F·(E)

F·

idI7: TT*·

F

F·(E)

F·

idI8:

F(E·)EE·

+T

I9: EE+T· TT·

*FI10: TT*F·I11: F(E)·

46第四十六頁，共99頁。47第四十七頁，共99頁。48第四十八頁，共99頁。49第四十九頁，共99頁。50第五十頁，共99頁。51第五十一頁，共99頁。52第五十二頁，共99頁。53第五十三頁，共99頁。54第五十四頁，共99頁。4.6.3LR分析器的模型輸入LR分析驅動程序輸出棧ActionGotosm…sm-1……s0…a1ai…an$分析表M動作表轉向表55第五十五頁，共99頁。LR語法分析器的行為為描述LR語法分析的行為，引入概念格局(Configuration)，用二元組表示

(s0s1s2…sm,aiai+1…an$)

棧的內(nèi)容

尚未處理的輸入代表右句型X1X2…Xmaiai+1…an，文法符號Xi是狀態(tài)si代表的文法符號分析棧存放狀態(tài)而不是文法符號56第五十六頁，共99頁。LR分析算法的動作語法分析器的下一動作由當前輸入符號ai和棧頂狀態(tài)sm查詢分析表action[sm,ai]決定移進歸約接受出錯57第五十七頁，共99頁。移進之前(s0s1s2…sm,aiai+1…an$)

輸入LR分析程序輸出Action[sm,ai]=“shift

s”Gotosmsm-1……s0…a1ai…an$?！?8第五十八頁，共99頁。移進之后(s0s1s2…sms

,

ai+1…an$)

LR分析程序輸出Action[sm,ai]=“shift

s”Gotosm

sm-1……s0…a1ai…an$

s輸入棧59第五十九頁，共99頁。歸約之前LR分析程序輸出棧Action[sm,ai]=“rA”sm…sm-r……s0…a1ai…an$Goto[sm-r,A]=s

…輸入60第六十頁，共99頁。歸約從棧中彈出||

個符號LR分析程序輸出Action[sm,ai]=“rA”sm-r……s0…a1ai…an$Goto[sm-r,A]=s

||輸入棧61第六十一頁，共99頁。歸約從棧中彈出||

個符號，再進棧LR分析程序輸出Action[sm,ai]=“rA”ssm-r……s0…a1ai…an$Goto[sm-r,A]=s

||輸入棧62第六十二頁，共99頁。接受LR分析程序輸出Action[s,$]=“accept”ss0…a1ai…an$Goto輸入棧63第六十三頁，共99頁。報錯LR分析程序輸出Action[s,a]未定義…a1ai…an$Gotosmsm-r……s0…輸入棧64第六十四頁，共99頁。初始格局LR分析程序輸出Action[s,a]Gotos0…a1ai…an$輸入棧65第六十五頁，共99頁。算法4.7LR分析算法輸入：一個輸入串w和文法G的一張LR分析表M。輸出：若wL(G)，輸出w的一個自底向上的分析；否則，報錯。方法：初始狀態(tài)s0

分別放在棧頂，w$放在輸入緩沖區(qū)；語法分析器執(zhí)行下面的程序，直至遇見接受或出錯動作。66第六十六頁，共99頁。置ip指向w$的第一個符號；…a1ai…an$ip67第六十七頁，共99頁。置ip指向w$的第一個符號；repeatforeverbegin

end

68第六十八頁，共99頁。置ip指向w$的第一個符號；repeatforeverbegin

令s是棧頂狀態(tài)，a是ip所指向的符號

end

s…………s0…a1a…an$iptop69第六十九頁，共99頁。置ip指向w$的第一個符號；repeatforeverbegin

令s是棧頂狀態(tài)，a是ip所指向的符號

if

action[s,a]=“shift

s”

thenbegin

將a和s先后壓入棧內(nèi)； 讓ip指向下一個輸入符號；

end

end

70第七十頁，共99頁。置ip指向w$的第一個符號；repeatforeverbegin

令s是棧頂狀態(tài)，a是ip所指向的符號

if

action[s,a]=“shift

s”

thenbegin

將a和s先后壓入棧內(nèi)； 讓ip指向下一個輸入符號；

end

elseif

action[s,a]=“reduce

A”

thenbegin

從棧頂彈出||個符號； 令s是當前棧頂狀態(tài)； 把A和goto[s,A]先后入棧； 輸出產(chǎn)生式A

end

end

71第七十一頁，共99頁。置ip指向w$的第一個符號；repeatforeverbegin

令s是棧頂狀態(tài)，a是ip所指向的符號

if

action[s,a]=“shift

s”

thenbegin

將a和s先后壓入棧內(nèi)； 讓ip指向下一個輸入符號；

end

elseif

action[s,a]=“reduce

A”

thenbegin

從棧頂彈出||個符號； 令s是當前棧頂狀態(tài)； 把A和goto[s,A]先后入棧； 輸出產(chǎn)生式A

end

elseif

action[s,a]=“acc”

then

returnend

72第七十二頁，共99頁。置ip指向w$的第一個符號；repeatforeverbegin

令s是棧頂狀態(tài)，a是ip所指向的符號

if

action[s,a]=“shift

s”

thenbegin

將a和s先后壓入棧內(nèi)； 讓ip指向下一個輸入符號；

end

elseif

action[s,a]=“reduce

A”

thenbegin

從棧頂彈出||個符號； 令s是當前棧頂狀態(tài)； 把A和goto[s,A]先后入棧； 輸出產(chǎn)生式A

end

elseif

action[s,a]=“acc”

then

return

else

error()end

73第七十三頁，共99頁。例4.33算法表達式文法(1)E

E+T(4)T

E(2)E

T(5)F

(E)(3)T

T*F(6)F

id

各個動作的編碼的含義：si表示把當前輸入符號和狀態(tài)i進棧rj表示用第j條產(chǎn)生式歸約acc表示接受空白項表示出錯74第七十四頁，共99頁。圖4.37表達式文法的LR分析表75第七十五頁，共99頁。圖4.38關于id*id的LR分析過程76第七十六頁，共99頁。補充:關于id(*id的LR分析過程77第七十七頁，共99頁。思考1：考慮算法的效率時間復雜度O(|w|)無回溯78第七十八頁，共99頁。思考2：你能否編程實現(xiàn)4.30？利用已學習的知識數(shù)據(jù)結構高級語言程序設計算法設計廣泛應用的編譯器開發(fā)工具已實現(xiàn)了這一算法YaccBison原理、實踐79第七十九頁，共99頁。思考3：如何構造動作表和分析表？輸入LR分析程序輸出sm

sm-1

…s0…a1ai…an$棧ActionGoto80第八十頁，共99頁。后續(xù)的內(nèi)容圍繞動作表和分析表的構造原理展開事實上，算法是通用的，不同的動作表和分析表的構造決定了不同的LR分析方法SLR(1)LR(1)LALR(1)81第八十一頁，共99頁。4.6.4構造SLR分析表簡單LR分析（SimpleLR）82第八十二頁，共99頁。構造SLR分析表狀態(tài)i從Ii構造，它的action函數(shù)確定如下：如果[A·a]在Ii中，并且goto(Ii,a)=Ij，那么置action[i,a]為sj。如果[A·]在Ii中，那么對FOLLOW(A)中的所有a，置action[i,a]為rj，j是產(chǎn)生式A的編號。如果[SS·]在Ii中，那么置action[i,$]為接受accept。如果出現(xiàn)動作沖突，那么該文法就不是SLR(1)的。83第八十三頁，共99頁。從DFA構造SLR分析表使用下面規(guī)則構造狀態(tài)i的goto函數(shù)：對所有的非終結符A，如果goto(Ii,A)=Ij,那么goto[i,A]=j。不能由上面兩步定義的條目都置為error。分析器的初始狀態(tài)是包含[S·S]的項目集對應的狀態(tài)。84第八十四頁，共99頁。算法4.32SLR分析算法輸入：一個拓廣文法G輸出：對于G的分析表的action子表和goto子表方法：1.構造G的LR(0)項目集規(guī)范族。2.對于狀態(tài)Ii的分析動作如下：

(a)若A.aBIi且goto(Ii,a)=

Ij

action[i,a]=“shiftj”(b)若A.

Ii,對于所有aFOLLOW(A)

action[i,a]=“reduceA”,AS(c)若SS.Ii,action[i,$]=“accept”3.若goto(Ii,A)=Ij,AVN,則goto[i,A]=j4.分析表其余位置為error85第八十五頁，共99頁。FOLLOW(E)={$,+,)}文法的SLR分析表86第八十六頁，共99頁。例I2: E

T·

T

T·*

F因為FOLLOW(E)={$,+,)},所以

action[2,$]=action[2,+]=action[2,)]=r2

action[2,*]=s787第八十七頁，共99頁。例每個SLR(1)文法都不是二義的，但是，有許多非二義的文法不是SLR(1)。例如，下面的產(chǎn)生式文法

S

L=R SR L*R Lid RL88第八十八頁，共99頁。拓廣文法G的LR(0)項目集規(guī)范族為：I0: S'·

S

S·

L=R

S·

R

L·*R

L·

id

R·

LI1: S'S

·

I2: SL·=R

RL·

I3: SR

·I4: L*·

R

R·

L

L·*R

L·

idI5: Lid

·I6: SL=·

R

R·

L

L·*R

L·

idI7: L*R

·I8: RL

·I9: SL=R

·89第八十九頁，共99頁。idS'SSL=RSRL*RLidRLLidSL=RRLS'S