Parsley Tutorial Part II: Parsing Structured Data

Now that you are familiar with the basics of Parsley syntax, let’s look at a more realistic example: a JSON parser.

The JSON spec on http://json.org/ describes the format, and we can adapt its description to a parser. We’ll write the Parsley rules in the same order as the grammar rules in the right sidebar on the JSON site, starting with the top-level rule, ‘object’.

object = ws '{' members:m ws '}' -> dict(m)

Parsley defines a builtin rule ws which consumes any spaces, tabs, or newlines it can.

Since JSON objects are represented in Python as dicts, and dict takes a list of pairs, we need a rule to collect name/value pairs inside an object expression.

members = (pair:first (ws ',' pair)*:rest -> [first] + rest)
          | -> []

This handles the three cases for object contents: one, multiple, or zero pairs. A name/value pair is separated by a colon. We use the builtin rule spaces to consume any whitespace after the colon:

pair = ws string:k ws ':' value:v -> (k, v)

Arrays, similarly, are sequences of array elements, and are represented as Python lists.

array = '[' elements:xs ws ']' -> xs
elements = (value:first (ws ',' value)*:rest -> [first] + rest) | -> []

Values can be any JSON expression.

value = ws (string | number | object | array
           | 'true'  -> True
           | 'false' -> False
           | 'null'  -> None)

Strings are sequences of zero or more characters between double quotes. Of course, we need to deal with escaped characters as well. This rule introduces the operator ~, which does negative lookahead; if the expression following it succeeds, its parse will fail. If the expression fails, the rest of the parse continues. Either way, no input will be consumed.

string = '"' (escapedChar | ~'"' anything)*:c '"' -> ''.join(c)

This is a common pattern, so let’s examine it step by step. This will match leading whitespace and then a double quote character. It then matches zero or more characters. If it’s not an escapedChar (which will start with a backslash), we check to see if it’s a double quote, in which case we want to end the loop. If it’s not a double quote, we match it using the rule anything, which accepts a single character of any kind, and continue. Finally, we match the ending double quote and return the characters in the string. We cannot use the <> syntax in this case because we don’t want a literal slice of the input – we want escape sequences to be replaced with the character they represent.

It’s very common to use ~ for “match until” situations where you want to keep parsing only until an end marker is found. Similarly, ~~ is positive lookahead: it succeed if its expression succeeds but not consume any input.

The escapedChar rule should not be too surprising: we match a backslash then whatever escape code is given.

escapedChar = '\\' (('"' -> '"')    |('\\' -> '\\')
                   |('/' -> '/')    |('b' -> '\b')
                   |('f' -> '\f')   |('n' -> '\n')
                   |('r' -> '\r')   |('t' -> '\t')
                   |('\'' -> '\'')  | escapedUnicode)

Unicode escapes (of the form \u2603) require matching four hex digits, so we use the repetition operator {}, which works like + or * except taking either a {min, max} pair or simply a {number} indicating the exact number of repetitions.

hexdigit = :x ?(x in '0123456789abcdefABCDEF') -> x
escapedUnicode = 'u' <hexdigit{4}>:hs -> unichr(int(hs, 16))

With strings out of the way, we advance to numbers, both integer and floating-point.

number = spaces ('-' | -> ''):sign (intPart:ds (floatPart(sign ds)
                                               | -> int(sign + ds)))

Here we vary from the json.org description a little and move sign handling up into the number rule. We match either an intPart followed by a floatPart or just an intPart by itself.

digit = :x ?(x in '0123456789') -> x
digits = <digit*>
digit1_9 = :x ?(x in '123456789') -> x

intPart = (digit1_9:first digits:rest -> first + rest) | digit
floatPart :sign :ds = <('.' digits exponent?) | exponent>:tail
                     -> float(sign + ds + tail)
exponent = ('e' | 'E') ('+' | '-')? digits

In JSON, multi-digit numbers cannot start with 0 (since that is Javascript’s syntax for octal numbers), so intPart uses digit1_9 to exclude it in the first position.

The floatPart rule takes two parameters, sign and ds. Our number rule passes values for these when it invokes floatPart, letting us avoid duplication of work within the rule. Note that pattern matching on arguments to rules works the same as on the string input to the parser. In this case, we provide no pattern, just a name: :ds is the same as anything:ds.

(Also note that our float rule cheats a little: it does not really parse floating-point numbers, it merely recognizes them and passes them to Python’s float builtin to actually produce the value.)

The full version of this parser and its test cases can be found in the examples directory in the Parsley distribution.