4 Tutorial

FParsec is built as two DLLs: FParsec.dll and FParsecCS.dll. To use FParsec in your project, you can either let NuGet install one of the NuGet packages, or you can build the two FParsec DLLs from source. The easiest way to build FParsec from source is using the Visual Studio solution files in the Build/VS11 folder of the source code package. Any project that uses FParsec has to reference both DLLs. See Download and Installation for more details.

All code snippets in this tutorial assume that you’ve opened the FParsec namespace:

open FParsec

Opening the FParsec namespace also automatically opens the Primitives, CharParsers and Error modules.

Let’s start with a simple example: parsing a single floating‐point number in a string.

The generic type Parser<'Result,'UserState> is the type of all parsers in FParsec. If you follow the hyperlink into the reference, you’ll see that Parser is a type abbreviation for a function type. However, at this point we don’t need to go into the details of the Parser type. It’s enough to note that the first type argument represents the type of the parser result. Thus, in the case of pfloat the type tells us that if the parser succeeds it returns a floating‐point number of type float. We won’t use a “user state” in this tutorial, so you can just ignore the second type argument for the time being.

run is the simplest function out of several provided by the CharParsers module for running parsers on input. Other functions allow you, for example, to run parsers directly on the contents of a file or a System.IO.Stream.

run applies the parser passed as the first argument to the string passed as the second argument and returns the return value of the parser in form of a ParserResult value. The ParserResult type is a discriminated union type with the two cases: Success and Failure. In case the parser succeeds, the ParserResult value contains the result value, otherwise it contains an error message.

Implementing parsers with FParsec typically means combining higher‐level parsers from lower‐level ones. You start with the parser primitives provided by the library and then successively combine these into higher‐level parsers until you finally have a single parser for the complete input.

The definition of str and floatBetweenBrackets involves three library functions that we haven’t yet introduced: pstring, >>. and .>>.

The function

val pstring: string -> Parser<string,'u>

takes a string as the argument and returns a parser for that string. When this parser is applied to an input stream it checks whether the following chars in the input stream match the given string. If the chars match the complete string, the parser consumes them, i.e. skips over them. Otherwise it fails without consuming any input. When the parser succeeds, it also returns the given string as the parser result, but since the string is a constant, you’ll rarely make use of the result.

The pstring function isn’t named string because otherwise it would hide the built‐in F# function string. In general, parser names in FParsec that would otherwise conflict with built‐in F# function names are prefixed by a single p char. pfloat is another example for this naming convention.

To save a few keystrokes we abbreviate pstring as str. So, for instance, str "[" is a parser that skips over the char '['.

As you can see from these signatures, both operators are parser combinators that construct a new parser from the two argument parsers. The parser p1 >>. p2 parses p1 and p2 in sequence and returns the result of p2. The parser p1 .>> p2 also parses p1 and p2 in sequence, but it returns the result of p1 instead of p2. In each case the point points to the side of the parser whose result is returned. By combining both operators in p1 >>. p2 .>> p3 we obtain a parser that parses p1, p2 and p3 in sequence and returns the result from p2.

The following tests show that floatBetweenBrackets parses valid input as expected and produces informative error messages when it encounters invalid input:

One of FParsec’s greatest strengths is the ease with which you can define your own parser abstractions.

Actually, you don’t need to define between, because this is already a built‐in FParsec combinator.

These are all trivial examples, of course. But since FParsec is merely an F# library and not some external parser generator tool, there are no limits to the abstractions you can define. You can write functions that take whatever input you need, do some arbitrarily complex computations on the input and then return a special purpose parser or parser combinator.

For example, you could write a function that takes a regular‐expression pattern as the input and returns a Parser for parsing input conforming to that pattern. This function could use another parser to parse the pattern into an AST and then compile this AST into a special‐purpose parser function. Alternatively, it could construct a .NET regular expression from the pattern and then return a parser function that uses FParsec’s CharStream API to directly apply the regex to the input stream (which is what the built‐in regex parser actually does).

Another example are extensible parser applications. By storing parser functions in dictionaries or other data structures and defining an appropriate extension protocol, you could allow plugins to dynamically register new parsers or modify existing ones.

The possibilities are really endless. But before you can fully exploit these possibilities, you first need to be familiar with the fundamentals of FParsec.

We’ve already spent three sections on discussing how to parse a single floating‐point number, so it’s about time we try something more ambitious: parsing a list of floating‐point numbers.

Let us first assume that we need to parse a sequence of floating‐point numbers in brackets, i.e. text in the following EBNF format: ("[" float "]")*. Valid input strings in this format are for example: "", "[1.0]", "[2][3][4]".

The parser many p repeatedly applies the parser p until p fails, i.e. it “greedily” parses as many occurrences of p as possible. The results of p are returned as a list in the order of occurrence.

If you just want to skip over a sequence and don’t need the list of parser results, you could use the optimized combinators skipMany or skipMany1 instead of many and many1.

sepBy takes an “element” parser and a “separator” parser as the arguments and returns a parser for a list of elements separated by separators. In EBNF notation sepBy p pSep could be written as (p (pSep p)*)?. Similar to many, there are several variants of sepBy.

Valid input strings in this format are for example: "[]", "[1.0]", "[2,3,4]".

If we want the parser to ignore whitespace, we need to make this explicit in the parser definition.

Next, we need to insert the ws parser at every point where we want to ignore whitespace. In general it’s best to skip whitespace after one parses elements, i.e. skip trailing instead of leading whitespace, because that reduces the need for backtracking (which will be explained below). Hence, we insert ws at two places to skip over any whitespace after brackets or numbers:

FParsec contains various built‐in parsers for chars, strings, numbers and whitespace. In this section we will introduce a few of the char and string parsers. For an overview of all available parsers please refer to the parser overview in the reference.

You’ve already seen several applications of the pstring parser (abbreviated as str), which simply skips over a constant string in the input. When the pstring parser succeeds, it also returns the skipped string as the parser result. The following example demonstrates this:

In this example we also used the <|> combinator to combine two alternative parsers. We’ll discuss this combinator in more detail below.

When you don’t need the result of the pstring parser, you can alternatively use the skipString parser, which returns the unit value () instead of the argument string. In this case it doesn’t make any difference to performance whether you use pstring or skipString, since the returned string is a constant. However, for most other built‐in parsers and combinators you should prefer the variants with the “skip” name prefix when you don’t need the parser result values, because these will generally be faster. If you look at the parser overview, you’ll see “skip” variants for many of the built‐in parsers and combinators.

Frequently one needs to parse string variables whose chars have to satisfy certain criteria. For instance, identifiers in programming languages often need to start with a letter or underscore and then need to continue with letters, digits or underscores. To parse such an identifier you could use the following parser:

Here we have used the many1Satisfy2L string parser, which is one of several primitives for parsing strings based on char predicates (i.e. functions that take a char as input and return a boolean value). It parses any sequence of one or more chars (hence the “many1” in the name) whose first char satisfies the first predicate function and whose remaining chars satisfy the second predicate (hence the “Satisfy2”). The string label given as the third argument (hence the “L”) is used in error message to describe the expected input.

Here we have used the manyStrings combinator, which parses a sequence of strings with the given string parser and returns the strings in concatenated form.

Parsing a string chunk‐wise using an optimized parser like many1Satisfy is usually a bit faster than parsing it char‐wise using manyChars and satisfy. In this case we can optimize our parser even a bit further – once we realize that two normal char snippets must be separated by at least one escaped char:

let stringLiteral3 =
    let normalCharSnippet = manySatisfy (fun c -> c <> '\\' && c <> '"')
    let escapedChar = (* like in stringLiteral2 *)
    between (pstring "\"") (pstring "\"")
            (stringsSepBy normalCharSnippet escapedChar)

The stringsSepBy combinator parses a sequence of strings (with the first argument parser) separated by other strings (parsed with the second argument parser). It returns all parsed strings, including the separator strings, as a single, concatenated string.

Note that stringLiteral3 uses manySatisfy instead of many1Satisfy in its normalCharSnippet definition, so that it can parse escaped chars that are not separated by normal chars. This can’t lead to an infinite loop because escapedChar can’t succeed without consuming input.

Whenever you need to apply multiple parsers in sequence and only need the result of one of them, a suitable combination of >>. and .>> operators will do the job. However, these combinators won’t suffice if you need the result of more than one of the involved parsers. In that case you can use the pipe2, …, pipe5 combinators, which apply multiple parsers in sequence and pass all the individual results to a function that computes the aggregate result.

For instance, with the pipe2 combinator

val pipe2: Parser<'a,'u> -> Parser<'b,'u> -> ('a -> b -> 'c) -> Parser<'c,'u>

you can construct a parser pipe2 p1 p2 f that sequentially applies the two parsers p1 and p2 and then returns the result of the function application f x1 x2, where x1 and x2 are the results returned by p1 and p2.

If you just want to return the parsed values as a tuple, you can use the predefined tuple2-5 parsers. For instance, tuple2 p1 p2 is equivalent to pipe2 p1 p2 (fun x1 x2 -> (x1, x2)).

Hopefully you find the >>‐with‐1‐or‐2‐dots‐notation intuitive by now.

If you need a pipe or tuple parser with more than 5 arguments, you can easily construct one using the existing ones. For example, do you have an idea how to define a pipe7 parser? This footnote gives a possible solution: ^[1]

This combinator allows you to support multiple alternative input formats at a given input position. For example, in the above section we used <|> to combine a parser for unescaped chars and a parser for escaped chars into a parser that supports both: normalChar <|> escapedChar.

Here we have also used the stringReturn parser, which skips the string constant given as the first argument and, if successful, returns the value given as the second argument.

If you’re curious why <|> behaves this way and how you can handle situations where you need <|> to try the alternative parser even if the first parser fails after consuming input, please see section 5.6 and section 5.7 in the user’s guide.

If you want to try more than two alternative parsers, you can chain multiple <|> operators, like in p1 <|> p2 <|> p3 <|> ..., or you can use the choice combinator, which accepts a sequence of parsers as the argument, like in choice [p1; p2; p3; ...].

When you start writing your own parsers with FParsec or try to compile some individual code snippets from above, you’ll come across a compiler issue that often causes some head‐scratching among new users of F# and FParsec: the value restriction. In this section we’ll explain the value restriction and how you can handle it in your FParsec programs.

When you work with FParsec you’ll sooner or later see this or similar error messages, in particular if you work with the interactive console prompt. Fortunately, this kind of error is usually easy to workaround.

The problem with the first snippet above is that the F# compiler infers the p value to have an unresolved generic type, although F# doesn’t permit a generic value in this situation. The return type of the pstring function is Parser<string,'u>, where the type parameter 'u represents the type of the CharStream user state. Since there is nothing in the first snippet that constrains this type parameter, the compiler infers the type Parser<string,'_a> for the parser value p, with '_a representing an unresolved type parameter.

In the second snippet this problem doesn’t occur, because the use of p as the first argument to the run function constrains the user state type. Since run only accepts parsers of type Parser<'t,unit>, the compiler infers the non‐generic type Parser<string,unit> for p.

Of course, constraining the type of a parser value to a non‐generic type is only a solution if you don’t actually need a generic type. If you do need a generic value, you’ll have to apply other techniques, as they are for example explained in the F# reference or in a blog entry by Dmitry Lomov. However, FParsec Parser values (not parametric parser functions) are usually only used in the context of a specific parser application with a fixed user state type. In that situation constraining the type is indeed the appropriate measure to avoid a value restriction error.

Now that we have discussed the basics of FParsec we are well prepared to work through a real world parser example: a JSON parser.

JSON (JavaScript Object Notation) is a text‐based data interchange format with a simple and lightweight syntax. You can find descriptions of the syntax on json.org and in RFC 4626.

In many applications one only has to deal with JSON files describing one particular kind of object. In such a context it sometimes can be appropriate to write a specialized parser just for that specific kind of JSON file. In this tutorial, however, we will follow a more general approach. We will implement a parser that can parse any general JSON file into an AST, i.e. an intermediate data structure describing the contents of the file. Applications can then conveniently query this data structure and extract the information they need. This is an approach comparable to that of XML parsers which build a data structure describing the document tree of an XML document. The great advantage of this approach is that the JSON parser itself becomes reusable and the document specific parsing logic can be expressed in the form of simple functions processing the AST of the JSON document.

The natural way to implement an AST in F# is with the help of a discriminated union type. If you look at the JSON specification, you can see that a JSON value can be a string, a number, a boolean, null, a comma‐separated list of values in square brackets, or an object with a sequence of key‐value pairs in curly brackets.

Here we’ve chosen the F# list type to represent a sequence of values and the Map type to represent a sequence of key‐value pairs, because these types are particularly convenient to process in F#.^[3] Note that the Json type is recursive, since both JList and JObject values can themselves contain Json values. Our parser will have to reflect this recursive structure.

Handling the number case is just as simple, because the JSON number format is based on the typical floating‐point number format used in many programming languages and hence can be parsed with FParsec’s built‐in pfloat parser:

let jnumber = pfloat |>> JNumber

(Note that F# allows us to pass the object constructor JNumber as a function argument.)

If you compare the precise number format supported by pfloat with that in the JSON spec, you’ll see that pfloat supports a superset of the JSON format. In contrast to the JSON format the pfloat parser also recognizes NaN and Infinity values, accepts a leading plus sign, accepts leading zeros and even supports the hexadecimal float format of Java and C99. Depending on the context this behaviour can be considered a feature or a limitation of the parser. For most applications it probably doesn’t matter, and the JSON RFC clearly states that a JSON parser may support a superset of the JSON syntax. However, if you’d rather only support the exact JSON number format, you can implement such a float parser rather easily based on the configurable numberLiteral parser (just have a look at how this is currently done in the pfloat source).

The JSON string format takes a little more effort to implement, but we’ve already parsed a similar format with the stringLiteral parsers in section 4.7, so we can just adapt one of those parsers for our purpose:

stringLiteral parses string literals as a sequence of normal char snippets separated by escaped char snippets. A normal char snippet is any sequence of chars that does not contain the chars '"' and '\\'. An escaped char snippet consists of a backslash followed by any of the chars '\\', '\"', '/', 'b', 'f', 'n', 'r', 't', or an Unicode escape. An Unicode escape consists of an 'u' followed by four hex chars representing an UTF‐16 code point.

As you might have guessed from the name, createParserForwardedToRef creates a parser (jvalue) that forwards all invocations to the parser in a reference cell (jvalueRef). Initially, the reference cell holds a dummy parser, but since the reference cell is mutable, we can later replace the dummy parser with the actual value parser, once we have finished constructing it.

This function takes four arguments: an opening string, a closing string, an element parser and a function that is applied to the parsed list of elements.

JSON objects are lists of key‐value pairs, so we need a parser for a key‐value pair:

let keyValue = stringLiteral .>>. (ws >>. str ":" >>. ws >>. jvalue)

(Remember, the points on both sides of .>>. indicate that the results of the two parsers on both sides are returned as a tuple.)

Having defined parsers for all the possible kind of JSON values, we can combine the different cases with a choice parser to obtain the finished parser for JSON values:

This parser will try to consume a complete JSON input stream and, if successful, will return a Json AST of the input as the parser result

And that’s it, we’re finished with our JSON parser. If you want to try this parser out on some sample input, please take a look at the JSON project in the Samples folder.

If this tutorial has whet your appetite for a more in‐depth introduction to FParsec, just head over to the user’s guide. If you can’t wait to write your own parser, then bookmark the parser overview page, maybe take a short look at the example parsers in the Samples folder and just start hacking. You can always consult the user’s guide at a later point should you get stuck somewhere.