Почему этот анализатор 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

В принципе, даже с перестановкой парсеров ваш подход не сработает. См. Этот ответ на похожий вопрос для объяснения: Мегапарсек: не удалось разобрать арифметическую строку