Shift

The Shift action happens when the parser is partway through a grammar construct and a new token is read in. As an example, state 4 in the sample parser is diagrammed with:

expr:     expr.'+' expr
expr:     expr.'-' expr
expr:     expr.'*' expr
expr:     expr.'/' expr
expr:     '(' expr.')'

'+'   shift 8
'-'   shift 7
'*'   shift 6
'/'   shift 5
')'   shift 9
 .    error

This shows that the parser shifts to various other states depending on the value of the lookahead symbol. For example, if the lookahead symbol is "*"—the parser shifts to state 6, which has the diagram:

expr:     expr '*'.expr

NUM   shift 2
'('   shift 1
 .    error

expr  goto 11

In this new state, the parser has further shifts it can make, depending on the next lookahead symbol.

When the parser shifts to a new state, it saves the previous state on a stack called the state stack. The stack provides a history of the states that the parser has passed through while it was reading input. It is also a control mechanism, as described in yacc output.

Paralleling the state stack is a value stack, which records the values of tokens and nonterminal symbols encountered while parsing. The value of a token is the yylval value returned by yylex() at the time the token was read. The value of a nonterminal symbol is the $$ value set by the recognition action associated with that symbol's definition. If the definition did not have an associate recognition action, the value of the symbol is the value of the first item in the symbol's definition.

At the same time that the Shift action pushes the current state onto the state stack, it also pushes the yylval value of the lookahead symbol (token) onto the value stack.