Re: Bison -v Stack Interpretation

[James K. Lowden]

On Thu, 21 Dec 2023 18:42:05 -0500
Steve Litt <slitt@troubleshooters.com> wrote:

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

Depending on how high is high, sure.  :-)  

See "5.5 Parser States" in the Bison manual.  As yourself if you
understand that.

A generic stack has push and pop operations, yes.  But Bison uses
different terminology because there's more going on.  The terms "shift"
and "reduce" are state-machine operations.  The affect the stack, but
they are not the stack operations. 

When a token is pushed onto the stack, the parser's state changes at
the same time; the term "shift" captures both effects.  Similarly, when
the parser recogonizes that a token sequence matches a rule, the
matching elements are indeed popped off.  Then the action is executed,
and a new element, not a token, is pushed on the stack, representing a
new state. The whole kaboodle is called "reduction".  

To really understand it requires study.  The original paper

        Yacc: Yet Another Compiler-Compiler
        Stephen C. Johnson

is worth reading, even if parts of it are hard to follow the first time
through.  It introduced yacc to the world as new technology.  It
explains these terms to an audience most of whom had never seen
anything like it.  

As you may know, yacc and Bison implement a small part of a body of
work in computer science, usually taught as a semester-long course. If
you want to know not just how Bison works, but how to write one
yourself, I recommend

        Engineering a Compiler
        Keith D. Cooper and Linda Torczon
        ISBN 978-0-12-088478-0

--jkl