Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #3173

Re: Good explanation of Recursive Ascent Parsing wanted

Show all headers | View raw

On 2022-09-29, Aaron Gray <aaronngray@gmail.com> 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

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