This section (took from the manual of Bison 1.49) describes how to use
the verbose report printed by wisent-compile-grammar to
understand the generated automaton, to tune or fix a grammar.
We will use the following example:
(let ((wisent-verbose-flag t)) ;; Print a verbose report!
(wisent-compile-grammar
'((NUM STR) ; %token NUM STR
((left ?+ ?-) ; %left '+' '-';
(left ?*)) ; %left '*'
(exp ; exp:
((exp ?+ exp)) ; exp '+' exp
((exp ?- exp)) ; | exp '-' exp
((exp ?* exp)) ; | exp '*' exp
((exp ?/ exp)) ; | exp '/' exp
((NUM)) ; | NUM
) ; ;
(useless ; useless:
((STR)) ; STR
) ; ;
)
'nil) ; no %start declarations
)
When evaluating the above expression, grammar compilation first issues the following two clear messages:
Grammar contains 1 useless nonterminals and 1 useless rules Grammar contains 7 shift/reduce conflicts
The *wisent-log* buffer details things!
The first section reports conflicts that were solved using precedence and/or associativity:
Conflict in state 7 between rule 1 and token '+' resolved as reduce. Conflict in state 7 between rule 1 and token '-' resolved as reduce. Conflict in state 7 between rule 1 and token '*' resolved as shift. Conflict in state 8 between rule 2 and token '+' resolved as reduce. Conflict in state 8 between rule 2 and token '-' resolved as reduce. Conflict in state 8 between rule 2 and token '*' resolved as shift. Conflict in state 9 between rule 3 and token '+' resolved as reduce. Conflict in state 9 between rule 3 and token '-' resolved as reduce. Conflict in state 9 between rule 3 and token '*' resolved as reduce.
The next section reports useless tokens, nonterminal and rules (note that useless tokens might be used by the scanner):
Useless nonterminals: useless Terminals which are not used: STR Useless rules: #6 useless: STR;
The next section lists states that still have conflicts:
State 7 contains 1 shift/reduce conflict. State 8 contains 1 shift/reduce conflict. State 9 contains 1 shift/reduce conflict. State 10 contains 4 shift/reduce conflicts.
The next section reproduces the grammar used:
Grammar Number, Rule 1 exp -> exp '+' exp 2 exp -> exp '-' exp 3 exp -> exp '*' exp 4 exp -> exp '/' exp 5 exp -> NUM
And reports the uses of the symbols:
Terminals, with rules where they appear
$EOI (-1)
error (1)
NUM (2) 5
STR (3) 6
'+' (4) 1
'-' (5) 2
'*' (6) 3
'/' (7) 4
Nonterminals, with rules where they appear
exp (8)
on left: 1 2 3 4 5, on right: 1 2 3 4
The report then details the automaton itself, describing each state with it set of items, also known as pointed rules. Each item is a production rule together with a point (marked by ‘.’) that the input cursor.
state 0
NUM shift, and go to state 1
exp go to state 2
State 0 corresponds to being at the very beginning of the parsing, in the initial rule, right before the start symbol (‘exp’). When the parser returns to this state right after having reduced a rule that produced an ‘exp’, it jumps to state 2. If there is no such transition on a nonterminal symbol, and the lookahead is a ‘NUM’, then this token is shifted on the parse stack, and the control flow jumps to state 1. Any other lookahead triggers a parse error.
In the state 1...
state 1
exp -> NUM . (rule 5)
$default reduce using rule 5 (exp)
the rule 5, ‘exp: NUM;’, is completed. Whatever the lookahead (‘$default’), the parser will reduce it. If it was coming from state 0, then, after this reduction it will return to state 0, and will jump to state 2 (‘exp: go to state 2’).
state 2
exp -> exp . '+' exp (rule 1)
exp -> exp . '-' exp (rule 2)
exp -> exp . '*' exp (rule 3)
exp -> exp . '/' exp (rule 4)
$EOI shift, and go to state 11
'+' shift, and go to state 3
'-' shift, and go to state 4
'*' shift, and go to state 5
'/' shift, and go to state 6
In state 2, the automaton can only shift a symbol. For instance, because of the item ‘exp -> exp . '+' exp’, if the lookahead if ‘+’, it will be shifted on the parse stack, and the automaton control will jump to state 3, corresponding to the item ‘exp -> exp . '+' exp’:
state 3
exp -> exp '+' . exp (rule 1)
NUM shift, and go to state 1
exp go to state 7
Since there is no default action, any other token than those listed above will trigger a parse error.
The interpretation of states 4 to 6 is straightforward:
state 4
exp -> exp '-' . exp (rule 2)
NUM shift, and go to state 1
exp go to state 8
state 5
exp -> exp '*' . exp (rule 3)
NUM shift, and go to state 1
exp go to state 9
state 6
exp -> exp '/' . exp (rule 4)
NUM shift, and go to state 1
exp go to state 10
As was announced in beginning of the report, ‘State 7 contains 1 shift/reduce conflict.’:
state 7
exp -> exp . '+' exp (rule 1)
exp -> exp '+' exp . (rule 1)
exp -> exp . '-' exp (rule 2)
exp -> exp . '*' exp (rule 3)
exp -> exp . '/' exp (rule 4)
'*' shift, and go to state 5
'/' shift, and go to state 6
'/' [reduce using rule 1 (exp)]
$default reduce using rule 1 (exp)
Indeed, there are two actions associated to the lookahead ‘/’: either shifting (and going to state 6), or reducing rule 1. The conflict means that either the grammar is ambiguous, or the parser lacks information to make the right decision. Indeed the grammar is ambiguous, as, since we did not specify the precedence of ‘/’, the sentence ‘NUM + NUM / NUM’ can be parsed as ‘NUM + (NUM / NUM)’, which corresponds to shifting ‘/’, or as ‘(NUM + NUM) / NUM’, which corresponds to reducing rule 1.
Because in LALR(1) parsing a single decision can be made, Wisent arbitrarily chose to disable the reduction, see Conflicts. Discarded actions are reported in between square brackets.
Note that all the previous states had a single possible action: either shifting the next token and going to the corresponding state, or reducing a single rule. In the other cases, i.e., when shifting and reducing is possible or when several reductions are possible, the lookahead is required to select the action. State 7 is one such state: if the lookahead is ‘*’ or ‘/’ then the action is shifting, otherwise the action is reducing rule 1. In other words, the first two items, corresponding to rule 1, are not eligible when the lookahead is ‘*’, since we specified that ‘*’ has higher precedence that ‘+’. More generally, some items are eligible only with some set of possible lookaheads.
States 8 to 10 are similar:
state 8
exp -> exp . '+' exp (rule 1)
exp -> exp . '-' exp (rule 2)
exp -> exp '-' exp . (rule 2)
exp -> exp . '*' exp (rule 3)
exp -> exp . '/' exp (rule 4)
'*' shift, and go to state 5
'/' shift, and go to state 6
'/' [reduce using rule 2 (exp)]
$default reduce using rule 2 (exp)
state 9
exp -> exp . '+' exp (rule 1)
exp -> exp . '-' exp (rule 2)
exp -> exp . '*' exp (rule 3)
exp -> exp '*' exp . (rule 3)
exp -> exp . '/' exp (rule 4)
'/' shift, and go to state 6
'/' [reduce using rule 3 (exp)]
$default reduce using rule 3 (exp)
state 10
exp -> exp . '+' exp (rule 1)
exp -> exp . '-' exp (rule 2)
exp -> exp . '*' exp (rule 3)
exp -> exp . '/' exp (rule 4)
exp -> exp '/' exp . (rule 4)
'+' shift, and go to state 3
'-' shift, and go to state 4
'*' shift, and go to state 5
'/' shift, and go to state 6
'+' [reduce using rule 4 (exp)]
'-' [reduce using rule 4 (exp)]
'*' [reduce using rule 4 (exp)]
'/' [reduce using rule 4 (exp)]
$default reduce using rule 4 (exp)
Observe that state 10 contains conflicts due to the lack of precedence of ‘/’ wrt ‘+’, ‘-’, and ‘*’, but also because the associativity of ‘/’ is not specified.
Finally, the state 11 (plus 12) is named the final state, or the accepting state:
state 11
$EOI shift, and go to state 12
state 12
$default accept
The end of input is shifted ‘$EOI shift,’ and the parser exits successfully (‘go to state 12’, that terminates).