GNU Bison - Fork to implement a variation of the Elkhound algorithm
See Elkhound: A Fast, Practical GLR Parser Generator
for the TR about this algorithm.
This fork aims at implementing this algorithm as an alternative of the existing
GLR algorithm of Bison (we call this algorithm Stack-GLR).
This project does not pretend to replace the existing Stack-GLR implementation
in Bison because is very good for almost all situations.
That said, there are some circumstances in which Stack-GLR algorithm behaves
exponentially. This is a documented fact in Bison.
The Elkhound algorithm provides an asymptotically better algorithm at the cost
of a higher overhead. Instead of duplicating stacks it represents the parsing
using a graph. We want to use an algorithm based on Elkound that we call
Graph-GLR.
make check
should pass and check both algorithms.