4 ms·
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
by drostie 14y ago
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 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/290 , http://therning.org/magnus/archives/295 http://therning.org/magnus/archives/295 , http://therning.org/magnus/archives/296 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 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.
- dan00 14y agoparseAddress = 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 '-'
- drostie 14y agoIt'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.)
- tmhedberg 14y agoThe (* >) 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/html/Control-Applicative.html#v:-42--62- http://hackage.haskell.org/packages/archive/base/latest/doc/...
- dan00 14y ago{-# 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
- evincarofautumn 14y agoBack 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 '-'