具有ε转换的左递归LR(0)项的闭包是什么？

Question

假设我有这样的语法：

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

项目A: • B 'a'的闭合部分是什么

换句话说，在计算闭包时，我如何处理epsilon转换？

Answer 1

这很简单。的闭包中包含

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

是所有的规则吗

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

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

    R1 = <dot> k ... ;

等等，但想必你已经很清楚这一点了。

你特定的问题是，如果R1可以为空，会发生什么？然后，您还需要包含

    X =   R1 <dot> R2 ... ;

类似地，对于R2为空，如果R1可以为空，并且类似地，如果R1，则Ri为空。Ri-1可以为空。在极端情况下，所有的Ri都可能是空的(语法中有很多可选子句)，最后可能会包含

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

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

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