Basic parsing
Below is an example parser operation scenario including shift and reduce operations.
Following grammar will be used:
@2 NT: b c;
Here is an automaton for above grammar. For each state list of actions is shown:
$accept: . STMT
actions
a shift to #3
STMT goto #2
state #2
$accept: STMT .
actions
$end reduce by @3 to $accept
state #3
STMT: a . NT d
actions
b shift to #5
NT goto #4
state #4
STMT: a NT . d
actions
d shift to #7
state #5
NT: b . c
actions
c shift to #6
state #6
NT: b c .
actions
d reduce by @2 to NT
state #7
STMT: a NT d .
actions
$end reduce by @1 to STMT
A schematic representation of automaton activity with regard to the grammar is shown on Fig. 12.
Automaton graph alone is not sufficient to understand parser operation. Stack contents must be also considered. Below is an example of parsing input text using above automaton:
Initial state is #1. Current state is always on top of the stack:
First symbol read is a. Action for symbol a in action table for state #1 is to shift and go to state #3.
Next input symbol is b. Action for symbol b in state #3 is to shift symbol to stack and go to state #5.
Next symbol is c. Action for symbol c is to shift symbol to stack and go to state #6.
There is only one action in state #6: to reduce by production @2 to nonterminal NT providing next input symbol is d. Since next symbol indeed is d parser performs reduction.
During reduction, top of stack elements matching the production are removed.
Automaton transitions and stack operation are synchronized. When reduction is performed top-of-stack element configuration is guaranteed to match the production.
After reduction stack becomes:
At this moment information saved on parser stack about previously visited becomes important. Removal of terminals b and c exposed state #3 which is now top-of-stack an thus current. Without stack, parser would not be able to return to this state.
Recent reduction produced nonterminal NT which must be processed. Automaton performs transition under this nonterminal right away. The action in state #3 for NT is push that nonterminal on stack and go to state #4. After that configuration is:
Next input symbol is d. Action for symbol d is to shift it and go to state #7.
In state #7 the action is to reduce by production @1 to nonterminal STMT providing input stream has come to an end. Reduction first removes top of stack elements corresponding to the production:
Action for STMT in state #1 is to go to state #2:
Top level nonterminal of grammar STMT was successfully processed, and input stream reached the end. Parsing ends with success.