構建LALR（1）項目集族

構造LALR（1）項目有兩種思路。一種是：先構造LR（1）項目，再合并同心項目；另一種是：先構造LR（0）項目，再為為其配上搜索符。本文介紹第二種方法。

搜索符生成有兩種方法。一是，自己生成。二是，上一項目集傳播獲得的。項目集之間傳播搜索符遇到的問題是：若多個項目集可以直接轉移到一個項目集I上，那么每當I接收到，這些項目集傳播過來的新的搜索符時，I就得重新再往下傳播自己新的搜索符。考慮到這一點可以使用壓棧的方式，將可以傳播的項目壓棧存好，將棧頂彈出用于傳播，在傳播過程中同時壓入新的可傳播項目。直到最后棧為空，即沒有項目可以傳播為止。

假設一含S’->S的拓廣文法為G。具體算法如下：

1. 構造G的 LR（0）項目集規范族（實就是為了方便分析，有皆可）。

2. 將I0,S’->S，#壓入棧。（I0為S’->S所在項目，#為搜索符，顯然它是可以傳播的）

3. 將規范族中的所有項目集的生成搜索符壓入棧。因為它們是新生的可傳播的。

4. 彈出棧頂，使棧頂往下傳播。傳播到下一個項目中后，生成自生成項目（就是自生符）。將新項入棧。繼續傳播，直到不能傳播為止。

5. 重復第4步，直到棧為空。

上面過程中，所有新項就是LALR（1）項目集族了，包括自生的，和傳播的。

示例。考慮如下文法，求其LALR（1）項目集族：

(1)S->L=R

(2)S->R

(3)L->*R

(4)L->i

(5)R->L

此文法的LR（0）項目集規范族為：

I0:	S'->·S		I4:	L->*·R
	S->·L=R			R->·L
	S->·R			L->·*R
	L->·*R			L->·i
	L->·i		I5:	L->i·
	R->·L		I6:	S->L=·R
I1:	S'->S·			R->·L
I2:	S->L·=R			L->·*R
	R->L·			L->·i
I3:	S->R·		I7:	L->*R·
			I8:	R->L·
			I9:	S->L=R·

LALR（1）項目集族構建過程詳解（略去了記錄新項目操作）：

將I0，S'->·S，#壓棧。接著各項目集自生符壓棧

只有I0有生成符：

I0，L->·*R，=

I0，L->·i,=

棧中的狀態為：

I0，S'->·S,#

I0,L->·*R,=

I0,L->·i,=

接下來，處理棧頂。

彈出：I0，L->·i,=傳播得：I5,L->i·,=。止住。

彈出：I0,L->·*R,=傳播得：I4,L->*·R,=。此項可以傳播，又可以自生成。先不急傳播，保存一下自生成的項目：

I4,R->·L,=

I4, L->·*R,=

I4, L->·i,=

棧狀態：

I0，S'->·S，#

I0，L->·*R，=

I4,R->·L,=

I4, L->·*R,=

I4, L->·i,=

好I4, L->*·R，=接著往下傳播，得到I7, L->*R·,=。止住。

彈出：I4, L->·i,=傳播得I5,L->i·,=。止住。注意，此項已經存在。

彈出I4, L->·*R,=傳播得：I4, L->*·R,=。此項已經傳播過了。（算法應該有個機制記錄項目是否被傳播過）

彈出：I4,R->·L,=傳播得：I8, R->L·,=。止住。

彈出：I0，L->·*R,=傳播得:I4, L->*·R，=。已傳播過。

彈出I0,S'->·S,#此時，它還沒有自生成，不著急傳播。它會生成：

I0,S->·L=R,#

I0,S->·R,#

I0,L->·i,#

I0,L->·*R,#

I0,R->·L,#

而這些項目都是可以傳播的，所有都得入棧（我的天呀，還有這么多！）。入棧后，棧狀態為：

I0,S->·L=R,#

I0,S->·R,#

I0,L->·i,#

I0,L->·*R,#

I0,R->·L,#

I0，S'->·S，#傳播得：I1, S'->S·,#不能繼續了。

彈出：I0,R->·L,#傳播得：I2,R->L·,#。止住。

彈出：I0,L->·*R,#傳播得：I4,L->*·R,#。此項又自生成：

I4,R->·L,#

I4,L->·*R,#

I4,L->·i,#

此時棧頂狀態：

I0,S->·L=R,#

I0,S->·R,#

I0,L->·i,#

I4,R->·L,#

I4,L->·*R,#

I4,L->·i,#

I4,L->*·R,#傳播得I7,L->*R·,#

彈出：I4,L->·i,#傳播得：I5,L->i·,#

彈出：I4,L->·*R,#傳播得：I4,L->*·R已經傳播過了。

彈出：I4,R->·L,#傳播得：I8,R->L·,#。

彈出：I0,L->·i,#傳播得：I5,L->i·,#（I5中已有，所以要注意冗余處理）

彈出：I0,S->·R,#傳播得：I3,S->R·,#

彈出：I0,S->·L=R,#傳播得：I2,S->L·=R,#，沒有自生成項，但可以傳播，故接著傳播得：I6,S->L=·R,#，此項自生成：

I6,R->·L,#

I6,L->·*R,#

I6,L->·i,#

此時棧狀態為：

I6,R->·L,#

I6,L->·*R,#

I6,L->·i,#

傳播I6,S->L=·R,#得：I9,S->L=R·,#

彈出：I6,L->·i,#傳播得：I5,L->i·,#

彈出：I6,L->·*R,#傳播得：I4,L->*·R,#已經處理過了。

彈出：I6,R->·L,#傳播得：I8,R->L·,#到此為止棧終于空了！LALR（1）項目集族也構建好了！

I0:	I1:	I2:	I3:	I4:
I0，S'->·S,#	I1, S'->S·,#	I2,S->L·=R,#	I3,S->R·,#	I4,L->*·R,=/#
I0,L->·*R,=/#		I2,R->L·,#		I4,R->·L,=/#
I0,L->·i,=/#				I4,L->·*R,=/#
I0,S->·L=R,#				I4,L->·i,=/#
I0,S->·R,#
I0,R->·L,#
I5:	I6:	I7:	I8:	I9:
I5,L->i·,=/#	I6,S->L=·R,#	I7, L->*R·,=/#	I8, R->L·,=/#	I9,S->L=R·,#
	I6,R->·L,#
	I6,L->·*R,#
	I6,L->·i,#

總結

以上是生活随笔為你收集整理的构建LALR（1）项目集族的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。