25 Oct 90 00:42:59 GMT

Related articles |
---|

SUMMARY: Parallel Parsing chou@CS.UCLA.EDU (1990-10-25) |

Newsgroups: | comp.parallel,comp.compilers |

From: | chou@CS.UCLA.EDU (Ching-Tsun Chou) |

Keywords: | parallel, bibliography, parse |

Organization: | UCLA Computer Science Department |

Date: | 25 Oct 90 00:42:59 GMT |

Some time ago I posted an article on USENET asking about references on

parallel parsing. Since then I have received a lot of responses.

Here's a summary. I have edited the messages a little to save space;

I hope no one would accuse me of destroying his or her beautiful writing. :-)

My sincere thanks to all who responded.

- Ching Tsun <chou@cs.ucla.edu>

--------------------------------------------------------------------------------

Reply-To: pratt@cs.stanford.edu

The fastest way I know to do CF parsing is with Valiant's CF parser. It

works by recursively computing transitive closures of nxn Boolean matrices.

Both its sequential and concurrent running times are the same as for

transitive closure. The best concurrent transitive closure algorithm

I know is O(log^2 n), hence this is the best I know for the concurrent

implementation of Valiant's algorithm. I can't find a pointer to the

literature right now, but it appeared somewhere around 1974-5.

Vaughan Pratt

Reply-To: parker@vienna.njit.edu (Bruce Parker)

The only work I know of is the brief description given by

Karp and Ramachandran [1]. They show how to apply a result of

Miller, Ramachandran, and Kaltofen [2] that yields an AC^1

algorithm for the problem of deciding whether a given string

is in the language generated by a given CFG in CNF. Since

AC^1 (= NC^2, this yields an O(lg^2 n) time, polynomial processor

solution. I don't know about lower bounds.

[1] Karp, Richard, and Vijaya Ramachandran, ``A survey of

parallel algorithms for shared-memory machines'',

Technical Report UCB/CSD 88/408. It costs five dollars

from the Publications Office, Computer Science Division

Publications, UC, Berkeley, CA 94720. It will also

appear as a chapter in ``Handbook of Theoretical

Computer Science'', MIT Press, price: $135 (ouch!)

[2] Miller, G. L., V. Ramachandran, and E. Kaltofen,

``Efficient parallel evaluation of striaght-line code

and arithmetic circuits'', SIAM J Computing, vol. 17,

1988, pp. 687-695.

Reply-To: lee@cs.rutgers.edu

Contact Dr. David Skillicorn at Queen's Univ., Kingston, Canada.

He maintains a bibliograph on parallel compilation which does include

a lot of references to parallel parsing.

He can be reached thru e-mail address: "skill@quics.queensu.ca".

Good luck.

Yong-fong

Reply-To: forstall@madrone.Berkeley.EDU (Bruce T. Forstall)

Here's a local database dump:

1. J. Chen and S. Kolodner,

Estimating the Speedup in Parallel Parsing, IEEE Transactions on

Software Engineering SE-11,1 (January 1985), 114-124.

2. Ilan Bar-on and Uzi Vishkin,

Optimal Parallel Generation of a Computation Tree Form, ACM

Transactions on Programming Languages and Systems 7,2 (April 1985),

348-357.

[%K] performance, theory, parallel algorithms, optimal speed-ups,

parsing

3. Y. Matsumoto,

"A PARALLEL PARSING ALGORITHM AND ITS COMPLEXITY", TM-0215, Institute

for New Generation Computer Technology, 1986. Extended abstract (8th

August 1986).

[%W] SU lib. #107292

4. W. Rytter,

"ON THE COMPLEXITY OF PARALLEL PARSING OF GENERAL CONTEXT-FREE

LANGUAGES", 75, University of Warwick, Department of Computer

Science, 1986.

[%W] SU lib. #105721

5. W. Rytter and R. Giancarlo,

"OPTIMAL PARALLEL PARSING OF BRACKET LANGUAGES", 85, University of

Warwick, Department of Computer Science, 1985.

[%W] SU lib. #105729

6. L. Langlois,

"PARALLEL PARSING ON AN ARRAY OF PROCESSORS", CSR-200-86, University

of Edinburgh, Department of Computer Science, 1986.

[%W] SU lib. #106946

7. Y. Matsumoto,

"PARSING GAPPING GRAMMARS IN PARALLEL", TR-318, Institute for New

Generation Computer Technology, 1987.

[%W] SU lib. #110113

8. O. H. Ibarra, T.-C. Pong and S. M. Sohn,

"PARALLEL PARSING ON THE HYPERCUBE", TR 88-23, University of

Minnesota, Computer Science Department, 1988.

[%W] SU lib. #112515

Reply-To: Bjorn Ellertsson <bje@math.ucla.edu>

Here are some refs that I have handy; I do

have some more but I cannot find them right now!

Bjorn

========

%A Fatemah Abdollahzadeh

%A Medhi Badii

%A D. J. Cooke

%T A New Grammar for Arithmetic Expressions in

a Parallel Processing Environment

%J Proceedings of the 1986 International Conference on Parallel Processing

%I IEEE

%D August 1986

%P 75-83

%K Mathematical analysis and computation, ambiguous context free grammars,

context sensitive grammars, phrase structure grammar, parsing,

%A Francois Baccelli

%A Thierry Fleury

%Z INRIA

%T On Parsing Arithmetic Expressions in a Multiprocessor Environment

%J Acta Informatica

%V 17

%D 1982

%P 287-310

%A Duane A. Bailey

%A Janice E. Cuny

%Z U Mass.

%T An Efficient Embedding of Large Trees in Processor Grids

%J Proceedings of the 1986 International Conference on Parallel Processing

%I IEEE

%D August 1986

%P 819-822

%K Multigrid/mesh applications, CHiP, shape grammars, interconnection,

%A Ilan Bar-On

%A Uzi Vishkin

%T Optimal Parallel Generation of a Computation Tree Form

%J ACM Transactions on Programming Languages and Systems

%I ACM

%V 7

%N 2

%D April 1985

%P 348-357

%K Parallel algorithms, optimal speed-ups, parsing

Ultracomputer,

%X An earlier version appears in ICPP 84 (from an Ultracomputer note).

%A Jik H. Chang

%A Oscar H. Ibarra

%A Michael A. Palis

%Z U Mn and U Penn

%T Parallel Parsing on a One-Way Array of Finite-State Machines

%J Proceedings of the 1986 International Conference on Parallel Processing

%I IEEE

%D August 1986

%P 887-894

%K Parallel processing techniques, string searching,

Cocke-Younger-Kasami (CYK) algorithm,

2-D iterative array of finite state machines,

%A N. S. Chang

%A K. S. Fu

%T A Study on Parallel Parsing of Tree Languages and its Application to

Syntactic Pattern Recognition

%E Morio Onoe

%E Kendall Preston, Jr.

%E Azriel Rosenfeld

%B Real-Time/Parallel Computing: Image Analysis

%I Plenum Press

%C New York, NY

%D 1981

%P 107-129

%X A simulation study for languages processing Landsat image processing

data. ECTA (Error Correcting Tree Automaton) is the basic tree language

model.

%A J. Chen

%A S. Kolodner

%T Estimating the Speedup in Parallel Parsing

%J IEEE Transactions on Software Engineering

%V SE-11

%N 1

%P 114-124

%D January 1985

%X Not to be confused with Sarkar and Deo's paper in ICPP 86.

%A J. Cohen

%A T. Hickey

%A J. Katcoff

%T Upper Bounds for Speedup in Parallel Parsing

%J Journal of the ACM

%V 29

%D 1982

%P 408-428

%T Parallel Generation of Postfix and Tree Forms

%A Eliezer Dekel

%A Sartaj Sahni

%J ACM Transactions on Programming Languages and Systems

%V 5

%N 3

%D July 1983

%P 300-317

%K Algorithms, arithmetic expressions, postfix, infix, tree form, parallel

computing, complexity

Categories: D.3.4 [Programming Languages]: processors - parsing

%A M. Fanty

%T Context-free Parsing in Connectionist Networks

%I University of Rochester Computer Science Department

%D NOV 1985

%R TR 174

%K H03 O06

%X algorithm to convert any context-free grammar into a connectionist

network

.br

30 pages $1.25

%A M. Feilmeier

%A G. Segerer

%T Numerical Stability in Parallel Evaluation of Arithmetic Expressions

%B Parallel Computers, Parallel Mathematics

%E M. Feilmeier

%I North-Holland

%D 1977

%P 107-112

%K parsing,

parallel algorithms

%X A further exposition of the ideas of Winograd's JACM "Parallel Evaluation"

paper 75.

%A Charles N. Fischer

%T On Parsing Context-free Languages in Parallel Environments

%R TR 75-237, PhD dissertation

%I CS Dept., Cornell Univ.

%C Ithaca, NY

%D 1975

%A Charles N. Fischer

%T On Parsing and Compiling Arithmetic Expressions on Vector Computers

%J ACM Transactions on Programming Languages and Systems

%V 2

%N 2

%D April 1980

%P 203-224

%K Vector parsing, vector compiling, arithmetic infix expressions, vector

computers

CR Categories: 4.12, 5.23, 5.25

%A Joseph A. Fisher

%A John R. Ellis

%A John C. Ruttenberg

%A Alexandru Nicolau

%T Parallel Processing: A Smart Compiler and a Dumb Machine

%J Proc. SIGPLAN '84 Symposium on Compiler Construction, SIGPLAN Notices

%I ACM

%V 19

%N 6

%D June 1984

%P 37-47

%K very long instruction word (VLIW), enormously long instruction (ELI),

trace scheduling,

%X Yet another paper on the parsing of the Yale ELI machine.

%A N. M. Gafter

%T Algorithms and Data Structures for Parallel Incremental Parsing

%J Proceedings of the 1987 International Conference on Parallel

Processing

%I IEEE

%D August 1987

%P 577-584

%K Compiler Techniques

%A Raghavendra Rao Loka

%T A Note on Parallel Parsing

%J SIGPLAN Notices

%I ACM

%V 19

%N 7

%D July 1984

%P 22-24

%A Yuji Matsumoto

%T A Parallel Parsing System for Natural Language Analysis

%I ICOT

%C Tokyo, Japan

%R TR-146

%D November 1985

%A M. Dennis Mickunas

%A Richard M. Schell

%T Parallel Compilation in a Multiprocessor Environment

%J Proc. ACM Annual Conference

%D 1978

%P 241-246

%K Parallel LP parser (PLR),

%X Extended abstract.

%A D. E. Oldfield

%T Document Abstracting on the Distributed Array Processor

%E D. J. Paddon

%B Supercomputers and Parallel Computation

%I Clarendon Press

%C Oxford, England

%D 1984

%P 135-146

%K Parsing, linguistics, SIMD, text reduction, syntax analysis, DAP

%X PhD thesis work. Did not quite reach the level of text quality

as analysed in SISD tools such as those found in the Writer's WorkBench.

%A C. V. Ramamoorthy

%A Juong H. Park

%A Hon F. Li

%T Compilation Techniques for Recognition of Parallel Processable Tasks in

Arithmetic Expressions

%J IEEE Transactions on Computers

%V C-22

%N 11

%D November 1973

%P 986-998

%K Explicit approach, implicit approach, maximum parallel form,

parallelism, parse tree, Polish string, recursion, "well formation."

%K Computer systems

%A Chuck Rieger

%A Steve Small

%T Toward a Theory of Distributed Word Expert Natural Language Parsing

%J IEEE Transactions on Systems, Man, and Cybernetics

%V SMC-11

%N 1

%D January 1981

%P 43-51

%K ai, distributed problem solving

%A D. Sarkar

%A N. Deo

%T An Optimal Parallel Parsing Algorithm for a Class of Block

Structured languages

%J Proceedings of the 1987 International Conference on Parallel Processing

%I IEEE

%D August 1987

%P 585-588

%K Compiler Techniques

%A Dilip Sarkar

%A Narsingh Deo

%T Estimating the Speedup in Parsing

%I Washington State University

%C Pullman, Washington

%d May 1985

%D January 1986 (revised)

%R CS-85-135

%A Dilip Sarkar

%A Narsingh Deo

%Z Wash. State U.

%T Estimating Speedup in Parallel Parsing

%J Proceedings of the 1986 International Conference on Parallel Processing

%I IEEE

%D August 1986

%P 157-163

%K Parallel processing languages, compilers, parallelism, parsing,

model, parallel algorithm,

%X I should fill this commentary with descriptions of model A and model B.

Not to be confuse with Chen and Kolodner's paper in IEEE TSE, Jan. 1985.

%A B. Selman

%A G. Hirst

%T A rule-based connectionist parsing system

%R TR

%I Department of Computer Science, University of Toronto

%D March 1985

%A S. L. Small

%A G. W. Cottrell

%A L. Shastri

%T Toward connectionist parsing

%J Proc., AAAI-82

%C Pittsburgh, PA

%D August 1982

%A Y. N. Srikant

%T Parallel Parsing of Arithmetic Expressions

%J Proceedings of the 1987 International Conference on Parallel

Processing

%I IEEE

%D August 1987

%P 589-591

%K Compiler Techniques

%A Y. N. Srikant

%A Priti Shankar

%T A new Parallel algorithm for parsing arithmetic infix expressions

%J Parallel Computing

%V 4

%N 3

%D June 1987

%P 291-304

%K Arithmetic infix expression, parse tree, SIMD computer, parallel

parsing algorithm, parallel programming, parallel code generation

%A Ross A. Towle

%A Richard P. Brent

%T On the time required to parse an arithmetic expression for parallel

processing

%J Proceedings of the 1976 International Conference on Parallel Processing

%D August 1976

%I IEEE

%P 254

%K

Language issues

%A D. L. Waltz

%A J. B. Pollack

%T Massively parallel parsing: A strongly

interactive model of natural language interpretation

%J Cognitive Science

%V 9

%P 51-74

%D 1985

Reply-To: rekers@cwi.nl (Jan Rekers)

Anton Nijholt made quite a study of parallel parsing algorithms. I have here

three reports of him which all cover the subject.

The best reference is maybe:

R. op den Akker, H. Albas, A, Nijholt & P. Oude Luttighuis

An annotated Bibliography on Parallel Parsing

Memoranda Informatica 89-67, 1989

University of Twente, Dept. of Computer Science

P.O. box 217

7500 AE Enschede

the Netherlands

Anton Nijholt can be reached by email: anijholt@utwente.nl

Good luck!

Reply-To: ichiyosh@icot.or.jp (Ichiyoshi Nobuyuki)

The following is an implementation of chart parsing in a committed

choice logic programming language.

\bibitem{PAX}

Y.~Matsumoto.

\newblock A parallel parsing system for natural language analysis.

\newblock In {\em Proceedings of the Third International Conference on Logic

Programming}, pages 396--409. Springer-Verlag, 1987.

\newblock Lecture Notes on Computer Science 225.

Reply-To: scott@cs.rochester.edu

| [Ned Irons told me over 10 years ago that he looked at it and didn't find

| much that he could speed up. Perhaps someone has had more luck since. -John]

Yes, indeed.

Neal Gafter, a recent Ph.D. graduate from Rochester (now at TI in Austin),

was able in his thesis to demonstrate the feasibility of parallelizing

each of the individual phases of a conventional compiler, including

parsing. As a matter of fact, he demonstrated the feasibility of parallel

incremental compilation, of which conventional compilation is just a

special case. An early discussion of his parsing algorithms can be found

in the proceedings of the 1987 ICPP (pp. 577-584). Full details appear

in his dissertation, available as UR CS TR 349. Shipping cost is $4.00.

To obtain a copy, send e-mail to tr@cs.rochester.edu, or U.S. mail to

TR Librarian, Computer Science Dept., Univ. of Rochester, Rochester, NY

14627.

Reply-To: gaudiot%priam.usc.edu@usc.edu (Jean-Luc Gaudiot)

Parallel Parsing of Context Free Languages.

I found an interesting algorithm in the following book:

Efficient Parallel Algorithms

Alan Gibbons and Wojciech Rytter

Cambridge University Press

Reply-To: Ed Kornkven <kornkven@cs.uiuc.edu>

I am aware of a thesis by Richard M. Schell at the University of Illinois

entitled "Methods for Constructing Parallel Compilers for Use in a

Multiprocessor Environment".

Reply-To: hoover@cs.UAlberta.CA (Jim Hoover)

You wouldn't know it from the title, but Larry Ruzzo's paper:

Walter L. Ruzzo, "Tree-Size Bounded Alternation", J. Computer and System

Sciences, 21, 1980, pp 218-235.

shows that CFL recognition can be done in O(log n)^2 time with a polynomial

number of processors. There may be an efficient parser lurking in the proofs.

Reply-To: skill@qucis.queensu.ca (David Skillicorn)

Perhaps I can save some time by responding to Chou's (chou@cs.ucla.edu)

request about parallel parsing directly.

There has indeed been a great deal of work in parallel parsing and

in parallel execution of other phases of compilation as well. Here is

a brief overview:

Parallel lexing: this is well understood. A log time (i.e. time logarithmic

in the length of the input) algorithm was discovered by Schell and

implemented and popularised by Hillis and Steele. It is very generally

applicable.

Parallel parsing: this has been studied by practitioners and theoreticians.

Many results are known. CFL can be parsed in polylog time using an

impractical number of processors. Subclasses can be parsed on a linear

number of processors in polylog time -- many such subclasses are known.

Their mutual inclusions and the largest such subclass are not known.

Deterministic CFL can be practically parsed in log time with reasonable

numbers of processors -- pathological examples will take much longer.

Semantic analysis: this is well understood for moderately parallel

architectures (work by Wortman et al., Vandevoorde). Some attempts

to attack it using attribute grammars have been tried (see Paris WAGA

proceedings). No results using large scale parallelism.

Optimization: some work using moderate parallelism.

Parallelizing parsing will obviously not make a dramatic difference

to compiler performance by itself because it's a small part of where

the time goes. People began with it because it's formally understood.

In any case, a parallel compiler wouldn't sensibly have a sequential

parser, so something had to be done.

The opportunities for speeding up compilation lie mainly in the later

phases, particularly optimization which is becoming steadily more

important. There are many opportunities for research here.

David Barnard and I maintain an electronic mailing list at Queen's.

If you want to be added to the list, send your physical and email

address to compile-request@qucis.queensu.ca. To send a message to the

list, post to compile@qucis.queensu.ca.

We also maintain an on-line bibliography on parallel compilation which

you may want if you'd like to read about work in the area. It's in

BiBTeX format. To request a copy send me email (skill@qucis.queensu.ca).

We invite all researchers in the area to tell us when they publish a

paper or tech report that's relevant.

The first Workshop on Parallel Compilation took place last May. Proceedings

may be obtained by sending $C15 to:

Heather Ball

Rm 215 Richardson Hall

Queen's University

Kingston Ontario

Canada K7L 3N6

A pro forma invoice may be requested from heather@qucis.queensu.ca for

those who need it.

We have recently completed a survey paper on the whole area of parallel

compilation. It will be available in the Queen's tech report series.

I'll post a further note when it's available.

Reply-To: cmk@ulysses.att.com

I have a collection of references on exactly this topic and I also

have submitted a new paper on this for the 2nd Intl Conf on Parsing

Technologies. If you are interested, let me know.

Reply-To: drk@cs.washington.edu

There is a Thinking Machines Tech Report on parsing using the CM-2.

NL-87-1

Context-Free PArsing on the Connection Machine (tm) System.

Reply-To: raman@cs.rochester.edu

Hi, you might consider the following references:

tan % lookup

context parallel

1986 ICALP Dymond & Ruzzo, Parallel RAMs with Owned Global Memory a

nd Deterministic Context-Free Language Recognition

1989 81 INFCTRL Gibbons & Rytter, Optimal Parallel Algorithms for Dynami

c Expression Evaluation and Context-Free Recognition

1987 73 INFCTRL Rytter, Parallel Time O(log n) Recognition of Unambiguou

s Context-free Languages

1981 13 IPL Nakamura & Aizawa, Acceptors for Isometric Parallel Cont

ext-Free Array Languages

1978 SICOMP Hunt & Rosenkrantz, Computational Parallels Between the

Regular and Context-Free Languages

1974 STOC Hunt & Rosenkrantz, Computational Parallels Between the

Regular and Context-Free Languages

1986 47 TCS Rytter, On the Complexity of Parallel Parsing of General

Context-free Languages (Note)

1975 TR Fischer, On Parsing Context Free Languages in Parallel E

nvironments (thesis)

------

Thanks are due to Joel Seiferas's on-line data base for local U of R usage.

Reply-To: palis@linc.cis.upenn.edu (Michael Palis)

There has been considerable research on parallel parsing algorithms for

general context-free languages, both by myself and other researchers.

Here's a list:

S. R. Kosaraju, "Speed of Recognition of Context-Free Languages by

Array Automata", SIAM Journal on Computing, 4:3 (1975), pp. 331-340.

Y. Chiang and K. S. Fu, "Parallel Parsing and VLSI Implementations

for Syntactic Pattern Recognition", IEEE Transactions on Pattern

Analysis and Machine Intelligence, 6:3 (1984), pp. 302-313.

J. H. Chang, O. H. Ibarra, and M. A. Palis, "Parallel Parsing on a

One-Way Array of Finite-State Machines", Proc. International Conference

on Parallel Processing, Chicago, Illinois, August 1986. Also appeared

in IEEE Transactions on Computers, C-36:1 (Jan. 1987), pp. 64-75.

O. H. Ibarra and M. A. Palis, "An Efficient All-Parses Systolic Algorithm

for General Context-Free Parsing", Proc. 1989 Workshop on Algorithms and

Data Structures, Ottawa, Canada, August 1989. Also to appear in

International Journal on Parallel Programming.

I have also done considerable work on parallel parsing algorithms for

more powerful grammars than CFGs, particularly those that are used

in natural language processing. Here's a list:

M. A. Palis and S. Shende, "Sublinear Parallel Time Recognition of Tree

Adjoining Languages", Proc. 1989 International Conference on Parallel

Processing, Chicago, Illinois, August 1989.

M. A. Palis, S. Shende, and D. Wei, "An Optimal Linear-Time Parallel Parser

for Tree Adjoining Languages", SIAM Journal on Computing, 19:1 (February 1990),

pp. 1-31.

M. A. Palis, S. Shende and D. Wei, "New Directions in Systolic Parsing",

Proc. 1989 International Conference on Systolic Arrays, Ireland, May 1989.

M. A. Palis and S. Shende, "Upper Bounds on Recognition of a Hierarchy of

Non-Context-Free Languages", to appear in Theoretical Computer Science. Also

Tech. Rpt. MS-CIS-88-56, Dept. of Comp. and Info. Science, Univ. of

Pennsylvania, July 1988.

We are currently implementing the parallel parser for tree adjoining

grammars on the Connection Machine. The paper is in preparation.

If you wish, I can send you copies of selected papers.

Reply-To: pnk@cs.brown.edu (Philip N. Klein)

CFL recognition was first shown to be in NC in

W. Ruzzo, "Tree-size bounded alternation," J. Comput. System Sci 21

(1980), pp. 218-235.

It can also be solved using the techniques of

L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff, "Fast parallel

computation of polynomials using few processors."

For the special case of deterministic CFL's, one can do slightly

better:

Philip N. Klein and John H. Reif, ``Parallel time O(log n)

acceptance of deterministic CFLs on an exclusive-write P-RAM,''

SIAM Journal on Computing, June 1988, pp. 463-485.

The algorithms cited above can be modified to obtain parse trees. In

unpublished work, I showed that the dCFL algorithm can be modified to

take O(log^2 n) time but using only n^2 log n processors.

Reply-To: Edoardo Biagioni <biagioni@cs.unc.edu>

Charles Fischer's 1975 dissertation at Cornell addresses the issue of

parallel parsing in general, though it starts out with simpler grammar

models than unrestricted context-free languages. He uses APL to express

the parallelism. I have found the work quite interesting and general.

Reply-To: ken@tucana.csis.dit.csiro.au

My colleague Neal Gafter did a thesis on parallel compilation. You can

get his thesis as a TR from the U of Rochester. Mail peg@cs.rochester.edu

for pricing.

Reply-To: skill@qucis.queensu.ca (David Skillicorn)

The electronic bibliography is at the end of this message.

--------------------8<--------------------------------------

@INPROCEEDINGS{appel,

AUTHOR = {Andrew W. Appel and John R. Ellis and Kai Li},

TITLE = {Real-time Concurrent Collection on Stock

Multiprocessors},

BOOKTITLE = {Proceedings ACM SIGPLAN '88 Conference on Programming Language

Design and Implementation},

PAGES = {11--20},

KEYWORDS = {compilers parallel garbage collection},

month = {July},

year = {1988},

*}*

@INPROCEEDINGS{seshadri1,

AUTHOR = {V. Seshadri and D. B. Wortman and M. D. Junkin and S.

Weber and C. P. Yu and I. Small},

TITLE = {Semantic Analysis in a Concurrent Compiler},

BOOKTITLE = {Proceedings ACM SIGPLAN '88 Conference on Programming Language

Design and Implementation},

PAGES = {233--240},

KEYWORDS = {compilers semantic analysis parallel compilers},

month = {July},

year = {1988},

*}*

@techreport{vandevoorde,

AUTHOR = {Mark Thierry Vandevoorde},

TITLE = {Parallel Compilation on a Tightly Coupled

Multiprocessor},

institution = {DEC report SRC TR-546},

PAGES = {87},

year = {1987},

KEYWORDS = {compilers parallel},

*}*

@TECHREPORT{boehm,

AUTHOR = {H-.J. Boehm and W. Zwaenepoel},

TITLE = {Parallel Attribute Grammar Evaluation},

institution = {Rice University Computer Science Technical Report

TR87--55},

YEAR = {1987},

MONTH = {June},

*}*

@ARTICLE{cohen:kolodner,

AUTHOR = {J. Cohen and S. Kolodner},

TITLE = {Estimating the Speedup in Parallel Parsing},

JOURNAL = {IEEE Transactions of Software Engineering},

VOLUME = {SE-11, No.1},

PAGES = {114--124},

YEAR = {1985},

MONTH = {January},

*}*

@ARTICLE{cohen:katcoff,

AUTHOR = {Jacques Cohen and Timothy Hickey and Joel Katcoff},

TITLE = {Upper bounds for speedup in parallel parsing},

JOURNAL = {Journal of the {ACM}},

VOLUME = {29},

number = {2},

YEAR = {1982},

*}*

@techreport{fanty,

AUTHOR = {M. Fanty},

TITLE = {Context-Free Parsing in Connectionist Networks},

institution = {Department of Computer Science, University of Rochester,

TR-174},

YEAR = {1985},

MONTH = {November},

*}*

@phdthesis{fischer1979,

AUTHOR = {Charles N. Fischer},

TITLE = {On Parsing Context-Free Languages in Parallel

Environments},

school = {Cornell University},

YEAR = {1975},

*}*

@ARTICLE{ghezzi,

AUTHOR = {Carlo Ghezzi and Dino Mandriolli},

TITLE = {Incremental parsing},

JOURNAL = {ACM Transactions on Programming Languages and

Systems},

VOLUME = {1,No.1},

YEAR = {1979},

MONTH = {July},

*}*

@book{hillis:connection,

AUTHOR = {W.D. Hillis},

TITLE = {The Connection Machine},

publisher = {MIT Press},

ADDRESS = {Cambridge, Mass},

YEAR = {1985},

*}*

@ARTICLE{hillis:steele,

AUTHOR = {W. Daniel Hillis and G.L. Steele},

TITLE = {Data Parallel Algorithms},

JOURNAL = {Communications of the ACM},

VOLUME = {29, No.12},

PAGES = {1170--1183},

YEAR = {1986},

MONTH = {December},

*}*

@ARTICLE{kastens,

AUTHOR = {U. Kastens},

TITLE = {Ordered Attribute Grammars},

JOURNAL = {Acta Informatica},

VOLUME = {13},

PAGES = {257--268},

YEAR = {1980},

*}*

@techreport{langlois,

AUTHOR = {L. Langlois},

TITLE = {Parallel Parsing on an Array of Processors},

institution = {University of Edinburgh, Department of Computer Science},

YEAR = {1986},

MONTH = {July},

*}*

@techreport{ligett,

AUTHOR = {D. Ligett and G. McCluskey and W. M. McKeeman},

TITLE = {Parallel {LR} Parsing},

number = {TR--82--03},

INSTITUTION = {Wang Institute of

Graduate Studies},

YEAR = {1982},

MONTH = {July},

*}*

@ARTICLE{lozinskii,

AUTHOR = {E.L. Lozinskii and S. Nirenburg},

TITLE = {Parsing in Parallel},

JOURNAL = {Computer Languages},

VOLUME = {11, No.1},

PAGES = {39--51},

INSTITUTION = {Pergamon Press},

YEAR = {1986},

*}*

@INPROCEEDINGS{sarkar:deo2,

AUTHOR = {Sarkar, D. and Deo, N.},

TITLE = {Estimating the speedup in parallel parsing},

BOOKTITLE = {International Conference on Parallel Processing},

ORGANIZATION = {IEEE},

YEAR = {1986},

*}*

@phdthesis{schell:thesis,

AUTHOR = {Schell, Jr., R. M.},

TITLE = {Methods for Constructing Parallel Compilers for use in

a Multiprocessor},

school = {University of Illinois at

Urbana-Champaign},

YEAR = {1979},

*}*

@INPROCEEDINGS{seshadri2,

AUTHOR = {V. Seshadri and I.S. Small and D.B. Wortman},

TITLE = {Concurrent Compilation},

BOOKTITLE = {Proceedings of the IFIP Conference on Distributed

Processing},

ADDRESS = {Amsterdam},

YEAR = {1987},

MONTH = {October},

*}*

@INPROCEEDINGS{steele:hillis,

AUTHOR = {G.L. Steele and W.D. Hillis},

TITLE = {{C}onnection {M}achine {L}isp: Fine-Grained Symbolic

Processing},

BOOKTITLE = {Proceedings of 1986 Symposium on Lisp and

Functional Programming},

PAGES = {279--297},

YEAR = {1986},

*}*

@ARTICLE{rytter,

AUTHOR = {W. Rytter},

TITLE = {On the Complexity of Parallel Parsing of General

Context-Free Languages},

JOURNAL = {Theoretical Computer Science},

VOLUME = {47},

PAGES = {315--321},

INSTITUTION = {North-Holland},

YEAR = {1986},

*}*

@article{cook:taxonomy,

author = {S.A. Cook},

title = {A Taxonomy of Problems with Fast Parallel Algorithms},

journal = {Information and Control},

volume = {64},

pages = {2--22},

publisher = {Academic Press},

year = {1985},

*}*

@article{barnard:skillicorn,

author = {D.T. Barnard and D.B. Skillicorn},

title = {Parallel Parsing on the {C}onnection {M}achine},

journal = {Information Processing Letters},

volume = {31, No.3},

month = {8th May},

year = {1989},

pages = {111--117},

*}*

@techreport{langlois1989,

author = {L. Langlois},

title = {Systolic Parsing of Context-Free Languages},

institution = {Universit\'e de Montr\'eal},

year = {1989},

number = {693},

*}*

@article{younger,

author = {D.H. Younger},

title = {Recognition and Parsing of Context-Free Languages in

Time $n^3$},

journal = {Information and Control},

volume = {10},

number = {2},

year = {1967},

pages = {189--208},

*}*

@article{ruzzo1980,

author = {W.L. Ruzzo},

title = {Tree-Size Bounded Alternation},

journal = {Journal of Computer and System Sciences},

volume = {21},

year = {1980},

pages = {218--235},

*}*

@inproceedings{rytter:unambiguous,

author = {W. Rytter},

title = {Parallel Time {O(log n)} Recognition of Unambiguous

{CFL}s},

booktitle = {Fundamentals of Computation Theory},

publisher = {Springer Lecture Notes in Computer Science 199},

address = {Cottbus, GDR},

month = {September},

year = {1985},

pages = {380--389},

*}*

@book{aho:ullman,

author = {A. Aho and J.D. Ullman},

title = {The Theory of Parsing, Translation and Compiling: Parsing},

publisher = {Prentice-Hall},

year = {1972},

volume = {I},

*}*

@InProceedings{GuibasKT,

Author = {L. J. Guibas and H. T. Kung and C. D. Thompson},

Key = {Guibas},

Title = {Direct {VLSI} Implementation of Combinatorial Algorithms},

BookTitle = {Caltech Conference on {VLSI}},

Pages = {509--525},

Month= {Jan},

Year= {1979},

*}*

@PhDThesis{Kosaraju69,

Author = {S. R. Kosaraju},

Key = {Kosaraju},

Title = {Computations on Iterative Automata},

School = {University of Pennsylvania},

Year = {1969},

*}*

@Article{Kosaraju75,

Author= {S. R. Kosaraju},

Key= {Kosaraju},

Title= {Speed of Recognition of Context-Free Languages

by Array Automata},

Journal= {SIAM Journal of Computing},

Volume= {4},

Number= {3},

Pages= {331--340},

Month= {September},

Year = {1975},

*}*

@article{kurk69,

author = {R. Kurki-Suonio},

title = {Notes on Top-Down Languages},

journal = {{BIT}},

volume = {9},

year = {1969},

pages = {225--238},

*}*

@book{trso85,

author = {J.P. Tremblay and P.G. Sorenson},

title = {The Theory and Practice of Compiler Writing},

publisher = {McGraw-Hill},

year = {1985},

*}*

@techreport{parsing:report,

author = {D.T. Barnard and D.B. Skillicorn},

title = {Parallel Parsing: A Status Report},

year = {1990},

number = {90-267},

institution = {Department of Computing and Information

Science, Queen's University},

*}*

@inproceedings{gross:zobel,

author = {T. Gross and A. Zobel and M. Zolg},

title = {Parallel Compilation for a Parallel Machine},

booktitle = {ACM SIGPLAN 89 Conference on Programming

Language Design and Implementation},

year = {1989},

pages = {91--100},

*}*

@inproceedings{khanna,

author = {S. Khanna and A. Ghafoor and A. Goel},

title = {A Parallel Compilation Technique Based on

Grammar Partitioning},

booktitle = {Computer Science Conference},

month = {February},

year = {1990},

*}*

@article{srikant:shankar,

author = {Y.N. Srikant and P. Shankar},

title = {Parallel Parsing of Programming Languages},

journal = {Information Sciences},

volume = {43},

year = {1987},

pages = {55--83},

*}*

@article{baer:ellis,

author = {J.-L. Baer and C.S. Ellis},

title = {Model, Design and Evaluation of a Compiler for a

Parallel Processing Environment},

journal = {IEEE Transactions on Software Engineering},

volume = {3},

number = {6},

month = {November},

year = {1977},

pages = {394--405},

keyword = {pipelining},

*}*

@inproceedings{huen,

author = {W. Huen and O. El-Dessouki and E. Huske and M.Evens},

title = {A Pipelined {DYNAMO} Compiler},

booktitle = {International Conference on Parallel Processing},

year = {1977},

pages = {57--66},

keyword = {pipelining},

*}*

@inproceedings{christopher,

author = {T. Christopher and O. El-Dessouki and M.Evens

and H. Harr and H. Klawans and P. Krystosek and

R. Mirchandani and Y. Tarhan},

title = {{SALAD} -- A Distributed Compiler for Distributed

Systems},

booktitle = {Proceedings International Conference on Parallel Processing},

year = {1981},

pages = {50--57},

keyword = {pipelining},

*}*

@inproceedings{miller:leblanc,

author = {J.A. Miller and R.J. LeBlanc},

title = {Distributed Compilation: A Case Study},

booktitle = {Proceedings of the 3rd International Conference

on Distributed Computing Systems},

month = {October},

year = {1982},

pages = {548--553},

keyword = {pipelining},

*}*

@article{eldessouki,

author = {O. El-Dessouki and W. Huen and M. Evens},

title = {Towards a Partitioning Compiler for a Distributed

Computing System},

journal = {J. of Digital Systems},

volume = {{IV}},

year = {1981},

*}*

@inproceedings{donegan:katzke,

author = {M.K. Donegan and S.W. Katzke},

title = {Lexical Analysis and Parsing Techniques for a

Vector Machine},

booktitle = {Proceedings of Conference on Programming Languages

and Compilers for Parallel and Vector Machines},

month = {March},

year = {1975},

pages = {138--145},

*}*

@inproceedings{ellis,

author = {C.A. Ellis},

title = {Parallel Compiling Techniques},

booktitle = {Proceedings of {ACM} 26th National Conference},

year = {1971},

pages = {508--519},

*}*

@article{lincoln,

author = {N. Lincoln},

title = {Parallel Programming Techniques for Compilers},

journal = {{SIGPLAN} Notices},

volume = {5},

month = {October},

year = {1970},

pages = {18--31},

*}*

@inproceedings{zosel,

author = {M. Zosel},

title = {A Parallel Approach to Compilation},

booktitle = {Conference Record of the {ACM} Symposium on Principles

of Programming Languages},

month = {October},

year = {1973},

pages = {59--70},

*}*

@inproceedings{krohn,

author = {H.E. Krohn},

title = {A Parallel Approach to Code Generation for

{F}ortran like Compilers},

booktitle = {Proceedings of Conference on Programming Languages

and Compilers for Parallel and Vector Machines},

month = {March},

year = {1975},

pages = {146--149},

volume = {10},

*}*

@article{dekel:sahni,

author = {E. Dekel and S. Sahni},

title = {Parallel Generation of Postfix and Tree Forms},

journal = {{ACM} Transactions on Programming Languages and

Systems},

volume = {5},

number = {3},

month = {July},

year = {1983},

pages = {300--317},

*}*

@article{chiang:fu,

author = {Y.T. Chiang and K.S. Fu},

title = {Parallel Parsing Algorithms and {VLSI} Implementations

for Syntactic Pattern Recognition},

journal = {{IEEE} Transactions on Pattern Analysis and Machine

Intelligence},

volume = {{PAMI}-6, No.3},

month = {May},

year = {1984},

pages = {302--313},

*}*

@article{brent,

author = {R.P. Brent},

title = {The Parallel Evaluation of General Arithmetic

Expressions},

journal = {Journal of the {ACM}},

volume = {21, No.2},

month = {April},

year = {1984},

pages = {201--206},

*}*

@article{baron,

author = {I. Bar--On and U. Vishkin},

title = {Optimal Parallel Generation of a Computation

Tree Form},

journal = {{ACM} Transactions on Programming Languages

and Systems},

volume = {7, No.2},

month = {April},

year = {1985},

pages = {348--357},

*}*

@ARTICLE{banatre,

author = {J. P. Ban\^{a}tre and J. P. Routeau and L. Trilling},

title = {An Event Driven Compiling Technique},

journal = {Communications of the ACM},

volume = {22},

year = {1979},

pages = {32--42},

*}*

@phdthesis{lipkie:thesis,

author = {D. E. Lipkie},

title = {A Compiler Design for Multiple Independent

Processor Computers},

school = {University of Washington},

year = {1979},

*}*

@article{chang:ibarra:palis,

author = {J. H. Chang and O. H. Ibarra and M. A. Palis},

title = {Parallel Parsing on a One-Way Array of Finite State Machines},

journal = {IEEE Transactions on Computers},

volume = {36},

number = {1},

pages = {64--75},

month = {January},

year = {1987},

*}*

@phdthesis{frankel:thesis,

author = {J. L. Frankel},

title = {The Architecture of Closely-Coupled Distributed Computers and

Their Language Processors},

school = {Harvard University},

year = {1983},

*}*

@inproceedings{katseff,

author = {H. P. Katseff},

title = {Using Data Partitioning to Implement a Parallel Assembler},

booktitle = {Proceedings of the ACM Parallel Programming

Languages and Systems Conference:

Experience with Applications},

volume = {23,9},

pages = {66-76},

month = {July},

year = {1988},

publisher = {Sigplan Notices},

*}*

@inproceedings{mickunas:schell,

author = {M. D. Mickunas and R. M. Schell},

title = {Distributed Compilation: A Case Study},

booktitle = {Proceedings of the ACM National Conference},

pages = {241-246},

month = {December},

year = {1978},

*}*

@mastersthesis{seshadri:thesis,

author = {V. Seshadri},

title = {Concurrent Semantic Analysis},

school = {University of Toronto},

month = {September},

year = {1988},

*}*

@article{gibbons:rytter2,

author = {Gibbons, A. and Rytter, W.},

title = {Optimal Parallel Algorithms for Dynamic Expression Evaluation

and Context-Free Recognition},

journal = {Information and Computation},

volume = {81},

number = {1},

pages = {32-45},

month = {April},

year = {1989},

*}*

@article{klein:reif,

author = {Klein, P. N. and Reif, J. H.},

title = {Parallel Time {O(log n)} Acceptance of Deterministic

{CFL}s on an Exclusive-Write {P-RAM}},

journal = {Siam Journal of Computing},

volume = {17},

number = {3},

pages = {463-485},

month = {June},

year = {1988},

*}*

@phdthesis{langlois1988,

author = {Langlois, L. C.},

title = {Parallel Parsing of Context-Free Languages on an Array

of Processors},

school = {University of Edinburgh},

month = {October},

year = {1988},

*}*

@article{matsumoto,

author = {Matsumoto, Yuji},

title = {A Parallel Parsing System for Natural Language Analysis},

journal = {New Generation Computing},

volume = {5},

pages = {63-78},

year = {1987},

*}*

@article{mickunas:schell21978,

author = {Mickunas, M. D. and Schell, R. M.},

title = {Parallel Compilation in a Multiprocessor Environment (Extended

Abstract)},

journal = {JACM},

volume = {29},

number = {2},

pages = {241-246},

year = {1978},

*}*

@article{szymanski:williams,

author = {Szymanski, T. G. and Williams, J. H.},

title = {Noncanonical Extensions of Bottom-up Parsing Techniques},

journal = {SIAM Journal of Computing},

volume = {5},

number = {2},

pages = {231-250},

month = {June},

year = {1976},

*}*

@techreport{yu:thesis,

author = {Yu, C. P.},

title = {Practical Parallel Lexing},

institution = {University of Toronto},

number = {CSRI-226},

month = {May},

year = {1989},

*}*

@article{junkin:wortman2,

author = {Junkin, M.D. and Wortman, D. B.},

title = {Supervisors -- An Approach to Controlling Concurrency},

journal = {submitted to: IEEE Transactions on Parallel and Distributed

Systems},

year = {1989},

*}*

@inproceedings{yu:wortman,

author = {Yu, C. P. and Wortman D. B.},

title = {Concurrent Lexical Analysis},

booktitle = {Proceedings ACM SIGPLAN `90 Conference on Programming Language Design

and Implementation},

year = {1990},

*}*

@inproceedings{wortman:junkin:seshadri,

author = {Wortman, D. B. and Junkin, M. D. and Seshadri, V.},

title = {Compiling Concurrently},

booktitle = {Proceedings ACM SIGPLAN `90 Conference on Programming

Language Design and Implementation},

year = {1990},

*}*

@article{dwork:kanellakis2:stockmeyer3,

author = {Dwork, C. and Kanellakis P. C. and Stockmeyer, L.},

title = {Parallel Algorithms for Term Matching},

journal = {SIAM J. Computing},

volume = {17},

number = {4},

month = {August},

year = {1988},

pages = {711-731},

*}*

@article{chisholm,

author = {Chisholm, P},

title = {Derivation of a Parsing Algorithm in {M}artin-{L}\`{o}f's Theory of

Types},

journal = {Science of Computer Programming},

volume = {8},

pages = {1-42},

year = {1987},

*}*

@techreport{ibarra:palis,

author = {Ibarra, O. H. and Palis, M. A.},

title = {An Efficient All-Parses Systolic Algorithm for General

Context-free Parsing},

institution = {University of Minnesota},

year = {1988},

*}*

@article{ruzzo1981,

author = {Ruzzo, W. L.},

title = {On Uniform Circuit Complexity},

journal = {Journal of Computer and System Sciences},

volume = {22},

pages = {365-383},

year = {1981},

*}*

@article{fischer:toplas,

author = {Fischer, C. N.},

title = {On Parsing and Compiling Arithmetic

Expressions on Vector Computers},

journal = {ACM Transactions on Programming Languages and Systems},

volume = {2},

number = {2},

pages = {203-224},

month = {April},

year = {1980},

*}*

@article{andre,

author = {Andr\'{e}, F. and Ban\^{a}tre, J. P. and Routeau, J. P.},

title = {A Multiprocessing Approach to Compile-Time Symbol Resolution},

journal = {ACM Transactions on Programming Languages and Systems},

volume = {3},

number = {1},

pages = {11-23},

month = {January},

year = {1981},

*}*

@article{knuth,

author = {Knuth, D. E.},

title = {Semantics of Context-Free Languages},

journal = {Mathematical Systems Theory},

volume = {2},

number = {2},

pages = {127-145},

month = {November},

year = {1967},

*}*

@inproceedings{gafter,

author = {Gafter, N. M.},

title = {Algorithms and Data Structures for Parallel Incremental

Parsing},

booktitle = {1987 International Conference on Parallel Processing},

pages = {577-591},

year = {1987},

*}*

@article{dymond,

author = {P.W. Dymond},

title = {Input-Driven Languages are in log n Depth},

journal = {Information Processing Letters},

volume = {26},

pages = {247-250},

keywords = {parallel computation log depth circuit, formula value

problem, input-driven language, context-free language},

month = {January},

year = {1988},

*}*

@article{greibach,

author = {Greibach, S. A.},

title = {The Hardest Context-Free Language},

journal = {SIAM Journal of Computing},

volume = {2},

number = {4},

month = {December},

year = {1973},

keywords = {context-free, quasirealtime, complexity, polynomial time

recognition},

*}*

@article{yamasaki,

author = {Yamasaki, H. and Takahashi, M.},

title = {Generalized Parenthesis Languages and Minimization of Their

Parenthesis Parts},

journal = {Theoretical Computer Science},

volume = {31},

year = {1984},

*}*

@article{borodin,

author = {Borodin, A.},

title = {On Relating Time and Space to Size and Depth},

journal = {SIAM Journal of Computing},

volume = {6},

number = {4},

month = {December},

keywords = {space, depth, time, size, computational complexity,

parallel arithmetic complexity, parallel time},

pages = {733-744},

year = {1977},

*}*

@article{srikant:shankar:1987,

author = {Srikant, Y. N. and Shankar, P.},

title = {A New Parallel Algorithm for Parsing Arithmetic Infix

Expressions},

journal = {Parallel Computing},

volume = {4},

pages = {291-304},

keywords = {arithmetic infix expression, parse tree, SIMD computer,

parallel parsing algorithm, parallel programming, parallel

code generation},

year = {1987},

*}*

@article{earley,

author = {Earley, J.},

title = {An Efficient Context-Free Parsing Algorithm},

journal = {Communications of the ACM},

volume = {13},

number = {2},

month = {February},

year = {1970},

keywords = {syntax analysis, parsing, context-free grammar, compilers,

computational complexity},

*}*

@inproceedings{sarkar:deo,

author = {Sarkar, D. and Deo, N.},

title = {An Optimal Parallel Parsing Algorithm for a Class of

Block-Structured Languages},

booktitle = {Proceedings of the International Conference of Parallel

Processing},

editor = {Ed. S. R. Sahni},

year = {1987},

*}*

@inproceedings{chiang:fu2,

author = {Chiang, Y. and Fu, K. S.},

title = {A {VLSI} Architecture for Fast Context-Free Language Recognition

({E}arley's {A}lgorithm)},

booktitle = {Proceedings of the IEEE Conference},

year = {1982},

*}*

@inproceedings{abdollahzadeh:badii:cooke,

author = {Abdollahzadeh, F. and Badii, M. and Cooke, D. J.},

title = {A New Grammar for Arithmetic Expressions in a Parallel

Processing Environment},

booktitle = {Proceedings of the IEEE Conference},

year = {1986},

*}*

@INPROCEEDINGS{allen,

AUTHOR = {Randy Allen and Steve Johnson},

TITLE = {Compiling {C} for Vectorization, Parallelization, and

Inline Expansion},

BOOKTITLE = {Proceedings ACM SIGPLAN '88

Conference on Programming Language

Design and Implementation},

PAGES = {241--249},

KEYWORDS = {compilers parallel programming inline substitution},

month = {July},

year = {1988},

*}*

@article{ibarra:nc,

author = {O.H. Ibarra and Tao Jiang and J.H. Chang and

B. Ravikumar},

title = {Some classes of languages in {NC}${}^{1}$},

journal = {Information Processing Letters},

volume = {29},

year = {1989},

pages = {111--117},

*}*

@article{barnard:skillicorn:pipeline,

author = {D.T. Barnard and D.B. Skillicorn},

title = {Pipelining Tree Structured Algorithms on {SIMD}

Architectures},

journal = {Information Processing Letters},

volume = {},

month = {},

year = {to appear},

pages = {},

*}*

@inproceedings{ruzzo:cfl,

author = {W.L. Ruzzo},

title = {On the Complexity of General Context-Free Language

Parsing and Recognition},

booktitle = {},

volume = {},

month = {},

year = {},

pages = {},

*}*

@article{skillicorn:barnard,

author = {D.B. Skillicorn and D.T. Barnard},

title = {Context-Free Parsing on $O(n)$

Processors},

journal = {Computer Languages},

volume = {},

month = {},

year = {submitted},

pages = {},

*}*

@inproceedings{pennello,

author = {T.J. Pennello and F. DeRemer},

title = {A Forward Move Algorithm for {LR} Error Recovery},

booktitle = {Fifth Annual Symposium on Principles of Programming

Languages},

month = {January},

year = {1978},

pages = {},

*}*

@article{skillicorn:survey,

author = {D.B. Skillicorn and D.T. Barnard},

title = {Parallel Compilation},

journal = {in progress},

volume = {},

month = {},

year = {1990},

pages = {},

*}*

@article{baccelli:fleury,

author = {F. Baccelli and T. Fleury},

title = {On Parsing Arithmetic Expressions in a Multi-processing

Environment},

journal = {Acta Informatica},

volume = {17},

year = {1982},

pages = {287--310},

*}*

@inproceedings{baer:bovett,

author = {J.L. Baer and D.P. Bovett},

title = {Compilation of Arithmetic Expressions for Parallel

Computations},

booktitle = {Proceedings of IFIP World Congress},

year = {1968},

pages = {340--346},

*}*

@article{bossi,

author = {A. Bossi and N. Cocco and L. Colussi},

title = {A Divide-and-Conquer Approach to General

Context-Free Parsing},

journal = {Information Processing Letters},

volume = {16},

year = {1983},

pages = {203--208},

*}*

@article{brent:goldschlager,

author = {R.P. Brent and L.M. Goldschlager},

title = {A Parallel Algorithm for Context-Free Parsing},

journal = {Australian Computer Science Communications},

volume = {6, No.1},

year = {1984},

pages = {7.1--7.10},

*}*

@inproceedings{carlisle:friesen,

author = {W.H. Carlisle and D.K. Friesen},

title = {Parallel Parsing Using {Ada}},

booktitle = {Proceedings of 3rd Annual National Conference on

{Ada} Technology},

month = {March},

year = {1985},

pages = {103--106},

*}*

@article{cheng:fu,

author = {H.D. Cheng and K.S. Fu},

title = {Algorithm Partitioning and Parallel Recognition of

Context-Free Languages Using Fixed-size {VLSI}

Architecture},

journal = {Pattern Recognition},

volume = {19},

year = {1986},

pages = {361--372},

*}*

@inproceedings{chu:fu,

author = {K.-H. Chu and K.S. Fu},

title = {{VLSI} Architectures for High-Speed Recognition of

Context-Free Languages and Finite-State Languages},

booktitle = {Proceedings of the 9th Annual International

Symposium on Computer Architecture},

year = {1982},

pages = {43--49},

*}*

@incollection{dymond:ruzzo,

author = {P.W. Dymond and W.L. Ruzzo},

title = {Parallel {RAM}s with Owned Global Memory and

Deterministic Context-Free Language Recognition},

booktitle = {Automata, Languages and Programming},

publisher = {Springer Lecture Notes in Computer Science 226},

editor = {L. Kott},

year = {1986},

pages = {95--104},

*}*

@phdthesis{frank,

author = {P.D. Frank},

title = {Bounded Non-determinism and the Parallel Parsing

of Context-Free Languages},

school = {University of Washington},

year = {1979},

*}*

@techreport{huang:guthrie,

author = {X-M. Huang and L. Guthrie},

title = {Parsing in Parallel},

institution = {New Mexico State University},

number = {MCCS-85-40},

year = {1985},

*}*

@incollection{kuiper:dijkstra,

author = {M.F. Kuiper and A. Dijkstra},

title = {Attribute Evaluation on a Network of

Transputers},

booktitle = {Developing Transputer Applications},

editor = {J. Wexler},

publisher = {IOS, Amsterdam},

year = {1989},

pages = {142--149},

*}*

@inproceedings{mattheyses,

author = {R. Mattheyses and C.M. Fiduccia},

title = {Parsing {D}yck Languages on Parallel Machines},

booktitle = {Proceedings of the 20th Allerton Conference

on Communication, Control and Computing},

year = {1982},

pages = {272-280},

*}*

@article{muller:preparata,

author = {D.E. Muller and F.P. Preparata},

title = {Restructuring of Arithmetic Expressions for Parallel

Evaluation},

journal = {J. Association for Computing Machinery},

volume = {23},

year = {1976},

pages = {534--543},

*}*

@inproceedings{nijholt,

author = {A. Nijholt},

title = {Parallel Parsing Strategies in Natural Language

Processing},

booktitle = {Proceedings of the International Workshop on

Parsing Technologies},

address = {Carnegie-Mellon, Pittsburgh},

month = {August},

year = {1989},

pages = {240--253},

*}*

@incollection{nijholt2,

author = {A. Nijholt},

title = {Parallel Approaches to Context-Free Language

Parsing},

booktitle = {Parallel Models of Natural Language Computation},

publisher = {Ablex, Norwood, N.J.},

editor = {U. Hahn and G. Adriaens},

year = {1990},

pages = {},

*}*

@techreport{oudeluttighuis,

author = {P.H.W.M. Oude Luttighuis},

title = {Parallel Parsing of Regular Right-Part Grammars},

institution = {Faculteit der Informatica, Universiteit Twente},

number = {INF89-63},

year = {1989},

*}*

@incollection{partsch,

author = {H. Partsch},

title = {Transformational Derivation of Parsing Algorithms

Executable on Parallel Architectures},

booktitle = {Programiersprachen und Programmentwicklung},

editor = {U. Amman},

publisher = {Springer},

year = {1984},

pages = {41--57},

*}*

@incollection{rytter:giancarlo:a,

author = {W. Rytter and R. Giancarlo},

title = {Optimal Parallel Parsing of Bracket Languages},

booktitle = {Parallel Algorithms and Architectures},

editor = {A. Albrecht and H. Jung and K. Mehlhorn},

publisher = {Springer Lecture Notes in Computer Science 269},

year = {1987},

pages = {146--154},

*}*

@incollection{sridharan,

author = {N.S. Sridharan},

title = {Semi-applicative Programming: Examples of Context-Free

Recognizers},

booktitle = {Distributed Artificial Intelligence},

chapter = {8},

editor = {M.N. Huhns},

publisher = {Morgan Kaufman Publishers, Los Altos, {CA}},

year = {1987},

pages = {203--245},

*}*

@inproceedings{klein:koskimies2,

author = {E. Klein and K. Koskimies},

title = {Parallel One-Pass Compilation},

booktitle = {Workshop on Attribute Grammars and their Applications},

address = {Paris},

publisher = {Springer Lecture Notes in Computer Science},

year = {1990},

pages = {76--90},

*}*

@techreport{klein:koskimies,

author = {E. Klein and K. Koskimies},

title = {The Parallelization of One-Pass Compilers},

institution = {Gesellschaft f\"{u}r Mathematik und

Datverarbeitung, Arbeitspapiere 416},

month = {November},

year = {1989},

*}*

@techreport{akker,

author = {R. op den Akker and H. Alblas and A. Nijholt and

P.H.W.M. Oude Luttighuis},

title = {An Annotated Bibliography on Parallel Parsing},

institution = {Faculteit der Informatica, Universiteit Twente},

number = {INF89-67},

month = {December},

year = {1989},

*}*

@inproceedings{klein:wpc,

author = {E.A. Klein},

title = {Attribute Evaluation in Parallel},

booktitle = {Proceedings of the Workshop of Parallel Compilation},

address = {Kingston, Ontario},

month = {May 6-8},

year = {1990},

pages = {8},

*}*

@inproceedings{gupta:pollock:soffa:wpc,

author = {R. Gupta and L. Pollock and M.L. Soffa},

title = {Parallelizing Data Flow Analysis},

booktitle = {Proceedings of the Workshop of Parallel Compilation},

address = {Kingston, Ontario},

month = {May 6-8},

year = {1990},

pages = {19},

*}*

@inproceedings{deo:wpc,

author = {N. Deo and S. Prasad},

title = {Some Fast {PRAM} Algorithms for Matching Parentheses},

booktitle = {Proceedings of the Workshop of Parallel Compilation},

address = {Kingston, Ontario},

month = {May 6-8},

year = {1990},

pages = {7},

*}*

@inproceedings{luttighuis:wpc,

author = {P.O. Luttighuis},

title = {Parallel Parsing of Regular Right-part Grammars},

booktitle = {Proceedings of the Workshop of Parallel Compilation},

address = {Kingston, Ontario},

month = {May 6-8},

year = {1990},

pages = {11},

*}*

@inproceedings{zobel:wpc,

author = {A. Zobel},

title = {Parallelized Compiler Optimization},

booktitle = {Proceedings of the Workshop of Parallel Compilation},

address = {Kingston, Ontario},

month = {May 6-8},

year = {1990},

pages = {12},

*}*

@inproceedings{langlois1990b,

author = {L. Langlois},

title = {Parallel parsing via the backward trace of systolic computations},

booktitle = {Proceedings of the Workshop of Parallel Compilation},

address = {Kingston, Ontario},

month = {May 6-8},

year = {1990},

pages = {8},

*}*

@inproceedings{lewke:wpc,

author = {K.D. Lewke},

title = {PILA: Lexical and Syntactical Analysis on

a Pipelined Processor},

booktitle = {Proceedings of the Workshop of Parallel Compilation},

address = {Kingston, Ontario},

month = {May 6-8},

year = {1990},

pages = {10},

*}*

@inproceedings{gafter1990,

author = {N.M. Gafter},

title = {On the Complexity of Parallel Compilation},

booktitle = {Proceedings of the Workshop of Parallel Compilation},

address = {Kingston, Ontario},

month = {May 6-8},

year = {1990},

pages = {7},

*}*

@inproceedings{wortman:wpc,

author = {D.B. Wortman},

title = {A Concurrent Modula-2+ Compiler},

booktitle = {Proceedings of the Workshop of Parallel Compilation},

address = {Kingston, Ontario},

month = {May 6-8},

year = {1990},

pages = {6},

*}*

@inproceedings{srikant,

author = {Y.N. Srikant},

title = {Parallel Parsing of Arithmetic Expressions},

booktitle = {Proceedings of the International Conference on

Parallel Processing},

month = {August},

year = {1987},

pages = {589--591},

*}*

@inproceedings{lee:marlowe:ryder:wpc,

author = {Y.-F. Lee and T.J. Marlowe and B.G. Ryder},

title = {Parallel Data Flow Analysis Algorithms},

booktitle = {Proceedings of the Workshop of Parallel Compilation},

address = {Kingston, Ontario},

month = {May 6-8},

year = {1990},

pages = {9},

*}*

@article{rytter:giancarlo,

author = {W. Rytter and R. Giancarlo},

title = {Optimal Parallel Parsing of Bracket Languages},

booktitle = {parallel Algorithms and Architectures},

series = {Springer Lecture Notes in Computer Science 269},

month = {May},

year = {1987},

pages = {146--154},

*}*

@article{sarkar:deo3,

author = {D. Sarkar and N. Deo},

title = {Estimating the Speedup in Parallel Parsing},

journal = {{IEEE} Transactions on Software Engineering},

volume = {16},

month = {July},

year = {1990},

pages = {677--683},

*}*

@article{burke:ryder,

author = {M.G. Burke and B.G. Ryder},

title = {A Critical Analysis of Incremental Iterative Dataflow

Analysis Algorithms},

journal = {{IEEE} Transactions on Software Engineering},

volume = {16},

month = {July},

year = {1990},

pages = {723--728},

*}*

@techreport{lee:report,

author = {Y.-F. Lee and T.J. Marlowe and B.G. Ryder},

title = {Parallel Hybrid Data Flow Analysis Algorithms},

institution = {Rutgers University Center for Computer

Aids for Industrial Productivity},

number = {CAIP-TR-108},

year = {1990},

*}*

@inproceedings{oudeluttighuis:wpc,

author = {P. Oude Luttighuis},

title = {Parallel Parsing of Regular Right-part Grammars},

booktitle = {Proceedings of the Workshop of Parallel Compilation},

address = {Kingston, Ontario},

month = {May 6-8},

year = {1990},

pages = {11},

*}*

@phdthesis{gafter:thesis,

author = {N.M. Gafter},

title = {Parallel Incremental Compilation},

school = {University of Rochester},

year = {1990},

note = {Also appears as Computer Science Technical Report 349},

*}*

@article{chang:chao,

author = {R.C. Chang and K.M. Chao},

title = {Parallel Operator-Precedence Parsing},

journal = {Journal of Information Science and Engineering},

volume = {6},

month = {March},

year = {1990},

pages = {51--62},

*}*

@techreport{fradet,

author = {P. Fradet and D. Le Metayer},

title = {Compilation of Functional Languages by Program

Transformation},

institution = {INRIA-Rennes, Rapports de Recherche 1040},

year = {1989},

*}*

@inproceedings{chytil:monien,

author = {M.P. Chytil and B. Monien},

title = {Caterpillars and Context-Free Languages},

booktitle = {{STACS}90 7th Annual Symposium on Theoretical

Aspects of Computer Science},

editor = {C. Choffrut and T. Lengauer},

series = {Springer Lecture Notes in Computer Science 415},

month = {February},

year = {1990},

pages = {70--81},

*}*

@book{wpc:proceedings,

author = {D.T. Barnard and D.B. Skillicorn (Eds.)},

booktitle = {Proceedings of a Workshop on Parallel Compilation},

address = {Kingston, Ontario, Canada},

month = {May},

year = {1990},

*}*

@book{tremblay:sorenson,

author = {J.P. Tremblay and P.G. Sorenson},

title = {The Theory and Practice of Compiler Writing},

publisher = {McGraw-Hill, New York},

year = {1985},

*}*

@techreport{alblas,

author = {H. Alblas},

title = {Parallel Incremental Attribute Evaluation},

institution = {Faculteit der Informatica, Universiteit Twente},

number = {INF90-42},

year = {1990},

*}*

@article{williams,

author = {J.H. Williams},

title = {Bounded Context Parsable Grammars},

journal = {Information and Control},

volume = {28},

year = {1975},

pages = {314-334},

*}*

@article{braunmuhl,

author = {B. von Braunm\"{u}hl and S. Cook and K. Mehlhorn and

R. Verbeek},

title = {The Recognition of Deterministic {CFL}s in Small

Time and Space},

journal = {Information and Control},

volume = {56},

year = {1983},

pages = {34-51},

*}*

@techreport{anderson,

author = {M.R. Anderson},

title = {Null Nonterminal Insertion in {LR}(k) Grammars},

institution = {University of Michigan, Computer Science and

Engineering},

number = {CSE-TR-49-90},

year = {1990},

*}*

@article{leivant,

author = {D. Leivant},

title = {Polymorphic Type Inference},

journal = {},

volume = {},

month = {},

year = {},

pages = {},

*}*

@inproceedings{damas:milner,

author = {L. Damas and R. Milner},

title = {Principal type-schemes for Functional Programs},

booktitle = {Conference Record of the Ninth Annual {ACM}

Symposium on Principles of Programming Languages},

year = {1982},

pages = {207--212},

*}*

@inproceedings{akker,

author = {R. op den Akker and B. Melichar and

J. Tarhio},

title = {The Hierarchy of {LR}-Attributed Grammars},

booktitle = {Workshop on Attribute Grammars and their Applications},

address = {Paris},

publisher = {Springer Lecture Notes in Computer Science 461},

year = {1990},

pages = {13--28},

*}*

@inproceedings{kuiper,

author = {M.F. Kuiper and S.D. Swierstra},

title = {Parallel Attribute Evaluation: Structure of Evaluators

and Detection of Parallelism},

booktitle = {Workshop on Attribute Grammars and their Applications},

address = {Paris},

publisher = {Springer Lecture Notes in Computer Science 461},

year = {1990},

pages = {61--75},

*}*

@inproceedings{vogt,

author = {H. Vogt and A. van der Berg and A. Freje},

title = {Rapid Development of a Program Transformation

System with Attribute Grammars and Dynamic Transformations},

booktitle = {Workshop on Attribute Grammars and their Applications},

address = {Paris},

publisher = {Springer Lecture Notes in Computer Science 461},

year = {1990},

pages = {101--115},

*}*

@inproceedings{wilhelm,

author = {R. Wilhelm},

title = {Tree Transformations, Functional Languages, and

Attribute Grammars},

booktitle = {Workshop on Attribute Grammars and their Applications},

address = {Paris},

publisher = {Springer Lecture Notes in Computer Science 461},

year = {1990},

pages = {116--129},

*}*

@inproceedings{rosendahl,

author = {M. Rosendahl},

title = {Abstract Interpretation using Attribute Grammars},

booktitle = {Workshop on Attribute Grammars and their Applications},

address = {Paris},

publisher = {Springer Lecture Notes in Computer Science 461},

year = {1990},

pages = {143--156},

*}*

@inproceedings{waite,

author = {W.M. Waite},

title = {Use of Attribute Grammars in Compiler Construction},

booktitle = {Workshop on Attribute Grammars and their Applications},

address = {Paris},

publisher = {Springer Lecture Notes in Computer Science 461},

year = {1990},

pages = {255--265},

*}*

@inproceedings{alblas2,

author = {H. Alblas},

title = {Concurrent Incremental Attribute Evaluation},

booktitle = {Workshop on Attribute Grammars and their Applications},

address = {Paris},

publisher = {Springer Lecture Notes in Computer Science 461},

year = {1990},

pages = {343--358},

*}*

Reply-To: reinoud@duteca2.tudelft.nl (R. Lamberts)

There is a small but interesting section on 'Parsing a Regular Language' in

the article Data Parallel algorithms, W. Daniel Hillis and Guy L. Steele,

Jr., Communications of the ACM, December 1986, Volume 29, number12. The

article is about the connection machine, actually, and contains a further

reference to an article about connection machine Lisp.

I hope this is of any help,

Reply-To: torsten@cs.utexas.edu (Torsten Suel)

The following paper gives an algorithm for parsing cf-languages in iterative

and cellular automata. The algorithm is based on Younger's, the speed of

recognition is linear ( in the 2-dimensional case ) or quadratic ( in the

1-dimensional case ) time. It is

S. Rao Kosaraju :

Speed of recognition of context-free languages by array automata

SIAM Journal of Computing, Vol.4 No.3, (1975) pp.331-340

I hope this could help you to figure out a parallel algorithm even if you

are not interested in cellular algorithms !

Reply-To: siegeert@cs.kuleuven.ac.be (Geert Adriaens)

There is an interesting annotated bibliography on parallel parsing,

available from the University of Twente, The Netherlands. Here's the

address:

University of Twente

Dept of CS

PO Box 217

7500 AE Enschede

the Netherlands

Eds: R. op den Akker, H. Albas, A. Nijholt, P. Oude Littighuis

You can also find an article by Nijholt in the Proceedings of the

First International Workshop on Parsing Technologies (Pittsburgh,

August 1989). You can write to Nijholt at the above address; an e-mail

address that you will have to turn into something that works from the

States is utrcu1!utinu2!anijholt.

Last but not least, there will be an article on parsing context-free

grammars in parallel in a book that I am editing together with a

German colleague (U. Hahn, Freiburg), titled "Parallel Natural Language

Processing". It will be out in the Spring of 91, with Ablex.

Reply-To: eerke@cs.kun.nl (Eerke Boiten)

Here in the Netherlands, I know of two groups that work or have worked

on parallel parsing.

Matthijs Kuiper at Utrecht University (matthijs@cs.ruu.nl or

kuiper@cs.ruu.nl, don't know which) has written a thesis on Parallel

Attribute Evaluation. He also reads news, I think, so probably he'll

reply to you anyway.

At Twente University, the compiler construction group (prof. Anton

Nijholt, dr. Henk Alblas, et al.) has recently compiled a bibliography

on parallel parsing, which is available as a techreport. They are also

doing research on parallel parsing. I don't know their email adresses,

but their reachable via: PO Box 217, NL-7500 AE Enschede.

Hope this helps,

Reply-To: Kieron Drake <kieron@root.co.uk>

Until recently I was a lecturer at Queen Mary and Westfield College,

University of London, and I remember one character there starting

a thesis on parallel parsing algorithms for the DAP machine

(Distributed Array Processor, SIMD machine with 1-bit PE's). I can't

remember his name but he was supervised by Dr Keith Clarke and Professor

Peter Landin. Keith's e-mail address is:

keithc@cs.qmw.ac.uk

He's a very helpful guy. Hope this helps.

Reply-To: gafter@frog.csc.ti.com

OK, here is my bibliography on the subject. You should also ask David

Skillicorn, who is maintaining a bibliography and mailing list on the

topic. A message from him is enclosed.

Neal

------------------------------------------------------------

@article{CH82,

Author = "Jacques Cohen and Timothy Hickey and Joel Katcoff",

Title = "Upper Bounds for Speedup in Parallel Parsing",

Journal = "Journal of the ACM",

Year = 1982,

Volume = 29,

Number = 2,

Pages = "408--428",

Month = "April"}

@article{CK85,

Author = "Jacques Cohen and Stuart Kolonder",

Title = "Estimating the Speedup in Parallel Parsing",

Journal = "IEEE Transactions on Software Engineering",

Year = 1985,

Volume = "11, 1",

Pages = "114--124",

Month = "January"}

@phdthesis{F75,

Author = "Charles N. Fischer",

Title = "On Parsing Context-Free Languages in

Parallel Environments",

School = "Cornell University",

Year = 1975,

Month = "April"}

@phdthesis{Gaf90,

Author = "Neal M. Gafter",

Title = "Parallel Incremental Compilation",

School = "University of Rochester",

Year = 1990,

Month = "May"}

@article{Klein88,

Author = "Philip N. Klein and John H. Reif",

Title = "Parallel Time O(log n) Acceptance of Deterministic

CFLs on an Exclusive-Write P-RAM",

Journal = "SIAM Journal on Computing",

Year = 1988,

Volume = "17",

Number = "3",

Pages = "463--485",

Month = "June"}

@techreport{Lig82,

Author = "Dan Ligett and Glen McCluskey and W. M. McKeeman",

Title = "Parallel LR Parsing",

Institution = "Wang Institute of Graduate Studies

School of Information Technology",

Year = 1982,

Number = "TR-82-03",

Month = "July"}

@inproceedings{Mic78,

Author = "M. D. Mickunas and R. M. Schell",

Title = "Parallel Compilation in a Multiprocessor Environment",

Booktitle = "Proceedings of the ACM Annual Conference",

Year = 1978,

Pages = "241--246"}

@inproceedings{Sar86,

Author = "Dilip Sarkar and Narsingh Deo",

Title = "Estimating the Speedup in Parallel Parsing",

Booktitle = "Proceedings of the 1986 IEEE International Conference

on Parallel Processing",

Year = 1986,

Pages = "157--163",

Organization = "IEEE",

Month = "August"}

@phdthesis{Sch79,

Author = "Schell, Jr., Richard Marion",

Title = "Methods for Constructing Parallel Compilers for use

in a Multiprocessor Environment",

School = "University of Illinois at Urbana-Champaign",

Year = 1979}

@techreport{Skillicorn88,

Author = "D. B. Skillicorn and D. T. Barnard",

Title = "Parallel Parsing on the Connection Machine",

Institution = "Queen's University",

Year = "1988",

Number = "TR 88-209",

Month = "January 27"}

------------------------------------------------------------

Date: Fri, 27 Jul 90 11:04:01 EDT

Reply-To: skill@qucis.queensu.ca

Subject: Parallel Compilation - documents from Queen's

Mailing list message 2: Documents available from Queen's

1. Proceedings of the Workshop on Parallel Compilation, Kingston, May 1990.

To order this tech report, send $C15 to:

Heather Ball

Office of the Vice-Principal Research

Richardson Hall

Queen's University

Kingston Ontario

CANADA K7L 3N6

If you need a pro forma invoice you may request one from

heather@qucis.queensu.ca

2. A technical report "Parallel Compilation: A Survey" describing some

recent work at Queen's. It includes an implementation of the Hillis/

Steele (really Schell) lexing algorithm and our LL parsing algorithm.

A hard copy but slightly outdated copy of the bibliography on

parallel compilation is included.

3. An on-line bibliography on parallel compilation in BiBTeX format.

We ask everyone active in the area to keep us informed of their new

publications in the area.

Please send requests for the last two items to me (skill@qucis.queensu.ca).

-David Skillicorn

Reply-To: rick@wucs1.wustl.edu (Rick Bubenik)

You might want to look at:

H.J. Boehm and W. Zwaenepoel, Parallel Attribute Grammar Evaluation.

Technical Report 85-39, Rice University, Department of Computer Science,

Houston, Tx., May 1986.

You can contact the department and request a copy at:

Department of Computer Science

Rice University

P.O. Box 1892

Houston, Tx. 77251-1892

Reply-To: ico.isc.com!digi!blee@Central.Sun.COM (Benjamin W. Lee)

I don't have the paper off hand, but if you are really interested,

let me know and I will go back to my pile of papers to dig it out.

The paper I remember is written by H.T. Kung from C.M.U. and Dr.

Chiang ?. The paper is adapting one of the parsing algorithm to

a triangular shaped systolic array. Kind of lengthy to read.

Took me 2-3 weeks to finish reading that paper in the past and

that is how I still remember it.

Reply-To: Greg Michaelson <greg@cs.heriot-watt.ac.uk>

Some work was done on this at the University of Edinburgh. You could

contact: s.michaelson@uk.ac.edinburgh for more details.

Reply-To: caroma@ai.mit.edu (Carl R. Manning)

I happen to run across this, but haven't read it:

A. Yonezawa and I. Ohsawa. "Object-Oriented Parallel Parsing for

Context Free Grammars" In _Proceedings_of_International_Conference_

_on_Computational_Linguistics_ (COLING) Budapest, pages 773-778,

International Committee on Computational Linguistics, 1988

Revised & Reprinted in A. Yonezawa, editor, _ABCL:_An_Object_

_Oriented_Concurrent_System, Cambridge, MA: MIT Press, 1990.

Reply-To: hubert@vega.ucsb.edu (Hung-Hsien Hubert Chang)

Baer, Ellis: Model , Desgin , and Evaluation of a compiler for a parallel processing enviornment

IEEE trans. on Soft Eng V.3 N.5 Nov 1977

Cohen , Hickey: Upper bounds for speedup in parallel parsing

JACM v.29 N2. Apr 1982

Cohen , Kolodner Estimating the speedup in parallel parsing

IEEE trans Soft Eng V.11 N.1 Jan 1985

Dekel, Sahni: parallel generation of postfix and tree-forms

ACM tran Prog lang syst V.5 N.3 July 1983

Donegan, Katzke : lexical analysisi and parsing techniques fro a vector machine

Proc Conf Prog. Lang and Compilers for paralle and vector machines.

ACM -SIGPLAN notics V.10 Mar 1975

Ellis: parallel compilign techniques

Proc. ACM 26th Nat. Conf 1971

Fisher: On parsing context-free languages in parallel enviornmets

Ph.D dissertation , Dep of computer science , Cornell Univ

Krohn: a prallel approach to code generation fro Fortran-like compilers

Proc. Conf. Prog. Lang and compilers for paralle and vector machines ACM-SIGPLAN

notices V.10 Mar 1975

Ligett, McCluskey, and McKeeman: parallel LR parsing

Wagn Institute of Gradaute studies, School of information technology, technical report TR 82-03 1982

Mickunas, Schell: parallel compilation in a multiprocessor enviornment

Proc ACM 1987

Hope it helps.

Reply-To: Robert C Elliott <rce10845@uxa.cso.uiuc.edu>

A paper titled "Object Oriented Parallel Parsing for Context-Free

Grammars" appears in Yonezawa's _ABCL: An Object-Oriented

Concurrent System_ (related to the actor model).

The article is by Yonezawa and Ohsawa. Yonesawa will be at OOPSLA

next week.

Reply-To: ht@cogsci.edinburgh.ac.uk

In Proceedings of the International Workshop on Parsing Technologies,

Carnegie Mellon, 1989 (Available from Joan Maddamme, Computer Science,

CMU, Pittsburgh, PA 15213-3890, Also a book soon from MIT Press --

Current Issues in Parsing Technology, Masaru Tomita editor) are a

number of papers, including a good brief survey by Nijholt. Also soon

to appear from Ablex: Parallel Models of Natural Language

Computation, Adriaens and Hahn, editors.

The abstract parallel chart parser described in my contribution to the

Pittsburgh workshop is available on request.

Reply-To: Jonathan Michael David Hill <hilly@cs.qmw.ac.uk>

I recently read on network news that you are interested in

parallel algorithms and implementations of parsing techniques .

I have developed and implemented parallel algoirthms for lexical

analysis and parsing .

Both algorithms exhibit SIMD parallelism and I have

implemented them on the AMT Distributed Array Proccessor which

contains 1024 processors (although a 4096 version is available

to me here , I have not ported the software ).

Both lexical analyser and parser have a time complexity logorithmic in

relation to the input length , although I have not got the

results with me at the present time , if I remember correctly

the parser can process about 2 million tokens per second .

If you are interested in the work I have done then e-mail or

write to me , and we can discuss this in more detail (or I

could send you a report on the work) .

=========================== MODERATOR ==============================

Steve Stevenson fpst@hubcap.clemson.edu

(aka D. E. Stevenson), steve@hubcap.clemson.edu

Department of Computer Science, comp.parallel

Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell

====================================================================

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.