Amamiya, Makoto; Mine, Tsunenori 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 Keywords:parallel-random access machine; directed acyclic graph; parallel parsing algorithm; context-free grammars PDFBibTeX XMLCite \textit{M. Amamiya} and \textit{T. Mine}, Front. Artif. Intell. Appl. 10, 351--367 (1991; Zbl 0862.68058)