How to write a JSON Parser in Pegex

Test First

The test is written in a testing language known as TestML. TestML just happens to also use Pegex in its compiler. Both TestML and Pegex are Acmeist frameworks, meaning that they are intended to work in multiple programming languages.

You can run the test like normal:

    > prove -lv t/test.t

The Pegex JSON Grammar

Since Pegex is Acmeist, I put the JSON grammar in its own repo so that it could be shared by many different projects in different programming languages. The grammar file is here: <https://github.com/ingydotnet/json-pgx/blob/master/json.pgx>.

Let's look at this small but complete language definition in detail.

The file starts with some comments. Comments can be used liberally in Pegex and go from a '#' to the end of a line. Just as you would expect.

    # A simple grammar for the simple JSON data language.
    # For parser implementations that use this grammar, see:
    # * https://github.com/ingydotnet/pegex-json-pm

Next we have what is called the Meta section of the grammar.

    %grammar json
    %version 0.0.1

Meta section lines are of the form:

    %key value

Your grammar should have at least a name and a version.

Everything else in the grammar is a set of things called "rules". A rule has a name and a definition. The first rule in a grammar is special. When a parser starts parsing it defaults to using the first rule as the starting rule (although this can be overridden).

We start the JSON grammar with this rule:

    json: map | seq

The name of this rule is 'json'. When we start parsing JSON we say that the entire text must match the rule 'json'. This makes a lot of sense.

This style of parsing is known as Top Down and Recursive Descent. Pegex is both of these. It should be noted that Pegex does not tokenize a text before parsing it. The rules themselves form a kind of tokenizer, pulling out the desired data segments as needed.

In this rule, we are saying that a 'json' document is either a 'map' (aka mapping or hash) OR it is a 'seq' (aka sequence or array), which assuming you know JSON (almost everybody does), is the only thing allowed at the top level.

In this rule, 'map' and 'seq' are called 'rule references'. They point to other named rules that are expected to be in the grammar. References are usually just the name of the subrule itself, but can also be enclosed in angle brackets (which are sometimes required). ie the rule above could also be written like this:

    json: map | seq

We are also introduced to the OR operator which is a single PIPE character. It should also be noted that a COLON simply separates a rule name and its definition.

The next line defines a new rule called 'node':

    node: map | seq | scalar

We are calling 'node' the list of general structures that any given point in the JSON data graph can be. This is simply a mapping, sequence or scalar.

Moving on, we need rules describing 'map', 'seq' 'scalar'. A grammar is complete when all of its rule references are defined.

Let's start with map:

    map:
        /- LCURLY -/
        pair* % /- COMMA -/
        /- RCURLY -/

This seems a lot more complicated, but let's break things down, one at a time. What we will find this rule to mean, is that a map is a '{' followed by zero or more (key/value) pairs separated by a comma, then ending with a '}'. Along the way there may also be intermittent whitespace. The '-' character indicates whitespace, but we'll cover that more later.

The first thing we notice is that a rule definition can span multiple lines. A rule definition ends when the next rule begins. Pegex actually allows for multiple rules on one line, but they must be separated by semicolons, like so:

    rule1: a|b; rule2: c|d; rule3: e|f

The next thing we see are forward slash characters. Like in Perl and JavaScript, a pair of slashes indicate a regular expression. In this rule we have 3 regular expressions.

It is a good time to note that Pegex grammars get compiled into a simple data structure that you can express as JSON or YAML. In fact the repository containing the Pegex grammar that we are discussing also contains the matching compiled forms. See: <https://github.com/ingydotnet/json-pgx/blob/master/json.pgx.yaml>. A quick glance at this file shows all the same rule definitions, but the regexes look much different.

That's because Pegex tries to make regexes readable and composable. That means that complex regexes can be defined as small parts that get composed into bigger parts. By the time they get compiled, they can be quite hard to understand.

For example if we had this Pegex grammar:

    greeting: / hello COMMA - world /
    hello: / (:'O' SPACE 'HAI' | 'Hey' SPACE 'there') /
    world: / (:Earth|Mars|Venus) /

It would compile to:

    greeting:
      .rgx: (?:O\ HAI|Hey\ there),\s*(?:Earth|Mars|Venus)

Note the the 'hello' and 'world' rules are gone, but their definitions have been baked into the one big regex for 'greeting'.

Additionally there are references to things like COMMA and SPACE. These are called Pegex Atoms, and there are atoms for all the punctuation characters, whitespace chars, and others. The full list is here: Pegex::Grammar::Atoms.

Having to write out 'SEMI' instead of ';' seems strange at first, but it is how Pegex easily separates metasyntax from text to be matched. Once you get used to it, it is very readable.

The actual whitespace (and comments) inside a regex are completely ignored by Pegex. This is the same as Perl's 'x' regex flag.

Finally the '-' is Pegex's 'possible whitespace' indicator, and usually expands to "\s*". It actually expands to "ws1", which expands to "ws*", which expands to "WS*", which expands to "\s*" (unless you override any of those rules).

Getting back to JSON...

The rule we defined for 'map' should now be more readable. Let's look at it again, but this time in a more compact form:

    map: /- LCURLY -/   (pair* % /- COMMA -/)   /- RCURLY -/

I've compacted the regexes (since they just mean curlies and commas with possible whitespace), and I've added parentheses around the middle stuff to indicate the the '%' operator has a tighter binding.

So what is the '%' operator? It was borrowed from Perl 6 Rules. Consider:

    a+ % b

This means one or more 'a', separated by 'b'. Simple. The %% operator means the same thing, except it indicates that a trailing 'b' is OK.

This notation is handy for things like comma separated lists. (Which is exactly what we are using it for here.)

The rule above means zero or more 'pair's separated by commas. (trailing comma not allowed, which is strictly correct for JSON).

Now is a good time to bring up 'rule quantifiers'. A rule quantifier is a suffix to a rule reference, and can be one of ? * or +. These suffixes mean the same thing that they would in regexes.

There are two other quantifier suffixes. '2+' is equivalent to the regex syntax {2,} and 2-5 is the same as {2,5}. When you use one of these two forms, you need to put the rule reference in angle brackets, or else the number looks like part of the rule name. For example:

    rule1: <rule2>5-9 <rule3>29+

not:

    rule1: rule25-9 rule329+

Let's take a look at that rule after Pegex compilation:

    map:
      .all:
      - .rgx: \s*\{\s*
      - +min: 0
        .ref: pair
        .sep:
          .rgx: \s*,\s*
      - .rgx: \s*\}\s*

The rule for 'map' says that the text must match 3 thing: a regex (opening curly brace), zero or more occurrences of a rule called 'pair' separated by a regex (comma), and finally another regex (closing curly).

One thing that we have silently covered is the AND operator. That's because there is no operator symbol for it. Consider the rules:

    a: b c+ /d/
    b: c | d
    c: d e | f % g

The PIPE character between 2 things means OR. No symbol between 2 things means AND. A PERCENT means ALTERNATION. ALTERNATION binds tightest and OR binds loosest, with AND in the middle. Precedence can be disambiguated with parentheses. Thus the rule for 'c' can be restated:

    c: ((d e) | (f % g))

OK. I think we've covered just about everything needed so far. That was a lot of learning for one rule, but now you know most of Pegex!

The next three rules need no new knowledge. Take a look at these and see if you can figure them out.

    pair:
        string
        /- COLON -/
        node

    seq:
        /- LSQUARE -/
        node* % /- COMMA -/
        /- RSQUARE -/

    scalar:
        string |
        number |
        boolean |
        null

A pair (you know... a hash key/value), is a string, a colon, and some node. A seq is zero or more comma-separated nodes between square brackets. A scalar can be one of 4 forms. Simple.

One interesting point is that has just arisen here, is the use of recursion. The rules for pair and seq both reference the rule for node. Thus, the grammar is recursive descent. It starts with the rule for the thing as a whole (ie 'json') and descends (recursively) until it matches all the specific characters.

    # string and number are interpretations of http://www.json.org/
    string: /
        DOUBLE
            (
                (:
                    BACK (:       # Backslash escapes
                        [
                            DOUBLE      # Double Quote
                            BACK        # Back Slash
                            SLASH       # Forward Slash
                            b           # Back Space
                            f           # Form Feed
                            n           # New Line
                            r           # Carriage Return
                            t           # Horizontal Tab
                        ]
                    |
                        u HEX{4}        # Unicode octet pair
                    )
                |
                    [^ DOUBLE CONTROLS ]  # Anything else
                )*
            )
        DOUBLE
    /

    /"((?:\\(?:["\\/bfnrt]|u[0-9a-fA-F]{4})|[^"\x00-\x1f])*)"/

    number: /(
        DASH?
        (: 0 | [1-9] DIGIT* )
        (: DOT DIGIT* )?
        (: [eE] [ DASH PLUS ]? DIGIT+ )?
    )/

    boolean: true | false

    true: /true/

    false: /false/

    null: /null/

Pegex::JSON::Grammar - The Pegex Grammar Class

It should be noted that Pegex uses Pegex to parse Pegex grammars. That is, this grammar: <https://github.com/ingydotnet/pegex-pgx/blob/master/pegex.pgx> is used by Pegex to parse our json.pgx grammar (and yes, it can parse pegex.pgx too).

It is conceivable that every time we wanted to parse JSON, we could parse the json.pgx grammar first, but that would be a waste of time. So we cache the big grammar tree as a pure Perl data structure inside Pegex::JSON::Grammar.

If for some reason we did need to change the json.pgx, we would have to recompile it to Perl and copy/paste it into our module. This would be a pain, so there is a special command to do it for us. Just run this:

    perl -Ilib -MPegex::JSON:Grammar=compile

If you are in heavy development mode and changing the grammar a lot, you can simply set an environment variable like this:

    export PERL_PEGEX_AUTO_COMPILE=Pegex::JSON::Grammar

and recompilation will happen automatically. This is possible because of this line in the grammar module:

    use constant file => '../json-pgx/json.pgx';

That line is only used during development and requires the grammar file to be in that location.

Pegex::JSON::Data - The Pegex Receiver Class

One of the hallmarks of Pegex, is that it keeps the grammar separate from the (receiver) code, thus