9

我想知道为什么 Haskell 中没有用于自下而上解析的通用解析器组合器，例如用于自上而下解析的 Parsec 组合器。
（我可以找到一些研究工作在 2004 年进行，但在
https://haskell-functional-parsing.googlecode.com/files/Ljunglof-2002a.pdf http://www.di.ubi.pt/~jpf/Site /Publications_files/technicalReport.pdf )

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

4

4 回答 4

12

这是因为参照透明性。就像没有函数可以区分

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.

于 2014-06-05T03:17:54.883 回答
4

正如 luqui 的回答所表明的那样，自下而上的解析器组合库是不现实的。如果有人访问此页面只是为了寻找haskell 的自下而上解析器生成器，那么您正在寻找的就是所谓的Happy 解析器生成器。这就像yacchaskell。

于 2014-06-05T05:01:43.257 回答
4

正如 luqui 上面所说：Haskell 对递归解析器定义的处理不允许定义自底向上的解析库。如果您以不同的方式表示递归语法，则可以使用自下而上的解析库。为自我推销道歉，使用这种方法的一个（研究）解析器库是语法组合器。它实现了一种称为统一保尔变换的文法变换，可以与自顶向下的解析器算法相结合，得到原始文法的自底向上解析器。

于 2014-06-05T20:09:48.847 回答
1

@luqui 本质上说，在某些情况下共享是不可观察的。但是，一般情况并非如此：存在许多可观察共享的方法。例如http://www.ittc.ku.edu/~andygill/papers/reifyGraph.pdf提到了几种实现可观察共享的不同方法，并提出了自己的新方法：

这种循环结构可用于解释，但不能用于进一步分析、漂亮打印或一般处理。这里的挑战以及本文的主题是如何让从 Haskell 托管的深度 DSL 中提取的树具有可观察的后边缘，或者更一般地说，可观察的共享。这是一个很好理解的问题，有许多标准解决方案。

请注意，@liqui 的“丑陋”解决方案被论文以显式标签的名义提及。该论文提出的解决方案仍然“丑陋”，因为它使用了所谓的“稳定名称”，但其他解决方案，例如http://www.cs.utexas.edu/~wcook/Drafts/2012/graphs.pdf（其中依赖于 PHOAS）可能会起作用。

于 2018-07-23T18:17:06.247 回答