Title

Optimal Parallel Parsing Algorithm For A Class Of Block-Structured Languages.

Abstract

A parallel parsing technique is presented in which parentheses are inserted in the string to be parsed for a syntax-directed partitioning. An O(log n)-time parallel parsing algorithm for a class of block-structured context-free languages is presented. The computation model is a concurrent-read, exclusive-write, parallel random-access machine. The digraph of a context-free grammar is used to define minimum subgrammars such that each subgrammar generates a finite language. The strings of these subgrammars are used to determine the number of parentheses to be inserted to the left and right of every terminal in the string to be parsed.

Publication Date

12-1-1987

Publication Title

Proceedings of the International Conference on Parallel Processing

Number of Pages

585-588

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

Socpus ID

0023591743 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0023591743

This document is currently not available here.

Share

COinS