News for hackers. Stuff that matters.
Re:Parser combinator library in C by drostie on Tuesday August 07, 2012 @06:22AM (#4349438)
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.

Re:Parser combinator library in C by dan00 on Tuesday August 07, 2012 @07:07AM (#4349512)

    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 '-'
Re:Parser combinator library in C by evincarofautumn on Tuesday August 07, 2012 @01:44PM (#4351227)
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 '-'
Re:Parser combinator library in C by drostie on Tuesday August 07, 2012 @08:07AM (#4349657)
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.)
Re:Parser combinator library in C by tmhedberg on Tuesday August 07, 2012 @08:15AM (#4349672)
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/...

Re:Parser combinator library in C by dan00 on Tuesday August 07, 2012 @09:14AM (#4349901)

    {-# 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