[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

NEWS: Much improved conflict messages in SableCC 2.13



Hi everyone.

Another release.  It was quick, but it is, I think, an interesting release.

I received a patch from Ben Menking <bmenking@bigfoot.com>.  This patch
contained some code to:
- Indicate the current position in a production using a * symbol instead of
using a position number
- Filtering out the state's irrelevant productions and displaying only those
that are directly involved in the conflict.

This code needed improvement (see the ChangeLog).  [I know, I'm picky]. 
Anyway, while improving this code, I said to myself, why not also implement a
related feature that was initially meant for SableCC 3.0.

The result is that, now SableCC 2.13 reports conflict in a much clearer way.
(1) It gets rid of irrelevant state items.
(2) It clearly indicates the action beside each item (reduce/shift)
(3) It indicates the parsing position using a "*" instead of an integer

Finally, and not least:

(4) It prints the shortest stack configuration that would expose the conflict!

The addition of (4) helps figuring out what is normally pretty difficult to
see:  The question we normally ask, when SableCC reports a conflict, is "what
kind of program would cause this conflict"?  (4) answers this question.  Thus,
it gives us an intuitive context to see the conflict. :-)

Here is a small example of ambiguous grammar, and the SableCC output (old and
new):
====================================
// an obviously ambiguous grammar
Tokens
  plus = '+';
  minus = '-';
  num = ['0'..'9']+;

Productions
  exp = {plus}  [lexp]:exp plus  [rexp]:exp |
        {minus} [lexp]:exp minus [rexp]:exp |
        {num}   num;
====================================
---OLD STYLE---
$ java SableCC ambiguous.sablecc
SableCC version 2.12
[...]
shift/reduce conflict on TPlus in {
        [PExp = PExp TPlus PExp]:1:TPlus,
        [PExp = PExp TPlus PExp]:1:TMinus,
        [PExp = PExp TPlus PExp]:1:EOF,
        [PExp = PExp TPlus PExp]:3:TPlus,
        [PExp = PExp TPlus PExp]:3:TMinus,
        [PExp = PExp TPlus PExp]:3:EOF,
        [PExp = PExp TMinus PExp]:1:TPlus,
        [PExp = PExp TMinus PExp]:1:TMinus,
        [PExp = PExp TMinus PExp]:1:EOF
}
====================================
---NEW STYLE---
$ java SableCC ambiguous.sablecc
SableCC version 2.13
[...]
shift/reduce conflict in state [stack: PExp TPlus PExp *] on TPlus in {
        [ PExp = PExp * TPlus PExp ] (shift),
        [ PExp = PExp TPlus PExp * ] followed by TPlus (reduce)
}

NOTE:
- NEW: the stack state is "in state [...]"
- The lookahead is "on ..."
- NEW: The parsing position is indicated by "*"
- NEW: The action is shown (reduce/shift)
- NEW: There are no spurious items
====================================
EXPLANATION

What the error message means is that if we have a program that starts with the
following:

  stack: PExp-1 TPlus PExp-2
  lookahead: TPlus

e.g.: (pick here anything that looks like "PExp TPlus PExp")

  3+4 (and an upcoming "+")

then there is a shift/reduce conflict as you could have:

[parentheses indicate a PExp]
  3+(4+...)...  
i.e.: shift the "+" in [ PExp = PExp-2 * TPlus  PExp-3 ]
                                 \4/      \+/   \.../    
In other words [PExp-2 TPlus PExp-3] will eventually be reduced to a PExp (let
say PExp-4), then the stack will look like 
  [ PExp-1 TPlus PExp-4 ]

or you could have
  (3+4)+... 
i.e.: reduce [ PExp = PExp-1 TPlus PExp-2 * ]
                       \3/    \+/   \4/

Neat, isn't it?

Have fun resolving conflicts!  (I'll use this version to resolve Scriptonite
conflicts http://scriptonite.sourceforge.net/).

Etienne
-- 
----------------------------------------------------------------------
Etienne M. Gagnon, M.Sc.                     e-mail: egagnon@j-meg.com
Author of SableCC:                 http://www.sable.mcgill.ca/sablecc/
----------------------------------------------------------------------