×

An \(O(n)\) time and \(O(n^ 2)\) processors parallel parsing algorithm for context-free grammars. (English) Zbl 0862.68058

Jaakkola, Hannu (ed.) et al., Advances in information modelling and knowledge bases. Amsterdam etc.: IOS Press. Front. Artif. Intell. Appl. 10, 351-367 (1991).
Summary: This paper proposes an efficient parallel parsing algorithm for general context-free grammars. In the proposed algorithm, any sentence of length \(n\) is parsed in \(O(n)\) time by using \(O(n^2)\) processors and memory spaces. The algorithm uses a modified LR transition diagram, which manages a direct state transition from reducing action states. Using this LR transition diagram, \(O(n^2)\) processors perform shift and reducing actions concurrently. This algorithm uses DAG (directed acyclic graph) to implement stacks. A processor is assigned to each DAG node. Redundant processors which have the same DAG node are not activated to reduce the number of processors into \(O(n^2)\). All processors act asynchronously on P-RAM (parallel-random access machine).
For the entire collection see [Zbl 0853.00019].

MSC:

68W15 Distributed algorithms
68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite