librelist archives

« back to archive

Inconsistent behavior Jison-Bison regarding reduce-reduce conflicts

Inconsistent behavior Jison-Bison regarding reduce-reduce conflicts

From:
Peter Holm
Date:
2011-05-05 @ 16:20
Hello!

While working with Jison, I have stumbled upon a weird situation regarding
conflicts:
Here is a grammar that gives no conflicts in bison, but gives reduce-reduce
conflicts in jison.
Why? Should not the lookahead solve this conflict?
If that is relevant, I am running jison 0.2.7.

The conflicts:

Conflict in grammar (state:4, token:r)
  reduce by vs -> v
  reduce by f -> v
Conflict in grammar (state:4, token:$end)
  reduce by vs -> v
  reduce by f -> v
Conflict in grammar (state:4, token::)
  reduce by vs -> v
  reduce by f -> v

The grammar:

%%

d
  : f "r"
  | vs
;

f : "v" "p"
  | "v"
;

vs
    : vs ":"
    | "v"
;

%%

Thanks in advance,
//Peter Holm

Re: [jison] Inconsistent behavior Jison-Bison regarding reduce-reduce conflicts

From:
Zachary Carter
Date:
2011-05-05 @ 16:56
On Thu, May 5, 2011 at 12:20 PM, Peter Holm <piotrholmskij@gmail.com> wrote:
> Hello!
>
> While working with Jison, I have stumbled upon a weird situation regarding
> conflicts:
> Here is a grammar that gives no conflicts in bison, but gives reduce-reduce
> conflicts in jison.
> Why? Should not the lookahead solve this conflict?
> If that is relevant, I am running jison 0.2.7.
>
> The conflicts:
>
> Conflict in grammar (state:4, token:r)
>   reduce by vs -> v
>   reduce by f -> v
> Conflict in grammar (state:4, token:$end)
>   reduce by vs -> v
>   reduce by f -> v
> Conflict in grammar (state:4, token::)
>   reduce by vs -> v
>   reduce by f -> v
>
> The grammar:
>
> %%
>
> d
>   : f "r"
>   | vs
> ;
>
> f : "v" "p"
>   | "v"
> ;
>
> vs
>     : vs ":"
>     | "v"
> ;
>
> %%
>
> Thanks in advance,
> //Peter Holm
>

This is a limitation of the LALR(1) parsing algorithm which merges
some states even though they have different lookaheads. The version of
Bison you are using must use LR(1), which keeps these steps separate
and thus avoids conflict.

Jison has an LR(1) mode, but it is only practical for small grammars
like your example. You can play around with the modes and even inspect
the parse tables here: http://zaach.github.com/jison/try/usf/. Click
on cells in the parse table at the bottom to expand them.

Though not ideal, you can do some rule shuffling to make it work in LALR(1):

%%

d
  : f "r"
  | vs
  | "v"
;

f : "v" "p"
;

vs
    : "v" ":"
;

%%

-- 
Zach Carter