Shift-Reduce Conflict in YACC for a rule starting with Action

448 views Asked by At
%token A B
%%
start:  {printf("Starting…\n");} A A
 | A B;

My book says that there is a shift-reduce conflict when the token is A because yacc converts to code to this.

%token A B
%%
start: empty A A
 | A B;
empty: {printf("Starting…\n");} ; 

I didn't get this. Here the second rule of start shifts, empty rule reduces. The first rule of start shifts too, So the first input expects A, while the second rule expects B. How is that a conflict? As far as I know,one rule must reduce, other should shift,than the two rules should expect the same token for an input for such conflict. However, one rule both shifts and reduces here(first rule), while the second rule only shifts, also they expect different tokes after those operations.

1

There are 1 answers

4
Chris Dodd On

The conflict is that it doesn't know whether or not to reduce the empty rule (run the action) before shifting the A. Both rules expect an A as the first token, so you get a shift/reduce conflict. Which should be done depends on the second token, so the grammar is not ambiguous and the conflict could be resolved by using more lookahead (using a GLR or backtracking parser).