skill@QUCIS.BITNET (07/16/88)
We have been looking at parallel techniques for parsing, starting
from the lexing result of the folks at Thinking Machines. We have
shown that, for SIMD-type architectures, languages whose grammars are
in LL can be parsed in O(log n) time. This does NOT extend to LR
(in fact, it's another interesting characterization of the difference).
Of course, this means that parallel parsing can be done on MIMD machines
with an extra log n penalty. We've also shown how to pipeline the
algorithm.
We've also started looking at parallelizing semantic analysis.
Stay tuned for success/failure.
We can send you a copy of the paper either electronically if you
have a troff environment and a decent email address; or by snail
mail if you send me an address (to skill@qucis.bitnet). We'd also
like to hear from anyone who's been thinking along the same lines.
David Skillicorn
David Barnard
Computing and Info Science
Queen's University
Kingston Ontario
Canada
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU
Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | bbn}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers. Meta-mail to ima!compilers-request