Parsec parse many question

Question

Hi. I need to create a parser for a programming language. So far it is 95% done, I'd say, except for a tiny detail.

The program written in this language has the following structure:

outputs
inputs
expressions

The requirement is that outputs cannot be mixed with inputs. For example:

x := output of int;
y := output of in;
.....
z := input of int;
t := input of in;
.....
expressions

I can parse a single output just fine but if I try to use (many1 output), to allow multiple outputs, it doesn't work because it tries to parse the inputs as outputs.

My main parser looks like this:

prog =
    do outs <- many1 output
       ins <- many1 input
       exs <- expressions
       eof
       return (Prog outs ins exs) 

I know it seems easy but I tried a lot of stuff and just cannot get it to work. Please help.

Answer 1

If your rule for output looks something like this:

output = do name <- ident
            string ":= output of"
            type <- ident
            char ';'
            return $ Out name type

and your input rule looks the same except with "input of", then the problem is that both rules start with an ident and since parsec doesn't backtrack automatically, it will just try to apply output first, consuming the ident and then fail when it can't match "output of".

To fix this you can just wrap output and input in try, i.e.

outs <- many1 (try output)
ins <- many1 (try input)

Answer 2

While sepp2k's answer works, I'd personally want to encapsulate the backtracking inside the output and input parsers.

Although this adds code to the parsers it make them more robust:

output = do name <- try prefix
            type <- ident
            char ';'
            return $ Out name type
  where
    prefix = do name <- ident
                string ":= output of"
                return name

With Parsec, its generally best to avoid try except for Char Parsers and use left factoring to improve the grammar (try can make parsers very fragile). Unfortunately the grammar you are working is not particularly friendly to left factoring and in this case it is probably not worth bothering.