zaach / jison

Bison in JavaScript.
http://jison.org
4.34k stars 448 forks source link

Unusual conflict when sufficient context for disambiguation is provided #344

Open vihanb opened 7 years ago

vihanb commented 7 years ago

This has me stumped for a couple of days, I'm trying to convert a LL grammar to LALR for Jison, but it throws this error:

Conflict in grammar: multiple actions possible when lookahead token is ) in state 35
- reduce by rule: Type ->
- reduce by rule: PropertyHead -> Identifier

States with conflicts:
State 35
  FunctionHeadItem -> Identifier .Type ? #lookaheads= ) ,
  FunctionHeadItem -> Identifier .Type #lookaheads= ) ,
  PropertyHead -> Identifier . #lookaheads= . [ ( )
  Type -> .: Identifier #lookaheads= ? ) ,
  Type -> . #lookaheads= ? ) ,

okay, looks likes theres a conflict with Identifier... that must mean PropertyHead and Type must together be ambiguous right? Well no, here's my whole grammar:

(I've outlines significant spots)

Entry
    : Program { return $1 }
    ;

Program
    : Program Statements -> $1.concat($2)
    |                    -> []
    ;

Statements
    : Statement SB       -> [ $1 ]
    | SB                 -> []
    ;

Statement
    : Expression
    ;

Expression
    : PropertyExpression            -> new node.ExpressionStatement(@1, $1)
    | IndependentLiteral            -> new node.ExpressionStatement(@1, $1)
    ;

// Handle Properties

PropertyExpression
    : PropertyHead PropertyTail    -> new node.PropertyExpression(@2, $1, $2)
    | PropertyHead 
    ;

//
// CONFLICT HERE
// Along with the above rule. `Identifier` on its own doesn't seem to be liked by Jison 
//
// `Literal` rule is omitted from this GH issue for brevity 
PropertyHead
    : Literal
    | Identifier
    | '(' Expression ')'           -> $2
    ;

PropertyTail
    : PropertyTail PropertyTailItem -> $1.concat($2)
    | PropertyTailItem              -> [ $1 ]
    ;

PropertyTailItem
    : '.' Identifier               -> $2
    | '[' Expression ']'            -> new node.EvaluatedIdentifier(@2, $2)
    | '(' List ')'                  -> new node.ArgumentList(@2, $2)
    ;

/**
 * Literals
 */

// Empty for now
Literal
    :
    ;

IndependentLiteral
    : Lambda
    ;

Lambda
    : FunctionHead LAMBDA_INDICATOR LambdaBody -> new node.Lambda(@$, $1, $2)
    ;

// Empty for now
LambdaBody
    :
    ;

/**
 * "Function" Rules
 */

FunctionHead
    : '(' FunctionHeadItems ')' -> $2
    ;

FunctionHeadItems
    : 
    | FunctionHeadItem                       -> [ $1 ]
    | FunctionHeadItems ',' FunctionHeadItem -> $1.concat($3)
    ;

//
// CONFLICT HERE
// If `Type` evaluated to its `| ` (empty) derivation. This could just be `Identifier` conflicting with the above
//
FunctionHeadItem
    : Identifier Type '?'                    -> new node.FunctionArgument(@$, [$1, $2], true)
    | Identifier Type                        -> new node.FunctionArgument(@$, [$1, $2], false)
    ;

/**
 * "Helper" Rules
 */

List
    : ListItems
    |                     -> []
    ;

ListItems
    : ListItems ',' Expression -> $1.concat($3)
    | Expression               -> [ $1 ]
    ;

Identifier
    : VARIABLE -> new node.Identifier(@1, $1)
    ;

Type
    : ':' Identifier
    |
    ;

As you can see LAMBDA_INDICATOR is sufficient to determine which to use.

So either this is a bug in Jison or LALR isn't working as expected, am I doing something wrong?