2
$\begingroup$

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?

$\endgroup$

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.