CODEWITHSUNDEEP
compiler-constructiongrammarcontext-free-grammarparser-generatorjison
Gabriel Ratener
Gabriel Ratener

Reputation: 605

Jison: Binary operation grammar conflict

In trying to set up my Jison grammar I had:

%left 'OR' 'AND'

%%

Expression:
    Operation
;

Operation:
    Expression Operator Expression {$$ = new yy.LogicalExpression($2, $1, $3)}
;

Operator:
    'AND'
|   'OR'
;

But that resulted in the following conflict message:

Conflict in grammar: multiple actions possible when lookahead token is OR in state 6
- reduce by rule: Operation -> Expression Operator Expression
- shift token (then go to state 5)
Conflict in grammar: multiple actions possible when lookahead token is AND in state 6
- reduce by rule: Operation -> Expression Operator Expression
- shift token (then go to state 4)

States with conflicts:
State 6
  Operation -> Expression Operator Expression . #lookaheads= $end OR AND
  Operation -> Expression .Operator Expression
  Operator -> .AND
  Operator -> .OR

When I replace eliminate the Operator non-terminal and instead write out the expression patterns directly:

%left 'OR' 'AND'

%%

Expression:
    Operation
;


Operation:
    Expression 'AND' Expression {$$ = new yy.LogicalExpression($2, $1, $3)}
|   Expression 'OR' Expression {$$ = new yy.LogicalExpression($2, $1, $3)}
;

I get no such error, why does the first grammar have a conflict, but not the second? They seem equivalent to my understanding.

Thanks in advance!

Upvotes: 3

Views: 153

Answers (1)

user207421
user207421

Reputation: 310985

Too much look ahead, but the first form is wrong anyway. The second form is correct. You need to write separate productions for AND and OR, and all other operators too. Otherwise you can't get operator precedence going.

Upvotes: 1

Related Questions