Lecture 9a - 480/580 (compiler construction)

Shift/Reduce Errors  (this material should follow page 1 of lecture 9).

Shift/reduce errors are an important topic in LR parsing, since they occur
so frequently and some are innocuous and some are fatal.
The major differences between types of LR parsers is basically how they
approach trying to deal with shift reduce errors.
In the past, I've spent lecture 9 discussing the various types of LR
parsers (SLR, LR(1), LALR).  I've decided to remove this material for 
two reasons

1) students have always found it tremendously confusing, and hence spend an
inordinate amount of time studying and worrying over it.

2) the issue is a relatively obscure one, really of more importance to
professional compiler writers than to casual users of YACC.  (I guess the
short way of saying this is that this topic isn't on my list of things I
want you to remember five years from now).

Instead, I want to discuss what a shift reduce errors is and how you as a
USER should approach the problem of dealing with shift/reduce errors.

The first tool is handling shift/reduce errors is information.
If you give the -v flag to yacc it will produce a huge file called y.output
which describes the finite state machine that it has built.
This can then be used to reconstruct the source of a shift reduce error.

As our first example, let us consider the obvious way to introduce an
``if-then'' statement as well as an ``if-then-else'' statement.  This would
be to rewrite the grammar as follows:

statement ->
	variable := expression
	id ( argument_list)
	| compound_statement
	| if expression then statement
	| if expression then statement else statement
	| while expression do statement
	| return expression
	| return
	| /* nothing */

If we run yacc on this, it will report the following error message

85: shift/reduce conflict (shift 99, red'n 30) on ELSEkw
state 85
	statement :  IFkw expression THENkw statement_ELSEkw statement 
	statement :  IFkw expression THENkw statement_    (30)

	ELSEkw  shift 99
	.  reduce 30

what does this mean?  Well, let us try to reconstruct just part of the FA.

[ build the fa starting from statement, leaving out all but the if then
else rules ].

what this means is that at this point in the FA 
a) it was possible to shift on the else
b) if it did the reduction, at least one of the paths it could have come
from would have permitted a shift on the else after the reduction.
Note - it may sometimes take a bit of hunting to find the possible path -
it usually isn't the obvious one.

What to do?  First off, you need to know what YACC will do with
shift/reduce errors.  The first thing it will do is to always shift.
Is this the right thing to do in this case?  Well, since it is, we can
just ignore this message - treat it as a warning and not an error.

Here is another one.  At least one of you made the mistake of using
parenthesis as the subscript indicators.  That is, rewriting the grammar
rule for subscript as

subscript ->
	variable ( expression
	| subscript , expression

If you do this and feed it to yacc, you get the following error messages

13: shift/reduce conflict (shift 31, red'n 57) on LEFTPAREN
state 13
	statement :  ID_LEFTPAREN argument_list RIGHTPAREN 
	name :  ID_    (57)
	name :  ID_UPARROW 

	UPARROW  shift 32
	LEFTPAREN  shift 31
	.  reduce 57

40: shift/reduce conflict (shift 70, red'n 57) on LEFTPAREN
state 40
	factor :  ID_LEFTPAREN argument_list RIGHTPAREN 
	name :  ID_    (57)
	name :  ID_UPARROW 

	UPARROW  shift 32
	LEFTPAREN  shift 70
	.  reduce 57

Again, lets try to see where these might have come from.  

[ go through construction from statement through variable and subscript ]

What this is saying is that at this point it can't decide whether to
reduce the name as part of a subscript list, or to continue as if it were
a procedure call.  Notice that the error doesn't point you directly to the
fact that this comes from a subscript list, you have to try to reason this
out.

In this case the shift is NOT always the right thing to do.  What this 
would indicate is that you need to rewrite the grammar.  In this case,
by changing the symbol used for subscripts.  So some shift/reduce errors
are bad, some are ok.