編譯程序原理與實(shí)現(xiàn)：第5章 LALR(1)方法

1、LR(1)分析存在的問(wèn)題為消除沖突，引入太多的狀態(tài);有些狀態(tài)含有完全相同的LR(0)項(xiàng)目部分，只有展望符部分是不同的;LR(1)項(xiàng)目的心：如果(A, ss) 是一個(gè)LR(1)項(xiàng)目，則其中的LR(0)項(xiàng)目部分稱為它的心;LR(1)自動(dòng)機(jī)狀態(tài)的心：一個(gè)狀態(tài)所含有的所有LR(1)項(xiàng)目的心;同心狀態(tài)：如果兩個(gè)LR(1)狀態(tài)具有相同的心，則稱這兩個(gè)狀態(tài)為同心狀態(tài)。LALR(1) 分析主要思想合并文法G的LR(1)自動(dòng)機(jī)中的同心狀態(tài)，得到的自動(dòng)機(jī)稱為L(zhǎng)ALR(1)自動(dòng)機(jī)；若這個(gè)得到的LALR(1)自動(dòng)機(jī)沒(méi)有沖突，則稱文法G是LALR(1)文法。LALR(1)分析過(guò)程構(gòu)造LALR(1)自動(dòng)機(jī) 構(gòu)造LALR(

2、1)分析表(同LR(1)分析表構(gòu)造方法)LALR(1)驅(qū)動(dòng)程序 = LR(1)驅(qū)動(dòng)程序如何構(gòu)造LALR(1)自動(dòng)機(jī)第一種途徑：首先構(gòu)造LR(1)自動(dòng)機(jī)然后合并其中的同心狀態(tài)該方法簡(jiǎn)單，但不現(xiàn)實(shí)(not practical)!Step1:構(gòu)造LR(1)自動(dòng)機(jī)VT = a, b, =VN = S, L, RS = SP: (1) S L = R (2) S R (3) L aR (4) L b (5) R L0Z S , #S L = R, #S R, #R3S R, # R L , #1ZS, #Sb4L b, =, # L5S L=R, # R L, #L aR, =, #L b , =, #

3、=a6S L=R, # R L , #L aR, #L b , #12L aR, =, # R L , =,#L aR, =,#L b , =,#b4L14R L, =,# a13L aR, =,# R7S L=R, # R8R L, # L11L b, # b9L aR, # R L , #L aR, #L b , #aL8R10L aR, # baStep2: 合并同心狀態(tài)狀態(tài)4和11同心 狀態(tài)8和14同心狀態(tài)10和13同心狀態(tài)9和12同心0Z S , #S L = R, #S R, #R3S R, # R L , #1ZS, #Sb4L b, =, # L5S L=R, # R L, #

4、L aR, =, #L b , =, #=a6S L=R, # R L , #L aR, #L b , #12L aR, =, # R L , =,#L aR, =,#L b , =,#b4L14R L, =,# a13L aR, =,# R7S L=R, # R8R L, # L11L b, # b9L aR, # R L , #L aR, #L b , #aL8R10L aR, # ba4141213 LR(1) 分析表Action 表Goto 表ab=#SLR0S12S41531Accept 3R24R4R45S6R56S9S11877R1 LR(1) 分析表 (接上頁(yè).)Action

5、表Goto 表ab=#SLR8R59S9S111010R311R412S12S4141313R3R314R4R415LALR(1) 分析表Action 表Goto 表ab=#SLR0S12S41531Accept 3R24R4R45S6R56S12S41477R112S12S4141313R3R314R4R4LALR(1) 自動(dòng)機(jī)對(duì)于給定的上下文無(wú)關(guān)文法 GG的LALR(1)項(xiàng)目跟LR(1)項(xiàng)目形式相同;LALR(1)自動(dòng)機(jī)中每個(gè)狀態(tài)S中各個(gè)項(xiàng)目的展望符集是把LR(1)自動(dòng)機(jī)中所有和S同心的狀態(tài)的對(duì)應(yīng)項(xiàng)目的展望符集合合并后得到的;如果每個(gè)LALR(1)的狀態(tài)都用該狀態(tài)的心(LR(0)項(xiàng)目)替換

6、，則LALR(1)自動(dòng)機(jī)和它的LR(0)自動(dòng)機(jī)相同;G的LALR(1) 自動(dòng)機(jī)的狀態(tài)數(shù)同LR(0)自動(dòng)機(jī)的狀態(tài)數(shù)相同；能不能用LR(0)自動(dòng)機(jī)構(gòu)造LALR(1)自動(dòng)機(jī)呢？如何構(gòu)造LALR(1)自動(dòng)機(jī)第二種途徑：首先構(gòu)造LR(0)自動(dòng)機(jī)然后為每個(gè)狀態(tài)的每個(gè)LR(0)項(xiàng)目計(jì)算展望符集；是實(shí)際應(yīng)用中采用的方法！關(guān)鍵是如何計(jì)算展望符呢？LALR(1)展望符的計(jì)算方法投影得到的項(xiàng)目: 展望符集是指向該狀態(tài)的所有狀態(tài)中對(duì)應(yīng)項(xiàng)目的展望符集的合集;S L=R, R L , L aR, L b , LALR(1) 狀態(tài)iS L =R, j1S L =R, jn派生得到的項(xiàng)目: 展望符集和LR(1)中的計(jì)算方法一

7、樣;構(gòu)造LALR(1) 自動(dòng)機(jī)VT = a, b, =VN = S, L, RS = SP: (1) S L = R (2) S R (3) L aR (4) L b (5) R LStep1: 構(gòu)造LR(0) 自動(dòng)機(jī)0 S S , S L = R, S R, R3S RR L , 1SSSb4L b, L5S L=R, R L, L aR, L b , =a6S L=R, R L , L aR, L b , LR7S L=R, aRLa13L aR, 14R L, 12 L aR, bR LL aR, L b ,Step2:計(jì)算展望符0 S S , S L = R, S R, R3S RR

8、L , 1SSSb4L b, L5S L=R, R L, L aR, L b , =a6S L=R, R L , L aR, L b , LR7S L=R, aRLa13L aR, 14R L, 12 L aR, b#R LL aR, L b ,=，#=，#=，#=，#=，#=，#=，#=，#=，#LALR(1) 文法如果文法G的LALR(1) 自動(dòng)機(jī)中沒(méi)有沖突,則文法G稱為L(zhǎng)ALR(1) 文法;注意: 由于對(duì)LR(1)自動(dòng)機(jī)中的同心狀態(tài)進(jìn)行了合并, 把展望符集進(jìn)行合并, 因此有可能導(dǎo)致沖突, 從而不是LALR(1)文法;合并同心狀態(tài)只能產(chǎn)生歸約-歸約沖突，不會(huì)產(chǎn)生移入-歸約沖突，為什么？LR

9、(0), SLR(1), LR(1)和LALR(1)比較狀態(tài)數(shù): LR(1) LALR(1) = SLR(1) = LR(0)展望符的確定: LR(0)沒(méi)有展望符；SLR(1)取follow集；LR(1)取不同位置的follow集；LALR(1)取同心項(xiàng)的展望符的并集；向前看輸入符: SLR(1),LR(1)和LALR(1)向前看一個(gè)輸入符；LR(0)不看;分析能力:LR(1) LALR(1) SLR(1) LR(0)第五章 自底向上的語(yǔ)法分析5.1 自底向上的語(yǔ)法分析方法概述5.2 LR(0)分析的有限自動(dòng)機(jī)5.3 LR(0) 分析5.4 SLR(1) 分析5.5 LR(1) 分析5.6 LALR(1) 分析5.7 LALR(1) 語(yǔ)法分析器的自動(dòng)生成器 (YACC)5.7 LALR(1) 語(yǔ)法分析程序生成器 (YACC)是一種廣泛采用的程序設(shè)計(jì)語(yǔ)言語(yǔ)法分析程序的生成工具;如