Re: Bison -v Stack Interpretation

[lostbits]

shift/reduce/pop/push are part of LALR(1) parsing (see 
https://en.wikipedia.org/wiki/LALR_parser as a start). Basically what 
happens is that the parser forms lookahead sets. The creation and 
sustenance of the lookahead sets is done with the pushes and pops. When 
the LALR(1) parser looks at the grammar, the parser decides to continue 
on without resolving what to do yet (shift) or to conclude that the 
left-hand side of some production rules (lhs : rhs;) is recognized, reduce.

So in summary, the stack is used as a vehicle to store information 
needed to make a reduce decision, the shift causes a push.

If I'm wrong, as often I am, then please correct. But I believe this is 
the essence of a bottom-up parser. FYI there are also top-down (LL(1)) 
parsers, e.g., ANTLR. If you are so inclined you might want to look at 
them also.

art

On 12/20/2023 9:50 PM, Steve Litt wrote:
> James K. Lowden said on Tue, 19 Dec 2023 21:11:41 -0500
>
> > On any given token, the parser either shifts the token onto its stack,
> > or reduces the stack.  To me, all the interesting stuff happens when
> > reducing, because that's literally where the action is.
> I'm puzzled about the words "stack", "shift", and "reduce".
>
> As has always been explained to me, the meaning of the word "stack" is
> that it's a Last In First Out (LIFO) array, object, contraption,
> whatever, and that when you add something it's called "pushing" it onto
> the stack, and when you remove something, the something removed is the
> one that last got pushed, and that's called "popping" it from the stack.
> What exactly is meant by "shift" and "reduce"?
>
> Thanks,
>
> SteveT
>
> Steve Litt
>
> Autumn 2023 featured book: Rapid Learning for the 21st Century
> http://www.troubleshooters.com/rl21