Resolving shift/reduce conflicts in Bison

Question

The grammar that has the conflict is as follow

method_call: T_ID T_LPAREN method_arg_list T_RPAREN T_SEMICOLON

value: T_ID T_LSB expr T_RSB
     | T_ID;

method_arg_list: /* Empty */
               | method_arg method_arg_list;

method_arg: string_constant
          | expr;

expr: value
    | '(' expr ')';

The problem is that when it reads a T_ID, it doesn't know whether it should shift and read the following '(' or reduce to a value. But shouldn't it check if the next token is a left parenthesis?

I am quite new to bison and parser in general and I am wondering what are the ways that I can rewrite the grammar and solve the conflict?

Edit

State 60

37 method_call: T_ID . T_LPAREN method_arg_list T_RPAREN T_SEMICOLON
67 value: T_ID . T_LSB expr T_RSB
68      | T_ID .

T_LPAREN  shift, and go to state 71
T_LSB     shift, and go to state 72

T_LPAREN  [reduce using rule 68 (value)]
$default  reduce using rule 68 (value)

There isn't enough information for us to be able to help you. You need to produce an MCVE (minimal reproducible example) which reproduces the error. It'll list some tokens (possibly listing some of the non-terminals as tokens, even though in your real grammar, they're non-terminals). You'll also show us the shift/reduce conflict report for just the problematic state in the output of yacc -v (bison -v). We need enough grammar to be able to reproduce the problem — but no more than enough to be able to reproduce the problem. — Jonathan Leffler
@JonathanLeffler the error disappeared after I changed a few things...I am still trying to figure out what happened.. — GalaxyVintage
I'm not sure whether the '(' should be T_LPAREN and the ')' should be T_RPAREN. As written, with %token T_ID T_LPAREN T_RPAREN T_SEMICOLON T_LSB T_RSB string_constant and Bison is OK with the code. I hope you're keeping a record of what broke and then what works; using a version control system becomes very important. — Jonathan Leffler
Galaxy: Usually function arguments are separated by commas. That's not by accident; if you just smushed arguments together without some sort of punctuation, then you end up with tons of ambiguities, also known as shift/reduce conflicts. I suspect the absence of the comma is a simple typo on your part. — rici

Bruce David Wilner Bruce David Wilner · Accepted Answer · 2016-07-02T23:33:28

Leffler is correct: we need to know about some higher-level sentential structures that may rely upon method calls and values and such.

I see what's going on from a CONCEPTUAL standpoint: we needn't get mired in any "y.output" nitty-gritty. Everything stems from your failure to separate arguments to the method call with commas. Also, I'd love to know why you're collecting your argument list right-recursively rather than left-recursively.

What is the difference between '(' and T_LPAREN, and between ')' and T_RPAREN? Does lex return one in one case, the other in another case? It seems to me that the simple pattern \( can't be mapped to both of these, but only to one; the same goes for the pattern \). Also, for readability, don't bother defining, e.g., T_LSB where '[' will do just fine.

Resolving shift/reduce conflicts in Bison

1 Answers