Can I read Look Ma, No Hashing, and No Arrays Neither on EtoBox?

Look Ma, No Hashing, and No Arrays Neither by Jiazhen Cai; Robert A. Paige is a scholarly article available to read on EtoBox.

What is Look Ma, No Hashing, and No Arrays Neither about?

It is generally assumed that hashing is essential to many algorithms related to efficient compilation; e.g., symbol table formation and maintenance, grammar manipulation, basic block optimization, and global optimization. This paper questions this assumption, and initiates development of an efficient alternative compiler methodology without hashing or sorting. Underlying this methodology are several generic algorithmic tools, among which special importance is given to Multiset Discrimination, which partitions a multiset into blocks of duplicate elements. We show how multiset discrimination, together with other tools, can be tailored to rid compilation of hashing without loss in asymptotic performance. Because of the simplicity of these tools, our results maybe of practical as well as theoretical interest. The various applications presented culminate with a new algorithm to solve iterated strength reduction folded with useless code elimination that runs in worst case asymptotic time and auxiliary space linear in the maximum text length of the initial and optimized programs. 1. Introduction. with linear search time and a hash table. They also pro-An important practical and theoretica

Author

Jiazhen Cai; Robert A. Paige

Publisher

ACM Press

Published

1991

Language

EN