构建LALR（1）项目集族

构建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,#