編譯第4章7白底黑字

4.5.5LALR（1）分析法 LR(1)分析法雖然可以解決SLR(1)方法所難以解決的移進(jìn)—?dú)w約或歸約—?dú)w約沖突，但是對(duì)同一個(gè)文法而言,當(dāng)搜索符不同時(shí),使得同一個(gè)項(xiàng)目集被分裂成多個(gè)項(xiàng)目集從而引起狀態(tài)數(shù)的劇烈增長，導(dǎo)致時(shí)間和內(nèi)存空間的急劇上升，使其應(yīng)用受到一定的限制，為了克服LR(1)分析法的這種缺點(diǎn)，我們可以采用LALR(1)分析法。4.5.5LALR（1）分析法 LALR(1)分析法是界于SLR(1)分析法和LR(1)分析法之間的一種語法分析方法，這種分析法能解決SLR(1)分析法所不能解決的沖突動(dòng)作，并且其分析表的狀態(tài)個(gè)數(shù)與SLR(1)分析表的狀態(tài)個(gè)數(shù)一樣多。 LALR(1)分析法的基本思想是對(duì)LR(1)項(xiàng)目集規(guī)范族中將所有同心的項(xiàng)目集合并為一，以減少項(xiàng)目集個(gè)數(shù)。4.5.5LALR（1）分析法

所謂同心的LR(1)項(xiàng)目集是指在兩個(gè)LR(1)項(xiàng)目集中,除搜索符不同之外,核心部分是相同的。

例如，分析前例文法的LR(1)項(xiàng)目集族，可以發(fā)現(xiàn)同心集如下：

0.S'→S3.L→*R1.S→L=R4.L→i2.S→R5.R→LI0:SI1:S'→S?,$LI2:S→L?=R,$R→L?,$I3:S→R?,$RI4:L→*?R,=/$R→?L,=/$L→?*R,=/$L→?i,=/$*I5:L→i?,=/$iiS'→?S,$S→?L=R,$S→?R,$L→?*R,=/$L→?i,=/$R→?L,$*I6:S→L=?R,$L→?*R,$L→?i,$R→?L,$I9:S→L=R?,$I11:L→*?R,$R→?L,$L→?*R,$L→?i,$I10:R→L?,$I12:L→i?,$I7:L→*R?,=/$I13:L→*R?,$I8:R→L?,=/$*LR(1)項(xiàng)目集族及轉(zhuǎn)換函數(shù)=RLRL*LiR0.S′→S1.S→L=R2.S→R3.L→*R4.L→i5.R→Li

I4與I11，I5與I12，I7與I13，I8與I10它們倆倆之間除了搜索符不同之外,“心”是相同的。將同心集合并為：4.5.5LALR（1）分析法I4,11:L→*?R,=/$R→?L,=/$L→?*R,=/$L→?i,=/$I5,12:L→i?,=/$I7,13:L→*R?,=/$I8,10:R→L?,=/$

4.5.5LALR（1）分析法

我們看到合并同心集后的項(xiàng)目集其核心部分不變，僅搜索符合并。對(duì)合并同心集后的項(xiàng)目集的轉(zhuǎn)換函數(shù)為GO(I,X)自身的合并，這是因?yàn)橄嗤男闹D(zhuǎn)換函數(shù)仍屬同心集。例如GO(I4,11,i)=GO(I4,i)∪GO(I11,i)=I5,12GO(I4,11,R)=GO(I4,R)∪GO(I11,R)=I7,13GO(I4,11,*)=GO(I4,*)∪GO(I11,*)=I4,114.5.5LALR（1）分析法

合并同心集需著重指出的是若文法是LR(1)文法,即它的LR(1)項(xiàng)目集中不存在動(dòng)作沖突,合并同心集后若有沖突也只可能是歸約—?dú)w約沖突而不可能是移進(jìn)—?dú)w約沖突。

假定LR(1)文法的項(xiàng)目集Ik與Ij為同心集，其中Ik={[A→α?,a1][B→β?aγ,b1]}Ij={[A→α?,a2][B→β?aγ,b2]}合并同心集后的項(xiàng)目集Ikj={[A→α?,a1/a2][B→β?aγ,b1/b2]}4.5.5LALR（1）分析法

因?yàn)榧僭O(shè)文法是LR(1)的,在Ik中

{a1}∩{a}=Φ,在Ij中{a2}∩{a}=Φ,顯然在Ikj中({a1}∪{a2})∩{a}=Φ

這也就是說合并同心集以后,不可能有移進(jìn)—?dú)w約沖突。

但可能有歸約—?dú)w約沖突。例如,可設(shè)想有兩個(gè)同心的LR(1)項(xiàng)目集:4.5.5LALR（1）分析法

現(xiàn)在我們可以根據(jù)合并同心集后的項(xiàng)目集族構(gòu)造文法的LALR(1)分析表，其構(gòu)造方法如下：Ik={[A→α?,a][B→α?,b]}Ij={[A→α?,b

][B→α?,a]}合并同心集后的項(xiàng)目集Ikj={[A→α?,a/b][B→α?,a/b]}合并后產(chǎn)生了歸約—?dú)w約沖突。4.5.5LALR（1）分析法 2.若LR(1)項(xiàng)目集族中不存在含沖突的項(xiàng)目集，則合并所有同心集，構(gòu)造出文法的LALR(1)項(xiàng)目集族。 1.構(gòu)造拓廣文法G′的LR(1)項(xiàng)目集族。

例如，對(duì)前例中文法G的LR(1)項(xiàng)目集族合并同心集后構(gòu)造出的LALR(1)項(xiàng)目集族如下圖所示。I0:0.S'→S1.S→L=R2.S→R3.L→*R4.L→i5.R→LSI1:S'→S?,$LI2:S→L?=R,$R→L?,$I3:S→R?,$RI4,11:L→*?R,=/$R→?L,=/$L→?*R,=/$L→?i,=/$*I5,12:L→i?,=/$iiS'→?S,$S→?L=R,$S→?R,$L→?*R,=/$L→?i,=/$R→?L,$*I9:S→L=R?,$I6:L→*?R,$R→?L,$L→?*R,$L→?i,$I7,13:L→*R?,=/$I8,10:R→L?,=/$LALR(1)項(xiàng)目集族及轉(zhuǎn)換函數(shù)RLR=*Li4.5.5LALR

（1）分析法4.LALR(1)項(xiàng)目集族構(gòu)造該文法的LALR(1)分析表的方法與LR(1)分析表的構(gòu)造方法相同。由圖構(gòu)造文法的LALR(1)分析表如下表所示。 3.若LALR(1)項(xiàng)目集族中不存在歸約—?dú)w約沖突，則該文法是LALR(1)文法。對(duì)例中的文法,由于合并同心集后不存在歸約—?dú)w約沖突，所以該文法是LALR(1)文法。G[S]的LALR(1)分析表01234,115,1267,13ACTIONGOTOi*=$SLRS5,12S4,11123accS6

r5r2S5,12

S4,11r4

r4S5,12S4,11r3

r3r5

r58,107,138,1098,109r1I0:0.S'→S1.S→L=R2.S→R3.L→*R4.L→i5.R→LSI1:S'→S?,$LI2:S→L?=R,$R→L?,$I3:S→R?,$RI4,11:L→*?R,=/$R→?L,=/$L→?*R,=/$L→?i,=/$*I5,12:L→i?,=/$iiS'→?S,$S→?L=R,$S→?R,$L→?*R,=/$L→?i,=/$R→?L,$*I9:S→L=R?,$I6:L→*?R,$R→?L,$L→?*R,$L→?i,$I7,13:L→*R?,=/$I8,10:R→L?,=/$LALR(1)項(xiàng)目集族及轉(zhuǎn)換函數(shù)RLR=*Li4.5.5LALR（1）分析法

對(duì)一給定的文法G，其LALR(1)分析表比LR(1)分析表狀態(tài)數(shù)要少，但在分析文法G[S]的某一個(gè)含有錯(cuò)誤的符號(hào)串時(shí),LALR(1)分析速度比LR(1)分析速度要慢，為什么？4.5.6對(duì)二義性文法的應(yīng)用

與其相應(yīng)的LR分析表一定含有多重定義的元素。如何利用這一缺點(diǎn)？

任何一個(gè)二義性文法決不是LR類文法，我們知道4.5.6對(duì)二義性文法的應(yīng)用E→E+E|E*E|(E)|id相應(yīng)的非二義性文法為：E→E+T|TT→T*F|FF→(E)|id例如，考慮算術(shù)表達(dá)式的二義性文法4.5.6對(duì)二義性文法的應(yīng)用2.二義性文法的LR分析表所含狀態(tài)數(shù)肯定比非二義性文法少,因?yàn)榉嵌x性文法含有右部僅只一個(gè)非終結(jié)符號(hào)的規(guī)則E→T和T→F，它們要占用狀態(tài)和降低分析器的分析效率。兩者相比，二義性文法的優(yōu)點(diǎn)在于:若需改變運(yùn)算符的優(yōu)先級(jí)或結(jié)合性,無需改變文法自身。4.5.6對(duì)二義性文法的應(yīng)用

現(xiàn)在我們構(gòu)造算術(shù)表達(dá)式二義性文法的LR(0)項(xiàng)目集規(guī)范族如下圖所示：算術(shù)表達(dá)式二義性文法的LR(0)項(xiàng)目集規(guī)范族和轉(zhuǎn)移函數(shù)I0:E'→·EE→·E+EE→·E*EE→·(E)E→·idI1:E'→E·E→E·+EE→E·*EI2:E→·E+EE→·E*EE→·(E)E→·idE→(·E)I3:E→id·I4:E→·E+EE→·E*EE→·(E)E→·idE→E+·EI5:E→·E+EE→·E*EE→·(E)E→·idE→E*·EI6:E→(E·)E→E·*EE→E·+EI7:E→E+E·E→E·*EE→E·+EI8:E→E*E·E→E·*EE→E·+EI9:E→(E)·E(id(id+id(I3I2﹡(idE+﹡E+﹡E﹡+)4.5.6對(duì)二義性文法的應(yīng)用

從圖中可以看出狀態(tài)I1,I7和I8中存在移進(jìn)—?dú)w約沖突,I1中沖突可用SLR(1)方法解決。

對(duì)I7和I8而言：

因?yàn)镕OLLOW(E')∩{+,*}=ф，即遇到輸入符號(hào)為‘$’時(shí)則接受，遇到‘＋’或‘*’時(shí)則移進(jìn)。FOLLOW(E)∩{+,*}={$,+,*,)}∩{+,*}≠Φ由于有4.5.6對(duì)二義性文法的應(yīng)用

因而I7和I8中沖突不能用SLR(1)方法解決，也不能用其它LR(K)方法解決，但是我們用+，*的優(yōu)先級(jí)和結(jié)合性可以解決這類沖突。4.5.6對(duì)二義性文法的應(yīng)用

那么在I7中,由于‘*’優(yōu)先級(jí)高于‘＋’,所以狀態(tài)7面臨‘*’移進(jìn)，又因‘＋’服從左結(jié)合，所以狀態(tài)7面臨‘＋’則用E→E＋E歸約。

若我們規(guī)定‘*’的優(yōu)先級(jí)高于‘＋’的優(yōu)先級(jí)，且它們都服從左結(jié)合4.5.6對(duì)二義性文法的應(yīng)用

在I8中,由于‘*’優(yōu)先于‘＋’且‘*’服從左結(jié)合，因此狀態(tài)8面臨‘＋’或‘*’都應(yīng)用E→E*E歸約。

由此構(gòu)造的該二義性文法的LR分析表如下表所示：4.5.6對(duì)二義性文法的應(yīng)用二義性文法的LR分析表0S3S2112345r4r4r4r4S4S5