为什么这个 Parsec 解析器会进入无限循环？

Question

以下解析器对任何输入都进入无限循环。

data Ast
    = Number Int
    | Identifier String
    | Operation Ast BinOp Ast
    deriving (Show, Eq)

data BinOp = Plus | Minus
    deriving (Show, Eq, Enum)

number = Number <$> read <$> many1 digit

identifier = Identifier <$> many1 letter

operator = choice $ mkParser <$> [(Plus, '+'), (Minus, '-')]
  where mkParser (f, c) = f <$ char c

operation = Operation <$> ast <*> operator <*> ast

ast :: Parser Ast
ast = operation <|> number <|> identifier

问题出在操作解析器的某个地方。我认为它与备用解析有关，但我不明白。

你能解释一下问题出在哪里吗？

谢谢！

Answer 1

问题真的出在无限递归上。您的 ast 解析器首先调用 operation 解析器。但是随后 operation 解析器再次调用 ast 。等等。 <*> 解析运算符也运行解析器。以非常非正式的方式解释与 <|> 的区别：<*> 一个接一个地运行解析器，无论 <|> 运行第一个解析器还是仅当它失败时才运行第二个。

operation = Operation <$> ast <*> operator <*> ast
ast       = operation <|> number <|> identifier

基本上，即使重新排列解析器，您的方法也行不通。有关解释，请参阅类似问题的答案：

为什么这个 Parsec 解析器会进入无限循环？

Why does this Parsec parser enter an infinite loop?

haskell

parsec