On Parsing and Compiling Arithmetic Expressions in Parallel Computational Environments

Abstract

The problem of parsing and compiling arithmetic expressions in parallel computational environments is considered. It is seen that the concept of Operator Precedence can be generalized to allow encodings of one or more arithmetic expressions to be transformed directly into encodings of their corresponding derivation trees. The algorithm which performs this transformation is compact, efficient (linear in both time and space), and highly concurrent. Further, it can be extended to compile arithmetic expressions directly into object code (in the form of quadruples). The extention preserves the compactness, efficiency (1inearity) and highly concurrent nature of the original a1gorithm.