Editing Parsing expression grammar (section)

=== Operational interpretation of parsing expressions ===
Each nonterminal in a parsing expression grammar essentially represents a parsing [[function (mathematics)|function]] in a [[recursive descent parser]], and the corresponding parsing expression represents the "code" comprising the function. Each parsing function conceptually takes an input string as its argument, and yields one of the following results:
* ''success'', in which the function may optionally move forward or ''consume'' one or more characters of the input string supplied to it, or
* ''failure'', in which case no input is consumed.

An atomic parsing expression consisting of a single '''terminal''' (i.e. literal) succeeds if the first character of the input string matches that terminal, and in that case consumes the input character; otherwise the expression yields a failure result. An atomic parsing expression consisting of the '''empty''' string always trivially succeeds without consuming any input.
 
An atomic parsing expression consisting of a '''nonterminal''' ''A'' represents a [[recursion|recursive]] call to the nonterminal-function ''A''. A nonterminal may succeed without actually consuming any input, and this is considered an outcome distinct from failure.

The '''sequence''' operator ''e''<sub>1</sub> ''e''<sub>2</sub> first invokes ''e''<sub>1</sub>, and if ''e''<sub>1</sub> succeeds, subsequently invokes ''e''<sub>2</sub> on the remainder of the input string left unconsumed by ''e''<sub>1</sub>, and returns the result. If either ''e''<sub>1</sub> or ''e''<sub>2</sub> fails, then the sequence expression ''e''<sub>1</sub> ''e''<sub>2</sub> fails (consuming no input).

The '''choice''' operator ''e''<sub>1</sub> / ''e''<sub>2</sub> first invokes ''e''<sub>1</sub>, and if ''e''<sub>1</sub> succeeds, returns its result immediately. Otherwise, if ''e''<sub>1</sub> fails, then the choice operator [[backtracking|backtracks]] to the original input position at which it invoked ''e''<sub>1</sub>, but then calls ''e''<sub>2</sub> instead, returning ''e''<sub>2</sub>'s result.

The '''zero-or-more''', '''one-or-more''', and '''optional''' operators consume zero or more, one or more, or zero or one consecutive repetitions of their sub-expression ''e'', respectively. Unlike in [[context-free grammar]]s and [[regular expression]]s, however, these operators ''always'' behave [[greedy algorithm|greedily]], consuming as much input as possible and never backtracking. (Regular expression matchers may start by 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.