In functional programming, parser combinators are a powerful way of writing parsers. A parser is a function that, given some input, returns possible parsed values and the rest of the input. Parsers can be written using combinators for composition, for example run two parsers in sequence or perform one parser any number of times.
Parsers can also implement the monad structure. In some cases, this makes the parser less efficient, but it is an elegant way of composing parsers and we can also benefit from the syntactic support for monads. In this article, we implement a simple parser combinators for F# and we look what additional expressive power we can get from the joinad structure and match! construct. This article is largely based on a previous article "Fun with Parallel Monad Comprehensions", which can be found on the publications page.
The item parser returns the first character from the input. When it succeeds, it consumes a single character, so it returns 1 as the second element of the tuple. The run function converts the input to a list (i.e. from a string) and then runs the parser. The condition tail =  specifies that only results that were parsed without any remaining characters should be returned.
The unit operation returns a single result containing the specified value that doesn't consume any input. The implementation of bind uses sequence comprehensions to run the parsers in sequence. It returs the result of the second parser and consumes the sum of characters consumed by the first and the second parser. The zero operation creates a parser that always fails, and plus represents a nondeterministic choice between two parsers.
The computation builder also defines ReturnFrom member (to allow the return! syntax). It provides Delay and Run members - these will be used later by the joinad definitions, but they change how Combine behaves. In particular, one way to define Delay is to simply return the function (of type unit -> Parser<'T>) that it gets as an argument. As a result, the second argument of Combine will also be a function and so it needs to be evaluated before calling plus. The Run member is used on a value obtained from Delay, so it simply runs the function.
The definition of map uses only Bind and Return. The definition of sat also uses Zero (it is inserted automatically in place of the else branch). The some combinator calls two parsers in sequence and then returns, so it also does not need any primitives beyond Bind and Return. Finally, the many combinator uses Combine to represent choice between the two parsers.
/// body and then the same number of 'cl' chars.
run (map charsToString skipBrackets) "(((hello)))"
If you run the last line of the listing, you get a list containing "hello", but also "(hello)" and "((hello))". This is because the many item parser can also consume brackets. To correct that, we need to write a parser that accepts any character except opening and closing brace. As we will see shortly, this can be elegantly solved using joinads and the merge operation. The next section adds the required structure and finishes the example.
In order to support the match! syntax, we need to add operation Merge of type M<'T1> * M<'T2> -> M<'T1 * T2> and an operation Choose of type M<'T> * M<'T> -> M<'T>. The first operation is sometimes also called parallel composition, so what could that mean for parsers? One possible implementation is to run two parsers specified as arguments at the same input and return both of their results. The snippet below shows the source code.
/// one that does not return empty sequence.
The parser created by merge independently parses the input string using both of the parsers. It uses sequence comprehensions to find all combinations of results such that the number of characters consumed by the two parsers was the same. For each matching combination, the parser returns a tuple with the two parsing results. Requiring that the two parsers consume the same number of characters is not an arbitrary decision. It means that the remaining unconsumed strings tail1 and tail2 are the same and so we can return either of them.
run (map charsToString skipAllBrackets) "(((hello)))"
When you run the last line of the sample, you can see that only "hello" is returned as the result. The parser body is constructed using the match! notation. It takes two notChar parsers as the arguments and runs them both on the same input. They boty read a single character and succeed when the character is not the specified symbol. This means that body succeds only if the character is not '(' and ')'. Both parsers return the same character, so we return the first one as the result and ignore the second (the _ pattern means that the parser must succeed, but we then ignore the value).
Each condition on the number is encoded as a single parser. The first one ensures that all characters of the input are digits. The second parser checks that the input consits of 10 symbols and the last parser ensures that the input starts with the prefix "1223". The single clause of the match! construct is translated to applications of the Merge operation, which runs all three parsers on the same input and returns the parsed values only when all three succeed - meaning that the input satisifies all three conditions.
If you run the parser on the two sample inputs, the first line should succeed (the number is valid Cambridge phone number), but the second one fails. The prefix "1865" is used in the Oxford area!
The match! construct now takes four arguments. The first two are parsers that ensure that the input consists of just digits and has 10 characters, respectively. The next two parsers check for prefixes "1223" and "1865". The last two parsers will never both match on the same input, so a clause that would try to obtain a value from both of them would never succeed. However, we can write other useful clauses.
All of the three clauses in the above sample require the first two parsers to succeed. If the third parser also succeeds, the first clause matches and the number is identified as a Cambridge number. The second line is similar and recognizes Oxford numbers. Finally, the last line ignores both of the startsWith parsers.
One expected property of pattern matching is that only a single clause will be executed. Joinad definitions that obey the laws also have this property. For parsers, the choose operation gives the required behaviour - when a number is identified as Cambridge or Oxford number, the parser does not return Other as a possible result, even though the parser would also succed. This is because choose returns only results of a single parser (unlike plus which combines all successful results).
This article shows that joinads and the match! construct have uses outside of the concurrent and programming domains. In particular, it is possible to implement joinad operations for parsers. The Merge operation creates a parser that runs two parsers on the same input and the Choose operation creates a parser that returns results of exactly one of the specified parsers (meaning a choice without backtracking). The Merge operation is particularly interesting, because it gives a way to write intersection of languages recognized by two parsers.
body and then the same number of 'cl' chars.
one that does not return empty sequence.
let! _ = char str.