Editing Parsing expression grammar (section)

== Implementing parsers from parsing expression grammars ==
Any parsing expression grammar can be converted directly into a [[recursive descent parser]].<ref name="ford02">{{cite thesis|url=http://pdos.csail.mit.edu/~baford/packrat/thesis|title=Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking|last=Ford|first=Bryan|date=September 2002|publisher=Massachusetts Institute of Technology|access-date=2007-07-27}}
<!-- I'm not sure how to incorporate all the info from this old ref into the new one above. If you can do so, or can verify that it has already been done, please delete this. --~~~~

Ford, Bryan, ''Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking'', Master’s thesis, Massachusetts Institute of Technology, September, 2002, http://pdos.csail.mit.edu/~baford/packrat/thesis/

-->
</ref> Due to the unlimited [[Parsing#Lookahead|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<ref name="ford02" />
is a form of [[parsing|parser]] similar to a recursive descent parser in construction, except that during the parsing process it [[memoization|memoizes]] the intermediate results of all invocations of the [[mutual recursion|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 grammar]]s 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.<ref name="merritt01">
{{cite web
|url=http://compilers.iecc.com/comparch/article/93-11-012
|title=Transparent Recursive Descent
|access-date=2009-09-04
|last=Merritt
|first=Doug
|date=November 1993
|publisher=Usenet group comp.compilers
}}
</ref>
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 parser]]s and [[LR parser]]s from parsing expression grammars,{{fact|date=December 2023}} with better worst-case performance than a recursive descent parser without memoization, 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 LL or LR parsers.

=== Bottom-up PEG parsing ===

A pika parser<ref name="Hut20">{{cite arXiv
| first= Luke A. D. |last=Hutchison
| title = Pika parsing: parsing in reverse solves the left recursion and error recovery problems
| year = 2020
|class=cs.PL
| eprint = 2005.06444
}}</ref> uses dynamic programming to apply PEG rules bottom-up and right to left, which is the inverse of the normal recursive descent order of top-down, left to right. Parsing in reverse order solves the left recursion problem, allowing left-recursive rules to be used directly in the grammar without being rewritten into non-left-recursive form, and also confers optimal error recovery capabilities upon the parser, which historically proved difficult to achieve for recursive descent parsers.