Reduce/reduce conflicts with Jison LALR

[rfranke]

Working on a parser for the Modelica language, Jison eventually required the -p lr option to avoid reduce/reduce conflicts. The same parser rules work with Bison and PLY though.

Here is a simple example that fails with Jison, while running well with Bison (2.4.1 and 2.5):

%token PREFIX1 PREFIX2 SUFFIX1 SUFFIX2

%%

start:
           opt_prefix1 SUFFIX1
        |  opt_prefix2 SUFFIX2
        ;

opt_prefix1:
          /* empty */
        | PREFIX1
        ;

opt_prefix2:
          /* empty */
        | PREFIX2
        ;

%%

The error message is:

Conflict in grammar: multiple actions possible when lookahead token is SUFFIX1 in state 0
- reduce by rule: opt_prefix2 ->
- reduce by rule: opt_prefix1 ->
Conflict in grammar: multiple actions possible when lookahead token is SUFFIX2 in state 0
- reduce by rule: opt_prefix2 ->
- reduce by rule: opt_prefix1 ->

The problems with -p lr are the long runtime of Jison (about 2-3 minutes on moparser.jison) and the large size of the resulting moparser.js.

[GerHobbelt]

Verified: still a bug. Jison doesn't cope well with epsilon rules which have different FOLLOW sets: these are merged into a single state while they shouldn't.

[DmitrySoshnikov]

Since Jison uses "LALR(1) by SLR(1)" algorithm, it seems incorrectly merges the lookaheads in the extended grammar, based only on the same final set. This should either be by compressing from CLR(1) with full lookahead sets, or consider correct LHS of a rule.

If this is still the issue for Jison, one can also use the alternative, the Syntax tool, which doesn't have this issue (including for epsilon rules), and has the same grammar format.