<p>Any context free language can be described by a grammar in Chomsky Normal Form, and then recognized by a nondeterministic algorithm that uses $O(\log^2 n)$ bits of memory: just guess the top-level production ($O(1)$ bits) and the breakpoint in the input string between the two substrings matched by the two sides of the production ($O(\log n)$ bits), recurse on the smaller side, and then continue non-recursively on the larger side.</p>

<p>By Savitch's theorem, it follows that the problem can be solved deterministically with $O(\log^4 n)$ bits of memory. The algorithm resulting from this technique would likely be quite inefficient, however.</p>

CC BY-SA 3.0
2011-10-21T18:27:23.553Z
I had just stumbled upon a similar result by Lewis et al. here: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5397245. Still, it leaves the question whether we can do better than quadratic space using only polynomial time.
Alex ten Brink
CC BY-SA 3.0
2011-10-21T18:12:59.783Z
2011-10-21T18:12:59.783Z
David Eppstein
<p><em>Deterministic</em> CFL’s can be parsed in space $O(\log^2 n)$ and polynomial time (i.e., in $\mathrm{SC}^2$). This is an old result of <a href="http://dl.acm.org/citation.cfm?id=804426" rel="nofollow">Cook</a>. It is an open problem whether nondeterministic CFL’s are also in SC (but this does not say anything about the existence of, say, linear space algorithms).</p>

CC BY-SA 3.0
2011-10-21T17:42:09.137Z
2011-10-21T17:42:09.137Z
Emil Jeřábek
<p>The first half of this answer is nothing more than an efficient ($\log^4(n)$ to $\log^2(n)$) rephrasing of David's answer in complexity theoretic terms.</p>

<p>Context free languages live in the complexity class $LOGCFL.$ This class is equivalently characterized by log depth <a href="http://www.cc.gatech.edu/fac/H.Venkateswaran/pubs/sulogcfl.ps" rel="nofollow">semi-unbounded circuits.</a> These are polynomial sized circuits wherein OR gates have unbounded fan-in and AND gates have bounded fan-in (say 2). By increasing depth by a log factor, we can replace every unbounded fan-in OR gate with bounded fan-in ORs. This put the problem in $NC^2.$ It is not difficult to see how $NC^2$ can be evaluated by a $DSPACE(\log^2(n))$ by say a depth first search that maintains the left/right sequence of children at the gates explored thus far. The result goes back to the Lewis-Hartmanis paper. And while this improves David's space bound,  this can take $n^{\log n}$ time. We do not know any better.</p>

<p>The traditional way to understand time space tradeoff is to use pebble games. There have been a few papers on CYK; a more recent attempt is in the first part of this <a href="http://www.thi.informatik.uni-frankfurt.de/~weinard/Presentations/TimeSpace.pdf" rel="nofollow">presentation</a>. Here it is shown that (a) linear space can be achieved at exponential time and (b) if time is restricted to $O(n^2)$, then CYK would use at least $n^2$ space. </p>

<p>Certainly a very interesting problem worthy of a look.</p>

CC BY-SA 3.0
2011-10-22T10:30:01.047Z
That was quite an interesting presentation, thanks for the link.
Alex ten Brink
CC BY-SA 3.0
2011-10-22T03:49:40.447Z
2011-10-26T23:49:08.787Z
2011-10-26T23:49:08.787Z
V Vinay
<p>There are a multitude of algorithms that can parse a context-free grammar in $O(n^3)$ time. Using matrix multiplication, one can even go asymptotically faster than that.</p>

<p>However, all algorithms for parsing arbitrary CFGs I know have a worst-case space usage of $\Omega(n^2)$ (although, admittedly, I have no idea what the space usage of that matrix multiplication algorithm is). I was wondering whether there are any algorithms that improve upon this space usage (so disregarding the time bound).</p>

<p>The question popped up into my mind after mentally linking $CSG = NDSPACE(n) \subseteq DSPACE(n^2)$ with the $\Omega(n^2)$ space bound on all the CFG parsing algorithms I knew. It's probably of no practical interest, but merely something I'd be interested in knowing.</p>

CC BY-SA 3.0
2011-10-21T17:06:05.547Z
Don't know about all other parsing algorithms, but those based on matrix multiplication do take $\Theta(n^2)$ space; see: http://cstheory.stackexchange.com/questions/1313/space-complexity-of-coppersmithwinograd-algorithm
Ryan Williams
<ds.algorithms><fl.formal-languages><space-bounded><parsing><context-free>
CFG parsing using $o(n^2)$ space
Alex ten Brink
# CFG parsing using $o(n^2)$ space

(Asked by: username_0 on 2011-10-21)

There are a multitude of algorithms that can parse a context-free grammar in $O(n^3)$ time. Using matrix multiplication, one can even go asymptotically faster than that.

However, all algorithms for parsing arbitrary CFGs I know have a worst-case space usage of $\Omega(n^2)$ (although, admittedly, I have no idea what the space usage of that matrix multiplication algorithm is). I was wondering whether there are any algorithms that improve upon this space usage (so disregarding the time bound).

The question popped up into my mind after mentally linking $CSG = NDSPACE(n) \subseteq DSPACE(n^2)$ with the $\Omega(n^2)$ space bound on all the CFG parsing algorithms I knew. It's probably of no practical interest, but merely something I'd be interested in knowing.

**Tags:** ds.algorithms, fl.formal-languages, space-bounded, parsing, context-free
> **Comments:**
> **username_1**: Don't know about all other parsing algorithms, but those based on matrix multiplication do take $\Theta(n^2)$ space; see: http://cstheory.stackexchange.com/questions/1313/space-complexity-of-coppersmithwinograd-algorithm  

---

## 3 answers

### Answer by username_4 on 2011-10-22. Score: 14 | Accepted answer

The first half of this answer is nothing more than an efficient ($\log^4(n)$ to $\log^2(n)$) rephrasing of David's answer in complexity theoretic terms.

Context free languages live in the complexity class $LOGCFL.$ This class is equivalently characterized by log depth [semi-unbounded circuits.](http://www.cc.gatech.edu/fac/H.Venkateswaran/pubs/sulogcfl.ps) These are polynomial sized circuits wherein OR gates have unbounded fan-in and AND gates have bounded fan-in (say 2). By increasing depth by a log factor, we can replace every unbounded fan-in OR gate with bounded fan-in ORs. This put the problem in $NC^2.$ It is not difficult to see how $NC^2$ can be evaluated by a $DSPACE(\log^2(n))$ by say a depth first search that maintains the left/right sequence of children at the gates explored thus far. The result goes back to the Lewis-Hartmanis paper. And while this improves David's space bound, this can take $n^{\log n}$ time. We do not know any better.

The traditional way to understand time space tradeoff is to use pebble games. There have been a few papers on CYK; a more recent attempt is in the first part of this [presentation](http://www.thi.informatik.uni-frankfurt.de/~weinard/Presentations/TimeSpace.pdf). Here it is shown that (a) linear space can be achieved at exponential time and (b) if time is restricted to $O(n^2)$, then CYK would use at least $n^2$ space.

Certainly a very interesting problem worthy of a look.

> **Comments:**
> **username_0**: That was quite an interesting presentation, thanks for the link.  

---

### Answer by username_2 on 2011-10-21. Score: 13

Any context free language can be described by a grammar in Chomsky Normal Form, and then recognized by a nondeterministic algorithm that uses $O(\log^2 n)$ bits of memory: just guess the top-level production ($O(1)$ bits) and the breakpoint in the input string between the two substrings matched by the two sides of the production ($O(\log n)$ bits), recurse on the smaller side, and then continue non-recursively on the larger side.

By Savitch's theorem, it follows that the problem can be solved deterministically with $O(\log^4 n)$ bits of memory. The algorithm resulting from this technique would likely be quite inefficient, however.

> **Comments:**
> **username_0**: I had just stumbled upon a similar result by Lewis et al. here: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5397245. Still, it leaves the question whether we can do better than quadratic space using only polynomial time.  

---

### Answer by username_3 on 2011-10-21. Score: 8

*Deterministic* CFL’s can be parsed in space $O(\log^2 n)$ and polynomial time (i.e., in $\mathrm{SC}^2$). This is an old result of [Cook](http://dl.acm.org/citation.cfm?id=804426). It is an open problem whether nondeterministic CFL’s are also in SC (but this does not say anything about the existence of, say, linear space algorithms).


---

