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

Question

假设我有这个语法:

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

什么被视为项目的结束A: • B 'a'？
换句话说，在计算闭包时如何处理 epsilon 转换？

Answer 1

这非常简单。包含在关闭中

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

都是规则

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

其中第一个(R1) 不为空。对于第一个(R1)中的每个(非空)标记 K，您需要(传递!)包括

    R1 = <dot> k ... ;

等等。但想必您已经清楚这一点。

你的具体问题是如果 R1 可以为空会发生什么？那么你也 需要包含

    X =   R1 <dot> R2 ... ;

类似地，如果 R1 可以为空，则 R2 为空；如果 R1 .. Ri-1 可以为空，则 Ri 为空。在极端情况下，所有 Ri 都可以为空(语法中有很多可选子句)，并且您最终可以包括

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

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

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