我已经用反向指针编写了一个 Earley 解析器，但它不能很好地处理可空语法。我还实现了 Aycock & Horspool 2002 的解决方案，如果它可以为空，则让 PREDICT 跳过非终结标记。不幸的是，这并不能准确地告诉您令牌需要采取哪条特定路径才能到达 epsilon。
我的想法（很愚蠢）是：
对于每个可以为空的非终结符，为该非终结符创建一个路径列表以到达 epsilon。
每次跳过可为空的非终结符时，添加一个称为 NULL 的反向指针。
扩展树时，每次遇到 NULL 时，都会创建一个树列表，列表中的每个路径对应于该可为空的非终结符。
最后，您遍历树列表并删除重复项。
我认为这会显着增加我的算法的时间复杂度，但我想不出一种更有效的方法来生成所有可能的解析树。
谁能建议一种更有效的方法来实现 Aycock & Horspool 2002 来创建解析树？