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.
Paper: pdf (602K).
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(log2n)
on a log-cost SIMDAG, using O(n6)
processors in each case.
The result shows that context-free language recognition is in
Pippinger's class NC. This result was obtained independently
[J. Computer and System Sciences 22 (1981), 365-383],
but his proof is rather indirect and his
processor bound is O(n15),
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),
For related papers, see Brent and Kung ,
Brent and Goldschlager
Go to next publication
Return to Richard Brent's index page