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