Tech Report -- Parallel Compilation

We have just finished a tech report describing some bits and pieces
related mostly to parallel parsing. If you would like a copy and you
do not regularly get Queen's tech reports, send email to:


                          heather@qucis.queensu.ca


Here is the abstract:


This report describes some of the work related to parallel compiling that has
been done at Queen's during the last year. It contains four chapters; the
first describes an implementation of the Steele/Hillis parallel lexing
algorithm, including finding the lexed tokens and extracting them. The
second chapter describes an implementation of the Skillicorn/Barnard
algorithm for parsing {LL} grammars in parallel. The third chapter describes
a scheduling method that allows {SIMD} machines to carry out more than one
reduction simultaneously. Because the parallel parsing and lexing algorithms
are of this kind, this scheduling method allows strings longer than the
number of processors in a system to be lexed or parsed efficiently. The
fourth chapter discusses a modification to the Cocke-Younger-Kasami that
allows parsing of context-free languages on a number of processors linear in
the input size in quadratic time. An extensive bibliography on parallel
compilation is included.


                                                                          -David Skillicorn
                                                                            David Barnard

Return to the comp.compilers page.
Search the comp.compilers archives again.