parsing - What is the closure of a left-recursive LR(0) item with epsilon transitions?

Question

Let's say I have this grammar:

A: ε
 | B 'a'
B: ε
 | B 'b'

What is considered to be the closure of the item A: • B 'a'?
In other words, how do I deal with the epsilon transitions when figuring out closures?

Answer 1

这很简单。包括在关闭

    A = ... <dot> X ... ;

都是规则

    X =   <dot> R1 R2 R3 ... ;

其中 first(R1) 不为空。对于 first(R1) 中的每个（非空）令牌 K，您需要（传递地！）包括

    R1 = <dot> k ... ;

等等，但大概你已经很清楚了。

您的具体问题是如果 R1 可以为空会发生什么？然后你还需要包括

    X =   R1 <dot> R2 ... ;

类似地，对于 R2 为空，如果 R1 可以为空，同样对于 Ri 为空，如果 R1 .. Ri-1 可以为空。在极端情况下，所有的 Ri 都可以是空的（你的语法中有很多可选的子句），你最终可以包括

    X =  R1 R2 ... Rn <dot> ;

请注意，确定 first(R1) “可以为空”本身就是一个传递闭包问题。

我为 DMS 构建的 GLR 解析器生成器使用 Warshall 算法预先计算 first_can_be_empty，然后在闭包构造中使用它。