2

我不知道我是否误解了正在发生的事情,或者维基百科的解释是否不正确。

维基百科说

FOLLOW(k,B)一个项目集k和一个非终结符B的集合是所有项目的后续集合的并集,K其中'•'后面是B

他们的示例语法如下所示:

S → E
E → T
E → ( E )
T → n
T → + T
T → T + n

他们发现 LR(0) 项集 0 为:

[S → • E]
[E → • T]
[E → • ( E )]
[T → • n]
[T → • + T]
[T → • T + n] 

这意味着,那FOLLOW(0,T)是项目集 0 中所有项目的后续集的并集,其中 '•' 后跟T

应用他们的逻辑,我们得到“项目集 0 中的项目,其中 '•' 后跟T实际上是这两个项目:

  • [E → • T]
  • [T → • T + n]

但是,这就是我卡住的地方:
第二个的后续集合包含符号),因为该项目[E → • ( E )]可以生产[E → • ( T )],这意味着 a)必须在后续集合中。

但是,维基百科说FOLLOW(0,T) = { $, '+' }.

我究竟做错了什么?

4

1 回答 1

1

我在这本书中找到了“Warshall's Closure Algorithm”的描述

Bornat : 理解和编写编译器

在这里有所帮助。(总的来说,我发现这本书比更著名的编译器设计书籍更具可读性和实用性!)

周围可能还有其他很好的算法描述。

编辑:我生疏了,但我相信维基百科的文章在这方面是正确的:

记住这是Follow(0,T).
现在您显然是对的,')' 在某些情况下可以跟随 T。

然而,不是从 0 的起点......这意味着一个表达式n)or n+n)or n+n+n),像这样明确地写出来,是明显的语法错误。

(让这些事情变得明确而不是用数学符号隐藏是我真正喜欢那本书的地方!)

于 2012-12-20T13:37:47.880 回答