CODEWITHSUNDEEP
grammarbisonreducejison
Benjamin Schulte
Benjamin Schulte

Reputation: 873

Jison: Reduce Conflict where actually no conflict is

I'm trying to generate a small JavaScript parser which also includes typed variables for a small project.

Luckily, jison already provides a jscore.js which I just adjusted to fit my needs. After adding types I ran into a reduce conflict. I minimized to problem to this minimum JISON:

Jison:

%start SourceElements
%%

// This is up to become more complex soon
Type
    : VAR
    | IDENT
    ;

// Can be a list of statements
SourceElements
    : Statement
    | SourceElements Statement
    ;

// Either be a declaration or an expression
Statement
    : VariableStatement
    | ExprStatement
    ;

// Parses something like: MyType hello;
VariableStatement
    : Type IDENT ";"
    ;

// Parases something like hello;
ExprStatement
    : PrimaryExprNoBrace ";"
    ;

// Parses something like hello;
PrimaryExprNoBrace
    : IDENT
    ;

Actually this script does nothing than parsing two statements:

VariableStatement

IDENT IDENT ";"

ExpStatement

IDENT ";"

As this is a extremly minimized JISON Script, I can't simply replace "Type" be "IDENT" (which btw. worked).

Generating the parser throws the following conflicts:

Conflict in grammar: multiple actions possible when lookahead token is IDENT in state 8
- reduce by rule: PrimaryExprNoBrace -> IDENT
- reduce by rule: Type -> IDENT
Conflict in grammar: multiple actions possible when lookahead token is ; in state 8
- reduce by rule: PrimaryExprNoBrace -> IDENT
- reduce by rule: Type -> IDENT

States with conflicts:
State 8
  Type -> IDENT . #lookaheads= IDENT ;
  PrimaryExprNoBrace -> IDENT . #lookaheads= IDENT ;

Is there any trick to fix this conflict?

Thank you in advanced! ~Benjamin

Upvotes: 2

Views: 559

Answers (1)

John Bollinger
John Bollinger

Reputation: 180968

This looks like a Jison bug to me. It is complaining about ambiguity in the cases of these two sequences of tokens:

  1. IDENT IDENT
  2. IDENT ";"

The state in question is that reached after shifting the first IDENT token. Jison observes that it needs to reduce that token, and that (it claims) it doesn't know whether to reduce to a Type or to a PrimaryExpressionNoBrace.

But Jison should be able to distinguish based on the next token: if it is a second IDENT then only reducing to a Type can lead to a valid parse, whereas if it is ";" then only reducing to PrimaryExpressionNoBrace can lead to a valid parse.

Are you sure the given output goes with the given grammar? It would be possible either to add rules or to modify the given ones to produce an ambiguity such as the one described. This just seems like such a simple case that I'm surprised Jison gets it wrong. If it in fact does, however, then you should consider filing a bug report.

Upvotes: 1

Related Questions