Content deleted Content added
AtlasDuane (talk | contribs) m →Practical use: added article |
Ilgeco1995 (talk | contribs) m →Implementing parsers from parsing expression grammars: Add reference to packrat |
||
Line 121:
</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
| |||