Keywords

Multiprocessors; Parallel processing (Electronic computers); Parsing (Computer grammar)

Abstract

Parsing in a multiprocessor environment is considered. Two models for asynchronous bottom-up parallel parsing are presented. A method for estimating speedup in asynchronous bottom-up parallel parsing is developed, and it is used to estimate speedup obtainable by bottom-up parallel parsing of Pascal-like languages. It is found that bottom-up parallel parsing algorithms can attain a maximum speedup of 0 (L1/2) with (L1/2) processors, where L is the number of tokens in the string being parsed. Hence, bottom-up parallel parsing technique does not yield good speedup. A new parsing technique is proposed for parsing a class of block-structured languages. The novelty of the technique is that it is inherently parallel. By applying this new technique, a string of L tokens can be parsed in O (log L) time with (L /log L) processors. The parsing algorithm uses a parenthesis-matching algorithm developed here. The parenthesis-matching algorithm can find matching of a sequence of parentheses in O (log L) time with (L /log L) processors. Thus, the new parsing algorithm is cost optimal.

Notes

If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

Graduation Date

1988

Semester

Spring

Advisor

Deo, Narsingh

Degree

Doctor of Philosophy (Ph.D.)

College

College of Arts and Sciences

Degree Program

Computer Science

Format

PDF

Pages

96 p.

Language

English

Rights

Public Domain

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Identifier

DP0022616

Accessibility Status

Searchable text

Download

Share

COinS