chou@CS.UCLA.EDU (Ching-Tsun Chou) (10/25/90)
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
====================================================================
--
Send compilers articles to compilers@esegue.segue.boston.ma.us
{ima | spdcc | world}!esegue. Meta-mail to compilers-request@esegue.chou@CS.UCLA.EDU (Ching-Tsun Chou) (10/25/90)
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>
--------------------------------------------------------------------------------
From: 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
From: 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.
From: 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
From: 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
From: 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
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
From: rekers@cwi.nl (Jan Rekers)
In article <1990Oct15.202912.12815@esegue.segue.boston.ma.us>,
chou@CS.UCLA.EDU (Ching-Tsun Chou) writes:
|> Does anyone know of any works, either theoretical or practical, on
|> parsing context-free languages with parallel algorithms?
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!
From: 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.
From: 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.
From: 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
From: 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".
From: 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.
From: 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.
-David Skillicorn
From: 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.
From: 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.
From: 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.
From: 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.
From: 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.
From: 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.
From: 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.
From: 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},
}
From: reinoud@duteca2.tudelft.nl (R. Lamberts)
Hi Ching Tsun,
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,
From: 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 !
From: 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.
From: 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,
From: 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.
From: 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
From: skill@qucis.queensu.ca
To: compile@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
From: 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
From: 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.
From: 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.
From: 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.
From: 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.
From: 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.
From: 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.
From: 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) .