Search code examples
haskellparsec

Complex Parsec Parsers


I don't quite know how else to ask. I think I need general guidance here. I've got something like this:

expr = buildExpressionParser table term
    <?> "expression"

term = choice [
    (float >>= return . EDouble)
    , try (natural >>= return . EInteger)
    , try (stringLiteral >>= return . EString)
    , try (reserved "true" >> return (EBool True))
    , try (reserved "false" >> return (EBool False))
    , try assign
    , try ifelse
    , try lambda
    , try array
    , try eseq
    , parens expr
    ]
    <?> "simple expression"

When I test that parser, though, I mostly get problems... like when I try to parse

 (a,b) -> "b"

it is accepted by the lambda parser, but the expr parser hates it. And sometimes it even hangs up completely in eternal rules.

I've read through Write Yourself a Scheme, but it only parses the homogeneous source of Scheme.

Maybe I am generally thinking in the wrong direction.

EDIT: Here the internal parsers:

assign = do
    i <- identifier
    reservedOp "="
    e <- expr
    return $ EAssign i e

ifelse = do
    reserved "if"
    e <- expr
    reserved "then"
    a <- expr
    reserved "else"
    b <- expr
    return $ EIfElse e a b

lambda = do
    ls <- parens $ commaSep identifier
    reservedOp "->"
    e <- expr
    return $ ELambda ls e

array = (squares $ commaSep expr) >>= return . EArray

eseq = do
    a <- expr
    semi <|> (newline >>= (\x -> return [x]))
    b <- expr
    return $ ESequence a b

table = [
        [binary "*" EMult AssocLeft, binary "/" EDiv AssocLeft, binary "%" EMod AssocLeft ],
        [binary "+" EPlus AssocLeft, binary "-" EMinus   AssocLeft ],
        [binary "~" EConcat AssocLeft],
        [prefixF "not" ENot],
        [binaryF "and" EAnd AssocLeft, binaryF "or" EAnd AssocLeft]
    ]

And by "hates it" I meant that it tells me it expects an integer or a floating point.


Solution

  • There appears to be left recursion, which will cause the parser to hang if the choice in term ever gets to eseq:

    expr -> term -> eseq -> expr

    The term (a,b) will not parse as a lambda, or an array, so it will fall into the eseq loop.

    I don't see why (a,b) -> "b" doesn't parse as an expr, since the choice in term should hit upon the lambda, which you say works, before reaching the eseq. What is the position reported in the parse error?