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.
| Identifer | oai:union.ndltd.org:ucf.edu/oai:stars.library.ucf.edu:rtd-6146 |
| Date | 01 January 1988 |
| Creators | Sarkar, Dilip |
| Publisher | University of Central Florida |
| Source Sets | University of Central Florida |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | Retrospective Theses and Dissertations |
| Rights | Public Domain |
Page generated in 0.018 seconds