matching greedily, but will then backtrack and try shorter matches if they fail to match.) For example, the expression a* will always consume as many a's as are consecutively available in the input string, and the expression (a* a) will always fail because the first part (a*) will never leave any a's for the second part to match. The and-predicate expression &e invokes the sub-expression e, and then succeeds if e succeeds and fails if e fails, but in either case never consumes any input. The not-predicate expression !e succeeds if e fails and fails if e succeeds, again consuming no input in either case. Examples This is a PEG that recognizes mathematical formulas that apply the basic five operations to non-negative integers. Expr ← Sum Sum ← Product (('+' / '-') Product)* Product ← Power (('*' / '/') Power)* Power ← Value ('^' Power)? Value ← [0-9]+ / '(' Expr ')' In the above example, the terminal symbols are characters of text, represented by characters in single quotes, such as '(' and ')'. The range [0-9] is a shortcut for the ten characters from '0' to '9'. (This range syntax is the same as the syntax used by regular expressions.) The nonterminal symbols are the ones that expand to other rules: Value, Power, Product, Sum, and Expr. Note that rules Sum and Product don't lead to desired left-associativity of these operations (they don't deal with associativity at all, and it has to be handled in post-processing step after parsing), and the Power rule (by referring to itself on the right) results in desired right-associativity of exponent. Also note that a rule like (with intention to achieve left-associativity) would cause infinite recursion, so it cannot be used in practice even though it can be expressed in the grammar. The following recursive rule matches standard C-style if/then/else statements in such a way that the optional "else" clause always binds to the innermost "if", because of the implicit prioritization of the '/' operator. (In a context-free grammar, this construct yields the classic dangling else ambiguity.) S ← 'if' C 'then' S 'else' S / 'if' C 'then' S The following recursive rule matches Pascal-style nested comment syntax, . The comment symbols appear in single quotes to distinguish them from PEG operators. Begin ← '(*' End ← '*)' C ← Begin N* End N ← C / (!Begin !End Z) Z ← any