編譯原理：第五章 語法分析3

1、 LR( )分析法是指從左到右掃描、最左歸約(LR)之意；它屬于自底向上分析方法。 常用的算法有LR(0)和LR(1)等，其中括號內(nèi)的數(shù)是指不查看(0)或只查看一個當(dāng)前符號(1)，即可確定當(dāng)前句型的句柄。5.4 LR( )分析法 利用一個分析表，登記選擇句柄產(chǎn)生式的知識； 利用一個分析棧，記錄分析過程；【分析算法】依次讀取單詞，并進行如下操作： 當(dāng)棧頂出現(xiàn)句柄時，規(guī)約之，否則移進。 5.4.1. LR( )分析法基本概念 LR( ) 分析法的基本要點有三：1. 什么是LR（）分析法？【例5.8】 G(Z): Z-aBAd, A-bc|c, B-bB|c 2. LR( )分析法分析過程示例： 符

2、號串 abccd 最左歸約過程: 符號串 abccd 的語法樹： abccd 的語法樹 a b c c dBBAZ 歸約過程的句柄：句柄次序 cbB caBAdabccd =.abBcd =.aBcd =.aBAd =.Z 句柄產(chǎn)生式 操 作 剩余串 w 分析棧 移進,NEXT d # c# a 歸約， A - c # d# a B 移進,NEXT # d# a B 歸約， Z - aBAd # a B A OK # B - bB B - c 移進,NEXT c d # c# a 移進,NEXT b c c d # a# 歸約， d # c # a b 歸約， d # c# a b 移進,NE

3、XT c c d # b# B B Z A a b c c d句柄(接上頁) 利用分析棧記錄行分析過程：【注】何時棧頂出現(xiàn)句柄？怎樣求當(dāng)前句柄產(chǎn)生式 ？設(shè) 待分析的符號串: abccd#3. 有限自動機用作句柄識別器： 如何確認首次出現(xiàn)的c 的父親是 B,而不是 A ？G(Z): Z - aBAd A - bc | c B - bB | c 句柄一定出現(xiàn)于某一個產(chǎn)生式的右部； 歸約過程中如何確認句柄？ 是否是句柄，還要看其所在符號串中的位置。 怎樣判斷棧頂出現(xiàn)的句柄不是 bc,而是 c ? 顯然是錯誤的(從文法中可判定：aA不能相鄰!) 若用 bc 歸約，則有 abccd aAcd( ) =.

4、 若用 A作父親，則有 abccd abAcd( ) =.顯然是錯誤的(從文法中可判定：Ac不能相鄰!語法樹 我們討論如下兩個問題：#abc cd#分析棧 擴展文法，使文法符號附有位置信息： B - b9 B10 (4)| c11 (5) Z - Z1 (0) Z - a2 B3 A4 d5 (1) A - b6 c7 (2)| c8 (3) 增設(shè)一個產(chǎn)生式(如：Z- Z )， 帶有位置編碼的文法符號，稱為文法出現(xiàn)。G(Z): Z - aBAd A - bc | c B - bB | cG(Z)并把產(chǎn)生式右端符號順序編碼，作為位置(狀態(tài))信息:【注】 由于文法出現(xiàn)比文法符號多了一個位置信息，

5、在分析時，如果用文法出現(xiàn)代替文法符號，是否有助于句柄的確認呢？ 句柄識別器的構(gòu)造方法 利用擴展文法構(gòu)造句柄識別器： 若把擴展文法中的位置號看成狀態(tài)，那么就可用有限自動機描述如下： 對每個產(chǎn)生式，構(gòu)造自動機，用以識別自己的符號串；(0,Z)=1; 預(yù)見 某個非終結(jié)符，也就預(yù)見 其所有產(chǎn)生式的頭符號;于是各產(chǎn)生式的子自動機可并接在一起。 【表示】: 0狀態(tài) 預(yù)見 Z 后變換為 1狀態(tài) ！ 設(shè)編碼0作為自動機的開始狀態(tài)，第二個產(chǎn)生式，構(gòu)造自動機：則 第一個產(chǎn)生式，構(gòu)造自動機：(0,a)=2; (2,B)=3; (3,A)=4; (4,d)=5; B - b9 B10 (4)| c11 (5) Z -

6、 Z1 (0)Z - a2 B3 A4 d5 (1)A - b6 c7 (2)| c8 (3)G(Z) 句柄識別器的自動機構(gòu)造示例：其中：r(j) 歸約函數(shù)(即 按序號為(j)的產(chǎn)生式歸約！)； 移進狀態(tài)： 歸約狀態(tài)：B - b9 B10 (4)| c11 (5)Z - Z1 (0)Z - a2 B3 A4 d5 (1)A - b6 c7 (2)| c8 (3)G(Z) 符號說明 0，2，3，4，6，9 ； 011+ZaBbbBccAdbcOKr(3)r(1)r(2)r(4)r(5)c 由擴展文法到句柄識別器的構(gòu)造過程如右圖所示：【例5.8】 5，7，8，10，11； 分析結(jié)束(OK)。 接受

7、狀態(tài)： 1 011+ZaBbbBccAdbcOKrrrrrc 根據(jù)句柄識別器進行LR分析過程： 根據(jù)句柄識別器， abccd# 識別過程：(#0,a)=(#0a2b9B10,c)=(#0a2B3A4,d)=(#0a2,b)=(#0a2b9,c)=(#0a2b9c11,c)=(#0a2B3,c)= (#0a2B3c8,d)=(#0a2B3A4d5,#)=(#0Z1,#)=0k 句柄識別器又稱“活前綴圖”: 意思是在最左歸約過程中，識別了句柄，實際上也就識別了以句柄為后綴的該句型(規(guī)范句型)的前部符號串。注B - b9 B10 (4)| c11 (5)Z - Z1 (0)Z - a2 B3 A4

8、d5 (1)A - b6 c7 (2)| c8 (3)句柄【例5.8】文法的句柄識別器:+LR(0)分析器的基本組成：LR(0)分析法要求文法應(yīng)是 LR(0）文法。LR(0)分析表 LR(0)控制器 LR(0)中的0,是指不必查看當(dāng)前符號就可確認句柄之意；5.4.2 LR(0)分析器設(shè)計1. LR(0)文法及其判定 句柄識別器中，移進和歸約不沖突；即 移進和歸約不同時發(fā)生！ 滿足下述特點的文法稱為 LR(0)文法。例5.8 文法，就是 LR(0)文法，請看： 歸約時不必查看當(dāng)前符號；【算法】 根據(jù)句柄識別器，填寫 LR(0)分析表： 若 (i,x)=k,x(VN+VT),則 R(i,x):=

9、xk ; 若 狀態(tài)i 標記有（-，r(j), 則 對任何 a (VT+#）， R(i,a):= r(j) ; R(1,#):= OK 。 2. LR(0)分析表構(gòu)造 擴展文法，構(gòu)造句柄識別器； LR()分析表是 LR()分析法的知識表,是句柄識別器的一種機內(nèi)表示形式：狀態(tài)編碼終結(jié)符 + #非終結(jié)符 R(_,_):0 1 a # Z nakOKZkr(j)r(j) 011+ZaBbbBccAdbcOKrrrrrcLR(0)分析表【例5.8】文法構(gòu)造過程： 9 10 Z A 1 5 0 4 8 d # 6 7 11 3 2 B c b a B10c11 b9r(4)r(4)r(4)r(4)r(4)

10、 Z1 A4 OKr(1)r(1)r(1)r(1)r(1) a2d5r(3)r(3)r(3)r(3)r(3)r(5)r(2) r(5)r(2)c7r(2)r(2)r(2)r(5)r(5)r(5)c8 b6 B3 b9c113. LR(0)控制程序設(shè)計開始PUSH(#0)NEXT(w)查LR(0)分析表R(Xk,w)=?R=空?YerrR=OK結(jié)束R=r(j)R=WiPUSH Wi 則 PUSH Ai;取 A - (j) POP(); 若 R(Xk,A)=Ai Xk 棧頂文法出現(xiàn)；歸約移進LR( )控制器n LR(0)分析法小結(jié)示例G(Z): Z - aBAd A - bc | c B - bB

11、 | c【例5.8】文法: 擴展文法，使文法符號附有位置信息： B - b9 B10 (4)| c11 (5)Z - Z1 (0)Z - a2 B3 A4 d5 (1)A - b6 c7 (2)| c8 (3) 由擴展文法構(gòu)造句柄識別器： 011+ZaBbbBccAdbcOKr(3)r(1)r(2)r(4)r(5)c 011+ZaBbbBccAdbcOKrrrrrc 9 10 Z A 1 5 0 4 8 d # 6 7 11 3 2 B c b a B10c11 b9r(4)r(4)r(4)r(4)r(4) Z1 A4 OKr(1)r(1)r(1)r(1)r(1) a2d5r(3)r(3)r(

12、3)r(3)r(3)r(5)r(2) r(5)r(2)c7r(2)r(2)r(2)r(5)r(5)r(5)c8 b6 B3 b9c11 由句柄識別器構(gòu)造LR(0)分析表： LR(0)分析法分析過程示例： 剩余串 操 作 w 分析棧#0 a2 b9 B10 PUSH(c8),NEXT(w) d# c#0 a2 REDUCE(3) # d#0 a2 B3 PUSH(d5),NEXT(w) # d#0 a2 B3 REDUCE(1) #0 a2 B3 A4 OK #0 d# d# cd# ccd# bccd# PUSH(c11),NEXT(w) c#0 a2 PUSH(a2),NEXT(w) a#0

13、 REDUCE(4) c REDUCE(5) c#0 a2 b9 PUSH(b9),NEXT(w) b#0 a2 b9 c11 B3 c8 A4 d5 Z1查分析表查產(chǎn)生式控制程序符號串：abccd#練習(xí)題:【習(xí)題5.8】 解釋下列詞語： 文法出現(xiàn)， LR(0)文法， LR(0)分析器組成。【習(xí)題5.9】構(gòu)造下述文法的LR(0)分析表： G(Z)： Z - aAb , A - cA | d【例5.9】LR(0)分析法示例1： 構(gòu)造下述文法的LR(0)分析表： G(Z)： Z - aAb , A - cA | d 0+ZaAdbcAOKr(1)r(2)r(3)cd 構(gòu)造句柄識別器： 擴展文法：G

14、(Z) Z- Z1 (0) Z - a2 A3 b4 (1) A - c5 A6 (2)| d7 (3) 設(shè)計LR(0) 分析表：r(3)r(2) d7 r(1) d7 d Z1 Z A6 A3 A OK 1 c5 5 a2 0 r(1) (1) r(1) r(1) 4r(3)r(2) #r(2)r(2) r(2) 6r(3)r(3) r(3) 7 b4 3 c5 2 c b a 0+ZaAdbcAOKr(1)r(2)r(3)cd【例5.10】左遞歸文法的LR(0)分析表構(gòu)造： d Z A 1 5 0 4 # 6 3 2 c b a 0+ZaAdbcOKr(1)r(2)r(3)Z-Z1(0);

15、Z -a2A3b4(1);A -A3c5(2)|d6(3)G(Z)【注】為了使句柄識別器是確定機，左遞歸產(chǎn)生式(2)中的A要與(1)中的A編碼相同!?, r(3) r(2) r(1) d6 Z1 A3 OKr(2) r(2) r(2) r(2) a2r(1) r(1) r(1) r(1)r(3) r(3) r(3) r(3) c5 b4 【例5.11】LR(0)分析法示例1 構(gòu)造下述文法的LR(0)分析表： G(Z) Z - aAb , A - Ac | d 擴展文法：G(Z) Z- Z1 (0) Z - a2 A3 b4 (1) A - A5c6 (2)| d7 (3) 構(gòu)造可歸前綴圖： 0+ZaAdbAcOKr(1)r(2)r(3