Basically, the general idea of parser combinators is that you want to be able to express your parsing grammar in the sort of high-level description that people actually talk in, not in the low-level description that you get when you are constantly looking at the element string[i] in some switch statement in some function. Here is a simple example:

    parseAddress = let
            hexStr2Int = Prelude.read . ("0x" ++)
        in do
            start <- many1 hexDigit
            char '-'
            end <- many1 hexDigit
            return $ Address (hexStr2Int start) (hexStr2Int end)

(taken from http://therning.org/magnus/archives/289 .)

In actual words, "here is the function for converting a hex string to an integer, now define the variable `start` as the parse of many (or one) hex digits, then there is a hyphen, then the variable `end` is another parse of many (or one) hex digits. Convert `start` and `end` into numbers and put them into an Address object."

There are three further blog posts on Haskell+Parsec from the above blog: http://therning.org/magnus/archives/290 , http://therning.org/magnus/archives/295 , http://therning.org/magnus/archives/296 .

If you are interested about how such things are generally implemented, this Strange Loop talk is interesting: http://www.infoq.com/presentations/Parser-Combinators

What's probably the most interesting thing to speak of here is simply the fact that it's written in C, rather than in a "normal" functional language. You'll see in the latter presentation for example that there is a sort of "circuit wiring" approach which you can do with Lisp functions, essentially using function calls a(x) in order to describe a directed graph vertex from x to a.

I knew that you could pass pointers to functions in C, but I was not aware that it was sophisticated enough to build a parser combinator library, so I might brush up on my rusty C skills to see if I can understand the details of the implementation here.

    parseAddress = 
       let hexStr2Int = Prelude.read . ("0x" ++)
           in do start <- many1 hexDigit
                 char '-'
                 end <- many1 hexDigit
                 return $ Address (hexStr2Int start) (hexStr2Int end)

Or in applicative style (using attoparsec), which I like a lot more than the monadic style, because you can read it quite literally from the left to the right:

    parseAddress = Address <$> hexDigits <*> (dash *> hexDigits)
       where
          hexDigits = string "0x" *> takeWhile1 hexadecimal
          dash      = char '-'

Back to Parsec using applicative style, and parsing the same thing as the original.

    parseAddress = Address <$> hexDigits <*> (dash *> hexDigits)
      where
        hexDigits = read . ("0x" ++) <$> many1 hexDigit
        dash = char '-'

It's not bad, but the "0x" is part of the conversion into an integer, not part of the parsed address. That is, the more-complicated-looking combinator converts the string "03-c0" to `Address 3 192`, while it looks like yours converts the string "0x03-0xc0" to to `Address "0x03" "0xc0"`. (I'm not totally sure about that; I'm still very new to Haskell. Thanks for the heads-up on attoparsec though.)

The (* >) operator [1] (the space in the middle is just to circumvent HN's rather dumb comment formatting) sequences its two arguments, ignoring the one on the left. So

    string "0x" *> takeWhile1 hexadecimal

parses a literal string "0x", then one or more hexadecimal digits, and the result is just the hexadecimal digits.

[1] http://hackage.haskell.org/packages/archive/base/latest/doc/...

    {-# LANGUAGE OverloadedStrings #-}
    
    import Control.Applicative
    import qualified Data.Attoparsec.Text as P
    import qualified Data.Text as T
    
    data Address = Address {start :: Int, end :: Int} deriving Show
    
    address = Address <$> hexDigits <*> (dash *> hexDigits)
       where
          hexDigits = P.string "0x" *> P.hexadecimal
          dash      = P.char '-'
    
    parse parser str = P.feed (P.parse parser $ T.pack str) T.empty

Put the above into a file like 'parse.hs'.

    ~> ghci parse.hs

    *Main> parse address "0x1-0x1"
    Done "" Address {start = 1, end = 1}

You might need to install attoparsec beforehand:

    cabal install attoparsec

The major parser libraries that I could find don't allow adding syntax at runtime or to add operators to the expression hierarchy at runtime. Many (though not all) of them also make it difficult to do custom error reporting. These were my major motivations.

Ah right, interesting use-case. I usually think of combinator parsing's advantages versus table-driven parsing (e.g. LALR) being primarily its expressiveness (and amenability to a functional-programming style), but it has a nice runtime-modifiable aspect as well.

I wonder how hard it'd be to build a runtime-modifiable table-driven parser, though. Assuming table compilation is fast enough, the most straightforward approach might be to just link in the grammar-compilation code so it's available at runtime, and rebuild the table each time a modification is made. I don't think you'd want to be doing complex incremental surgery on a table-driven parser, but you might not need to.

Not C .. but are you familiar with Ometa (and its variations, Ometa/JS, Ometa#, PyMeta, etc?) http://tinlizzie.org/ometa/

It's a turing-complete parser specification language with an interpreter that is very close to being a packrat parser, which embraces adding and extending syntax (in a more general way than your library does, if I understand correctly).

Implementing the same idea in C should be possible. I have no idea why you want to add syntax at runtime, but the Ometa model might fit your plans better.

FParsec's OperatorPrecedenceParser component[1] does support adding (and removing) operators to the expression grammar at runtime.

[1] http://www.quanttec.com/fparsec/reference/operatorprecedence...

Doesn't Boost.Spirit [1] allow adding syntax and operators at runtime? (Seriously asking; have never used Spirit)

[1] http://boost-spirit.com/home/