title: Why does a yacc-generated state machine state not include a valid next token?
body: <p>I'm using PLY (Python Lex/Yacc) for a parser.  I'm getting the following output:</p>
  
  <pre><code>State  : 52
  Stack  : &lt;shortened preamble&gt; primary_expr ARROW simple_name LPAREN ID COLON . LexToken(INTEGER,'Integer',13,362)
  Action : Shift and goto state 116
  
  State  : 116
  Stack  : &lt;shortened preamble&gt; primary_expr ARROW simple_name LPAREN ID COLON INTEGER . LexToken(BAR,'|',13,370)
  ERROR: Error  : &lt;shortened preamble&gt; primary_expr ARROW simple_name LPAREN ID COLON INTEGER . LexToken(BAR,'|',13,370)
  </code></pre>
  
  <p>You can see that in state 52, it shifted the <code>INTEGER</code> token, and went to state 116.  The state machine output file for state 116 has this:</p>
  
  <pre><code>state 116
  
    (56) simple_type -&gt; INTEGER .
  
    RBRACKET        reduce using rule 56 (simple_type -&gt; INTEGER .)
    EQ              reduce using rule 56 (simple_type -&gt; INTEGER .)
    SEMI            reduce using rule 56 (simple_type -&gt; INTEGER .)
  </code></pre>
  
  <p>This seems to be a state just to reduce <code>INTEGER</code> to <code>simple_type</code>.  Yet the <code>BAR</code> token (which appears next in the input) is not listed here.</p>
  
  <p>The rule I <em>expect</em> to be matched is:</p>
  
  <pre><code>iterator_expr : primary_expr ARROW simple_name LPAREN uninitialized_variable BAR other_expr RPAREN
  </code></pre>
  
  <p>These other rules provide the reduction of the last three tokens to match the rule.</p>
  
  <pre><code>simple_type : INTEGER
  type_specifier : simple_type
  declarator : ID COLON type_specifier
  uninitialized_variable : declarator
  </code></pre>
  
  <p><em>So</em>, it looks to me like the state machine is all set to go into state 116, reduce <code>INTEGER</code> to <code>simple_type</code>, <code>simple_type</code> to <code>type_specifier</code>, <code>ID COLON type_specifier</code> to <code>declarator</code>, <code>declarator</code> to <code>uninitialized_variable</code>, and continue happily with <code>BAR</code> from there.  However, it seems to be going to a state with only shift actions and complaining about the next shift.  There are no shift/reduce or reduce/reduce conflicts about any of the rules mentioned.</p>
  
  <p>Why would it <em>need</em> to consider <code>BAR</code> next, and why didn't it list it as a possibility in the state machine?</p>
  
  <p>EDIT 4/20/18:<br>
  I changed the rule I expect to be matched to:</p>
  
  <pre><code>iterator_expr : primary_expr ARROW simple_name LPAREN declarator BAR other_expr RPAREN
  </code></pre>
  
  <p>(i.e., changed <code>uninitialized_variable</code> to <code>declarator</code>), and <code>BAR</code> now appears as a next token in state 116.  The parser now chooses to reducue <code>simple_type -&gt; INTEGER</code> rather than shift <code>BAR</code>, and matches fine.  I wonder if there's something about having to match a non-terminals (<code>unintialized_variable</code>), then matching some terminals (ID, COLON) and some non-terminals that somehow thwarts detection of valid next tokens.</p>
  
  <p>I realized no one can debug this without the full grammar (which is unfortunately proprietary).  But I'm interested to understand what principles of yacc might be involved, and also looking to document good debugging techniques for these weird issues.  I'm actually encountering this issue for other rules that include an <code>expression</code> non-terminal inside of other rules--things like '+' show up as invalid next token, when clearly the <code>expression</code> non-terminal should cover it.  How <em>does</em> the list of next valid tokens get created, and what would prevent one so clearly listed in a rule from showing up? </p>