The Perl Toolchain Summit needs more sponsors. If your company depends on Perl, please support this very important event.

Pegex Syntax

The term "Pegex" can be used to mean both the Pegex Parser Framework and also the Pegex Grammar Language Syntax that is used to write Pegex grammar files. This document details the Pegex Syntax.

Pegex is a self-hosting language. That means that the grammar for defining the Pegex Language is written in the Pegex Language itself. You can see it for yourself here: https://github.com/ingydotnet/pegex-pgx/blob/master/pegex.pgx.

I encourage you to take a quick look at that link even now. A Pegex grammar (like this one) is made up of 2 parts: a meta section and a rule section.

The meta section just contains keyword/value meta attributes about the grammar. Things like the grammar's name and version.

The real meat of a Pegex grammar is in its rules. The very first rule of the grammar above is (basically):

    grammar: meta_section rule_section

Which says, a grammar IS a meta_section followed by a rule_section. But hey, we already knew that!

Meta Section

The meta statements ate the top of a grammar file look like this:

    %pegexKeyword value

Let's look at the top the the pegex.pgx grammar:

    # This is the Pegex grammar for Pegex grammars!
    %grammar pegex
    %version 0.1.0

This defines two meta values: grammar and version, which specify the name and the version of the grammar, respectively.

You'll also notice that the first line is a comment. Comments start with a # and go until the end of the line. Comments are allowed almost anywhere in the grammar, both on their own lines, after statements, and even within regex definitions as we will see later.

The Pegex Meta Section ends when the Pegex Rule Section begins (with the first rule definition).

Rule Section

The remainder of a Pegex grammar is a set of named rules. Each rule is a rule name, followed by a ':', followed by the definition of the rule, followed by a ';' or a newline.

Here are a couple rules from the pegex.pgx grammar. (These are the rules that start to define a rule!).

    rule_definition:
        rule_start
        rule_group
        ending

    rule_start: /
        ( rule_name )     # Capture the rule_name
        BLANK*
        COLON -
    /

Rule definitions are infix expressions. They consist of tokens separated by operators, with parentheses to disambiguate binding precedence. There are 3 distinct tokens and 3 operators.

The 3 token types are: rule-reference, regex and error-message. The 3 operators are AND (' '), OR ('|') and ALT ('%', '%%').

Here's an example from a Pegex grammar for parsing JSON:

    json: hash | array
    array: / LSQUARE / ( node* % / COMMA / ) (
        / RSQUARE / | `missing ']'` )

This is saying: "json is either a hash or array. array is '[', zero or more nodes separated by commas, and a ']'. error if no ']'".

hash, array and node are rule references, meaning that they refer to named rules within the grammar that must match at that point. Text surrounded by a pair of '/' chars forms a regex. Text surrounding by backticks is an error message.

LSQUARE, RSQUARE and COMMA are also rule references. Rules may be referred to inside of regexes, as long as they refer to regexes themselves. In this way big regexes can be assembled from smaller ones, thus leading to reuse and readability. Finally, the '*' after node is called a "quantifier". More about those later.

Rule References

A rule reference is the name of a rule inside angle brackets. The brackets are usually optional. Inside a regex, a rule reference without <> must be preceded by a whitespace character.

    <sub_rule_name>
    sub_rule_name

When used outside a regex, a reference can have a number of prefix modifiers. Note the the angle brackets are not required here, but add to readability.

    =rule  # Zero-width positive assertion (look-ahead)
    !rule  # Zero-width negative assertion (look-ahead)
    .rule  # Skip (ie: parse but don't capture a subpattern)
    -rule  # Flat (flatten the array captures)
    +rule  # Always wrap

(Skipping and wrapping are explained in [Return Values].)

A reference can also have a number of suffixed quantifiers. Similar to regular expression syntax, a quantifier indicates how many times a rule (reference) should match.

    rule?      # optional
    rule*      # 0 or more times
    rule+      # 1 or more times
    <rule>8    # exactly 8 times
    <rule>2+   # 2 or more times
    <rule>2-3  # 2 or 3 times
    <rule>0-6  # 0 to 6 times

Note that you must use angle brackets if you are using a numbered modifier:

    rule8    # WRONG!  This would match rule "rule8".
    rule2+   # WRONG!  This would match rule "rule2", 1 or more times.
    rule2-3  # WRONG!  Pegex syntax error

There is a special set of predefined "Atoms" that refer to regular expression fragments. Atoms exist for every punctuation character and for characters commonly found in regular expressions. Atoms enhance readability in grammar texts, and allow special characters (like slash or hash) to be used as Pegex syntax.

For example, a regex to match a comment might be '#' followed by anything, followed by a newline. In Pegex, you would write:

    comment: / HASH ANY* EOL /

instead of:

    comment: /#.*\r?\n/

Pegex would compile the former into the latter.

Here are some atoms:

    DASH    # -
    PLUS    # +
    TILDE   # ~
    SLASH   # /
    HASH    # # (literal)
    QMARK   # ? (literal)
    STAR    # * (literal)
    LPAREN  # ( (literal)
    RPAREN  # ) (literal)
    WORD    # \w
    WS      # \s

The full list can be found in the [Atoms source code|https://metacpan.org/source/Pegex::Grammar::Atoms].

Regexes

In Pegex we call the syntax for a regular expression a "regex". ie When the term "regex" is used, it is referring to Pegex syntax, and when the term "regular expression" is used it refers to the actual regular expression that the regex is compiled into.

A regex is a string inside forward slashes.

    /regex/

The regex syntax mostly follows Perl, with the following exceptions:

    # Any rules in angle brackets are referenced in the regex
    / ( <rule1> | 'non_rule' ) /  # "non_rule" is interpreted literally

    # The syntax implies a /x modifier, so whitespace and comments are
    # ignored.
    / (
        rule1+   # Match rule1 one or more times
        |
        rule2
    ) /

    # Whitespace is declared with dash and plus.
    / - rule3 + /  # - = \s*, + = \s+, etc.

    # Any (?XX ) syntax can have the question mark removed
    / (: a | b ) /  # same as / (?: a | b ) /

Error Message

An error message is a string inside backticks. If the parser gets to an error message in the grammar, it throws a parse error with that message.

    `error message`

Operators

The Pegex operators in descending precedence order are: ALT, AND, and OR.

AND and OR are the most common operators. AND is represented by the absence of an operator. Like in these rules:

    r1: <a><b>
    r2: a b

Those are both the same. They mean rule a AND (followed immediately by) rule b.

OR means match one or the other.

    r: a | b | c

means match rule a OR rule b OR rule c. The rules are checked in order and if one matches, the others are skipped.

ALT means alternation. It's a way to specify a separator in a list.

    r: a+ % b

would match these:

    a
    aba
    ababa

%% means that a trailing separator is optional.

    r: a+ %% b

would match these:

    a
    ab
    aba
    abab

ANY operators take precedence over everything else, similar to other parsers. These rules have the same binding precedence:

    r1: a b | c % d
    r2: (a b) | (c % d)

Parens are not only used for indicating binding precedence; they also can create quantifiable groups:

    r1: (a b)+ c

would match:

    abababac

Return Values

All return values are based on the capture groups ($1/$2/$3/etc. type variables) of parsed RE statements. The exact structure of the result tree depends on the type of Receiver used. For example, Pegex::Tree will return:

    $1              # single capture group
    [ @+[1..$#+] ]  # multiple capture groups

This would be a match directly from the RE rule. As rules go further back, things are put into arrays, but only if there is more than one result. For example:

    r: (a b)+ % +
    a: /( ALPHA+ )/
    b: /( DIGIT+ )( PLUS )/

    # input = foobar123+
    # output (using Pegex::Tree) = [
    #     'foobar', [ '123', '+' ]
    # ]
    #
    # input = foobar123+ boofar789+
    # output (using Pegex::Tree) = [
    #     [ 'foobar', [ '123', '+' ] ],
    #     [ 'boofar', [ '789', '+' ] ],
    # ]

Skipping

Any rule can use the skip modifier (DOT) to completely skip the return from that rule (and any children below it). The rule is still processed, but nothing is put into the tree. (This is different from, say, putting undef into the return.) This can also affect the number of values returned, and thus, whether a value comes as an array:

    r: (a .b)+ % +
    a: /( ALPHA+ )/
    b: /( DIGIT+ )( PLUS )/

    # input = foobar123+ boofar789+
    # output (using Pegex::Tree) = [
    #     'foobar',
    #     'boofar',
    # ]

The skip modifier can also be used with groups. (This is the only group modifier allowed so far.)

    r: .(a b)+ % +
    a: /( ALPHA+ )/
    b: /( DIGIT+ )( PLUS )/

    # output (using Pegex::Tree) = []

Wrapping

You can also turn on "wrapping" with the Pegex::Tree::Wrap receiver. This will wrap all match values in a hash with the rule name, like so:

    { rule_A => $match }
    { rule_B => [ @matches ] }

Note that this behavior can be "hard set" with the +/- rule modifiers:

    -rule  # Flatten array captures
    +rule  # Always wrap (even if using Pegex::Tree)

This is simply a check in the gotrule for the receiver. So, any specific got_* receiver methods will override even these settings, and choose to pass the match as-is. In this case, the got_* sub return value dictates what ultimately gets put into the tree object:

    +rule_A   # in this case, the + is useless here

    sub got_rule_A {
        my ($self, $matches_arrayref) = @_;
        return $matches_arrayref;
        # will be received as [ @matches ]
    }

You can "correct" this behavior by passing it back to gotrule:

    +rule_A   # now + is honored

    sub got_rule_A {
        my ($self, $matches_arrayref) = @_;
        return $self->gotrule($matches_arrayref);
        # will be received as { rule_A => [ @matches ] }
    }

See Also