## Parallel Parsing of Context-Free Languages on an Array of Processors

##### Abstract

Kosaraju [Kosaraju 69] and independently ten years later, Guibas, Kung and
Thompson [Guibas 79] devised an algorithm (K-GKT) for solving on an array of
processors a class of dynamic programming problems of which general context-free
language (CFL) recognition is a member. I introduce an extension to K-GKT
which allows parsing as well as recognition. The basic idea of the extension is to
add counters to the processors. These act as pointers to other processors. The
extended algorithm consists of three phases which I call the recognition phase, the
marking phase and the parse output phase. I first consider the case of unambiguous
grammars. I show that in that case, the algorithm has O(n2log n) space complexity
and a linear time complexity. To obtain these results I rely on a counter implementation
that allows the execution in constant time of each of the operations:
set to zero, test if zero, increment by 1 and decrement by 1. I provide a proof of
correctness of this implementation. I introduce the concept of efficient grammars.
One factor in the multiplicative constant hidden behind the O(n2log n) space complexity
measure for the algorithm is related to the number of non-terminals in the
(unambiguous) grammar used. I say that a grammar is k-efficient if it allows the
processors to store not more than k pointer pairs. I call a 1-efficient grammar an
efficient grammar. I show that two properties that I call nt-disjunction and rhsdasjunction
together with unambiguity are sufficient but not necessary conditions
for grammar efficiency. I also show that unambiguity itself is not a necessary condition
for efficiency. I then consider the case of ambiguous grammars. I present
two methods for outputting multiple parses. Both output each parse in linear time.
One method has O(n3log n) space complexity while the other has O(n2log n) space
complexity. I then address the issue of problem decomposition. I show how part of
my extension can be adapted, using a standard technique, to process inputs that
would be too large for an array of some fixed size. I then discuss briefly some issues
related to implementation. I report on an actual implementation on the I.C.L.
DAP. Finally, I show how another systolic CFL parsing algorithm, by Chang,
Ibarra and Palis [Chang 87], can be generalized to output parses in preorder and
inorder.