Re: Good explanation of Recursive Ascent Parsing wanted

On 2022-09-29, Aaron Gray <aaronngray@gmail.com> wrote:
> I am after a good explanation of Recursive Ascent Parsing as I wish to
> implement a parser generator to generate recursive ascent C/C++ code
> from an LR1 grammar.
>
> Regards,
>
> Aaron
> [The Wikipedia article isn't bad and has several promising references,
> but I wonder if it's worth the effort. RA parsing does what yacc or
> bison does, but by turning each state into a function. It's supposed
> to be faster than a table driven parser, but LALR parsers are already
> so fast, how much faster will it be? Maybe it'll even be slower since
> there is a lot more code so it's less likely to fit in a CPU cache.
> -John]


John, I suspect the idea is that this is suited for languages that
are compiled well and have good tail call support, to that that
the recursion is stackless.


A table-driven parser is an interpreter for a table. Tables can
be compiled to a goto graph, and a goto graph can be represented
by tail recursion which compiles to goto. This can be faster than the
original table-interpreting loop.


Although, those improvements will succumb to Amdahl's law; you would
best be able to demonstrate the improvement in a program which does
nothing but parse a canned token stream: no lexing is going on and the
reductions do nothing (basically the syntax is being validated and
that's all).


It be useful in applications like, say, validating some syntax that is
arriving as a real-time input.


I'd ping the GNU Bison mailing list to see if they are interested
in the technique. It's doable in C; C compilers have good tail
call support. And in any case, the technique doesn't strictly
require functions: a giant yyparse() can be generated which just
contains a self-contained goto graph.


--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
[You're right but my eyeballs hurt when I think about looking at or
trying to debug the giant goto graph. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.