问题标签 [uu-parsinglib]

问题

我知道Parsec并且uu-parsinglib我已经在它们中编写了解析器。最近我发现 中存在一个问题uu-parsinglib，这可能会严重影响其性能，我没有找到解决方法。

让我们考虑以下 Parsec 解析器：

什么是等价的uu-parsinglib？它不会是以下内容：

不同之处在于， in Parsec,many会贪婪地吃(pa <* pb)（对"ab"）直到不再匹配，而 in uu-parsinglib,pList_ng不是贪婪的，因此在解析每个 后它将保留在内存中可能的回溯方式(pa <* pb)。

有没有办法写类似pList(try(pa <* pb))in 的东西uu-parsinglib？

例子

一个很好的例子是

和一个样本输入"ababab"。

使用Parsec，我们会得到错误（因为pTest贪婪地解析一对"ab"），但是在 中uu-parsinglib，字符串将被解析而没有问题。

编辑

我们不能从 切换pList_ng到pList，因为它不等同于Parsec版本。例如：

以及在使用 greedy 时"ababa"会成功Parsec但失败的示例输入。uu-parsinglibpList

如果我们在这里使用当然uu-parsinglib会成功pList_ng，但是对于某些输入和规则可能会慢很多。例如，考虑到输入"ababab",Parsec会简单地失败，因为pTest会消耗整个字符串并且pa不会被匹配。uu-parsinglib也会失败，但检查更多步骤 - 它将匹配整个字符串并失败，然后丢弃最后"ab"一对并再次失败，等等。如果我们有一些嵌套规则和有趣的输入文本，它将产生巨大的差异。

一个小基准

为了证明问题确实存在，请考虑以下语法（在伪代码中 - 但我认为它非常直观）：

因此，作为我们程序的输入，我们得到一个包含模式的字符串，例如“abababaaba”包含 2 个模式“abababa”和“aba”。

让我们在两个库中制作解析器！

uu-parsinglib：

Parsec：

结果？uu-parsinglib比300% 慢：

ghc -O3（用标志编译）

我正在编写一个编译器uu-parsinglib，我看到了一件非常奇怪的事情。我定义了一个pChoice组合器，如：

（注意，我正在使用 greedy <<|>）。

让我们考虑以下代码：

每个元素都以不同的字符Expr.Var开头 - 以字母、Expr.Lit数字、L.pParensed括号(、Expr.Tuple大括号{和Expr.List括号开头[。

我有一个很大的测试代码，其中没有元组也没有列表。代码解析为0.15s. 当我取消注释上述行时，时间增加到0.65s. 这是超过 400% 的减速……这怎么可能？我只使用了贪婪的运算符，而且我确信解析器不会在TuplenorList部分中使用，因为在整个代码中没有元组或列表。

如果您需要更多代码或定义，我当然会发布它。

作为真实语言解析器的简化子问题，我正在尝试为虚构语言的表达式实现解析器，该语言看起来类似于标准命令式语言（如 Python、JavaScript 等）。它的语法具有以下结构：

• 整数
• 标识符 ( [a-zA-Z]+)
• +带和*和括号的算术表达式
• 结构访问.（例如foo.bar.buz）
• 元组（例如(1, foo, bar.buz)）（消除歧义，一个元组写成(x,)）
• 功能应用程序（例如foo(1, bar, buz())）
• 函数是第一类的，因此它们也可以从其他函数返回并直接应用（例如foo()()是合法的，因为foo()可能返回一个函数）

所以这种语言的一个相当复杂的程序是

关联性应该是

我目前正在使用非常好的uu-parsinglib应用解析器组合库。

第一个问题显然是直观的表达式语法 (expr -> identifier | number | expr * expr | expr + expr | (expr)是左递归的。但我可以使用pChainl组合器解决这个问题（参见parseExpr下面的示例）。

剩下的问题（因此这个问题）是函数应用与从其他函数返回的函数（f()()）。同样，语法是左递归的expr -> fun-call | ...; fun-call -> expr ( parameter-list )。有什么想法可以优雅地解决这个问题uu-parsinglib吗？（我猜这个问题应该直接适用于parsec,attoparsec和其他解析器组合器）。

请参阅下面我当前版本的程序。它运行良好，但功能应用程序仅在标识符上工作以删除左递归：

我正在寻找satisfy像 Parsec 那样的功能。就像是：

我发现的唯一东西是pSatisfy，它需要一个Insertionas 参数。我不明白为什么这是必要的......我只是希望解析器在谓词不满足的情况下失败！

我怎样才能做到这一点？

我需要一个类型的值，它会在空（长度为 0）输入时Parser ()成功（并返回），并在所有其他情况下失败。()

pSatisfy (const False)不完全符合要求。pEnd甚至似乎不适合这个目的。

pExact 0 pAscii可能是确切的“按定义”解决方案。似乎仍然不起作用：

我正在尝试使用 uu-parsinglib[Word8]而不是 [Char] 进行操作。（我想使用 uu-parsinglib 进行错误报告。）我需要一个解析器来获取Word8序列中的下一个，无论它是什么。一旦有了它，我就可以构建更复杂的解析器。但是我很难弄清楚如何编写它。我能得到的最接近的是：

但是，该实现显然返回了错误的类型。

这让我感到惊讶，因为我看不到 for 的类型签名如何pSatisfy限制我返回 aChar而不是 a Word8。

我该如何实施pRawWord8？

我正在尝试编译一个有几年历史并且实际上不再维护的 Haskell 程序。它有一长串依赖项，需要我安装旧版本的uu-parsinglib. 具体来说，它已经计算出它想要uu-parsinglib-2.7.4.3的，但我得到了一个奇怪的编译错误。我是一个相当有经验的程序员，但不是在 Haskell 中，所以我在这里有点摸不着头脑。阴谋集团给了我以下错误：

谁能帮我吗？