Re: Bison -v Stack Interpretation
On Thu, 21 Dec 2023 18:42:05 -0500 Steve Litt 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
Re: Bison -v Stack Interpretation
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 >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 >> >>
Re: Bison -v Stack Interpretation
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
Re: Bison -v Stack Interpretation
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 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 > >
Re: Bison -v Stack Interpretation
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
Re: Bison -v Stack Interpretation
On Wed, 20 Dec 2023 19:58:26 +0100 Dan Ohlsson wrote: > I have difficulties understanding the stack content when executing > bison with the -v options. Please explain or give reference to where > I can find information! That's a really big question, Dan. Do you want to come to Brussels in February to hear my FOSDEM talk? Perhaps the best information is in 8.5.2 Enabling Debug Traces for ?mfcalc? In the Bison info manual. To understand it, you have to understand how the LALR parser works. If you're like me, that takes awhile to internalize. 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. Reducing stack by rule 6 (line 44): "Rule 6" is among the rules enumerated in the output file if you used verbose mode. Line 44 refers to you parse.y file, or whatever was input to Bison. Each element in the rule to the right of the colon is a terminal or nonterminal, and has a value. But of course you know that. What can be mysterious is when Bison reports a syntax error. As a technical matter, it means that the last token retrieved from yylex matches no rule in the current state. That is, if in State X there is no acceptable token T, then T is in error. (Of course, you can get to X by mistake too. There is an infinite combination of shoelaces and knots.) To understand what state X is when T arrives, you also have to consult the report file produced in verbose mode. My last bit advice is this: turn on yy_flex_debug, too (assuming you're using flex). Quite often, the T returned by yylex is not the one you would have hoped for, given the input text, perhaps because the list of strings it digests has fallen behind what the parser demands. HTH. --jkl
