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 22:32:10 -0000 (UTC) Organization: A noiseless patient Spider Lines: 40 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <22-09-021@comp.compilers> References: <22-09-018@comp.compilers> <22-09-019@comp.compilers> <22-09-020@comp.compilers> Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="70197"; mail-complaints-to="abuse@iecc.com" Keywords: parse, yacc Posted-Date: 29 Sep 2022 20:25:33 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:3173 On 2022-09-29, Aaron Gray wrote: > Kaz, Oh this sounds potentially very efficient, thank you, I will have > a serious play and see if I can get this to work ! If you look at how Yacc programs typically work: they use goto anyway. The reason I say this is that the parser actions all get compiled into one big yyparse() function, right into its body, and end up as targets of the labels of a switch() statement, or possibly gotos. It's just that the gotos are computed, with the help of the parser tables. So basically what you're doing is eliminating the computed goto; instead of changing some state variable and returning to the top of a loop to switch on it, you just jump to the destination directly. I think there are still situations where a computed goto is inevitable. The LALR parser is a push-down automaton: where the LR(0) items form the basic state transitions for recognizing the regular language of the senential patterns. This is augmented by the stack to handle the recursion in the grammar. When reductions occur and the stack is popped, it is not statically known which state the machine will end up in; so there cannot tbe a hard coded goto or tail call. This is because the same phrase structure, e,g, "expression" can occur in multiple contexts. So here, the goto-based or tail-recursion-based implementation still requires a computed goto. Thus in C a switch statement would be used, or the GNU C computed labels; or else if tail calls are used, then perhaps function pointers could be pushed into the stack. I'm not looking at this at the required level of detail, but my intuition for the problem space affords me a modicum of assurance. :) -- TXR Programming Language: http://nongnu.org/txr Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal