Editing Packrat parser (section)

=== Left recursion ===
Left recursion happens when a grammar production refers to itself as its left-most element, either directly or indirectly. Since Packrat is a recursive descent parser, it cannot handle left recursion directly.<ref name=":2">{{Cite book |last1=Warth |first1=Alessandro |last2=Douglass |first2=James R. |last3=Millstein |first3=Todd |title=Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation |chapter=Packrat parsers can support left recursion |date=2008-01-07 |chapter-url=https://doi.org/10.1145/1328408.1328424 |series=PEPM '08 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=103–110 |doi=10.1145/1328408.1328424 |isbn=978-1-59593-977-7|s2cid=2168153 }}</ref> During the early stages of development, it was found that a production that is left-recursive can be transformed into a right-recursive production.<ref>{{Cite book |title=Compilers: principles, techniques, & tools |date=2007 |publisher=Pearson Addison-Wesley |isbn=978-0-321-48681-3 |editor-last=Aho |editor-first=Alfred V. |edition=2nd |location=Boston Munich |editor-last2=Lam |editor-first2=Monica S. |editor-last3=Sethi |editor-first3=Ravi |editor-last4=Ullman |editor-first4=Jeffrey D.}}</ref> This modification significantly simplifies the task of a Packrat parser. Nonetheless, if there is an indirect left recursion involved, the process of rewriting can be quite complex and challenging. If the time complexity requirements are loosened from linear to [[Complexity class|superlinear]], it is possible to modify the memoization table of a Packrat parser to permit left recursion, without altering the input grammar.<ref name=":2" />