Pika parser
In computer science, a pika parser[1] is a parser that applies PEG rules right to left, bottom-up, using dynamic programming, which is the inverse of the normal recursive descent or packrat parsing order[2] of top-down, left to right.
Properties
By parsing in reverse, pika parsing solves the left recursion problem, allowing left-recursive rules to be used directly in the grammar without them having to be rewritten into non-left-recursive form,[3] and also provides optimal error recovery capabilities for the parser, which historically proved difficult to achieve for recursive descent parsers.[4] The ability to recover from syntax errors is critical to the function of IDEs and compilers.
Performance
Like a packrat parser, a pika parser takes time linear in the length of the input and the depth of the parse tree. However, for very large grammars, Pika parsing incurs a sizeable constant multiplier per input character, which may mean that other parsers with super-linear parse time are faster for short to moderate inputs. For smaller grammars, e.g. an expression grammar, Pika parsing may be significantly faster than other parsers (as shown in the original paper).
Name origin
Pika parsing is named for the pika, which, like a packrat, stores food for the winter in "haystacks" or caches. (The earlier packrat parsing method got its name from the use of a memo table to store function call parameters and their results for later reuse, to avoid duplicated work.)
References
- ↑ A bot will complete this citation soon. Click here to jump the queue arXiv:2005.06444v3.
- ↑ Ford, Bryan (2002-09-03). "Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking" (PDF) (Master Thesis). Massachusetts Institute of Technology. Archived from the original on 2020-03-31. Retrieved 2020-06-18. Unknown parameter
|url-status=ignored (help)CS1 maint: Unfit url (link) - ↑ de Medeiros, Sérgio Queiroz; Mascarenhas, Fabio; Ierusalimschy, Roberto (2014-02-13) [2012-07-02]. "Left Recursion in Parsing Expression Grammars". Science of Computer Programming. 96: 177–190. arXiv:1207.0443v3. doi:10.1016/j.scico.2014.01.013. Unknown parameter
|s2cid=ignored (help) - ↑ de Medeiros, Sérgio Queiroz; de Azevedo Alvez, Jr., Gilney; Mascarenhas, Fabio (2020-10-01) [2019-05-06]. "Automatic Syntax Error Reporting and Recovery in Parsing Expression Grammars". Science of Computer Programming. v2. 187: 102373. arXiv:1905.02145v2. doi:10.1016/j.scico.2019.102373.
This article "Pika parser" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Pika parser. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
