parsecRemovingLeftRecursion.hs

import Text.ParserCombinators.Parsec

data Expr = Str String | Number Int | Add Expr Expr
    deriving Show

expr :: Parser Expr
expr = do
    left <- try str <|> number -- nonterminals and terminals that does not start with `expr`
    let rest = do
            char '+'
            right <- expr
            return $ Add left right
    try rest <|> return left



line :: Parser [Expr]
line = do
    result <- many expr
    eol                       -- end of line
    return result

add :: Parser Expr
add = do
    left <- expr
    char '+'
    skipMany $ char ' '
    right <- expr
    return $ Add left right

number :: Parser Expr
number = do
    numbers <- many1 $ digit
    return $ (Number (read numbers))

str :: Parser Expr
str = do
    char '"'
    content <- many $ noneOf ['"', '\n']
    char '"'
    return $ Str content
        
eol = char '\n'

parseExpr :: String -> Either ParseError [Expr]
parseExpr input = parse line "(unknown)" input