Use Elkhound's techniques to optimize the GLR mode

[DemiMarie]

trafficstars

The GLR mode of Happy is likely to be slow. Fortunately, the problem of speeding it up has already been solved by Elkhound, which can generate parsers in C++ or OCaml.

[simonmar]

This isn't a particularly useful bug report. "Likely to be slow" - why? Have you benchmarked it? I'm inclined to close this without more details.

[ghost]

the reference seems to be to this code

https://github.com/WeiDUorg/elkhound

[andreasabel]

See also:

Tom Ridge. Simple, functional, sound and complete parsing for all context- free grammars. In International Conference on Certified Programs and Proofs, pages 103–118. Springer, 2011.

From Conclusions (section 12):

The time complexity of the memoized version of our algorithm is O(n^5). Real-world performance comparisons on the grammar E -> E E E | "1" | ǫ indicate that we are faster than the popular Happy parser generator running in GLR mode across a wide range of inputs.

Page 14:

parsers generated by Happy in GLR mode appear to be O(n^6) although GLR is theoretically O(n^3) in the worst case.

[DemiMarie]

There is also an algorithm called BRNGLR that achieves worst-case O(n³).