Content deleted Content added
→Implementing parsers from parsing expression grammars: Flagging claim about LL and LR parsers |
Moved section on bottom–up parsing |
||
Line 151:
It is also possible to build [[LL parser]]s and [[LR parser]]s from parsing expression grammars,{{fact}} 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 conveys optimal error recovery capabilities upon the parser, which historically proved difficult to achieve for recursive descent parsers.▼
== Advantages ==
Line 299 ⟶ 309:
S → start(G1) | start(G2)
</syntaxhighlight>
▲== 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 conveys optimal error recovery capabilities upon the parser, which historically proved difficult to achieve for recursive descent parsers.
== Practical use ==
| |||