parsing - Haskell 中的通用自下而上解析器组合器

Question

我想知道为什么 Haskell 中没有像用于自上而下解析的 Parsec 组合器那样用于自下而上解析的通用解析器组合器。
(我发现 2004 年期间进行了一些研究工作，但之后就没有了
https://haskell-functional-parsing.googlecode.com/files/Ljunglof-2002a.pdf http://www.di.ubi.pt/~jpf/Site/Publications_files/technicalReport.pdf )

有什么具体原因没有实现吗？

Answer 1

这是因为引用透明性。正如没有函数可以区分两者的区别

let x = 1:x
let x = 1:1:1:x
let x = 1:1:1:1:1:1:1:1:1:...  -- if this were writeable

没有函数可以区分有限图语法和无限树语法之间的区别。自下而上的解析算法需要能够将语法视为图形，以便枚举所有可能的解析状态。

事实上，自上而下的解析器将其输入视为无限树，这使得它们变得更加强大，因为树在计算上可能比任何图都更复杂；例如，

numSequence n = string (show n) *> option () (numSequence (n+1))

接受从n开始的任何有限升序数字序列。这有无限多种不同的解析状态。 (也许可以用上下文无关的方式来表示这一点，但这会很棘手，并且我认为需要比解析库更多地理解代码)

可以通过要求所有解析器以这样的方式“标记”来编写自下而上的组合器库，尽管它有点难看

• 相同的标签始终引用相同的解析器，并且
• 只有一组有限的标签

此时它开始看起来更像传统的语法规范而不是组合规范。然而，它仍然可以是美好的；您只需标记递归产生式，这将排除任何无限大的规则，例如 numSequence。