|
So far, we have avoided ambiguous grammars. But, in practice, it can significantly simplify a grammar by letting it be ambiguous and dealing with the ambiguity by selecting certain actions.
As an example, let's use our ambiguous expression grammar.
| E | → | n |
| E | → | E + E |
| E | → | E * E |
| E | → | ( E ) |
Here is what Bison says about this grammar.
State 9 conflicts: 2 shift/reduce
State 10 conflicts: 2 shift/reduce
Grammar
0 $accept: E $end
1 E: 'n'
2 | E '+' E
3 | E '*' E
4 | '(' E ')'
state 0
0 $accept: . E $end
'n' shift, and go to state 1
'(' shift, and go to state 2
E go to state 3
state 1
1 E: 'n' .
$default reduce using rule 1 (E)
state 2
4 E: '(' . E ')'
'n' shift, and go to state 1
'(' shift, and go to state 2
E go to state 4
state 3
0 $accept: E . $end
2 E: E . '+' E
3 | E . '*' E
$end shift, and go to state 5
'+' shift, and go to state 6
'*' shift, and go to state 7
state 4
2 E: E . '+' E
3 | E . '*' E
4 | '(' E . ')'
'+' shift, and go to state 6
'*' shift, and go to state 7
')' shift, and go to state 8
state 5
0 $accept: E $end .
$default accept
state 6
2 E: E '+' . E
'n' shift, and go to state 1
'(' shift, and go to state 2
E go to state 9
state 7
3 E: E '*' . E
'n' shift, and go to state 1
'(' shift, and go to state 2
E go to state 10
state 8
4 E: '(' E ')' .
$default reduce using rule 4 (E)
state 9
2 E: E . '+' E
2 | E '+' E .
3 | E . '*' E
'+' shift, and go to state 6
'*' shift, and go to state 7
'+' [reduce using rule 2 (E)]
'*' [reduce using rule 2 (E)]
$default reduce using rule 2 (E)
state 10
2 E: E . '+' E
3 | E . '*' E
3 | E '*' E .
'+' shift, and go to state 6
'*' shift, and go to state 7
'+' [reduce using rule 3 (E)]
'*' [reduce using rule 3 (E)]
$default reduce using rule 3 (E)
But what if we just select actions to do where there are conflicts? Bison has already done that, preferring to do a shift whenever it encounters a shift-reduce conflict.
Selecting actions can be dangerous because you might make it impossible to parse some grammatically correct sequences of tokens.
But in cases like our expression grammar, we can choose actions based on precedence and associativity rules.
The idea is to define a precedence and associativity of some tokens, such as binary operators. We also need to select precedence and associativity of some productions, typically those that have binary operators in them.
Suppose that a state has a shift-reduce conflict on lookahead t. The reduce action will be for some production, say production k.
The parser selects either the shift or the reduce action as follows.
If token t has higher precedence than production k, do a shift.
If token t has lower precedence than production k, do the reduce.
If token t and production k have the same precedence, then select the action as follows.
If token t is right-associative, select the shift action.
If token t is left-associative, select the reduce action.
Here is the grammar with those rules installed, as a Bison grammar.
/* Precedence is low to high. */
%left '+'
%left '*'
%%
E : 'n'
| E '+' E %prec '+'
| E '*' E %prec '*'
| '(' E ')'
;
%%
The state machine is identical to the previous case, but actions have been selected according to precedence.
state 0
0 $accept: . E $end
'n' shift, and go to state 1
'(' shift, and go to state 2
E go to state 3
state 1
1 E: 'n' .
$default reduce using rule 1 (E)
state 2
4 E: '(' . E ')'
'n' shift, and go to state 1
'(' shift, and go to state 2
E go to state 4
state 3
0 $accept: E . $end
2 E: E . '+' E
3 | E . '*' E
$end shift, and go to state 5
'+' shift, and go to state 6
'*' shift, and go to state 7
state 4
2 E: E . '+' E
3 | E . '*' E
4 | '(' E . ')'
'+' shift, and go to state 6
'*' shift, and go to state 7
')' shift, and go to state 8
state 5
0 $accept: E $end .
$default accept
state 6
2 E: E '+' . E
'n' shift, and go to state 1
'(' shift, and go to state 2
E go to state 9
state 7
3 E: E '*' . E
'n' shift, and go to state 1
'(' shift, and go to state 2
E go to state 10
state 8
4 E: '(' E ')' .
$default reduce using rule 4 (E)
state 9
2 E: E . '+' E
2 | E '+' E .
3 | E . '*' E
'*' shift, and go to state 7
$default reduce using rule 2 (E)
state 10
2 E: E . '+' E
3 | E . '*' E
3 | E '*' E .
$default reduce using rule 3 (E)
|