1

我试图在 Haskell 中使用 parsec 编写解析器，特别是回溯是如何工作的。

采用以下简单的解析器：

import Text.Parsec

type Parser = Parsec String () String

parseConst :: Parser
parseConst =  do {
    x <- many digit;
    return $ read x
}

parseAdd :: Parser
parseAdd = do {
    l <- parseExp;
    char '+';
    r <- parseExp;
    return $ l <> "+" <> r
}

parseExp :: Parser
parseExp = try parseConst <|> parseAdd

pp :: Parser
pp = parseExp <* eof

test = parse pp "" "1+1"

test有价值

Left (line 1, column 2):
unexpected '+'
expecting digit or end of input

在我看来，这应该会成功，因为我try在parseConst.parseExp

我错过了什么？我也对如何自己调试的指针感兴趣，我尝试使用parserTraced它让我得出结论，它确实不是回溯。

PS。我知道这是编写表达式解析器的一种糟糕的方式，但我想了解它为什么不起作用。

4

1 回答 1

0

这里有很多问题。

首先，parseConst永远无法正常工作。类型说它必须产生一个String, 所以read :: String -> String。该特定实例要求输入是带引号的字符串，因此如果您尝试评估它产生的值，则Read传递 0 个或多个数字字符read总是会导致调用。error

其次，parseConst可以成功匹配零个字符。我想你可能想要some而不是many. 如果遇到不以数字开头的输入，这将使其实际上失败。

第三，(<|>)不按你的想法做。您可能认为它(a <* c) <|> (b <* c)可以与 互换(a <|> b) <* c，但事实并非如此。也没有办法投入try并使其相同。问题是(<|>)提交到哪个分支成功，如果有的话。在(a <|> b) <* c, 如果a匹配，以后就没有办法回溯并在那里尝试b了。不管你如何try四处游荡，它都无法撤消(<|>)承诺a. 相反，在and或and都匹配输入(a <* c) <|> (b <* c)之前不会提交。acbc

这就是你遇到的情况。(try parseConst <|> parseAdd) <* eof经过一些内联后，您有. 因为parseConst将永远成功（见第二期），parseAdd即使eof失败，也永远不会被尝试。因此，在parseConst消耗零个或多个前导数字后，解析将失败，除非这是输入的结尾。解决这个问题基本上需要仔细规划您的语法，(<|>)以便在本地安全地提交任何使用。也就是说，每个分支的内容不得以仅由语法的后面部分消除歧义的方式重叠。

请注意，这种令人不快的行为(<|>)是 parsec 系列库的工作方式，而不是 Haskell 中所有解析器库的工作方式。其他库在没有 parsec 系列选择的左偏或提交行为的情况下工作。

于 2020-12-22T09:41:45.047 回答