Open puffnfresh opened 11 years ago
Thank you for your feedback. I've updated the section on complexity.
As of presently, there are several things missing from the article:
Unfortunately, I'm in a very busy period of my life and currently don't have the time to extend the article. But I put the text under version control to make collaboration simple. If anyone wants to improve on it, their contributions would be most welcome.
The Graph-Structured Stack (GSS) is the trick which gets GLL's worst-case parse time down to O(n^3).
Masaru Tomlta's paper describes the GSS in detail:
http://acl.ldc.upenn.edu/P/P88/P88-1031.pdf
Without a correct GSS, the parser isn't really GLL. The worst-case performance would be at least O(n^4).