Re: Good explanation of Recursive Ascent Parsing wanted

From	Kaz Kylheku <864-117-4973@kylheku.com>
Newsgroups	comp.compilers
Subject	Re: Good explanation of Recursive Ascent Parsing wanted
Date	2022-09-29 17:49 +0000
Organization	A noiseless patient Spider
Message-ID	<22-09-019@comp.compilers> (permalink)
References	<22-09-018@comp.compilers>

Show all headers | View raw

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]

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Good explanation of Recursive Ascent Parsing wanted Aaron Gray <aaronngray@gmail.com> - 2022-09-28 20:26 -0700
  Re: Good explanation of Recursive Ascent Parsing wanted Kaz Kylheku <864-117-4973@kylheku.com> - 2022-09-29 17:49 +0000
    Re: Good explanation of Recursive Ascent Parsing wanted Aaron Gray <aaronngray@gmail.com> - 2022-09-29 11:55 -0700
      Re: Good explanation of Recursive Ascent Parsing wanted Kaz Kylheku <864-117-4973@kylheku.com> - 2022-09-29 22:32 +0000
  Re: Good explanation of Recursive Ascent Parsing wanted anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-09-30 08:05 +0000
    Re: Good explanation of Recursive Ascent Parsing wanted antispam@math.uni.wroc.pl - 2022-10-06 15:30 +0000
      Re: Good explanation of Recursive Ascent Parsing wanted Kaz Kylheku <864-117-4973@kylheku.com> - 2022-10-07 18:57 +0000
  Re: Good explanation of Recursive Ascent Parsing wanted Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2022-09-30 10:45 +0000

csiph-web