Lemon中的Followset的理解

不能直接理解为每个非终结符的Follow集，否则，lemon得到的只是简单的SLR(1)分析器。注意到followset是定义成项目(Config)的属性，在这里应该理解为向前搜索符。验证如下，注意，在程序lemon.c中要开启TEST宏定义：

语法文件（test.y^[1]）：

%include {

#include <iostream>

#include "ex2def.h"

#include "example2.h"

}

%token_type {Token}

%default_type {Token}

%type start {Token}

%type s {Token}

%type b {Token}

%type A {Token}

%type B {Token}

%syntax_error {

std::cout << "Syntax error!" << std::endl;

}

start ::= s.

s ::= b b.

b ::= A b.

b ::= B.

运行

>lemon –c test.y

得到test.out如下：

State 0:

start ::= * s

[$]

To (state 1) start ::= s *

To (state 0) s ::= * b b

s ::= * b b

[$]

To (state 2) s ::= b * b

b ::= * A b

[A B]

To (state 4) b ::= A * b

b ::= * B

[A B]

To (state 6) b ::= B *

A shift 4

B shift 6

start accept

s shift 1

b shift 2

State 1:

(0) start ::= s *

[$]

From (state 0) start ::= * s

$ reduce 0

State 2:

s ::= b * b

[$]

To (state 3) s ::= b b *

To (state 2) b ::= * A b

To (state 2) b ::= * B

From (state 0) s ::= * b b

b ::= * A b

[$]

To (state 4) b ::= A * b

b ::= * B

[$]

To (state 6) b ::= B *

A shift 4

B shift 6

b shift 3

State 3:

(1) s ::= b b *

[$]

From (state 2) s ::= b * b

$ reduce 1

State 4:

b ::= * A b

[$ A B]

To (state 4) b ::= A * b

b ::= A * b

[$ A B]

To (state 5) b ::= A b *

To (state 4) b ::= * A b

To (state 4) b ::= * B

From (state 0) b ::= * A b

From (state 4) b ::= * A b

From (state 2) b ::= * A b

b ::= * B

[$ A B]

To (state 6) b ::= B *

A shift 4

B shift 6

b shift 5

State 5:

(2) b ::= A b *

[$ A B]

From (state 4) b ::= A * b

$ reduce 2

A reduce 2

B reduce 2

State 6:

(3) b ::= B *

[$ A B]

From (state 0) b ::= * B

From (state 2) b ::= * B

From (state 4) b ::= * B

$ reduce 3

A reduce 3

B reduce 3

文法的First集和Follow集如下：

	First	Follow
S’	a, b	#
S	a, b	#
B	a, b	#, a, b

显然，生成的test.out是LALR(1)分析器。

[1] 陈火旺,刘春林等.程序设计语言编译原理［M］.第3版,北京:国防工业出版社,2000年1月:115.