What are some examples of context-free grammars that necessarily trigger cubic worst-case complexity for GLR parsers?

I have seen a mention of the example S $\rightarrow$ SSS | SS | "a" but I would be interested to find more information on this and also find proofs of their worst-case complexity. Can anyone refer to papers that would cover this?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.