Path: csiph.com!1.us.feeder.erje.net!feeder.erje.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Kaz Kylheku <864-117-4973@kylheku.com> Newsgroups: comp.compilers Subject: Re: Good explanation of Recursive Ascent Parsing wanted Date: Thu, 29 Sep 2022 17:49:06 -0000 (UTC) Organization: A noiseless patient Spider Lines: 45 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <22-09-019@comp.compilers> References: <22-09-018@comp.compilers> Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="77523"; mail-complaints-to="abuse@iecc.com" Keywords: parse, performance, comment Posted-Date: 29 Sep 2022 14:04:44 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:3171 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] 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]