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