Parser Combinators in Elixir

On the other hand writing parser combinators is really reaallly easy. In my experience it's almost just as declarative (you build up chunks of your grammar from smaller chunks), and yet you maintain good control over the control flow of your parser - when it backtracks, what errors you report, etc. And since its in the language you are using, debugging uses regular debugging tools, and custom logic is expressed in regular haskell

Now ANTLR4 also allows writing predicates in the target language, but how and when they get executed is pretty difficult to figure out

Overall, I would say if the thing you need to parse is pretty simple (clearly specced, straightforward grammar) a parser generator could be worth it. But if theres anything more complex (optional semicolons, context-sensitive ignoring whitespace, etc) I would much prefer the comfort and understandability of parser combinators

I'd say the difficulty was moderately high, but that was with no real prior experience with parsers. With that water under the bridge, I'd now rate it at around moderate effort. And the result was gaining a clear and precise understanding of the implicit state machine transitions, and being able to control exactly where and how those transitions happen, such that I didn't really need much of a lexer (the "lexer" just tags each character with its position, so that I didn't have to track that separately in the actual parser code itself).

That said, the result is a bit of a tangled mess; it didn't start that way, but eventually the parsing logic got complex enough that I needed to resort to Erlang's preprocessor macros, and while the end result is manageable through some judicious organization, in hindsight I probably could've done the same with functions, and in a more reusable and maintainable way. If I ever get around to another parser rewrite, I might try using parser combinators or some approximation thereof instead.

----

[1]: Technically the second or third, since I rewrote it a couple times as one can see from the commit history - although said history is a bit hard to pin down across all the renames of the relevant file.

The few times I’ve attempted to use a parser generator, I could never figure them out. By contrast, when I started using parser combinators (in Haskell), I was able to start writing parsers almost immediately.

> I know good error messages are the main benefit of writing parsers by hand; can you also get those with parser combinators?

It depends on the library, of course, but they can get pretty good if you annotate your parsers correctly. For comparison, here’s the CSV parser from the article translated into Haskell (using ‘megaparsec’, https://hackage.haskell.org/package/megaparsec):

    -- stack --resolver lts-17.9 script --package megaparsec
    module Main where
    
    import Data.Bifunctor
    import Data.Void
    
    import Text.Megaparsec
    import Text.Megaparsec.Char
    
    type Parser = Parsec Void String
    
    quotedChar :: Parser String
    quotedChar = label "string character" $ string "\"\"" <|> (pure <$> anySingleBut '\"')
    
    regularVal :: Parser String
    regularVal = takeWhileP (Just "a non-escaped character") $ not . (`elem` ['\r', '\n', ','])
    
    escapedVal :: Parser String
    escapedVal = char '\"' *> (concat <$> many quotedChar) <* char '\"'
    
    value :: Parser String
    value = escapedVal <|> regularVal
    
    line :: Parser [String]
    line = sepBy1 value (char ',') <* newline
    
    parseCSVFile :: String -> Either String [[String]]
    parseCSVFile input = first errorBundlePretty $ parse (many line) "" input
    
    main :: IO ()
    main = do
        putStrLn "INPUT:\n-----"
        putStrLn input
        putStrLn "\nOUTPUT:\n------"
        case parseCSVFile input of
            Left err -> putStrLn err
            Right r  -> print r
      where
        input =
            "this,is,a,test\n\
            \1,\"an \"\"escaped,string\",2,3\n\
            \whoops,\"there is,an unpaired,quote"

    INPUT:
    -----
    this,is,a,test
    1,"an ""escaped,string",2,3
    whoops,"there is,an unpaired,quote
    
    OUTPUT:
    ------
    3:35:
      |
    3 | whoops,"there is,an unpaired,quote
      |                                   ^
    unexpected end of input
    expecting '"' or string character

It’s dependent on the implementation, but with ‘megaparsec’ it’s a combination of both. It’s often OK by default — e.g. my example above has no explicit error recovery — but in more complex parsers, you’ll need to wrap some components with ‘try’, to indicate that it needs to backtrack if an error was found. (There’s other error-recovery combinators as well, such as ‘withRecovery’ and ‘observing’, but in practise you mostly end up using ‘try’.)