Parallel Parsing and Compiling

Parallel Parsing and Compiling

Post by David Skillico » Thu, 18 Oct 1990 00:16:47

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

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

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

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

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


1. compile&parse with joe

Has anyone set up joe to compile the file in the current window and parse
the errors without any interaction?

Right now I have to press ^E C then type

gcc -Wall -c myfile.c

How would I go make a macro so that the name of the current file is
somehow automatically inserted? I need it to be the right filename so the
errors can be parsed correctly - unlike the spellcheck macro which just
cat's the current window to ispell.tmp.

I am using joe 2.2 (I think.. I am not sure where the version number is
:(), running under Linux 1.2.8.


Erwin Andreasen  Viby J, Denmark   Computer Science Student at Aarhus Business


2. Need only:- EAD/GC/Citizen who are local to NY/NJ only

3. cross compiling gcc - parse error

4. how to generate DTMF on h323 answer call

5. Need References on Incremental Parsing and Compiling

6. comp.os.msdos.programmer FAQ diffs

7. ipx under win2k

8. Please Help - HP Scanjet 4c ands NT

9. parallel parsing

10. Parallel Parsing

11. Looking for recent papers on parallel lexing/parsing

12. SUMMARY: Parallel Parsing