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
