Recursive ascent parser: Difference between revisions

Revision as of 23:00, 25 January 2024

Revision as of 12:44, 29 November 2024

Line 1:

In [[computer science]], '''recursive ascent parsing''' is a technique for implementing an [[LR parser]] which uses mutually-recursive functions rather than tables. Thus, the parser is ''directly encoded'' in the host language similar to [[recursive descent]]. Direct encoding usually yields a parser which is faster than its table-driven equivalent<ref>{{cite journal|title=Very fast LR parsing|author=Thomas J Penello|journal=ACM SIGPLAN Notices |year=1986|volume=21 |issue=7 |pages=145–151 |doi=10.1145/13310.13326 |url=http://portal.acm.org/citation.cfm?id=13310.13326|doi-access=free }}</ref> for the same reason that compilation is faster than interpretation. It is also (nominally) possible to hand edit a recursive ascent parser, whereas a tabular implementation is nigh unreadable to the average human.

Recursive ascent was first described by Thomas Pennello in his article {{cite book|chapter=Very fast LR parsing| doi=10.1145/12276.13326 |chapter-url=http://portal.acm.org/citation.cfm?id=13310.13326| title=Proceedings of the 1986 SIGPLAN symposium on Compiler construction - SIGPLAN '86 | year=1986 | last1=Pennello | first1=Thomas J. | pages=145–151 | isbn=0897911970 | s2cid=17214407 }} in 1986. He was not intending to create a hand-editable implementation of an LR parser, but rather a maintainable and efficient parser implemented in [[assembly language]]. The technique was later expounded upon by G.H. Roberts<ref>{{cite journal|title=Recursive ascent: an LR analog to recursive descent|year=1988|author=G.H. Roberts|journal=ACM SIGPLAN Notices |volume=23 |issue=8 |pages=23–29 |doi=10.1145/47907.47909 |s2cid=12740771 |url=http://portal.acm.org/citation.cfm?id=47907.47909|doi-access=free }}</ref> in 1988 as well as in an article by Leermakers, Augusteijn, Kruseman Aretz<ref>{{cite journal|title=A functional LR parser|author=Leermakers, Augusteijn, Kruseman Aretz|journal=Theoretical Computer Science |year=1992|volume=104 |issue=2 |pages=313–323 |doi=10.1016/0304-3975(92)90128-3 |url=http://portal.acm.org/citation.cfm?id=146986.146994|doi-access=free }}</ref> in 1992 in the journal ''Theoretical Computer Science''. An extremely readable description of the technique was written by Morell and Middleton<ref>{{cite news|title=Recursive-ascent parsing|author1=Larry Morell |author2=David Middleton |name-list-style=amp |year=2003|journal=Journal of Computing Sciences in Colleges|volume=18|issue=6|pages=186–201|url=http://portal.acm.org/citation.cfm?id=770849}}</ref> in 2003. A good exposition can also be found in a TOPLAS article by Sperber and Thiemann.<ref>{{cite journal|title=Generation of LR parsers by partial evaluation|author=Sperber and Thiemann|journal=ACM Transactions on Programming Languages and Systems |year=2000|volume=22 |issue=2 |pages=224–264 |doi=10.1145/349214.349219 |s2cid=14955687 |url=http://portal.acm.org/citation.cfm?id=349219&dl=GUIDE&coll=GUIDE&CFID=56087236&CFTOKEN=74111863|doi-access=free }}</ref>

Recursive ascent has also been merged with recursive descent, yielding a technique known as [[recursive ascent/descent]]. This implementation technique is arguably easier to hand-edit due to the reduction in states and fact that some of these states are more intuitively top-down rather than bottom up. It can also yield some minimal performance improvements over conventional recursive ascent.<ref>{{cite web|title=ScalaBison Recursive Ascent-Descent Parser Generator|author1=John Boyland |author2=Daniel Spiewak |name-list-style=amp |year=2009|url=http://www.cs.uwm.edu/~boyland/papers/scala-bison.pdf|archive-url=https://web.archive.org/web/20090718161230/http://www.cs.uwm.edu/~boyland/papers/scala-bison.pdf|archive-date=2009-07-18|url-status=dead}}</ref>