Parallel algorithms for compilation

Abstract

This thesis discusses the design of parallel algorithms for the compilation process. The model of computation is an SIMD (Single Instruction, Multiple Data) computer with shared memory, where no read or write conflicts are permitted. Several phases of the compilation process have been studied, and parallel algorithms have been designed for the following tasks:

Conversion of arithmetic infix expressions into syntax trees Restructuring of arithmetic expressions into forms more suitable for parallel evaluation Code generation for SIMD machines from syntax trees representing arithmetic expressions Parsing of a subclass of regular languages — the PF(k) parsable languages Parsing of a subclass of deterministic context-free languages, specified using a new scheme — the hierarchical language specification scheme

Complexity estimates have been obtained for all the above algorithms. It has been shown that a complexity bound of O(log² n) is attainable on O(n) processors for all the algorithms listed above, except for (3) (code generation), which requires O(n) time, where n is the length of the string being processed.