项目作者: rofirrim

项目描述 :
GNU Bison - Fork to implement a variation of the Elkhound algorithm
高级语言: C
项目地址: git://github.com/rofirrim/bison.git
创建时间: 2017-11-20T20:38:38Z
项目社区:https://github.com/rofirrim/bison

开源协议:Other

下载


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.