2

The following parser enters an infinite loop for any input.

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

The problem is somewhere in the operation parser. I assume it's related to the alternate parsing but I don't understand it.

Can you explain what the problem is?

Thanks!

vidi
  • 2,056
  • 16
  • 34

1 Answers1

4

Problem is really in infinite recursion. Your ast parser calls operation parser first. But then operation parser calls ast back again. And so on. <*> operator for parsing also runs parsers. Explanation of difference from <|> in very informal manner: <*> runs parsers in sequence one by one whether <|> runs first parser and only if it fails runs second.

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

Basically, even with rearranging parsers your approach won't work. See this answer on similar question for explanation: Megaparsec: Not able to parse arithmetic string

Shersh
  • 9,019
  • 3
  • 33
  • 61
  • From my understanding, it seems it isn't possible because "Parsec can't handle left-recursive grammars" (https://stackoverflow.com/a/43299434/1663462). – Chris Stryczynski Jan 26 '19 at 22:51
  • @ChrisStryczynski you're correct. But it's possible to change your grammar in a such way that it's still equivalent to its left-recursive version but doesn't contain left recursion. – Shersh Jan 27 '19 at 09:31