CODEWITHSUNDEEP
bisonyaccshift-reduce-conflict
Charlestar
Charlestar

Reputation: 1

Why Bison can reduce an "error" item to an empty rule

I have the following yacc grammar:

33 CompSt: "{" DefList StmtList "}"
34       | "{" error ";" DefList StmtList "}"
......
52 DefList: Def DefList
53        | %empty

54 Def: Specifier DecList ";"
55    | Specifier error ";"
56    | Specifier DecList error ";"
57    | Specifier VarDec "[" error ";"
58    | Specifier VarDec "[" INT error ";" 

59 DecList: Dec
60        | Dec "," DecList

61 Dec: VarDec
62    | VarDec "=" Exp

I add the rule 34 to handle the situation when an illegal item appears at the beginning of a pair of brace. I think this rule is necessary (If you have any other methods, please tell me), but there is a shift/reduce warning:

33 CompSt: "{" . DefList StmtList "}"
34       | "{" . error ";" DefList StmtList "}"

 error   shift, and go to state 45
 STRUCT  shift, and go to state 2
 TYPE    shift, and go to state 3

 error   [reduce using rule 53 (DefList)]

I don't understand why "error" can be reduced by rule 53, and I have no idea how to fix this warning.

Thank you very much for your reply.

Upvotes: 0

Views: 120

Answers (1)

rici
rici

Reputation: 241671

In a shift-reduce conflict, the parser has two options: reduce (a specific production), leaving the lookahead token to be handled afterwards, or shift the lookahead token. Error rules are no different; error is, at least initially, treated as any other token would be. (The special handling is the resynchronization after error is shifted, but that's after it is shifted.)

So it's not error that would be reduced by production 53. It's the empty Deflist which came before the error. Of course, this reduction never happens because bison resolves shift-reduce conflicts in favour of the shift action, but it is warning you in case you think it is important that the empty Deflist be reduced.

Although this shift-reduce conflict doesn't matter, it's a bit ugly and it's not at all obvious why you feel the need to add the error production in the first place. You really don't need that many error productions since errors effectively bubble up the parse. (Unless you're trying to produce specific error messages in each case, I suppose.)

I'd remove the error productions 55 through 58, change 34 to the much simpler

| "{" error "}"

And add

| error ';'

To Deflist (after production 52).

Upvotes: 1

Related Questions