<p>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.</p>

<p>[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, <em>Theoretical Computer Science</em> 82(1):165--176. <a href="http://dx.doi.org/10.1016/0304-3975(91)90180-A">doi: 10.1016/0304-3975(91)90180-A</a></p>

CC BY-SA 3.0
2012-03-02T15:33:02.183Z
2012-03-02T16:09:12.153Z
2012-03-02T16:09:12.153Z
Sylvain
<p>When tinkering with noncanonical LR parsing, I thought up a parsing method (with infinitely sized tables, which makes it somewhat <em>unpractical</em>) capable of parsing exactly the unambiguous grammars in $O(n^2)$ time, and I wondered if it is possible to do better:</p>

<blockquote>
  <p>Can all unambiguous grammars be parsed in linear time?</p>
</blockquote>

<p>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 <a href="http://compilers.iecc.com/comparch/article/91-04-021">here</a>, but no answer was given as far as I know.</p>

<reference-request><fl.formal-languages><time-complexity><parsing><context-free>
Can all unambiguous grammars be parsed in linear time?
Alex ten Brink
# Can all unambiguous grammars be parsed in linear time?

(Asked by: username_0 on 2012-03-01)

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](http://compilers.iecc.com/comparch/article/91-04-021), but no answer was given as far as I know.

**Tags:** reference-request, fl.formal-languages, time-complexity, parsing, context-free

---

## 1 answers

### Answer by username_1 on 2012-03-02. Score: 24 | Accepted answer

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](http://dx.doi.org/10.1016/0304-3975(91)90180-A)


---

