我试图让解析器从不明确的语法中返回所有可能的解析结果（解析森林），并通过根据用户上下文/历史和知识库评估它们来从解析森林中进行选择。出于性能原因，这可能应该使用 packrat 解析器和搜索限制/上限参数来限制在应用生产规则时递归调用的数量以避免无限循环。
作为 Scala 及其 Parser Combinators 的新手，我不知道如何做到这一点，或者根本不知道它是否可以做到。有人可以帮忙吗？非常感激。
最好的问候，托马斯·胡安
问问题
980 次
1 回答
11
Scala 的内置解析器组合器无法做到这一点。Packrat 组合器仅限于明确的语法。如果您尝试处理歧义，您将失去记忆能力，即使对于明确的轨迹，解析复杂度也会变为 O(k^n)。所以，不要那样做。
您想要的是一个能够正确处理歧义的解析器组合器框架。据我所知，Scala 唯一这样的框架是我的GLL 组合器。语法几乎与 Scala 的解析器组合器相同（主要区别在于更高数量的函数可以正常工作），但输出是 a Stream[A]，其中A是结果类型。因此，你得到了一个解析森林。请注意，结果实际上不是 SPPF（共享打包解析林），因此如果您生成指数数量的结果，则流将具有成比例的大小。这样做是为了保持结果类型的最终灵活性。
在最坏的情况下， GLL 组合子是 O(n^3) ，即使对于病态模棱两可的语法也是如此。在解析线索明确的平均情况下，GLL 组合子是 O(n)。恒定的时间开销目前有点过多，但优化是一个正在进行的项目。我们在Precog的生产环境中使用 GLL 组合器，因此您可以期待该库在未来得到很好的维护。
于 2012-04-23T15:43:49.083 回答