Editing LR parser (section)

=== LR parse steps for example A * 2 + 1 ===

In LR parsers, the shift and reduce decisions are potentially based on the entire stack of everything that has been previously parsed, not just on a single, topmost stack symbol. If done in an unclever way, that could lead to very slow parsers that get slower and slower for longer inputs. LR parsers do this with constant speed, by summarizing all the relevant left context information into a single number called the LR(0) '''parser state'''. For each grammar and LR analysis method, there is a fixed (finite) number of such states. Besides holding the already-parsed symbols, the parse stack also remembers the state numbers reached by everything up to those points.

At every parse step, the entire input text is divided into a stack of previously parsed phrases, a current look-ahead symbol, and the remaining unscanned text.  The parser's next action is determined by its current LR(0) {{color|#928|state number}} (rightmost on the stack) and the lookahead symbol. In the steps below, all the black details are exactly the same as in other non-LR shift-reduce parsers. LR parser stacks add the state information in purple, summarizing the black phrases to their left on the stack and what syntax possibilities to expect next.  Users of an LR parser can usually ignore state information.  These states are explained in a later section.

{| class="wikitable"
|-
! <small>{{br}}Step</small> !! <small>Parse Stack{{br}}<sub>{{color|#928|state}}</sub> [Symbol<sub>{{color|#928|state}}</sub>]* </small> !! <small>Look{{br}}Ahead</small> !! <small>{{br}}Unscanned</small> !! <small>Parser{{br}}Action</small> !! <small>{{br}}Grammar Rule</small>|| <small>Next{{br}}State</small>
|-
|align="center"| 0 || <sub>{{color|#928|0}}</sub>
|| ''id'' || align="right" | * 2 + 1 || shift ||  ||align="center"| {{color|#928|9}}
|-
|align="center"| 1 || <sub>{{color|#928|0}}</sub> ''id''<sub>{{color|#928|9}}</sub> 
|| *  ||  align="right" | 2 + 1 || reduce || Value → ''id'' ||align="center"| {{color|#928|7}}
|-
|align="center"| 2 || <sub>{{color|#928|0}}</sub> Value<sub>{{color|#928|7}}</sub>
|| * ||  align="right" | 2 + 1 || reduce || Products → Value ||align="center"| {{color|#928|4}}
|-
|align="center"| 3 || <sub>{{color|#928|0}}</sub> Products<sub>{{color|#928|4}}</sub>
|| * ||  align="right" | 2 + 1 || shift || ||align="center"| {{color|#928|5}}
|-
|align="center"| 4 || <sub>{{color|#928|0}}</sub> Products<sub>{{color|#928|4}}</sub> *<sub>{{color|#928|5}}</sub> 
|| ''int'' ||  align="right" | + 1 || shift ||  ||align="center"| {{color|#928|8}}
|-
|align="center"| 5 || <sub>{{color|#928|0}}</sub> Products<sub>{{color|#928|4}}</sub> *<sub>{{color|#928|5}}</sub> ''int''<sub>{{color|#928|8}}</sub> 
|| + ||  align="right" | 1 || reduce || Value → ''int'' ||align="center"| {{color|#928|6}}
|-
|align="center"| 6 || <sub>{{color|#928|0}}</sub> Products<sub>{{color|#928|4}}</sub> *<sub>{{color|#928|5}}</sub> Value<sub>{{color|#928|6}}</sub>
|| + ||  align="right" | 1 || reduce || Products → Products * Value ||align="center"| {{color|#928|4}}
|-
|align="center"| 7 || <sub>{{color|#928|0}}</sub> Products<sub>{{color|#928|4}}</sub> 
|| + || align="right" | 1 || reduce || Sums → Products ||align="center"| {{color|#928|1}}
|-
|align="center"| 8 || <sub>{{color|#928|0}}</sub> Sums<sub>{{color|#928|1}}</sub> 
|| + || align="right" | 1 || shift ||  ||align="center"| {{color|#928|2}}
|-
|align="center"| 9 || <sub>{{color|#928|0}}</sub> Sums<sub>{{color|#928|1}}</sub> +<sub>{{color|#928|2}}</sub>  
|| ''int'' || align="right" | ''eof'' || shift ||  ||align="center"| {{color|#928|8}}
|- 
|align="center"| 10 || <sub>{{color|#928|0}}</sub> Sums<sub>{{color|#928|1}}</sub> +<sub>{{color|#928|2}}</sub> ''int''<sub>{{color|#928|8}}</sub>
|| ''eof'' ||  || reduce || Value → ''int'' ||align="center"| {{color|#928|7}}
|-
|align="center"| 11 || <sub>{{color|#928|0}}</sub> Sums<sub>{{color|#928|1}}</sub> +<sub>{{color|#928|2}}</sub> Value<sub>{{color|#928|7}}</sub> 
|| ''eof'' ||  || reduce || Products → Value ||align="center"| {{color|#928|3}}
|-
|align="center"| 12 || <sub>{{color|#928|0}}</sub> Sums<sub>{{color|#928|1}}</sub> +<sub>{{color|#928|2}}</sub> Products<sub>{{color|#928|3}}</sub>
|| ''eof'' ||  || reduce || Sums → Sums + Products ||align="center"| {{color|#928|1}}
|-
|align="center"| 13 || <sub>{{color|#928|0}}</sub> Sums<sub>{{color|#928|1}}</sub> 
|| ''eof'' ||  || accept ||  || 
|-
|}

At initial step 0, the input stream "A * 2 + 1" is divided into
* an empty section on the parse stack,
* lookahead text "A" scanned as an ''id'' symbol, and
* the remaining unscanned text "* 2 + 1".
The parse stack begins by holding only initial state 0.  When state 0 sees the lookahead ''id'', it knows to shift that ''id'' onto the stack, and scan the next input symbol '''*''', and advance to state 9.

{{rule}}

At step 4, the total input stream "A * 2 + 1" is currently divided into 
* the parsed section "A&nbsp;*" with 2 stacked phrases Products and '''*''',
* lookahead text "2" scanned as an ''int'' symbol, and
* the remaining unscanned text " + 1".
The states corresponding to the stacked phrases are 0, 4, and 5.  The current, rightmost state on the stack is state 5.  When state 5 sees the lookahead ''int'', it knows to shift that ''int'' onto the stack as its own phrase, and scan the next input symbol '''+''', and advance to state 8.

{{rule}}

At step 12, all of the input stream has been consumed but only partially organized.  The current state is 3.  When state 3 sees the lookahead ''eof'', it knows to apply the completed grammar rule
:: Sums → Sums + Products
by combining the stack's rightmost three phrases for Sums, '''+''', and Products into one thing.  State 3 itself doesn't know what the next state should be.  This is found by going back to state 0, just to the left of the phrase being reduced.  When state 0 sees this new completed instance of a Sums, it advances to state 1 (again).  This consulting of older states is why they are kept on the stack, instead of keeping only the current state.