1、編譯原理,第7章分析,一起交流 共同進(jìn)步,2,主要內(nèi)容,本章學(xué)習(xí)目標(biāo) 7.1自下而上分析及LR分析概述 7.2LR分析算法 PPT 1-36 7.3SLR(1) 分析 7.4LR（1）分析 7.5LALR分析 7.6使用二義文法 本章小結(jié) 重點(diǎn)習(xí)題解析 作業(yè) 相關(guān)術(shù)語(yǔ)的回顧（英文版）,一起交流 共同進(jìn)步,3,本章學(xué)習(xí)目標(biāo),一學(xué)習(xí)目標(biāo) 掌握LR分析器 二課程安排 2學(xué)時(shí),本章知識(shí)結(jié)構(gòu),自下而上分析算法 能力強(qiáng) 構(gòu)造復(fù)雜 最常用和最有效的模型-移進(jìn)歸約(動(dòng)作）,將輸入分成兩部分：未消化和半消化的,總控程序,output,Input#未消化,半消化的,分析表,產(chǎn)生式表,一起交流 共同進(jìn)步,6,S E

2、 E T | E + T T int | (E),Reduce: 如能找到一產(chǎn)生式 A w 且棧中的內(nèi)容是 qw (q 可能為空), 則可以將其歸約為 qA.即倒過(guò)來(lái)用這個(gè)產(chǎn)生式. 如上例, 若棧中內(nèi)容是 (int ，我們使用產(chǎn)生式 T int柄把棧中內(nèi)容歸約為(T Shift: 如不能執(zhí)行一個(gè)歸約且在未消化的輸入中還有 token ，就把它從輸入移到棧中. 如上例,假定棧中內(nèi)容是 ( ,輸入中還有 int+int)#.不能對(duì)( 執(zhí)行一個(gè)歸約，因?yàn)樗缓腿魏萎a(chǎn)生式的右端匹配.所以把輸入的第一個(gè)符號(hào)移到棧中,于是棧中內(nèi)容是 (int ，而余留的輸入是 +int)# .,一起交流 共同進(jìn)步,7,R

3、educe的一個(gè)特殊情況：棧中的全部?jī)?nèi)容w歸約為開(kāi)始符號(hào)S （即施用 S w） ，且沒(méi)有余留輸入了，意味著已成功分析了整個(gè)輸入串. 移進(jìn)歸約分析中還會(huì)出現(xiàn)一種情況，就是出錯(cuò)，比如當(dāng)前的token不能構(gòu)成一個(gè)合法句子的一部分，例如上面的文法，試分析 int+)時(shí)就會(huì)發(fā)生錯(cuò)誤.,STACK REMAINING INPUT PARSER ACTION 1 (int + int)# Shift 2 ( int + int)# Shift 3 (int + int)# Reduce: T int 4 (T + int)# Reduce: E T 5 (E + int)# Shift 6 (E + int

4、)# Shift 7 (E + int )# Reduce: T int 8 (E + T )# Reduce: E E + T 9 (E )# Shift 10 (E) # Reduce: T (E) 11 T # Reduce: E T 12 E # Reduce: S E 13 S #,一起交流 共同進(jìn)步,9,沖突,(E + T )# Reduce:E E + T why?不用 E T (E ) # 若使用了E T，在棧中形成的(E+E不是規(guī)范句型的活前綴（viable prefixes） （E+E不能和任何產(chǎn)生式的右端匹配 （E+E）不是規(guī)范句型 活前綴 是規(guī)范句型（右句型）的前綴，但

5、不超過(guò)句柄 移進(jìn)歸約分析的棧中出現(xiàn)的內(nèi)容加上余留輸入構(gòu)成規(guī)范句型,一起交流 共同進(jìn)步,10,沖突及解決方法,沖突： 移進(jìn)-歸約 沖突 歸約-歸約 沖突 解決方法： Conflict Solutions 改寫(xiě)文法 根據(jù)產(chǎn)生式出現(xiàn)的順序來(lái)選擇 根據(jù)算符的優(yōu)先級(jí) 特定的一種shift-reduce實(shí)現(xiàn)技術(shù)（分析） L 從左到右掃描輸入串 R 最右推導(dǎo)的逆過(guò)程 能力強(qiáng) 幾乎所有CFG的語(yǔ)言結(jié)構(gòu)都能用LR分析 不需要對(duì)文法附加條件,一起交流 共同進(jìn)步,11,規(guī)范推導(dǎo) 規(guī)范句型 規(guī)范歸約,最右推導(dǎo)：在推導(dǎo)的任何一步，其中、是句型，都是對(duì)中的最右非終結(jié)符進(jìn)行替換 最右推導(dǎo)被稱為規(guī)范推導(dǎo)。由規(guī)范推導(dǎo)所得的句型

6、稱為規(guī)范句型。 GS： SE EE+T|T T(E)|intSE T (E) (E+T) (E+int) (T+int) (int+int) 規(guī)范歸約 假定是G的一個(gè)句子，稱序列n ,n-1 ,0是 的一個(gè)規(guī)范歸約 如果該序列滿足： （1） n = （2）0為文法的開(kāi)始符號(hào) （3）對(duì)任何j,0j=n, j-1是從j經(jīng)把句柄替換為相應(yīng)產(chǎn)生式的左部而得到的,一起交流 共同進(jìn)步,12,LR分析法及基本思想 分析器模型和分析算法 LR分析特征討論,7.1 分析器,LR分析法,LR分析法是一種自下而上進(jìn)行規(guī)范歸約的語(yǔ)法分析方法。,這里L(fēng)是指從左到右掃描輸入符號(hào)串。R是指構(gòu)造最右推導(dǎo)的逆過(guò)程。,這種分析法

7、比遞歸下降分析法、預(yù)測(cè)分析法和算符優(yōu)先分析法對(duì)文法的限制要少得多。,LR分析法的基本思想:,LR分析法是一種規(guī)范歸約分析法。,規(guī)范歸約分析法的關(guān)鍵是在分析過(guò)程中如何確定分析棧棧頂?shù)姆?hào)串是否形成句柄。,LR分析法的基本思想,一起交流 共同進(jìn)步,15,分析器模型,LR分析器由3部分組成：總控程序、分析表、分析棧。,一起交流 共同進(jìn)步,16,LR分析器的工作過(guò)程, 在總控程序的控制下，自左向右掃視輸入串的各個(gè)字符； 按分析表的指示（動(dòng)作，狀態(tài)轉(zhuǎn)移）完成相應(yīng)的分析工作； 分析棧記錄的是從開(kāi)始到目前為止的整個(gè)歷程； 對(duì)當(dāng)前可能遇到的輸入符號(hào)進(jìn)行預(yù)測(cè)。 分析表是LR分析器的核心，棧頂狀態(tài)和輸入符號(hào)是唯一

8、確定的。,一起交流 共同進(jìn)步,17,LR分析表 GS: (1)S a A c B e (2)A b (3)A Ab (4)B d,一起交流 共同進(jìn)步,18,LR分析使用兩張表,ACTION表 告訴分析器：棧頂狀態(tài)為S, 當(dāng)前輸入符號(hào)是a時(shí)做什麼 1. ACTIONS,a= Sj 2. ACTIONS,a=rj (第j條產(chǎn)生式為A) 3. ACTIONS,a=acc 4. ACTIONS,a= error GOTO表 GOTOS,A棧頂狀態(tài)為S，歸約之后的非終結(jié)符為A時(shí)，要放到棧頂?shù)男聽(tīng)顟B(tài),一起交流 共同進(jìn)步,19,分析,GS: (1)S a A c B e (2)A b (3)A Ab (4)

9、B d w=abbcde#,Step states. The rest of inputaction goto 1 0 abbcde# s2 2 02 bbcde# s4 3 024 bcde# r2 goto(3,A) 4 023 bcde# s6 5 0236 cde# r3 goto(3,A) 6 023 cde# s5 7 0235 de# s8 8 02358 e# r4 goto(7,B) 9 02357 e# s9 10 023579 # r1 goto(1,S) 11 01 # acc,GS: (1)S a A c B e (2)A b (3)A Ab (4)Bd w=abbc

10、de#,1) E E + T2) E T 3) T (E)4) T id,一起交流 共同進(jìn)步,22,id + (id),7.2 LR分析算法,置ip指向輸入串w的第一個(gè)符號(hào) 令S為棧頂狀態(tài) a是ip指向的符號(hào) 重復(fù) begin if ACTIONS,a=Sj then begin PUSH j,a(進(jìn)棧) ip 前進(jìn)(指向下一輸入符號(hào)) end else if ACTIONS,a=rj (第j條產(chǎn)生式為A) then begin pop | 項(xiàng) 令當(dāng)前棧頂狀態(tài)為S push GOTOS,A和A(進(jìn)棧) end else if ACTIONs,a=acc then return (成功） els

11、e error end.重復(fù),一起交流 共同進(jìn)步,24,分析程序,例: GS: S a A c B e 1 A b 2 A Ab 3 B d 4 w=abbcde#,一起交流 共同進(jìn)步,25,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,a,b,b,c,d,e,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn),2） #a bbcde# 移進(jìn),4） #aA bcde# 移進(jìn),6） #aA cde# 移進(jìn),7） #aAc de# 移進(jìn),9） #aAcB e# 移進(jìn),11） #S # 接受,符號(hào)串a(chǎn)bbcde是否是GS的子,對(duì)輸入串a(chǎn)bbcde#的移進(jìn)-

12、規(guī)約分析過(guò)程,步驟,符號(hào)棧,輸入符號(hào)串,動(dòng)作,1） # abbcde# 移進(jìn) 0 S2,2） #a bbcde# 移進(jìn) 02 S4,4） #aA bcde# 移進(jìn) 023 S6,6） #aA cde# 移進(jìn) 023 S5,7） #aAc de# 移進(jìn) 0235 S8,9） #aAcB e# 移進(jìn) 02357 S9,11） #S # 接受 01 acc,對(duì)輸入串a(chǎn)bbcde#的LR分析過(guò)程,3） #ab bcde# 歸約(Ab) 024 r2 3,5） #aAb cde# 歸約(AAb) 0236 r3 3,8） # aAcd e# 歸約(Bd) 02358 r4 7,10） #aAcBe #

13、歸約(SaAcBe) 023579 r1 1,狀態(tài)棧,ACTION,GOTO,文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,Si:移進(jìn)，將狀態(tài)i和輸入符進(jìn)棧 ri:歸約，用第i個(gè)產(chǎn)生式歸約，同時(shí)狀態(tài)棧與符號(hào)棧退出相應(yīng)個(gè)符號(hào)，并把GOTO表相應(yīng)狀態(tài)和第i個(gè)產(chǎn)生式的左部非終結(jié)符入棧。,一起交流 共同進(jìn)步,27,Question,LR分析表是如何構(gòu)造的？,一起交流 共同進(jìn)步,28,LR分析表是如何構(gòu)造的？,Review ：LR分析器的關(guān)鍵部分是分析表的構(gòu)造。 從給定的上下文無(wú)關(guān)文法直接構(gòu)造識(shí)別文法所有規(guī)范句型活前綴的DFA，然后再將DFA轉(zhuǎn)換成一張LR分析表。,一起交

14、流 共同進(jìn)步,29,LR分析表是如何構(gòu)造的？,為了給出構(gòu)造LR分析表的算法，需要定義一些重要的概念和術(shù)語(yǔ)。 文法規(guī)范句型的活前綴 1.字符串的前綴是指字符串的任意首部。例如，字符串a(chǎn)bc的前綴有：,a,ab,abc。 2. 規(guī)范句型活前綴是指規(guī)范句型的前綴, 這種前綴不包含句柄右邊的任何符號(hào)。,一起交流 共同進(jìn)步,30,活前綴,活前綴 G=(Vn,Vt,P,S),若有S A , 符號(hào)串是的前綴,則稱是文法G的活前綴. 其中S是對(duì)原文法擴(kuò)充(SS)增加的非終結(jié)符. S不出現(xiàn)在任何產(chǎn)生式的右部. 如G=(S,a,SSa,Sa,S),R,一起交流 共同進(jìn)步,31,Example,推導(dǎo)過(guò)程 S aAc

15、Be1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1 可歸前綴 活前綴可歸前綴 規(guī)約時(shí)在棧里的句型的前綴規(guī)約前可在棧里的規(guī)范句型(不含句柄)的前綴 ab2a aAb3a,aA aAcd4a,aA,aAc aAcBe1a,aA,aAc,aAcB,一起交流 共同進(jìn)步,32,x,5,9,2,14,3,0,6,7,10,11,12,16,15,17,18,S,a,a,a,a,A,A,A,b,c,c,b,d,e,B,圖7.3 識(shí)別可歸前綴的NFA,一起交流 共同進(jìn)步,33,圖7.4 識(shí)別可歸前綴的DFA,x,2,3,5,7,A,b,a,S,b,c,B,e,d,結(jié)論：只要能構(gòu)造出CFC文法的識(shí)

16、別可歸前綴的DFA，就可以構(gòu)造出相應(yīng)的分析表(Action和Goto表),文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B d,一起交流 共同進(jìn)步,34,構(gòu)造文法活前綴DFA的三種方法,根據(jù)形式定義求出活前綴的正規(guī)表達(dá)式，然后由此正規(guī)表達(dá)式構(gòu)造NFADFA 求出文法的所有項(xiàng)目，按照一定規(guī)則構(gòu)造識(shí)別機(jī)活前綴的NFADFA P134：把拓廣文法的第一個(gè)項(xiàng)目作為初態(tài)集的核，通過(guò)求核的閉包和轉(zhuǎn)換函數(shù)，求出LR（0）項(xiàng)目集規(guī)范簇，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的鏈接關(guān)系得到識(shí)別或前綴的DFA。,一起交流 共同進(jìn)步,35,分析程序,LR 文法 對(duì)于一個(gè)cfg 文法, 如果能夠構(gòu)造一張 L

17、R 分析表, 使得它的每一個(gè)入口均是唯一的（Sj,rj,acc,空白），則稱該 cfg 是LR 文法,一起交流 共同進(jìn)步,36,分析,特征: 規(guī)范的 符號(hào)棧中的符號(hào)是規(guī)范句型的前綴，且不含句柄以后的任何符號(hào)(活前綴) 分析決策依據(jù)棧頂狀態(tài)和現(xiàn)行輸入符號(hào)？識(shí)別活前綴的 DFA. 四種技術(shù) LR(0) SLR(1) LR(1) LALR(1),一起交流 共同進(jìn)步,37,LR(0) 分析,LR(0)文法 能力最弱，理論上最重要 存在FA 識(shí)別活前綴 識(shí)別活前綴的DFA如何構(gòu)造 （LR(0)項(xiàng)目集規(guī)范族的構(gòu)造） LR(0)分析表的構(gòu)造,一起交流 共同進(jìn)步,38,識(shí)別活前綴的DFA,啟示:LR分析使用的

18、信息之一是句柄左部的內(nèi)容. 定義(非終結(jié)符的左文)計(jì)算可歸前綴的基礎(chǔ) LC(A)= | SA, V*, Vt*, 對(duì)拓廣文法的開(kāi)始符號(hào)S: LC(S)= 若BA 則:LC(A)LC(B). 注：LC(A)表明了在規(guī)范推導(dǎo)中在非終結(jié)符A左邊的符號(hào)串的集合。,一起交流 共同進(jìn)步,39,GS: (0) SS (1) S a A c B e (2)A b (3) A Ab (4)B d,每個(gè)非終結(jié)符的左文方程組 LC(S)= LC(S)=LC(S). LC(A)=LC(S).a LC(A) LC(B)=LC(S).aAc 化簡(jiǎn)為： S= S=S A=Sa+A B=SaAc,用代入法求解得： S= S=

19、 A=a+A B=aAc 令 =S，S，A， B，a，A,c 則方程兩邊都是上的正規(guī)式 而A=a+A 即為 A=a | A 由正規(guī)式所表示的正規(guī)集 得： A=a,一起交流 共同進(jìn)步,40,GS: (0) SS (1) S a A c B e (2)A b (3) A Ab (4)B d,定義(產(chǎn)生式的LR(0)左文) LR(0)LC(A)=| =且SA , Vt* 有推論：LR(0)LC(A )=LC(A). 則有: LR(0)LC(SS)=S LR(0)(LC(SaAcBe)=aAcBe LR(0)LC(Ab)=ab LR(0)LC(AAb)=aAb LR(0)LC(Bd)=aAcd ( =

20、VnVt)上的正規(guī)式,R,一起交流 共同進(jìn)步,41,構(gòu)造LR(0)項(xiàng)目集規(guī)范族,LR(0)項(xiàng)目集規(guī)范族(構(gòu)成識(shí)別一個(gè)文法的活前綴的DFA的狀態(tài)的全體) 。 LR（0）項(xiàng)目或配置（ item or configuration）. 文法每一個(gè)產(chǎn)生式的右部添加一個(gè)圓點(diǎn)指示識(shí)別的位置，圓點(diǎn)右移一位代表LR（0）的一個(gè)項(xiàng)目（一個(gè)產(chǎn)生式項(xiàng)目的個(gè)數(shù)為右部符號(hào)個(gè)數(shù)+1）。 A xyz A.xyz Ax.yz Axy.z Axyz. 如：SaAd S.aAd Sa .Ad SaA .d SaAd .,一起交流 共同進(jìn)步,42,項(xiàng)目的分類(lèi),根據(jù)圓點(diǎn)所在的位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符或?yàn)榭瞻秧?xiàng)目分為以下幾種：

21、歸約項(xiàng)目：A 移進(jìn)項(xiàng)目：Aa，aVT (a是終結(jié)符), , V* 以下同 待約項(xiàng)目: AB, BVN 接受項(xiàng)目：S S , S為文法開(kāi)始符號(hào) 形如 A的LR(0)項(xiàng)目只有A 是歸約項(xiàng)目,一起交流 共同進(jìn)步,43,例 GS為: S a A c B e A b A Ab B d 1)構(gòu)造識(shí)別活前綴的DFA 2)構(gòu)造它的LR(0)分析表。 3)分別給出對(duì)輸入符號(hào)串a(chǎn)bbcde和 Abbbce的LR(0)分析步驟。,一起交流 共同進(jìn)步,44,GS拓廣為: S S S a A c B e A b A Ab B d,I0 : S S S a A c B e,I1 : S S ,I2 : S a A c B

22、 e A b A Ab,I3 : S a A c B e A A b,I4 : A b ,I5 : S a A c B e B d,I7 : S a A c B e,I8 : B d ,I9 : S a A c B e ,I6 : A A b ,S,a,A,b,b,c,B,e,d,GL= ab+ cde,一起交流 共同進(jìn)步,45,活前綴與句柄的關(guān)系：,GS: 若S = A = r是的前綴，則稱r 是G的一個(gè)活前綴 1.活前綴已含有句柄的全部符號(hào)，表明產(chǎn)生式A的 右部已出現(xiàn)在棧頂 2.活前綴只含句柄的一部分符號(hào)表明A12的右部子串1已出現(xiàn)在棧頂，期待從輸入串中看到2推出的符號(hào) 3. 活前綴不含有

23、句柄的任何符號(hào)，此時(shí)期望A的右部所推出的符號(hào)串,R,一起交流 共同進(jìn)步,46,活前綴,與句柄 ,與 LR(0)項(xiàng)目,為刻劃這種分析過(guò)程中的文法G的每一個(gè)產(chǎn)生式的右部符號(hào)已有多大一部分被識(shí)別（出現(xiàn)在棧頂）的情況，分別用標(biāo)有圓點(diǎn)的產(chǎn)生式來(lái)指示位置。 A刻劃產(chǎn)生式A的 右部已出現(xiàn)在棧頂 A12 刻劃A12的右部子串1已出現(xiàn)在棧頂，期待從輸入串中看到2推出的符號(hào) A 刻劃沒(méi)有句柄的任何符號(hào)在棧頂，此時(shí)期望A的右部所推出的符號(hào)串 對(duì)于A的LR(0)項(xiàng)目只有A,一起交流 共同進(jìn)步,47,構(gòu)造識(shí)別活前綴的DFA,LR（0） 項(xiàng)目集的閉包LOSURE, GO 函數(shù)， function CLOSURE (I);

24、 /* I 是項(xiàng)目集*/ J:= I; repeat for J 中的每個(gè)項(xiàng)目A .B 和產(chǎn)生式 B ，若B . 不在J中 do 將 B . 加到J中 until 再?zèng)]有項(xiàng)目加到J中 return J ; GO (I,x) = CLOSURE(J) ; 其中， I:項(xiàng)目集，x: 文法符號(hào)， J=任何形如A x. 的項(xiàng)目|A .x I,一起交流 共同進(jìn)步,48,LR（0） 項(xiàng)目集的閉包LOSURE,若當(dāng)前處于A XYZ刻劃的情況，期望移進(jìn) First(Y)中的某些符號(hào)，假如有產(chǎn)生式 Y u | w . 那么Y u和Y w這兩個(gè)項(xiàng)目便是刻劃期望移進(jìn) First(Y)中的某些符號(hào)的情況. A XYZ

25、 Y u Y w 這三個(gè)項(xiàng)目對(duì)應(yīng)移進(jìn)歸約分析的同一個(gè)狀態(tài),這三個(gè)項(xiàng)目構(gòu)成一個(gè)配置集, 對(duì)應(yīng)每個(gè)配置集，分析表將有一個(gè)狀態(tài).,一起交流 共同進(jìn)步,49,LR(0)項(xiàng)目集規(guī)范族,計(jì)算LR（0）項(xiàng)目集規(guī)范族 C=I0 ，I1 , . In Procedure itemsets(G); Begin C := CLOSURE (S.S) Repeat For C 中每一項(xiàng)目集I和每一文法符號(hào)x Do if GO(I,x) 非空且不屬于C Then 把 GO(I,x) 放入C中 Until C 不再增大 End;,一起交流 共同進(jìn)步,50,例：文法G: （0）SE (1) EaA (2) EbB (3)

26、AcA (4) Ad (5) BcB (7) Bd LR(0) 項(xiàng)目集規(guī)范族（識(shí)別G的活前綴的DFA)： I0: SE I1: SE I2: EaA EaA A.cA EbB Ad,一起交流 共同進(jìn)步,51,I3: EbB I4: Ac.A I5: BcB AcA BcB Bd A .d BcB Bd I6: I7: I8: EaA EbB AcA I9: BcB I10: Ad I11: BcB,一起交流 共同進(jìn)步,52,LR(0)分析表的構(gòu)造,假定C=I0, I1,，In，令每個(gè)項(xiàng)目集Ik的下標(biāo)k 為分析器的一個(gè)狀態(tài)，因此，G 的LR(0)分析表含有狀態(tài)0，1，n。令那個(gè)含有項(xiàng)目SS的Ik

27、的下標(biāo)k為初態(tài)。ACTION和GOTO可按如下方法構(gòu)造： 若項(xiàng)目Aa屬于Ik且GO (Ik, a)= Ij, a為終結(jié)符，則置ACTIONk, a為“把狀態(tài)j和符號(hào)a移進(jìn)?！?，簡(jiǎn)記為“sj”; 若項(xiàng)目A屬于Ik, 那么，對(duì)任何終結(jié)符a, 置ACTIONk, a為“用產(chǎn)生式A進(jìn)行規(guī)約”，簡(jiǎn)記為“rj”;其中，假定A為文法G的第j個(gè)產(chǎn)生式； 若項(xiàng)目SS屬于Ik, 則置ACTIONk, #為“接受”，簡(jiǎn)記為“acc”; 若GO (Ik, A)= Ij, A為非終結(jié)符，則置GOTO(k, A)=j; 分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“出錯(cuò)標(biāo)志”。,一起交流 共同進(jìn)步,53,按上述算法構(gòu)

28、造的含有ACTION和GOTO兩部分的分析表，如果每個(gè)入口不含多重定義，則稱它為文法G的一張LR(0)表。具有LR(0)表的文法G稱為一個(gè)LR（0）文法。 LR(0)文法是無(wú)二義的。,一起交流 共同進(jìn)步,54,例 文法G:（0）SE (1) EaA (2) EbB (3) AcA (4) Ad (5) BcB (6) Bd,一起交流 共同進(jìn)步,55,例：（0）SS (1)SrD (2) DD,i (3) DI Real x,y, LR（0）項(xiàng)目 1. SS 2. SS 3. SrD 4. SrD 5. SrD 6. DD,i 7. DD,i 8. DD,i 9. DD,i 10. Di 11.

29、 Di,一起交流 共同進(jìn)步,56,NFA,1,3,10,7,8,i,S,r,r,D,4,6,D,一起交流 共同進(jìn)步,57,例： (0) SS (1)SrD (2) DD,i (3) Di LR（0）項(xiàng)目集規(guī)范族 I0: SS I3: Sr D Sr D DDi I1: SS I4: Di I2: SrD I5: DDi DD i I6: DDi Di 其中I3中含有移進(jìn)/歸約沖突 文法不是LR(0)的，如何解決？,一起交流 共同進(jìn)步,58,SLR(1)技術(shù),若 LR(0) 項(xiàng)目集規(guī)范族中有項(xiàng)目集IK含 移進(jìn)/歸約 歸約/歸約 沖突： IK : .A.b , P . , Q . , 若FOLLO

30、W(Q) FOLLOW(P) = FOLLOWP(P) b = FOLLOW(Q) b = 則解決沖突的SLR(1)技術(shù)： action k,b = 移進(jìn) 對(duì)a FOLLOW (P) 則 action k,a =用 P 歸約 對(duì)a FOLLOW (Q) 則 action k,a =用 Q 歸約 能用SLR(1)技術(shù)解決沖突的文法稱為SLR(1)文法。 SLR(1)文法是無(wú)二義的。,一起交流 共同進(jìn)步,59,SLR表,假定C=I0, I1,，In，令每個(gè)項(xiàng)目集Ik的下標(biāo)k 為分析器的一個(gè)狀態(tài)，因此，G 的SLR分析表含有狀態(tài)0，1，n。令那個(gè)含有項(xiàng)目SS的Ik的下標(biāo)k為初態(tài)。函數(shù)ACTION和G

31、OTO可按如下方法構(gòu)造： 若項(xiàng)目Aa屬于Ik且GO (Ik, a)= Ij, a為終結(jié)符，則置ACTIONk, a為“把狀態(tài)j和符號(hào)a移進(jìn)?！?，簡(jiǎn)記為“sj”; 若項(xiàng)目A屬于Ik, 那么，對(duì)任何輸入符號(hào)a, aFOLLOW(A),置ACTIONk, a為“用產(chǎn)生式A進(jìn)行規(guī)約”，簡(jiǎn)記為“rj”;其中，假定A為文法G的第j個(gè)產(chǎn)生式； 若項(xiàng)目SS屬于Ik, 則置ACTIONk, #為“接受”，簡(jiǎn)記為“acc”; 若GO (Ik, A)= Ij, A為非終結(jié)符，則置GOTO(k, A)=j; 分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“出錯(cuò)標(biāo)志”。 按上述算法構(gòu)造的含有ACTION和GOTO兩部

32、分的分析表，如果每個(gè)入口不含多重定義，則稱它為文法G的一張SLR表。具有SLR表的文法G稱為一個(gè)SLR（1）文法。數(shù)字1的意思是，在分析過(guò)程中頂多只要向前看一個(gè)符號(hào)。,一起交流 共同進(jìn)步,60,實(shí)數(shù)說(shuō)明文法的SLR（1）分析表 狀態(tài) ACTION GOTO r , i # S D 0 S2 1 1 acc 2 S4 3 3 r1 S5 r1 r1 4 r3 r3 r3 r3 5 S6 6 r2 r2 r2 r2,一起交流 共同進(jìn)步,61,? SLR,例：文法G: （0）SS (1) SaAd (2) SbAc (3) Saec (4) Sbed (5) Ae LR(0) 項(xiàng)目集規(guī)范族（識(shí)別G的

33、活前綴的DFA)： I0: SS I1: SS I2: SaAd SaAd Saec SbAc Ae Saec Sbed,一起交流 共同進(jìn)步,62,? SLR,I3: SbAc I4: I5: Sbed SaAd Saec Ae Ae I6: I7: I8: SbAc Sbed SaAd Ae I9: Saec I10: SbAc I11: Sbed,一起交流 共同進(jìn)步,63,一起交流 共同進(jìn)步,64,?,I5: S aec A e S=S=aAd=aed S=S=aec I7: S bed A e S=S=bAc=bec S=S=bed ？信息 哪些輸入符號(hào)能跟在句柄之后,R,R,R,R,R

34、,R,R,R,R,R,一起交流 共同進(jìn)步,65,Another example （P142）,GS: (0) SS (1) SL=R (2) SR (3) L *R (4) Li (5) RL LR(0)項(xiàng)目集規(guī)范族和G0函數(shù) I1 S S. I6 I0 SS I2 SL=R S L=.R L .*R SL=R R L. R .L L .i SR L*R I3 Li SR RL I4 L* R I7 I5 RL L*R Li L*R L .i I8 RL,一起交流 共同進(jìn)步,66,(1)不是LR(0)文法 I2 SL=R R L.中存在移進(jìn)/歸約沖突 （2） SLR能否解決I2中的沖突 FOL

35、LOW（R）=#,=與=交不為空 不是SLR（1）文法 SL.=R RL. 若用 RL 歸約 則形成 R= 而 R=不是活前綴 ?早知此信息 向前搜索符 LR（1）方法 若 A .B I 則 B . （ B 是一產(chǎn)生式） I 把FIRST（B）中的符號(hào)作為用B 歸約的搜索符,一起交流 共同進(jìn)步,67,LR（1）項(xiàng)目 A . ， a LR（K）項(xiàng)目 A . ， a1 a2 aK ,一起交流 共同進(jìn)步,68,構(gòu)造LR(1)項(xiàng)目集規(guī)范族和G0函數(shù),closure(I)按如下方式構(gòu)造 (1) I的任何項(xiàng)目屬closure(I)； (2)若A1B2，aclosure(I)，B是一產(chǎn)生式，那么對(duì)于FIRS

36、T(2a)中的每個(gè)終結(jié)符b，如果B,b不在closure(I)中，則把它加進(jìn)去； (3)重復(fù)（1）（2），直至closure(I)不再增大。,一起交流 共同進(jìn)步,69,GO函數(shù)： 若I是一個(gè)項(xiàng)目集，X是一個(gè)文法符號(hào) GO(I, X)= closure(J) 其中 J= 任何形如AX,a的項(xiàng)目A.X,aI LR(I)項(xiàng)目規(guī)范族C的構(gòu)造算法類(lèi)同LR(0)的，只是初始時(shí)： C= closure(SS,#);,一起交流 共同進(jìn)步,70,LR(1)項(xiàng)目集規(guī)范族,I0: SS, # I5: S aec,# S aAd, # A e,d S bAc, # I6: S bAc, # S aec, # I7:

37、S bed, # S bed, # A e,c I1: S S,# I8: S aAd, # I2: S aAd, # I9: S aec, # S aec, # I10: S bAc, # A e, d I11: S bed, # I3: S bAc, # S bed, # Ae,c I4: S aAd, #,一起交流 共同進(jìn)步,71,LR(1)項(xiàng)目集規(guī)范族,I1: SS,# I9 :S L=R. ,# I2: I6: SL=R,# I0: SS,# SL=R,# RL,# SL=R,# RL,# L*R,# SR,# I3: Li,# L*R,=/# SR,# Li,=/# I4: I11

38、: RL,# L*R,=/# L*R,# L*R,=/# RL,# I5: Li,=/# Li,=/# L*R,# RL,=/# Li,# I7 L*R ,=/# I8 RL,#/= I10 I13 I12: Li. RL,# L*R,#,一起交流 共同進(jìn)步,72,LR(1)分析表的構(gòu)造,若項(xiàng)目AA屬于Ik, 那么 置 ACTIONk, a為“用產(chǎn)生式A進(jìn)行規(guī)約”，簡(jiǎn)記為“rj”;其中，假定A為文法G的第j個(gè)產(chǎn)生式；,一起交流 共同進(jìn)步,73,規(guī)范的LR(1)分析表的構(gòu)造,假定LR(1)項(xiàng)目集規(guī)范族C=I0, I1,，In，令每個(gè)項(xiàng)目集Ik的下標(biāo)k 為分析器的一個(gè)狀態(tài)，G 的LR（1）分析表含

39、有狀態(tài)0，1，n。 1.令那個(gè)含有項(xiàng)目SS ，#的Ik的下標(biāo)k為狀態(tài)0（初態(tài)）.ACTION表和GOTO表可按如下方法構(gòu)造 2.若項(xiàng)目A,b屬于Ik, 那么置ACTIONk, b為“用產(chǎn)生式A進(jìn)行規(guī)約”，簡(jiǎn)記為“rj”;(假定A為文法G的第j個(gè)產(chǎn)生式) 3.若項(xiàng)目Aa,b屬于Ik且GO (Ik, a)= Ij,則置ACTIONk, a為“把狀態(tài)j和符號(hào)a移進(jìn)棧”，簡(jiǎn)記為“sj”; 4.若項(xiàng)目SS,#屬于Ik, 則置ACTIONk, #為“接受”，簡(jiǎn)記為“acc”; 5.若GO (Ik, A)= Ij, A為非終結(jié)符，則置GOTO(k, A)=j; 分析表中凡不能用規(guī)則1至5填入信息的空白格均置

40、上“出錯(cuò)標(biāo)志”。 按上述算法構(gòu)造的含有ACTION和GOTO兩部分的分析表，如果每個(gè)入口不含多重定義，則稱它為文法G的一張規(guī)范的LR(1)分析表。具有規(guī)范的LR(1)表的文法G稱為一個(gè)LR（1）文法。,一起交流 共同進(jìn)步,74,LR(1) 文法滿足下面兩個(gè)條件 1.如果一個(gè)項(xiàng)目集里有項(xiàng)目 A uxv , a ， x是終結(jié)符，那就不會(huì)有項(xiàng)目B u, x 2.項(xiàng)目集里所有歸約項(xiàng)目 的向前搜索符不相交，即不能同時(shí)含有項(xiàng)目 A u, a 和B v , a,一起交流 共同進(jìn)步,75,LR（K）分析,LR（K）項(xiàng)目 A . ， a1 a2 aK a1 a2 aK 向前搜索符串 移進(jìn)項(xiàng)目 A . a， a1

41、 a2 aK 待約項(xiàng)目 A . B， a1 a2 aK 歸約項(xiàng)目 A . ， a1 a2 aK ,一起交流 共同進(jìn)步,76,LR(1)比SLR（1）能力強(qiáng),例2 (0) SS (1)SL=R (2)SR (3)L *R (4)Lid (5)RL不能用SLR（1）技術(shù)解決，但能用LR（1）,一起交流 共同進(jìn)步,77,I1:SS ,#,I5:Li ,=/#,I7:L*R ,=/#,I8:RL ,=/#,I9:SL=R ,#,I3:SR ,#,I12:Li ,#,I10:RL ,#,I13:L*R ,#,I0:S S,# S L=R,# S R,# L *R,=/# L i,=/# R L,#,I4

42、: L *R,=/# R L,=/# L i,=/# L *R,=/#,I6:S L= R,# R L,# L *R,# L i,#,I11:L * R,# R L,# L *R,# L i,#,I2:S L =R,# R L,#,s,R,=,L,R,i,i,*,i,i,R,L,L,R,L,*,*,*,例2的 LR(1)項(xiàng)目集及轉(zhuǎn)換函數(shù),一起交流 共同進(jìn)步,78,每個(gè)SLR（1）文法都是LR（1）的，一個(gè)SLR（1）文法的規(guī)范LR分析器比其SLR（1）分析器的狀態(tài)要多。,例 G(S):S BB BaB B b I0:S.S S .BB B .aB B .b I1:S S. I2:S B.B B

43、.aB B.b I3:Ba.B B.aB B.b I4:BaB. I5: Bb. I6: SBB.,一起交流 共同進(jìn)步,79,I0:S S,# S BB,# B aB,a/b B b,a/b,I1:S S,#,I2:S BB,# B aB,# B b,#,I5:S BB,#,I6:BaB,# B aB,# B b,#,I3:B aB,a/b B aB,a/b B b,a/b,I4:B b,a/b,I7:B b,#,I9:B aB,#,I8:B aB,a/b,s,B,B,a,b,b,b,B,B,a,a,a,LR(1)項(xiàng)目集規(guī)范族和轉(zhuǎn)換函數(shù),b,一起交流 共同進(jìn)步,80,LALR在SLR（1）和L

44、R（1）間尋找折衷辦法（狀態(tài)數(shù)目，分析能力）,LALR (lookahead LR) 合并LR（1）項(xiàng)目集規(guī)范族的同心集I36 I47 I89（除搜索符外兩個(gè)集合是相同的）.,I3:B aB,a/b B aB,a/b B b,a/b,I6:B aB,# B aB,# B b,#,I4:B b,a/b,I7:B b,#,I8:B aB,a/b,I9:B aB,#,一起交流 共同進(jìn)步,81,構(gòu)造 LALR(1)分析表.方法1-“brute-force”,1.構(gòu)造文法G的規(guī)范 LR(1) 狀態(tài). 2.合并同心集的狀態(tài). 3.新 LALR(1) 狀態(tài)的GO函數(shù)是合并的同心集狀態(tài)的GO函數(shù)的并. 4. LALR(1)分析表的ACTION 和 GOTO 登錄