One of the many strengths of haskell is the ability to easily embed other small languages (sometimes called EDSL, short for embedded domain specific language) inside it. One famous example of this is the family of libraries known as parser combinators. They aim to solve the task of parsing structured text into well-typed data-structures, and succeed in it quite beautifully. In this short series of blog posts I will show you how to implement a simple and usable parser combinator library. You can find the source code for the library we will be developing [here](https://github.com/japiirainen/microparser). For real world use-cases you should propably just use [***megaparsec***](https://hackage.haskell.org/package/megaparsec). ## MicroParser So now let's build own own toy parser combinator library! We will call it ***MicroParser***. ```haskell {-# LANGUAGE DeriveFunctor #-} module MicroParser where import Control.Applicative (Alternative (..)) import Control.Monad (void) import qualified Data.Char as Char import Data.List (intercalate) ``` Let's start by thinking what the type of a parser should be? Structurally a parser is a function which takes an input stream of characters and yields a parse tree by applying the parsing logic over the input stream of characters to build up a composite data structure. ```haskell data ParseResult = ParseSuccess !a !Int String | ParseFailure [(Int, String)] deriving (Functor, Show) newtype Parser a = Parser {unParser :: Int -- ^ offset -> String -- ^ input stream of characters -> ParseResult a } ``` Our parser is polymorphic over the thing our parser should produce when successful. Internally our parser function takes an `Int` as it's first argument, which represents the position of the character we are currently parsing. This is useful for reporting errors. Other than that the type is relatively straight forward. Let's define a function for running a parser. ```haskell runParser :: Parser a -> String -> Either String a runParser (Parser p) ts = case p 0 ts of ParseSuccess x _ _ -> Right x ParseError es -> Left $ "Expecting " <> intercalate " OR " [ e <> " at position " <> show i | (i, e) <- es ] ``` Running a parser yields either a parse result when successful and an error message in the case of an error, which we represent here as a (somewhat) formatted string. In proper parser combinator libraries error handling is handled in more elegant and structured ways. Now we have defined the basic structure of our library, but it is not very usable at this point. We have no convenient way of constructing parsers nor do we have any way of combining them. So clearly we need to do some more work. The power of parser combinators mostly come from the typeclass instances we define for our `Parser` type. Especially `Applicative` and `Alternative` in our case. Some parser combinator libraries encourage the usage of the syntactic sugar haskell provides for monads. We are not going to define a monad instance for our parser since we can do plenty without it. To define `Applicative` and `Alternative` instances we need to first define `Functor` for out `Parser` type. Here is the `Functor` instance definition for our `Parser` type. ```haskell instance Functor Parser where fmap f (Parser p) = Parser (\i ts -> fmap f (p i ts)) ``` Now we can move on to the more interesting instances. Let's start with Applicative. ```haskell instance Applicative Parser where pure x = Parser (ParseSuccess x) Parser a <*> Parser b = Parser ( \i ts -> case f i ts of ParseError es -> ParseError es ParseSuccess x i' ts' -> case g i' ts' of ParseError es' -> ParseError es' ParseSuccess x' i'' ts'' -> ParseSuccess (x x') i'' ts'' ) ``` This might be a bit intimidating if you are unfamiliar with `Applicative`. I'll not go through explaining `Applicatives` in detail here, since it's out of the scope of this blog post, but I highly suggest learning what they are and to start building an intuition on when you should use them. [Here](https://wiki.haskell.org/Typeclassopedia#Applicative) is a good starting point. ### Alternatives Next we will define `Alternative`. Alternative is not as well known as typeclasses such as `Functor`, `Applicative` and `Monad` but are super useful for our use-case, so I think it's worth looking at them in a bit more detail. The `Alternative` typeclass has four members including `empty`, `some`, `many` and most importantly for us `<|>`. Let's explore what `<|>` does. The `Maybe` data type is well known so I will use it for demostration purposes since most people know what it represents. For me the mental model for `<|>` is the following. "Try executing the left hand side function and if successful, return the result, otherwise return the result of calling the right hand side function". (This mental model happens to work for `Maybe`, but is not always correct since the operator can have different effects on other data types.) ```shell ghci> Just 4 <|> Just 5 Just 4 ghci> Just 4 <|> Nothing Just 4 ghci> Nothing <|> Just 4 Just 4 ghci> Nothing <|> Nothing Nothing ``` But we are implementing parsers... how can we use this? Well we can express ***choice*** with it. Particulally we can think of it as saying "try parse this, then try parse this, then try parse this, and so on". This might sound a bit abstract at this point. But will become clear when we are finished! ```haskell instance Alternative Parser where empty = Parser (\_ _ -> ParseError []) Parser f <|> Parser g = Parser ( \i ts -> case f i ts of success@ParseSuccess {} -> success ParseError errs0 -> case g i ts of success@ParseSuccess {} -> success ParseError errs1 -> ParseError (errs0 <> errs1) ) ``` This instance definition actually follows the mental model quite clearly. "Run the first parser, if successful, return the results, otherwise run the second parser". We are getting closer. Almost all the hard work is now done and we can move on to the fun part. ### Combinators To wrap up the first part of this series of posts, we will define a fundamental combinator found in almost all of the parser combinator libraries, `satisfy`, and show a couple of use-cases for it. We will write `satisfy` in terms of a more general function called `satisfyMaybe`, which takes a description (used for error messages), a function from `Char` to a `Maybe` value indicating weather the character ***satisfies*** some condition or not. ```haskell satisfyMaybe :: String -> (Char -> Maybe a) -> Parser a satisfyMaybe descr p = Parser ( \i ts -> case ts of (t : ts') | Just x <- p t -> ParseSuccess x (i + 1) ts' _ -> ParseError [(i, descr)] ) satisfy :: String -> (Char -> Bool) -> Parser Char satisfy descr p = satisfyMaybe descr (\t -> if p t then Just t else Nothing) ``` Once we have `satisfy` we can define various combinators based on it. We will start with one that parses any character, one that parses a ***specific*** character, one for parsing whitespace and finally one that parses a specific sequence of characters. ```haskell anyChar :: Parser Char anyChar = satisfy "any character" (const True) char :: Char -> Parser () char c = void $ satisfy (show c) (== c) spaces :: Parser () spaces = void $ many (satisfy "whitespace" Char.isSpace) string :: String -> Parser () string [] = pure () string (x : xs) = char x *> string xs ``` Here's an example of how one might use these. Suppose we want to parse a key value pair into a `KV` data type. ```haskell -- | example kaye value pair text :: String text = "key: value" -- | Data type we would like parse the text into newtype KV = KV (String, String) deriving (Show) ``` We can do this via the following parser. Here we leverage some of the combinators we defined previously. ```haskell pKv :: Parser KV pKv = KV <$> parseKv where parseKv = (,) <$> many alpha <* char ':' <* spaces <*> many alpha ``` Admittedly this example is not the best one and doesn't show the full power of parser combinators. We need some additional combinators to gain more ***power*** to see what they are really capable of. But that is a challenge we will tackle in part 2 of this series of posts. Thank you for reading, hope you enjoyed. Have a nice day, and until next time! My other posts can be found [here](https://japiirainen.com). - Joona

parsercombinators

Implementing parser combinators pt. 1

Join Our Newsletter. No Spam, Only the good stuff.