single character The parsing expression matches and consumes the text "foo" but only if it is followed by the text "bar". The parsing expression matches the text "foo" but only if it is not followed by the text "bar". The expression matches a single "a" but only if it is not part of an arbitrarily long sequence of a's followed by a b. The parsing expression matches and consumes an arbitrary-length sequence of a's and b's. The production rule describes the simple context-free "matching language" . The following parsing expression grammar describes the classic non-context-free language : S ← &(A 'c') 'a'+ B !. A ← 'a' A? 'b' B ← 'b' B? 'c' Implementing parsers from parsing expression grammars Any parsing expression grammar can be converted directly into a recursive descent parser. Due to the unlimited lookahead capability that the grammar formalism provides, however, the resulting parser could exhibit exponential time performance in the worst case. It is possible to obtain better performance for any parsing expression grammar by converting its recursive descent parser into a packrat parser, which always runs in linear time, at the cost of substantially greater storage space requirements. A packrat parser is a form of parser similar to a recursive descent parser in construction, except that during the parsing process it memoizes the intermediate results of all invocations of the mutually recursive parsing functions, ensuring that each parsing function is only invoked at most once at a given input position. Because of this memoization, a packrat parser has the ability to parse many context-free grammars and any parsing expression grammar (including some that do not represent context-free languages) in linear time. Examples of memoized recursive descent parsers are known from at least as early as 1993. This analysis of the performance of a packrat parser assumes that enough memory is available to hold all of the memoized results; in practice, if there is not enough memory, some parsing functions might have to be invoked more than once at the same input position, and consequently the parser could take more than linear time. It is also possible to build LL parsers and LR parsers from parsing expression grammars, with better worst-case performance than a recursive descent parser, but the unlimited lookahead capability of the grammar formalism is then lost. Therefore, not all languages that can be expressed using parsing expression grammars can be parsed by