Open DemiMarie opened 8 years ago
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.
the reference seems to be to this code
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.
There is also an algorithm called BRNGLR that achieves worst-case O(n³).
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.