Re: Good explanation of Recursive Ascent Parsing wanted

From	Aaron Gray <aaronngray@gmail.com>
Newsgroups	comp.compilers
Subject	Re: Good explanation of Recursive Ascent Parsing wanted
Date	2022-09-29 11:55 -0700
Organization	Compilers Central
Message-ID	<22-09-020@comp.compilers> (permalink)
References	<22-09-018@comp.compilers> <22-09-019@comp.compilers>

Show all headers | View raw

On Thursday, 29 September 2022 at 19:04:47 UTC+1, Kaz Kylheku wrote:
> On 2022-09-29, Aaron Gray <> 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]

Hi John, I am working on a modern (initially C++) Source to Source
Compiler Compiler that supports all parsing algorithms. I already have
a LEX and YACC like tools LG and PG, that are tools which are library
based.

I did not find the WikiPedia code very enightening. What I did find
was an obvious explanation, follow the item closure spaces !

What I am actually doing is working on marrying Recursive Descent with
backtracking with Recursive Ascent for the LR expression bits. Rather
than using an operator grammar for them, well that as well, but yes.

> 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.

Kaz, Oh this sounds potentially very efficient, thank you, I will have
a serious play and see if I can get this to work !

> 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.

Many thanks !

Aaron

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