Difficulty with precedence operators

[NickHeiner]

I have a shift/reduce conflict and I'm trying to resolve it with precedence operators.

Here is my jison file:

%lex

%%
\s+                   /* skip whitespace */
\w+                   return 'WORD';

/lex

%left WORD

%start expressions

%%
e
    : e e
        {$$ = $1 + '(' + $2 + ')';}
    | WORD
        {$$ = $1;}
    ;

expressions
    : e
        { return $1;}
    ;

The conflict I get is:

Conflict in grammar: multiple actions possible when lookahead token is WORD in state 4
- reduce by rule: e -> e e
- shift token (then go to state 3)

States with conflicts:
State 4
  e -> e e . #lookaheads= $end WORD
  e -> e .e
  e -> .e e
  e -> .WORD

I am using [email protected].

I have the following input to the parser:

outerfn innerfn arg

With the above grammar, it compiles to:

outerfn(innerfn(arg))

I want to solve the shift/reduce conflict, and I want to be able to control which of the following two options the language compiles to:

(outerfn(innerfn))(arg)

I would expect that I could do this using precedence operators, but when the following alternatives have no effect:

%left WORD
/* OR */
%right WORD

Am I doing something wrong, or just not understanding how this works?

[nolanlawson]

I don't believe you can resolve shift-reduce ambiguities using precedence. In my experience, though, a good way to fix ambiguities is to use the ebnf style to collapse your grammar into simpler rules.

E.g. your grammar can become:

%lex

%%
\s+                   /* skip whitespace */
\w+                   return 'WORD';

/lex

%left WORD

%start expressions

%%

%ebnf

top
    : e+
        {$top_repetition0} // do something with the array here

    ;

e
    : WORD
        {$$ = $1;}
    ;

expressions
    : top
        { return $1;}
    ;

If you need help with debugging your grammar, you might like the Jison debugger I wrote. (Although it doesn't tell you if you have ambiguities.)

[NickHeiner]

I don't believe you can resolve shift-reduce ambiguities using precedence.

Is that right? The Bison docs suggest otherwise – is this a difference between Bison and Jison?

When possible, you should rather use precedence directives to fix the conflicts explicitly (see Using Precedence For Non Operators).

from https://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html

[NickHeiner]

I've only looked at the jison debugger for two seconds but it already seems super useful. Thanks!

[GerHobbelt]

The bison advice is applicable to jison grammars as well; however do note that this particular grammar would need more than a %prec hack to make it obvious again what it does.

I find that using %prec hacks is a last straw and almost always renders the grammar immutable as in: try to add one more language bit in there and you get toasted.

Anyway, to show that it can be done: see the above commit.

[GerHobbelt]

The %prec hack is shown in here:

https://github.com/GerHobbelt/jison/blob/master/examples/issue-293.jison

The trick with %prec is to remember that precedence is a relative thing. In other words: it takes two (or many) to party.