Re: redundant merges for GLR

[Joel E. Denny]

On Tue, 19 Jul 2005, Joel E. Denny wrote:

> I am attempting to use bison's %glr-parser and %merge to construct parse
> forests.  I'm getting duplicate representations of some trees within the
> forest.  Both bison 1.875 and 2.0 give the same results.

<snip>

> At the end of this email is a simple bison spec that demonstrates the
> problem.

<snip>

> Reformatted for readability, the following is the output I would expect
> from the start production's semantic action:
>
>   merge{
>     S <- merge{
>       A <- A1 <- 'a' and A <- A2 <- 'a'
>     } and S <- B <- 'a'
>   }
>
> Reformatted for readability, the actual output is:
>
>   merge{
>     merge{
>       S <- merge{
>         A <- A1 <- 'a' and A <- A2 <- 'a'
>       } and S <- B <- 'a'
>     } and S <- A <- A2 <- 'a'
>   }
>
> Notice that the tree S <- A <- A2 <- 'a' is represented twice.

Reformatted for readability, the output for bison 2.0b is:

  merge{
    merge{
      S <- merge{
        A <- A1 <- 'a' and A <- A2 <- 'a'
      } and S <- B <- 'a'
    } and S <- merge{
      A <- A1 <- 'a' and A <- A2 <- 'a'
    }
  }

Now the tree S <- A <- A1 <- 'a' is also represented twice.  That is, it
seems the problem has worsened... at least for this test case.

I'm not sure of the significance, but I also noticed this at the end of
the parser trace:

  Error: popping token $end ()Error: popping nterm tree ()Error: popping
  token $end ()

This did not happen with prior versions of bison for this test case.
This is a wild guess, but does this have something to do with the new
destructor call on the start symbol?  If so, `Error' is a bit misleading.

Thanks.

Joel Denny