我想知道为什么在Haskell中没有像用于自顶向下解析的Parsec组合子那样用于自下而上解析的通用解析器组合子
(我可以发现2004年进行了一些研究工作，但之后就没有了
https://haskell-functional-parsing.googlecode.com/files/Ljunglof-2002a.pdfhttp://www.di.ubi.pt/~jpf/Site/Publications_files/technologicalReport.pdf(
没有实现这一目标有什么具体的原因吗？
这是因为引用透明。正如没有任何功能可以区分
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))
接受从CCD_ 1开始的任何有限的数字升序。这有无数种不同的解析状态。(也许可以用无上下文的方式来表示这一点，但这会很棘手，而且需要比解析库更多的代码理解，我认为(
自下而上的组合子库可以通过要求所有解析器以
- 相同的标签总是指向相同的解析器，并且
- 只有一组有限的标签
在这一点上，它开始看起来更像是语法的传统规范，而不是组合规范。然而，它仍然可能是美好的；您只需要标记递归生成，这将排除任何无限大的规则，如numSequence。
因为luqui的回答表明自下而上的解析器组合子库是不现实的。如果有人来到这个页面只是在寻找haskell的自下而上的解析器生成器，那么你要寻找的就是Happy解析器生成器。这就像haskell的yacc。
正如luqui上面所说：Haskell对递归解析器定义的处理不允许定义自下而上的解析库。但是，如果您以不同的方式表示递归语法，则可以使用自下而上的解析库。对自我推销表示歉意，使用这种方法的一个(研究(解析器库是语法组合子。它实现了一种称为统一Paull变换的语法变换，该变换可以与自上而下的语法分析器算法相结合，为原始语法获得自下而上的语法分析器。
@luqui本质上说，在某些情况下，共享是不可观察的。然而，一般情况并非如此：存在许多可观察共享的方法。例如。http://www.ittc.ku.edu/~andygill/piers/reifyGraph.pdf提到了实现可观察共享的几种不同方法，并提出了自己的新方法：
这种循环结构可以用于解释，但不能用于进一步的分析，漂亮的印刷，或一般的处理。这个这里的挑战，也是本文的主题，是如何允许树木从Haskell托管的深度DSL中提取以具有可观察的后边缘，或者更一般地，可观察共享。这是一个众所周知的问题，具有许多标准解决方案。
请注意，本文以显式标签的名义提到了@liqui的"丑陋"解决方案。该论文提出的解决方案仍然"丑陋"，因为它使用了所谓的"稳定名称"，但其他解决方案http://www.cs.utexas.edu/~wcook/Drafts/2012/graphs.pdf(依赖于PHOAS(可能会起作用。