Browse Prior Art Database

An Optimal Parallel Parsing Algorithm for a Class of Block-Structured Languages

IP.com Disclosure Number: IPCOM000128315D
Original Publication Date: 1987-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 17 page(s) / 45K

Publishing Venue

Software Patent Institute

Related People

Dilip Sarkar: AUTHOR [+4]

Abstract

We have designed an 0(log n)-time parallel parsing algorithm for a class of block- structured languages. The model of computation used is CREW PRAM. Digraph of a context-free language is used to define minimum subgram mars such that each of them generates a finite language. A class of context-free, block-structured languages is identified which can be parsed in 0(log n) time. The strings generated by the subgram- mars of these languages are used to determine the number of parentheses to be inserted to the left and right of every terminal of a string to be parsed. After insertion of parentheses, every matched pair of parentheses contains a string that can be parsed in 0(1) time. Using [Equation ommitted] processors insertion of parentheses is com- pleted in 0(log n) time; parenthesis-matching takes [Equation ommitted] time. Length of the string within each matched pair of parentheses is bounded by a constant, when the strings in next higher nested pairs are replaced by nonterminals. Thus, a processor can build the parse subtree for a string within a matched pair of parentheses in 0(1) time; (n / log n) processors can build the parse tree for the input string in 0(log n) time. Index Terms: Context-free grammars, directed graphs, models of parallel computation, parallel compiling, parallel parsing, subgram:rnars of context-free grammars.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 17

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

An Optimal Parallel Parsing Algorithm for a Class of Block-Structured Languages

by

Dilip Sarkar and Narsingh Deo

CS-TR-87 AN OPTIMAL PARALLEL PARSING ALGORITHM FOR A CLASS OF BLOCK- STRUCTURED LANGUAGES

Didp Sa-rkar Narsingh Deo Department of Computer Science University of Central Florida, Orlando, FL 3?816

ABSTRACT

We have designed an 0(log n)-time parallel parsing algorithm for a class of block- structured languages. The model of computation used is CREW PRAM. Digraph of a context-free language is used to define minimum subgram mars such that each of them generates a finite language. A class of context-free, block-structured languages is identified which can be parsed in 0(log n) time. The strings generated by the subgram- mars of these languages are used to determine the number of parentheses to be inserted to the left and right of every terminal of a string to be parsed. After insertion of parentheses, every matched pair of parentheses contains a string that can be parsed in 0(1) time. Using

(Equation Omitted)

processors insertion of parentheses is com- pleted in 0(log n) time; parenthesis-matching takes

(Equation Omitted)

time. Length of the string within each matched pair of parentheses is bounded by a constant, when the strings in next higher nested pairs are replaced by nonterminals. Thus, a processor can build the parse subtree for a string within a matched pair of parentheses in 0(1) time; (n / log n) processors can build the parse tree for the input string in 0(log n) time.

Index Terms: Context-free grammars, directed graphs, models of parallel computation, parallel compiling, parallel parsing, subgram:rnars of context-free grammars.

1. INTRODUCTION

The demand for fast computation and the limitation on the speed of computation with a single processor have motivated researchers to investigate parallel computa-tion. In last ten years, a good deal of work has been reported on parallel algorithms in various application areas; the problem of designing programming languages for parallel computers and the problem of generating effiCient object code for them have received much attention. However, the amount of

University of Central Florida Page 1 Dec 31, 1987

Page 2 of 17

An Optimal Parallel Parsing Algorithm for a Class of Block-Structured Languages

work reported on developing efficient com-pilers to run on parallel machines is relatively meager (see Section 11).

Two complementary aspects in the design of parallel compilers are: (1) pipelining different sequential processes (viz. scanning, parsing, etc.) [5]; and (2) parallelization inside each process [3, 4. 7. 8, 13, 14, 18, 19, 21]. In this paper we consider the latter approach for parsing. Parallel parsing is composed of two phases: partitioning of the input string among the processors and parsing concurrently with the processors. The simple regular-interval partitioning method divides the string into substri...