tho*_*uan 8 performance grammar parsing scala parse-forest
我试图让解析器从一个模糊的语法中返回所有可能的解析结果(解析林),并通过根据用户上下文/历史和知识库评估它们来从解析林中进行选择.出于性能原因,这可能应该使用packrat解析器和搜索限制/上限参数来限制递归调用的数量,以应用生产规则以避免无限循环.
作为Scala及其Parser Combinators的新手,我无法弄清楚如何做到这一点或者是否可以完成.有人可以帮忙吗？非常感激.
此致,Thomas Juan
Dan*_*wak 11
你不能用Scala的内置解析器组合器做到这一点.Packrat组合器仅限于明确的语法.如果你试图处理歧义,你就会失去记忆的能力,即使对于明确的路径,解析复杂度也会变为O(k ^ n).所以,不要这样做.
你想要的是一个正确处理歧义的解析器组合框架.据我所知,Scala唯一的这样的框架是我的GLL组合器.语法几乎是相同的Scala的解析器组合(其主要区别在于较高的arity功能工作正常),但输出的是Stream[A],其中,A在结果类型.因此,你得到一个解析森林.请注意,结果实际上不是SPPF(共享打包解析林),因此如果生成指数数量的结果,则流将具有比例大小.这样做是为了保持结果类型的最大灵活性.
在最坏的情况下,GLL组合子是O(n ^ 3),即使对于病态模糊的语法也是如此.在平均情况下,解析轨迹是明确的,GLL组合子是O(n).恒定的时间开销目前有点过分,但优化是一个持续的项目.我们在Precog的生产中使用GLL组合器,因此您可以期待图书馆能够得到很好的维护.
| 归档时间： |
|
| 查看次数： |
891 次 |
| 最近记录： |