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(log2n)
on a log-cost SIMDAG, using O(n6)
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(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),
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