GNU Bison - Fork to implement a variation of the Elkhound algorithm
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
build-aux
data
djgpp
doc
etc
examples
gnulib @ ea6cb04
lib
m4
po
runtime-po
src
submodules
tests
.gitattributes
.gitignore
.gitmodules
.prev-version
.project
.travis.yml
.x-sc_require_config_h
.x-sc_unmarked_diagnostics
.x-update-copyright
AUTHORS
COPYING
ChangeLog-1998
ChangeLog-2012
Makefile.am
NEWS
PACKAGING
README
README-alpha
README-hacking
README.md
REFERENCES
THANKS
TODO
bootstrap
bootstrap.conf
cfg.mk
configure.ac

README.md

GNU Bison fork with alternative GLR algorithm

Build Status

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.

Goals

  • Provide an alternative implementation of GLR (Graph-GLR) for GNU bison based on the Elkhound algorithm.
  • Make it as production ready as Stack-GLR algorithm.
    • This means that make check should pass and check both algorithms.
  • Make Graph-GLR reasonably competitive respect Stack-GLR
    • We accept that the performance of Graph-GLR will always be behind that of Stack-GLR.

Non-goals

  • Make Graph-GLR the new GLR default of Bison.
  • Make the algorithm match or exceed the performance of the Stack-GLR algoritm.