Re: Bison -v Stack Interpretation

[Steve Litt]

Thanks Piotr!

The https://www.gnu.org/software/bison/manual/html_node/Algorithm.html
you recommended *seems* very clear to me, but I want to ask you if I
really understand it. So from your recommended link, I deduce the
following:

1) The parser stack truly is a Last In First Out (LIFO) stack like we
   learned about in programming 101, where adding an element to the
   stack is called "pushing" and taking an element off the stack is
   called "popping", with the last element pushed being the first
   element popped. But in this case we use different vocabulary.

2) Pushing an element is called "shifting" in this context. "Push" and
   "shift" are pretty much synonyms.

3) Regardless of how the "reducing" process is really done
   algorithmically,  reducing the parser stack acts like the following
   set of operations:
      a: One by one, pop every element off the stack in order to make a
         rule.
      b: Calculate the "value" of the rule, considering various
         elements' (tokens') semantic values.
      c: Push (shift) the result back onto the stack.

If the preceding attempt at an explanation accurately describes the
meaning of the words "parser stack", "shift" and "reduce", then I
understand completely and it makes perfect sense. When I need a
calculator, I run the command line Reverse Polish Notation calculator
called dc, and dc operates pretty much exactly like the description I
gave above. 

So, on a high level, do I now have a good understanding of the
definitions of "parser stack", "shift" and "reduce"?

Thanks so much for your help.

SteveT

Steve Litt 

Autumn 2023 featured book: Rapid Learning for the 21st Century
http://www.troubleshooters.com/rl21


Piotr Siupa said on Thu, 21 Dec 2023 08:36:03 +0100

>The manual has a nice explanation of those concepts:
>https://www.gnu.org/software/bison/manual/html_node/Algorithm.html
>
>Regards,
>Piotr
>
>
>On Thu, Dec 21, 2023 at 6:51 AM Steve Litt <slitt@troubleshooters.com>
>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
>>
>>