BASIC STRUCTURE

The general outline of a textual PEG is

PEG <<name>> (<<start-expression>>)
   <<rules>>
END;

Note: We are using text in double angle-brackets as place-holders for things not yet explained.

NAMES

Names are mostly used to identify the nonterminal symbols of the grammar, i.e. that which occurs on the left-hand side of a <rule>. The exception to that is the name given after the keyword PEG (see previous section), which is the name of the whole grammar itself.

The structure of a name is simple:

[1]

It begins with a letter, underscore, or colon, followed by

[2]

zero or more letters, digits, underscores, or colons.

Or, in formal textual notation:

    ([_:] / <alpha>) ([_:] / <alnum>)*

    Hello
    ::world
    _:submarine55_

    12
    .bogus
    0wrong
    @location

RULES

The main body of the text of a grammar specification is taken up by the rules. Each rule defines the sentence structure of one nonterminal symbol. Their basic structure is

     <<name>>  <-  <<expression>> ;

The <name> specifies the nonterminal symbol to be defined, the <expression> after the arrow (<-) then declares its structure.

Note that each rule ends in a single semicolon, even the last. I.e. the semicolon is a rule terminator, not a separator.

We can have as many rules as we like, as long as we define each nonterminal symbol at most once, and have at least one rule for each nonterminal symbol which occured in an expression, i.e. in either the start expression of the grammar, or the right-hande side of a rule.

EXPRESSIONS

The parsing expressions are the meat of any specification. They declare the structure of the whole document (<<start-expression>>), and of all nonterminal symbols.

All expressions are made up out of atomic expressions and operators combining them. We have operators for choosing between alternatives, repetition of parts, and for look-ahead constraints. There is no explicit operator for the sequencing (also known as concatenation) of parts however. This is specified by simply placing the parts adjacent to each other.

Here are the operators, from highest to lowest priority (i.e. strength of binding):

    # Binary operators.
    <<expression-1>>     <<expression-2>>  # sequence. parse 1, then 2.
    <<expression-1>>  /  <<expression-2>>  # alternative. try to parse 1, and parse 2 if 1 failed to parse.
    # Prefix operators. Lookahead constraints. Same priority.
    & <<expression>>  # Parse expression, ok on successful parse.
    ! <<expression>>  # Ditto, except ok on failure to parse.
    # Suffix operators. Repetition. Same priority.
    <<expression>> ?  # Parse expression none, or once (repeat 0 or 1).
    <<expression>> *  # Parse expression zero or more times.
    <<expression>> +  # Parse expression one or more times.
    # Expression nesting
    ( <<expression>> ) # Put an expression in parens to change its priority.

    ([_:] / <alpha>) ([_:] / <alnum>)*

    [_:] / <alpha>

    ([_:] / <alnum>)*

    [_:]
    <alpha>
    <alnum>

[1]

names, i.e. nonterminal symbols,

[2]

string literals, and

[3]

character classes.

Names we know about already, or see section Names for a refresher.

String literals are simple. They are delimited by (i.e. start and end with) either a single or double-apostroph, and in between the delimiters we can have any character but the delimiter itself. They can be empty as well. Examples of strings are

    ''
    ""
    'hello'
    "umbra"
    "'"
    '"'

For the last, but not least of our atomic expressions, character classes, we have a number of predefined classes, shown below, and the ability to construct or own. The predefined classes are:

    <alnum>    # Any unicode alphabet or digit character (string is alnum).
    <alpha>    # Any unicode alphabet character (string is alpha).
    <ascii>    # Any unicode character below codepoint 0x80 (string is ascii).
    <control>  # Any unicode control character (string is control).
    <ddigit>   # The digit characters [0-9].
    <digit>    # Any unicode digit character (string is digit).
    <graph>    # Any unicode printing character, except space (string is graph).
    <lower>    # Any unicode lower-case alphabet character (string is lower).
    <print>    # Any unicode printing character, incl. space (string is print).
    <punct>    # Any unicode punctuation character (string is punct).
    <space>    # Any unicode space character (string is space).
    <upper>    # Any unicode upper-case alphabet character (string is upper).
    <wordchar> # Any unicode word character (string is wordchar).
    <xdigit>   # The hexadecimal digit characters [0-9a-fA-F].
    .          # Any character, except end of input.

    [ <<range>>* ]

   <<character>> - <character>>

    [_:]
    [0-9]
    [0-9a-fA-F]

Basically characters in the input stand for themselves, and in addition to that we several types of escape syntax to to repesent control characters, or characters outside of the encoding the text is in.

All the escaped forms are started with a backslash character ('\', unicode codepoint 0x5C). This is then followed by a series of octal digits, or 'u' and hexedecimal digits, or a regular character from a fixed set for various control characters. Some examples:

    \n \r \t \' \" \[ \] \\ #
    \000 up to \277         # octal escape, all ascii character, leading 0's can be removed.
    \u2CA7                  # hexadecimal escape, all unicode characters.
    #                       # Here 2ca7 <=> Koptic Small Letter Tau

WHITESPACE AND COMMENTS

One issue not touched upon so far is whitespace and comments.

Whitespace is any unicode space character, i.e. anything in the character class <space>, and comments. The latter are sequences of characters starting with a '#' (hash, unicode codepoint 0x23) and ending at the next end-of-line.

Whitespace can be freely used between all syntactical elements of a grammar specification. It cannot be used inside of syntactical elements, like names, string literals, predefined character classes, etc.

NONTERMINAL ATTRIBUTES

Lastly, a more advanced topic. In the section Rules we gave the structure of a rule as

     <<name>>  <-  <<expression>> ;

This is not quite true. It is possible to associate a semantic mode with the nonterminal in the rule, by writing it before the name, separated from it by a colon, i.e. writing

    <<mode>> : <<name>>  <-  <<expression>> ;

is also allowed. This mode is optional. The known modes and their meanings are:

value

The semantic value of the nonterminal symbol is an abstract syntax tree consisting of a single node node for the nonterminal itself, which has the ASTs of the symbol's right hand side as its children.

leaf

The semantic value of the nonterminal symbol is an abstract syntax tree consisting of a single node node for the nonterminal, without any children. Any ASTs generated by the symbol's right hand side are discarded.

void

The nonterminal has no semantic value. Any ASTs generated by the symbol's right hand side are discarded (as well).

Of these three modes only leaf and void can be specified directly. value is implicitly specified by the absence of a mode before the nonterminal.

Now, with all the above under our belt it should be possible to not only read, but understand the formal specification of the text representation shown in the next section, written in itself.

EXAMPLE

Our example specifies the grammar for a basic 4-operation calculator.

PEG calculator (Expression)
    Digit      <- '0'/'1'/'2'/'3'/'4'/'5'/'6'/'7'/'8'/'9'	;
    Sign       <- '-' / '+'					;
    Number     <- Sign? Digit+					;
    Expression <- '(' Expression ')' / (Factor (MulOp Factor)*)	;
    MulOp      <- '*' / '/'					;
    Factor     <- Term (AddOp Term)*				;
    AddOp      <- '+'/'-'					;
    Term       <- Number					;
END;

Using higher-level features of the notation, i.e. the character classes (predefined and custom), this example can be rewritten as

PEG calculator (Expression)
    Sign       <- [-+] 						;
    Number     <- Sign? <ddigit>+				;
    Expression <- '(' Expression ')' / (Factor (MulOp Factor)*)	;
    MulOp      <- [*/]						;
    Factor     <- Term (AddOp Term)*				;
    AddOp      <- [-+]						;
    Term       <- Number					;
END;