編譯原理：第五章 語(yǔ)法分析3

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

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

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

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

5、在分析時(shí)，如果用文法出現(xiàn)代替文法符號(hào)，是否有助于句柄的確認(rèn)呢？ 句柄識(shí)別器的構(gòu)造方法 利用擴(kuò)展文法構(gòu)造句柄識(shí)別器： 若把擴(kuò)展文法中的位置號(hào)看成狀態(tài)，那么就可用有限自動(dòng)機(jī)描述如下： 對(duì)每個(gè)產(chǎn)生式，構(gòu)造自動(dòng)機(jī)，用以識(shí)別自己的符號(hào)串；(0,Z)=1; 預(yù)見(jiàn) 某個(gè)非終結(jié)符，也就預(yù)見(jiàn) 其所有產(chǎn)生式的頭符號(hào);于是各產(chǎn)生式的子自動(dòng)機(jī)可并接在一起。 【表示】: 0狀態(tài) 預(yù)見(jiàn) Z 后變換為 1狀態(tài) ！ 設(shè)編碼0作為自動(dòng)機(jī)的開(kāi)始狀態(tài)，第二個(gè)產(chǎn)生式，構(gòu)造自動(dòng)機(jī)：則 第一個(gè)產(chǎn)生式，構(gòu)造自動(dòng)機(jī)：(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) 句柄識(shí)別器的自動(dòng)機(jī)構(gòu)造示例：其中：r(j) 歸約函數(shù)(即 按序號(hào)為(j)的產(chǎn)生式歸約！)； 移進(jì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) 符號(hào)說(shuō)明 0，2，3，4，6，9 ； 011+ZaBbbBccAdbcOKr(3)r(1)r(2)r(4)r(5)c 由擴(kuò)展文法到句柄識(shí)別器的構(gòu)造過(guò)程如右圖所示：【例5.8】 5，7，8，10，11； 分析結(jié)束(OK)。 接受

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

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

9、xk ; 若 狀態(tài)i 標(biāo)記有（-，r(j), 則 對(duì)任何 a (VT+#）， R(i,a):= r(j) ; R(1,#):= OK 。 2. LR(0)分析表構(gòu)造 擴(kuò)展文法，構(gòu)造句柄識(shí)別器； LR()分析表是 LR()分析法的知識(shí)表,是句柄識(shí)別器的一種機(jī)內(nèi)表示形式：狀態(tài)編碼終結(jié)符 + #非終結(jié)符 R(_,_):0 1 a # Z nakOKZkr(j)r(j) 011+ZaBbbBccAdbcOKrrrrrcLR(0)分析表【例5.8】文法構(gòu)造過(guò)程： 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è)計(jì)開(kāi)始PUSH(#0)NEXT(w)查L(zhǎng)R(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)；歸約移進(jìn)LR( )控制器n LR(0)分析法小結(jié)示例G(Z): Z - aBAd A - bc | c B - bB

11、 | c【例5.8】文法: 擴(kuò)展文法，使文法符號(hào)附有位置信息： B - b9 B10 (4)| c11 (5)Z - Z1 (0)Z - a2 B3 A4 d5 (1)A - b6 c7 (2)| c8 (3) 由擴(kuò)展文法構(gòu)造句柄識(shí)別器： 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 由句柄識(shí)別器構(gòu)造LR(0)分析表： LR(0)分析法分析過(guò)程示例： 剩余串 操 作 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)生式控制程序符號(hào)串：abccd#練習(xí)題:【習(xí)題5.8】 解釋下列詞語(yǔ)： 文法出現(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)造句柄識(shí)別器： 擴(kuò)展文法：G

14、(Z) Z- Z1 (0) Z - a2 A3 b4 (1) A - c5 A6 (2)| d7 (3) 設(shè)計(jì)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)【注】為了使句柄識(shí)別器是確定機(jī)，左遞歸產(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 擴(kuò)展文法：G(Z) Z- Z1 (0) Z - a2 A3 b4 (1) A - A5c6 (2)| d7 (3) 構(gòu)造可歸前綴圖： 0+ZaAdbAcOKr(1)r(2)r(3