Shift/Reduce conflict in variable declaration

0
votes

I am using bison to write a parser to a C-like grammar, but I'm having problem in variable declaration.

My variables can be simples variable, arrays or structs, so I can have a variable like a.b[3].c.

I have the following rule:

var : NAME             /* NAME is a string */
    | var '[' expr ']'
    | var '.' var
    ;

which are giving me a shift/reduce conflict, but I can't think of a way to solve this.

How can I rewrite the grammar or use Bison precedence to resolve the problem?

2
parsingbisonyacc

2 Answers

1
votes

I don't know why you want the . and [] operators to be associative, however something like this might inspire you.

y
%union{}

%token NAME

%start var

%left   '.'
%left   '['

%%

var:
    NAME
|   var '[' expr ']'
|   var '.' var

Also, as var probably appears in expr, there may be other problems with the grammar.

1
votes

It's certainly possible to resolve this shift-reduce conflict with a precedence declaration, but in my opinion that just makes the grammar harder to read. It's better to make the grammar reflect the semantics of the language.

A var (what some might call an lvalue or a reference) is either the name of a simple scalar variable or an expression built up iteratively from a var naming a complex value and a selector, either a member name or an array index. In other words:

var     : NAME
        | var selector
        ;
selector: '.' NAME
        | '[' expression ']'
        ;

This makes it clear what the meaning of a.b[3].c is, for example; the semantics are described by the parse tree:

       a.b[3].c
     +----+----+
     |         |
   a.b[3]     .c
  +---+--+
  |      |
 a.b    [3]
+-+-+
|   |
a  .b

It's not necessary to create the selector rule; it would be trivial to wrap the two rules together. If you don't feel that it is clearer as written above, the following will work just as well:

var: NAME
   | var '.' NAME
   | var '[' expression ']'
   ;