Keywords

Multiprocessors, Parallel processing (Electronic computers), Parsing (Computer grammar), Asynchronous bottom-up parsing, Parenthesis-matching parallel algorithm, Block-structured language parsing, Parallel parsing speedup estimation, Cost-optimal parsing (O(log L) time, L/log L processors)

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 pages

Language

English

Rights

Public Domain

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Identifier

DP0022616

Subjects

Parsing (Computer grammar); Parallel algorithms; Parallel processing (Electronic computers)--Mathematics; Parallel processing (Electronic computers)--Mathematical models; Multiprocessors--Evaluation

Accessibility Status

Searchable text

Download

Share

COinS
 

Accessibility Statement

This item was created or digitized prior to April 24, 2026, or is a reproduction of legacy media created before that date. It is preserved in its original, unmodified state specifically for research, reference, or historical recordkeeping. In accordance with the ADA Title II Final Rule, the University Libraries provides accessible versions of archival materials upon request. To request an accommodation for this item, please submit an accessibility request form.