Editing LR parser (section)

=== Finite state machine ===

The parse table describes all possible LR(0) states and their transitions.  They form a [[finite-state machine]] (FSM).  An FSM is a simple engine for parsing simple unnested languages, without using a stack.  In this LR application, the FSM's modified "input language" has both terminal and nonterminal symbols, and covers any partially parsed stack snapshot of the full LR parse.

Recall step 5 of the Parse Steps Example:

{| 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>
|-
| 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 
|-
|}

The parse stack shows a series of state transitions, from the start state 0, to state 4 and then on to 5 and current state 8.  The symbols on the parse stack are the shift or goto symbols for those transitions.  Another way to view this, is that the finite state machine can scan the stream "Products&nbsp;*&nbsp;''int''&nbsp;+&nbsp;1" (without using yet another stack) and find the leftmost complete phrase that should be reduced next.  And that is indeed its job!

How can a mere FSM do this when the original unparsed language has nesting and recursion and definitely requires an analyzer with a stack?  The trick is that everything to the left of the stack top has already been fully reduced.  This eliminates all the loops and nesting from those phrases.  The FSM can ignore all the older beginnings of phrases, and track just the newest phrases that might be completed next.  The obscure name for this in LR theory is "viable prefix".