Re: Full LR(1) parser generator Hyacc 0.9 release

>> > merging states with
>> > identical cores cannot produce new S/R conflicts.
>
> Every S/R conflict is preserved for at least some but not necessarily
> all of its viable prefixes. Before splitting, the conflict might
> resolve as a reduce. After splitting, the action is a shift for any
> viable prefix for which the conflict is not preserved. That is, for
> such viable prefixes, the action might change. This is the scenario I
> most commonly encounter.


Here is a grammar that gives different results for the two different
possibilities.


/* LR(2) grammar */


      G -> S <eof>


      S -> c X t
          -> c Y p
          -> r X n
          -> r Y p


      X -> a i
      Y -> a i n
          -> a i t


Method A. When splitting states based on only R/R conflicts, you end up
with 17 states.


Method B. When splitting states based on R/R and S/R conflicts, you end
up with 19 states.


Using method B, state 10 and state 18 have the same cores.
In state 10 the conflict is S/R for only t.
In state 18 the conflict is S/R for only n.


Using method A, states 10 and 18 are merged and you have S/R conflicts
on both t and n in the merged state.


Below are the relevant states for method B, which produces two more
states than method A.


//////////////////////////// STATE 2 /////////////////////////////


* 1 S -> c . X t
* 2 S -> c . Y p


                  X +=> 5
                  Y +=> 6
                  a +=> 7


Came from: 0.


//////////////////////////// STATE 3 /////////////////////////////


* 3 S -> r . X n
* 4 S -> r . Y p


                  X +=> 13
                  Y +=> 14
                  a +=> 15


Came from: 0.


//////////////////////////// STATE 5 /////////////////////////////


* 1 S -> c X . t


                  t +=> 8


Came from: 2.


//////////////////////////// STATE 6 /////////////////////////////


* 2 S -> c Y . p


                  p +=> 9


Came from: 2.


//////////////////////////// STATE 7 /////////////////////////////


* 5 X -> a . i
* 6 Y -> a . i n
* 7 Y -> a . i t


                  i +=> 10


Came from: 2.


//////////////////////////// STATE 10 /////////////////////////////


* 6 Y -> a i . n
* 7 Y -> a i . t
* 5 X -> a i .


                  t +=> 11
                  n +=> 12
                  (default) <= 5 (2, X)


Came from: 7.


//////////////////////////// STATE 13 /////////////////////////////


* 3 S -> r X . n


                  n +=> 16


Came from: 3.


//////////////////////////// STATE 14 /////////////////////////////


* 4 S -> r Y . p


                  p +=> 17


Came from: 3.


//////////////////////////// STATE 15 /////////////////////////////


* 5 X -> a . i
* 6 Y -> a . i n
* 7 Y -> a . i t


                  i +=> 18


Came from: 3.


//////////////////////////// STATE 18 /////////////////////////////


* 6 Y -> a i . n
* 7 Y -> a i . t
* 5 X -> a i .


                  t +=> 11
                  n +=> 12
                  (default) <= 5 (2, X)


Came from: 15.


///////////////////////////////////////////////////////////////////




Paul B Mann

Return to the comp.compilers page.
Search the comp.compilers archives again.