Re: y.output format

[Akim Demaille]

>>>>> "Tim" == Tim Van Holder <address@hidden> writes:

>> I am afraid however I get a shift/reduce conflict which I do not
Tim> understand.
>> Where can I find a simple tutorial which explains the y.output file
Tim> format ?

Tim> Not sure about where there's a tutorial, but these steps should
Tim> help:

To end this presentation, I strongly recommend that you try to reach
the state where there is the conflicts.  I'll show this on a simple
example:

%%
exp: exp '?' exp ':' exp
   | "exp"
   ;

This grammar is the ternary ?: operator from C.  Run bison:

/tmp % bison --trace -v foo.y -o foo.c

Here is the foo.output:

|State 7 contains 1 shift/reduce conflict.
|
|
|Grammaire
|
|  Number, Line, Rule
|    0   2 $axiom -> exp $
|    1   2 exp -> exp '?' exp ':' exp
|    2   3 exp -> "exp"
|
|
|Terminaux, suivis des règles où ils apparaissent
|
|$ (0) 0
|':' (58) 1
|'?' (63) 1
|error (256)
|"exp" (257) 2
|
|
|Non-terminaux, suivis des règles où ils apparaissent
|
|$axiom (6)
|    à gauche: 0
|exp (7)
|    à gauche: 1 2, à droite: 0 1
|
|
|état 0
|
|    $axiom  ->  . exp $   (règle 0)
|    exp  ->  . exp '?' exp ':' exp   (règle 1)
|    exp  ->  . "exp"   (règle 2)
|
|    "exp"      décalage et aller à l'état 1
|
|    exp        aller à l'état 2
|
|
|
|état 1
|
|    exp  ->  "exp" .   (règle 2)
|
|    $défaut    réduction par la règle 2 (exp)
|
|
|
|état 2
|
|    $axiom  ->  exp . $   (règle 0)
|    exp  ->  exp . '?' exp ':' exp   (règle 1)
|
|    $          décalage et aller à l'état 3
|    '?'        décalage et aller à l'état 4
|
|
|
|état 3
|
|    $axiom  ->  exp $ .   (règle 0)
|
|    $défaut    accepter
|
|
|état 4
|
|    exp  ->  . exp '?' exp ':' exp   (règle 1)
|    exp  ->  exp '?' . exp ':' exp   (règle 1)
|    exp  ->  . "exp"   (règle 2)
|
|    "exp"      décalage et aller à l'état 1
|
|    exp        aller à l'état 5
|
|
|
|état 5
|
|    exp  ->  exp . '?' exp ':' exp   (règle 1)
|    exp  ->  exp '?' exp . ':' exp   (règle 1)
|
|    '?'        décalage et aller à l'état 4
|    ':'        décalage et aller à l'état 6
|
|
|
|état 6
|
|    exp  ->  . exp '?' exp ':' exp   (règle 1)
|    exp  ->  exp '?' exp ':' . exp   (règle 1)
|    exp  ->  . "exp"   (règle 2)
|
|    "exp"      décalage et aller à l'état 1
|
|    exp        aller à l'état 7
|
|
|
|état 7
|
|    exp  ->  exp . '?' exp ':' exp   (règle 1)
|    exp  ->  exp '?' exp ':' exp .   (règle 1)
|
|    '?'        décalage et aller à l'état 4
|
|    '?'        [réduction par la règle 1 (exp)
|    $défaut    réduction par la règle 1 (exp)

You try to *reach* the state 7 from the initial state:

state 0
Push a exp, i.e. stack is |- exp
state 2
Push a '?'                |- exp '?'
state 4
Push an exp               |- exp '?' exp
state 5
push a ':'                |- exp '?' exp ':'
state 6
push an exp               |- exp '?' exp ':' exp
state 7

We reached state 7.  Now look at it, and look for the conflict:

|    '?'        décalage et aller à l'état 4
|
|    '?'        [réduction par la règle 1 (exp)

The conflict is on '?', in other words, the stack is:

 |- exp '?' exp ':' exp

and the lookahead is '?'.

The conflict can be read as:

        When I have recognized the sequence `exp ? exp : exp' and when
        a ? arrives, I don't know if I should shift the ? or reduce
        the rule.

In some cases, reading the state only is enough (and this example
shows this), in other cases, understanding how you reached the state
helps a lot.


Oh, BTW, all this crap is the proof that Bison (Yacc) is a bad tool,
it doesn't help you too much.  But that's a necessary tradeoff with
performances.  These tools are for experts :(