使用 Parsec 在 Haskell 中编写小型解析器时出现问题

Question

我正在尝试使用以下代码为小语言编写解析器

import Text.ParserCombinators.Parsec
import Text.Parsec.Token

data Exp = Atom String | Op String Exp

instance Show Exp where
  show (Atom x) = x
  show (Op f x) = f ++ "(" ++ (show x) ++ ")"

parse_exp :: Parser Exp
parse_exp = (try parse_atom) <|> parse_op

parse_atom :: Parser Exp
parse_atom = do
  x <- many1 letter
  return (Atom x)

parse_op :: Parser Exp
parse_op = do
  x <- many1 letter
  char '(' 
  y <- parse_exp
  char ')'
  return (Op x y)

但是当我输入 ghci 时

>>> parse (parse_exp <* eof) "<error>" "s(t)"

我得到输出

Left "<error>" (line 1, column 2):
unexpected '('
expecting letter or end of input

如果我重新定义parse_exp为

parse_exp = (try parse_op) <|> parse_atom

然后我得到正确的结果

>>> parse (parse_exp <* eof) "<error>" "s(t)"
Right s(t)

但我很困惑为什么第一个不起作用。解析中此类问题是否有通用的解决方案？

Answer 1

当 Parsec 解析器（例如parse_atom）在特定字符串上运行时，有四种可能的结果：

1. 它成功了，消耗了一些输入。
2. 它失败了，消耗了一些输入。
3. 它成功了，不消耗任何输入。
4. 它失败了，不消耗任何输入。

在 Parsec 源代码中，这些被称为“consumed ok”、“consumed err”、“empty ok”和“empty err”（有时缩写为 cok、cerr、eok、eerr）。

当两个 Parsec 解析器用于替代方案（例如 ）时p <|> q，它的解析方式如下。首先，Parsec 尝试解析p. 然后：

• 如果结果是“consumed ok”或“empty ok”，则解析成功，并且这将成为整个解析器的结果p <|> q。
• 如果这导致“空错误”，Parsec 会尝试替代方案q，这将成为整个解析器的结果p <|> q。
• 如果这导致“consumed err”，则整个解析器p <|> q将失败并显示“consumed err”（cerr）。

p请注意返回 cerr（导致整个解析器失败）与返回 eerr（导致q尝试替代解析器）之间的关键区别。

该try函数通过将“cerr”结果转换为“eerr”结果来更改解析器的行为。

这意味着如果您尝试使用"s(t)"不同的解析器解析文本：

• with the parser parse_atom <|> parse_op, the parser parse_atom returns "cok" consuming "s" and leaving unparseable text "(t)" which causes an error
• with the parser try parse_atom <|> parse_op, the parser parse_atom still returns "cok" consuming "s", so the try (which only changes cerr to eerr) has no effect, and the unparseable text "(t)" causes the same error
• with the parser parse_op <|> parse_atom, the parser parse_op successfully parses the string (actually, it doesn't because the recursive call to parse_exp can't parse "t", but let's ignore that); however, if the same parser was used on the text "s", then parse_op would consume the "s" before failing (i.e., cerr), causing the entire parse to fail instead of trying the alternative parse_atom
• 使用解析器try parse_op <|> parse_atom，这将解析"s(t)"，与前面的示例完全相同，并且try不会产生任何效果；但是，它也适用于 text "s"，因为parse_op会消耗"s"cerr 失败之前的内容，然后try通过将 cerr 转换为 eerr 来“拯救”解析，并且parse_atom将检查替代方案，成功解析（cok）atom "s"。

这就是为什么您的问题的“正确”解析器是try parse_op <|> parse_atom.

请注意，这种行为不是单子解析器的基本方面。这是 Parsec（以及像 Megaparsec 这样的兼容解析器）做出的设计选择。其他一元解析器对于替代方案的<|>工作方式可能有不同的规则。

此类 Parsec 解析问题的“一般解决方法”是了解表达式中的事实p <|> q：

• p首先尝试，如果成功，q将被忽略，即使q会提供“更长”或“更好”或“更合理”的解析或避免进一步的额外解析错误。在 中parse_atom <|> parse_op，因为parse_atom可以在用于 的字符串上成功parse_op，所以此顺序将无法正常工作。
• qp仅在失败且不消耗输入的情况下才尝试。如果您希望检查替代方案，则必须安排p在失败时不消耗任何内容，可以使用。因此，如果在意识到无法继续并返回 cerr 之前开始消耗某些内容（例如标识符），则不会起作用。tryqparse_op <|> parse_atomparse_op

作为使用 的替代方法try，您还可以更仔细地考虑解析器的结构。例如，另一种书写方式parse_exp是：

parse_exp :: Parser Exp
parse_exp = do
  -- there's always an identifier
  x <- many1 letter
  -- there *might* be an expression in parentheses
  y <- optionMaybe (parens parse_exp)
  case y of
    Nothing -> return (Atom x)
    Just y' -> return (Op x y')

  where parens = between (char '(') (char ')')

这可以写得更简洁一些，但即便如此，它也不像try parse_op <|> parse_atom. （不过，它的性能更好，因此在某些应用程序中可能需要考虑这一点。）