In a few recent posts I talked about playing with fparsec to parse data into usable syntax trees. But, even after all the time spent fiddling with it, I really didn’t fully understand how combinators actually worked. With that in mind, I decided to build a version of fparsec from scratch. What better way to understand something than to build it yourself? I had one personal stipulation, and that was to not look at the fparsec source. To be fair, I cheated with one function (the very first one) so I kind of cheated a lot, but I didn’t peek at anything else, promise.

Combinators

The principle behind combinators is that they are a way to take two functions and combine them into another function. Functional programming is chock full of this pattern. In general, you can combine any function to get any other function, but what makes a combinator powerful is when you combine a function, with another function, and get the same signature as the first function. Now you can recursively combine functions together.

For example, lets say I have a function defined like this:

  
let parser = state -\> result \* state

So it takes some input state, and gives you some sort of result along with a new state.

To make this useful though, I need to get the result and do something else with it. So, lets say I have another function that takes a result, and gives you a function that takes a new state and returns a new result.

  
let applier = result -\> (state -\> result \* state)

Is it possible to combine these two somehow? Sure:

  
let combiner parser applier =  
 fun state -\>  
 match parser state with  
 | (Some(result), newState) -\>  
 let nextParser = applier result  
 nextParser newState  
 | (None, newState) -\> (None, newState)

What’s the function signature of this combiner function?

  
(state -\> result \* state) -\> (result -\> (state -\> result \* state)) -\> (state -\> result \* state)

That’s kind of a mouthful, so lets add a type alias:

  
type Parser = state -\> result \* state

Now what is the type signature?

  
Parser -\> (result -\> Parser) -\> Parser

That’s a lot better.

We’ve just defined a way to take some function that takes a state and returns a result, combine it with something that takes a result and returns a new function, and it gives you a NEW parser. So you’ve combined the two things together to create the same kind of thing as the first thing!

What’s neat about this is you can use this basic combiner function to build up parsers that do small work.

Define a simple parser

Building a parser function is easy, it can be anything. Remembering the signature:

  
state -\> result \* state

Here is something that parsers a single character from a string:

  
let oneCharParser =  
 fun (state:string) -\>  
 let firstChar = state.Chars(0)  
 let remainingState = state.Substring(0, state.Length - 1)  
 (Some(firstChar), remainingState)

You can create more complex parsers too, maybe one that takes a regular expression or matches on a specific string. Anything you want.

Building on the combiner

Now that there is a combiner, and a way to define a parser, lets build on that. First lets alias the combiner function I first wrote out to make it a little easier to use:

  
let (\>\>=) current next = combiner current next

This operator, mimics the syntax from fparsec (and haskells parsec). Next, lets make a combinator function that takes two parsers, and returns the result of the second parser (ignoring the result of the first):

  
let (\>\>.) parser1 parser2 =  
 parser1 \>\>= fun firstResult -\>  
 parser2 \>\>= fun secondResult -\>  
 secondResult

But wait, that won’t really work. Remember that the combiners second argument wants a function that takes a result and returns a parser (which is a function that takes a state and returns a result) [i.e. of the signature result -> (state -> result * state).

If you look closely, we aren’t returning a parser at the end of this, we are just returning a value (i.e. just result). We need some sort of way to return a value as a parser. Hmm, fparsec has this and its called preturn. Let’s add this too:

  
let preturn value = fun state -\> (Some(value), state)

Not so bad. Now lets tie it in:

  
let (\>\>.) parser1 parser2 =  
 parser1 \>\>= fun firstResult -\>  
 parser2 \>\>= fun secondResult -\>  
 preturn secondResult

Awesome, now the magic that is the F# type inference system is happy!

But, we can do so much more. If all we need to do is create custom operators that leverage the combiner function we can create functions that:

  • Takes two parsers and returns the first (.>>)
  • Takes two parsers and returns the second (>>.)
  • Takes two parsers and returns a tuple of the result (.>>.)
  • Takes a parser and preturns its value into a parameterized discriminated union type (|>>)
  • Takes a parser and preturns its value into a non parameterized discriminated union type (|>>%)

State

In FParsec and other combinators, the state is a character stream. But when building out my own parsec clone I saw no reason that the state had to be tied to a specific type. Parser states share a few things in common:

  • Consume and return a consumed value
  • Backtrack to a position
  • Test if the state contains a predicate
  • Know if they are empty

When building my parser I kept this in mind and made the combinator library work on a general state interface that I called IStreamP

  
type IStreamP\<'StateType, 'ConsumeType\> =  
 abstract member state : 'StateType  
 abstract member consume : int -\> 'ConsumeType option \* IStreamP\<'StateType, 'ConsumeType\>  
 abstract member backtrack : unit -\> unit  
 abstract member hasMore : unit -\> bool

Using this interface I was able to implement a string parser state, as well as a binary parser state. Both states can be reused with all the combinator functions which is part of what makes parser combinators so robust. You get to mix language functionality with the grammar you are parsing.

An example

Now that I have all the basic building blocks, lets try parsing a CSV. The bulk of the work is being able to parse a string. But to parse a string, we have to see if the state matches something. So lets start with that. The combinator I wrote has a generic match function that you inject a predicate to:

  
let matcher eval target =  
 fun currentState -\>  
 match eval currentState target with  
 | Some(amount) -\> currentState.consume amount  
 | None -\> (None, currentState)

The signature of the eval function is:

  
state -\> 'a -\> int

So an evaluator function takes the current state, and some sort of target (maybe you are trying to match on a specific string) and if the predicate returns some integer amount, the state consumes the amount the predicate told it to take. A simple way of doing this is to see if the beginning of the string matches what you want to take:

  
type ParseState = State\<string, string\>

let private getStringStream (state:ParseState) = (state :?\> StringStreamP)

let private startsWith (input:ParseState) target = (input |\> getStringStream).startsWith input target

let matchStr str = matcher startsWith str

Basically its just getting a starts with expression match function from the state class. The idea here is that each state class can contain its own predicates to match on, so you don’t have to mix stuff between a binary state parser and a string state parser.

And just to show what the startsWith function looks like:

  
member x.startsWith (inputStream:IStreamP\<string, string\>) target =  
 if String.IsNullOrEmpty inputStream.state then None  
 else if inputStream.state.StartsWith target then  
 Some target.Length  
 else None

Building on this we can create matches that match using regex, or do other work. Taking kind of a leap of faith here, let me show the finished CSV parser (full source is on my github)

  
let delimType = ","

let(|DelimMatch|EscapedType|Other|) i =  
 if i = "\\" || i ="\"" then EscapedType  
 else if i = delimType then DelimMatch  
 else Other

let delim\<'a\> = matchStr delimType

let quote = matchStr "\""

let validNormalChars = function  
 | EscapedType  
 | DelimMatch -\> false  
 | rest -\> not (isNewLine rest)

let inQuotesChars = function  
 | "\"" -\> false  
 | \_ -\> true

let unescape = function  
 | "n" -\> "\n"  
 | "r" -\> "\r"  
 | "t" -\> "\t"  
 | c -\> c

let quoteStrings = (many (satisfy (inQuotesChars) any)) \>\>= foldChars

let escapedChar\<'a\> = matchStr "\\" \>\>. (anyOf matchStr [delimType; "\"";"n";"r";"t"] |\>\> unescape)

let normal\<'a\> = satisfy validNormalChars any

let normalAndEscaped = many (normal \<|\> escapedChar) \>\>= foldChars

let literal\<'a\> = between quote quoteStrings quote

let csvElement = ws \>\>. (literal \<|\> normalAndEscaped)

let listItem\<'a\> = delim \>\>. opt csvElement

let elements\<'a\> = csvElement .\<?\>\>. many listItem

let lines\<'a\> = many (elements |\> sepBy \<| newline) .\>\> eof

It should look very similiar to fparsec, but slightly different. For example, the .\<?\>\>. operator takes an item parser, and an item list parser, and optionally applies both the item and the list. If the list returns any results it preturns the first item with the item list, otherwise just returns the first item.

Another example

Just to demonstrate the power of decoupling the combinator logic from the state/stream logic, lets use the same combinator functions on a binary stream:

If we implement a new binary state stream, it might look like this:

  
type BinStream (state:Stream) =  
 let startPos = state.Position

interface IStreamP\<Stream, byte[]\> with  
 member x.state = state

member x.consume (count) =  
 let mutable bytes = Array.init count (fun i -\> byte(0))  
 state.Read(bytes, 0, count) |\> ignore

(Some(bytes), new BinStream(state) :\> IStreamP\<Stream, byte[]\> )

member x.backtrack () = state.Seek(startPos, SeekOrigin.Begin) |\> ignore

member x.hasMore () = state.Position \<\> state.Length

member x.streamCanBeConsumed (state:IStreamP\<Stream, byte[]\> ) count =  
 if (int)state.state.Position + (int)count \<= (int)state.state.Length then  
 Some(count)  
 else  
 None

And we can define a whole bunch of basic parsers to work with this stream:

  
module BinParser =

let private byteToInt (b:byte) = System.Convert.ToInt32(b)  
 let private toInt16 v = System.BitConverter.ToInt16(v, 0)  
 let private toInt32 v = System.BitConverter.ToInt32(v, 0)  
 let private toInt64 v = System.BitConverter.ToInt64(v, 0)

type ParseState = State\<Stream, byte[]\>

let private getBinStream (state:ParseState) = (state :?\> BinStream)

let private streamCanBeConsumed (state:ParseState) count = (state |\> getBinStream).streamCanBeConsumed state count

let private binMatch (num:int) = matcher streamCanBeConsumed num

let byteN\<'a\> = binMatch

let byte1\<'a\> = byteN 1 \>\>= fun b1 -\> preturn b1.[0]

let byte2\<'a\> = byteN 2

let byte3\<'a\> = byteN 3

let byte4\<'a\> = byteN 4

let int16\<'a\> = byte2 |\>\> toInt16

let int32\<'a\> = byte4 |\>\> toInt32

let int64\<'a\> = byteN 8 |\>\> toInt64

let intB\<'a\> = byte1 |\>\> byteToInt

And here is a unit test to show how it might be used:

  
[\<Test\>]  
let ``test reading two sets of 4 bytes``() =  
 let bytes = [|0;1;2;3;4;5;6;7;8|] |\> Array.map byte

let stream = new MemoryStream(bytes)

let binaryStream = new BinStream(stream)

let parser = manyN 2 byte4

let result = test binaryStream parser

result |\> should equal [[|0;1;2;3|];[|4;5;6;7|]]

Conclusion

What I like about combinators is that you build on the smallest blocks. And, unlike parser generators, you can mix language constructs with your grammar. Unfortunately debugging combinators is extremely difficult, since each combinator is a function that is composed of other functions. When you build a complex grammar up from those blocks, its easy to get lost in which function you are in and where you came from. The up side is that you can easily test against each building block independently.