LR与SLR（FOLLOW集与搜索符）的区别

LR

与

SLR

（

FOLLOW

集与搜索符）的区别

语法分析中，

SLR

使用的是

FOLLOW

集，

LR

使用的是搜索符，这是它们功能强弱不一的根本原因。

**FOLLOW

集的计算方法：**

对于方法的开始符

S

，置

于

FOLLOW(S)

中；

若

A->

α

B

β是一个产生式，则把

FIRST(

β

)/{

ε

}

加至

FOLLOW(B)

中；

若

A->

α

B

是一个产生式，则把

FOLLOW(A)

加至

FOLLOW(B)

中。

对于第二条，在

FIRST

集中除去ε的操作的解释是：跟着一个空输入没有什么意义，如果真的什么都不跟，那么至少有个

垫底，所以没有必要加入ε。

搜索符的计算方法：

教材（陈火旺，国防工业出版社）上没有直接给出搜索符的算法。但在构造

LR(1)

项目集族的过程中，涉及到了搜索符的计算。下面是求

LR(1)

项目集闭包的过程：

I

的任何项目都属于

CLOSURE(I);

若项目［

A->

α·

B

β

,a

］属于

CLOSURE(I)

，

B->

ξ是一个产生式，那么对于

FIRST(

β

a)

中的每个终结符

b

，如果［

B->

·ξ

,b

］原来不在

CLOSURE(I)

中，则把它加入；

重复执行步骤

2

，直至

CLOSURE(I)

不再增大。

区别。

显然，步骤

2

涉及了搜索符的计算。在使用一个项目的搜索符时，其实在考查多个搜索符，也就是

FIRST(

β

a)

。所以我们把

FIRST(

β

a)

叫作 搜索符集 。有点像

FOLLOW

集，它也是跟在方法符号后面的终结符。

从搜索符集的计算过程来看，它是一个更严格的

FOLLOW

集。因为它只使用了

FOLLOW

集计算方法中的第

1

、

2

条

(

第

1

步骤在这里没有体现

)

。这样带来的后果就是：搜索符集一定会出现于某个句型中，且紧跟于，其项目中产生式左部的非终结符之后。而

FOLLOW

集的元素却未必。

步骤

2

能保证所求紧跟于非终结符之后。因为文法语言中，若

A->

α

B

β是一个产生式，则一定有一个句型含α

B

β短语，进而将

B

分解，此时

FIRST(

β

)

必跟其后。

步骤

3

则不然。其思路可以理解成，跟在

A

后的终结符就一定跟在

B

后面。这样的推理是没有错的，但问题在于要将

B

归约成

A

，

B

前面得出现α，若无α，即使

B

后面，出现了

FOLLOW(B)

也不能归约成

A

。

引用教材的例子。

考虑方法：

(1)S->L=R

(2)S->R

(3)L->*R

(4)L->i

(5)R->L

可以有计算出

FOLLOW(R)

中含有

”=”

，但遇到

R=

的时，也不能做归约处理。因为

R

前面没有

”*”

号，而该文法中不含有以

R=

为前缀的句型。再计算

FOLLOW(B)

，会发现

”=”

号是由步骤

3

算出来的。即通过

(1)

与

(3)

认为跟在

L

后的终结符就一定跟在

R

后面，但

(3)

中要求的是

R

前面有

”*”

号。