Parsing expression grammar: Difference between revisions

Revision as of 17:13, 27 December 2023

Revision as of 19:13, 27 December 2023

Line 150:

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 ===