Parallel algorithms for compilation.

Abstract

This thesis explores the design of parallel algorithms for the compilation process, using a SIMD (Single Instruction, Multiple Data) shared memory architecture that avoids read/write conflicts. Several phases of compilation are studied, and efficient parallel algorithms are proposed for:

Converting arithmetic infix expressions into syntax trees Restructuring expressions for parallel evaluation Generating code for SIMD machines from syntax trees Parsing a subclass of regular languages (PF(k) parsable languages) Parsing a subclass of deterministic context-free languages using a new hierarchical specification scheme

Complexity analysis shows that most algorithms achieve a time complexity of O(log² n) using O(n) processors, where n is the length of the input string. An exception is the code generation algorithm, which requires O(n) time. These results demonstrate the feasibility and efficiency of parallel compilation techniques on SIMD architectures.