我注意到明显缺乏用函数式语言创建解析器的 LL 解析器。我一直在寻找但没有成功的理想发现是为 ANTLR 风格的 LL(*) 语法生成 Haskell 解析器(语法的模小数重新格式化),并且令我惊讶的是,每个最后一个解析器生成器都具有函数我发现的语言目标是某种 LR 解析器。
我想将我正在开发的这种具有功能特性的语言的解析器从 ANTLR 转换为语言本身的自托管,如果我可以将另一种功能语言中几乎肯定正确的东西移植到我的语言中,那将会有很大帮助(最好是我熟悉的 Haskell 和 Scala),而不必完全从头开始重写,尽管最终我可能会这样做,因为核心语言很小。
在这一点上,我很好奇,甚至不仅仅是一个解决方案why没有这样的 LL(*) 甚至 LL(k) 解析器生成器,但有很多 LR 生成器,因为 LL 本质上看起来更容易。
主要原因是大多数用函数式语言编写的 LL(k) 解析器只是使用解析器组合器实现,因为生成解析器组合器库的最简单路径是递归下降 http://en.wikipedia.org/wiki/Recursive_descent_parser.
哈斯克尔的parsec http://hackage.haskell.org/package/parsec, 阿托秒差距 http://hackage.haskell.org/package/parsec, and 多解析 http://hackage.haskell.org/package/polyparseScala 的常用解析器组合器都生成有效的 LL(*) 解析器。
parsec 和 attoparsec 都要求您使用显式的 try 组合器来进行回溯,但这只是为了效率和 scala解析器组合器 http://www.scala-lang.org/api/current/scala/util/parsing/combinator/Parsers.html还可以处理Packrat 解析 http://www.scala-lang.org/api/current/scala/util/parsing/combinator/PackratParsers.html.
考虑以下片段公告 http://byorgey.wordpress.com/2011/03/28/binders-unbound/布伦特·约尔吉 (Brent Yorgey) 最近的作品unbound http://hackage.haskell.org/package/unbound包裹:
parseAtom = parens parseTerm
<|> var <$> ident
<|> lam <$> brackets ident <*> parseTerm
很容易看出原来的语法。
LR 解析器需要更复杂的预处理来生成要有效执行的表,因为使用类似的直接手工编码递归上升 http://en.wikipedia.org/wiki/Recursive_ascent_parser非常糟糕。
通过将解析器组合器实现为 EDSL 而不是外部工具,您可以更好地利用编程语言的高级功能。您可以使部分语法更高阶,构建词法分析器黑客 http://en.wikipedia.org/wiki/The_lexer_hack直接进入解析器等。典型的 LR 解析器生成器无法执行这些操作,或者只能在有限的上下文中以临时方式提供它们,因为最终需要能够发出表。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)