## A parallel algorithm for context-free parsing

85. R. P. Brent and L. M. Goldschlager,
A parallel algorithm for context-free parsing,
* Australian Computer Science Communications* 6 (1984), 7.1-10.
Abstract:
dvi (3K),
pdf (77K),
ps (28K).

Paper: pdf (602K).

## Abstract

We present an algorithm which solves the parsing problem for any
context-free grammar, and is suitable for execution on a synchronous
computer with unbounded parallelism (formally, we use the SIMDAG model).
The algorithm parses arbitrary
input strings of length *n* in time O(log *n*)
on a unit-cost SIMDAG,
or in time O(log^{2}*n*)
on a log-cost SIMDAG, using O(*n*^{6})
processors in each case.
## Comments

The result shows that context-free language recognition is in
Pippinger's class NC. This result was obtained independently
by Ruzzo
[*J. Computer and System Sciences* 22 (1981), 365-383],
but his proof is rather indirect and his
processor bound is O(*n*^{15}),
so our method of proof is more
likely to be of use in practice.
Our exponent 6 is still
uncomfortably high. In fact it is twice the exponent for
*n* × *n* matrix
multiplication, and can be reduced somewhat using "fast"
matrix multiplication techniques
[Coppersmith and Winograd, * SIAM J. on Computing* 11 (1982),
472-492].

For related papers, see Brent and Kung [55],
Brent and Goldschlager
[64,
72].

Go to next publication

Return to Richard Brent's index page