Parsing Expression Grammars (PEG)  are a derivative of Extended Backus-Naur Form (EBNF)  with a different interpretation, designed to represent a recursive descent parser. A PEG can be directly represented as a recursive-descent parser.
Like EBNF, PEG is a formal grammar for describing a formal language in terms of a set of rules used to recognize strings of this language. Unlike EBNF, PEGs have an exact interpretation. There is only one valid parse tree (see Abstract Syntax Tree) for each PEG grammar.
Sequences are represented by juxtaposition like in EBNF:
The PEG expression above states that, in order for this to succeed,
b must follow
Here's the syntax diagram:
Here's a trivial example:
which means the character
must be followed by a digit.
In Spirit.Qi, we use the
Alternatives are represented in PEG using the slash:
a / b
In Spirit.Qi and Spirit.Karma,
we use the
Alternatives allow for choices. The expression above reads: try to match
succeeds, success, if not try to match
This is a bit of a deviation from the usual EBNF interpretation where you
Here's the syntax diagram:
PEGs allow for ambiguity in the alternatives. In the expression above, both
can both match an input string. However, only the first matching alternative
is valid. As noted, there can only be one valid parse tree.
Again, like EBNF, PEG uses the regular-expression Kleene star and the plus loops:
Spirit.Qi and Spirit.Karma use the prefix star and plus since there is no postfix star or plus in C++.
Here are the syntax diagrams:
The first, called the Kleene star, matches zero or more of its subject
a. The second, plus, matches one ore more
of its subject
Unlike EBNF, PEGs have greedy loops. It will match as much as it can until its subject fails to match without regard to what follows. The following is a classic example of a fairly common EBNF/regex expression failing to match in PEG:
In PEG, alnum will eat as much alpha-numeric characters as it can leaving nothing more left behind. Thus, the trailing digit will get nothing. Loops are simply implemented in recursive descent code as for/while loops making them extremely efficient. That is a definite advantage. On the other hand, those who are familiar with EBNF and regex behavior might find the behavior a major gotcha. PEG provides a couple of other mechanisms to circumvent this. We will see more of these other mechanisms shortly.
In some cases, you may want to restrict a certain expression. You can think of a PEG expression as a match for a potentially infinite set of strings. The difference operator allows you to restrict this set:
a - b
The expression reads: match
There is no difference operator in Spirit.Karma, as the concept does not make sense in the context of output generation.