When tinkering with noncanonical LR parsing, I thought up a parsing method (with infinitely sized tables, which makes it somewhat unpractical) capable of parsing exactly the unambiguous grammars in $O(n^2)$ time, and I wondered if it is possible to do better:
Can all unambiguous grammars be parsed in linear time?
I'm quite sure I read somewhere that this is the case, but it doesn't come up when searching the internet. The same question was asked here, but no answer was given as far as I know.
Unambiguous context-free parsing is in $O(n^2)$ using Earley's algorithm. Whether there exists a parsing algorithm working in linear-time on all the unambiguous context-free grammars is an open problem. One of the most advanced statements of this kind is due to Leo [1991], who showed that a variant of Earley parsing works in linear time for all LRR grammars.
[Leo 1991] Joop M. I. M. Leo. A general context-free parsing algorithm running in linear time on every LR($k$) grammar without using lookahead, Theoretical Computer Science 82(1):165--176. doi: 10.1016/0304-3975(91)90180-A
