CODEWITHSUNDEEP
cparsingcompiler-constructionbison
paternostrox
paternostrox

Reputation: 445

Bison: Reduce/reduce conflict on non-tokens

So I'm in the process of making a compiler for C-- and I'm currently making literal, variable and function tables.

And this rule is giving me a reduce/reduce conflict:

lval: ID { check_var(); }
| ID { check_var(); } LBRACK NUM RBRACK
| ID { check_var(); } LBRACK ID { check_var(); } RBRACK;

Error is the following:

parser.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]
parser.y:104.6-21: warning: rule useless in parser due to conflicts [-Wother]
 | ID { check_var(); } LBRACK ID { check_var(); } RBRACK;
      ^^^^^^^^^^^^^^^^

I have precendece rules to avoid reduce errors on tokens, but now it's pointing to a non token, so not sure what I'm supposed to do?

If it helps by any chance these are my precedence rules:

%token INPUT OUTPUT WRITE
%token  RETURN VOID IF ELSE WHILE ASSIGN SEMI COMMA
%token LPAREN RPAREN LBRACE RBRACE LBRACK RBRACK
%token NUM ID STRING INT
%left EQ NEQ GE LE GT LT
%left PLUS MINUS
%left TIMES OVER

Upvotes: 0

Views: 89

Answers (1)

aschepler
aschepler

Reputation: 72431

Bison does not check for whether two custom code blocks within your syntax are identical. So it treats your grammar as basically:

lval: ID action_1
    | ID action_2 LBRACK NUM RBRACK
    | ID action_3 LBRACK ID action_4 RBRACK
;

And Bison (by default) acts as an LALR(1) parser, meaning it only looks ahead one token before making decisions. So when it sees that the top of the stack is an ID token and the look-ahead token is an LBRACK token, it can't decide whether it should execute action_2 or action_3, not realizing it doesn't actually matter.

Solve this by using a subrule to combine the common thing that should happen when an ID is followed by an LBRACK (and also in other situations):

id_with_check: ID { check_var(); } ;

lval: id_with_check
    | id_with_check LBRACK NUM RBRACK
    | id_with_check LBRACK id_with_check RBRACK
;

Upvotes: 6

Related Questions