Recursive ascent parser: Difference between revisions

Revision as of 11:18, 14 October 2009

Revision as of 10:52, 27 September 2010

Line 3:

Recursive ascent was first described by Thomas Penello in his article {{cite web|title=Very fast LR parsing|url=http://portal.acm.org/citation.cfm?id=13310.13326}} 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 web|title=Recursive ascent: an LR analog to recursive descent|year=1988|author=G.H. Roberts|url=http://portal.acm.org/citation.cfm?id=47907.47909}}</ref> in 1988 as well as in an article by Leermakers, Augusteijn, Kruseman Aretz<ref>{{cite web|title=A functional LR parser|author=Leermakers, Augusteijn, Kruseman Aretz|year=1992|url=http://portal.acm.org/citation.cfm?id=146986.146994}}</ref> in 1992 in the journal ''Theoretical Computer Science''. An extremely readable description of the technique was written by Morell and Middleton<ref>{{cite web|title=Recursive-ascent parsing|author=Larry Morell and David Middleton|year=2003|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 web|title=Generation of LR parsers by partial evaluation|author=Sperber and Thiemann|year=2000|url=http://portal.acm.org/citation.cfm?id=349219&dl=GUIDE&coll=GUIDE&CFID=56087236&CFTOKEN=74111863}}</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|author=John Boyland and Daniel Spiewak|year=2009|url=http://www.cs.uwm.edu/~boyland/papers/scala-bison.pdf}}</ref>.

Recursive Ascent-Descent Parser Generator|author=John Boyland and Daniel Spiewak|year=2009|url=http://www.cs.uwm.edu/~boyland/papers/scala-bison.pdf}}</ref>.

== Summary ==