Editing Packrat parser (section)


{{Short description|Type of parser}}
{{Infobox algorithm
|name={{PAGENAMEBASE}}
|class=[[Parsing]] grammars that are [[Parsing expression grammar|PEG]]
|data=[[String (computer science)|String]]
|time=<math>O(n)</math> or <math>O(n^2)</math> without special handling of  iterative combinator
|best-time={{plainlist|
* <math>O(n)</math>
}}
|average-time=<math>O(n)</math>
|space=<math>O(n)</math>
}}

The '''Packrat parser''' is a type of [[Parsing|parser]] that shares similarities with the [[recursive descent parser]] in its construction. However, it differs because it takes [[parsing expression grammar|parsing expression grammars (PEGs)]] as input rather than [[LL grammar|LL grammars]].<ref name=":3">{{Cite arXiv |last=Ford |first=Bryan |date=2006 |title=Packrat Parsing: Simple, Powerful, Lazy, Linear Time |eprint=cs/0603077 }}</ref>

In 1970, Alexander Birman laid the groundwork for packrat parsing by introducing the "TMG recognition scheme" (TS), and "generalized TS" (gTS).  TS was based upon Robert M. McClure's [[TMG (language)|TMG]] compiler-compiler, and gTS was based upon Dewey Val Schorre's [[META II|META]] compiler-compiler.
Birman's work was later refined by Aho and Ullman; and renamed as Top-Down Parsing Language (TDPL), and Generalized TDPL (GTDPL), respectively.  These algorithms were the first of their kind to employ deterministic top-down parsing with backtracking.<ref name=":1">{{Cite book |last=Ford |first=Bryan |title=Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages |chapter=Parsing expression grammars |date=2004-01-01 |chapter-url=https://doi.org/10.1145/964001.964011 |series=POPL '04 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=111–122 |doi=10.1145/964001.964011 |isbn=978-1-58113-729-3|s2cid=7762102 }}</ref><ref name=":0">{{Cite web |last=Flodin |first=Daniel |title=A Comparison Between Packrat Parsing and Conventional Shift-Reduce Parsing on Real-World Grammars and Inputs |url=http://uu.diva-portal.org/smash/get/diva2:752340/FULLTEXT01.pdf }}</ref> 

Bryan Ford developed PEGs as an expansion of GTDPL and TS. Unlike [[Context-free grammar|CFGs]], PEGs are unambiguous and can match well with machine-oriented languages. PEGs, similar to GTDPL and TS, can also express all [[LL parser|LL(k)]] and [[LR parser|LR(k)]]. Bryan also introduced Packrat as a parser that uses [[memoization]] techniques on top of a simple PEG parser. This was done because PEGs have an unlimited [[Parsing#Lookahead|lookahead]] capability resulting in a parser with [[exponential time]] performance in the worst case.<ref name=":1" /><ref name=":0" />

Packrat keeps track of the intermediate results for all mutually recursive parsing functions. Each parsing function is only called once at a specific input position. In some instances of packrat implementation, if there is insufficient memory, certain parsing functions may need to be called multiple times at the same input position, causing the parser to take longer than linear time.<ref>{{Cite book |last1=Mizushima |first1=Kota |last2=Maeda |first2=Atusi |last3=Yamaguchi |first3=Yoshinori |title=Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering |chapter=Packrat parsers can handle practical grammars in mostly constant space |date=2010-05-06 |url=https://dl.acm.org/doi/10.1145/1806672.1806679 |language=en |publisher=ACM |pages=29–36 |doi=10.1145/1806672.1806679 |isbn=978-1-4503-0082-7|s2cid=14498865 }}</ref>