A PARALLEL ALGORITHM FOR CONTEXT-FREE PARSING

RICHARD P. BRENT AND LESLIE M. GOLDSCHLAGER

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. 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. (A SIMDAG is a model of a synchronous parallel machine [3].)

Comments

Only the Abstract is given here. The full paper appeared as [1]. The result shows that contextfree language recognition is in Pippinger’s class NC. This result was obtained independently by Ruzzo [4], 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, and can be reduced somewhat using “fast” matrix multiplication techniques [2].

References

1. R. P. Brent and L. M. Goldschlager, “A parallel algorithm for context-free parsing”, Proc. Seventh Australian Computer Science Conference, special issue of Australian Computer Science Communications 6 (1984), 7.1–7.10. Also appeared as Report CMA-R50-83, CMA, ANU, 1983, 11 pp. rpb085.

2. D. Coppersmith and S. Winograd, “On the asymptotic complexity of matrix multiplication”, SIAM J. on Computing 11 (1982), 472–492.

3. L. M. Goldschlager, “A universal interconnection pattern for parallel computers”, J. ACM 29 (1982), 1073–1086.

4. W. L. Ruzzo, “On uniform circuit complexity”, J. Computer and System Sciences 22 (1981), 365–383.

(Brent) Centre for Mathematical Analysis, Australian National University, Canberra

(Goldschlager) Department of Computer Science, University of Sydney, Sydney, NSW 2006, Australia

1991 Mathematics Subject Classification. Primary 68Q15; Secondary 68M07, 68Q22, 68Q25, 68Q35, 68Q52.

Key words and phrases. Context-free language recognition, parsing, NC, polylog time, parallel computation, models of computation, SIMDAG.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1984, Australian Computer Science Communications.

Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb085a typeset using AMS-L^{A}TEX