Affordable Access

Publisher Website

Parallel lexical analysis and parsing on the AMT distributed array processor

Authors
Journal
Parallel Computing
0167-8191
Publisher
Elsevier
Publication Date
Volume
18
Issue
6
Identifiers
DOI: 10.1016/0167-8191(92)90008-u
Keywords
  • Compiler
  • Lexical Analysis
  • Parsing
  • Parallel Prefix Technique
  • Simd
Disciplines
  • Computer Science
  • Mathematics

Abstract

Abstract I discuss an implementation of a parallel lexical analyser and parser for the AMT Distributed Array Processor (DAP). I show that by utilising the two dimensional topology of the DAP it is possible to improve the complexity of the Hillis & Steele [5,6] lexing algorithm from logarithmic squared time to logarithmic time in relation to the input length. I also show that the conclusions produced by Barnard & Skillicorn [1] that languages generated by LL(1) grammars can be parsed in logarithmic time on SIMD system is incorrect, and only a subset of the languages generated can be parsed in at least logarithmic time.

There are no comments yet on this publication. Be the first to share your thoughts.