Abstract
The question of how many temporary storage registers are needed to evaluate compiled arithmetic and masking expressions is discussed. It is assumed that any combination of left-to-right, right-to-left, top-to-bottom, and bottom-to-top techniques may be used to evaluate an expression, but that no factoring or re-arranging of the expression may occur. On this basis, the maximum number of registers needed to evaluate nonparenthesized expressions isN+1, withN the number of dyadic operator precedence levels. For parenthesized expressions with a maximum ofK nested parenthetical subexpressions, the maximum number of registers needed is (K+1)N+1.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Bibliography
J. Cohen,Langages pour l'écriture de compilateurs, Doctoral dissertation, University of Grenoble, Grenoble, France, 1967.
I. Nakata,On compiling algorithms for arithmetic expressions, Comm. ACM 10, 8 (August 1967), 492–494.
R.R. Redziejowski,On arithmetic expressions and trees, Comm. ACM 12, 2 (February 1969), 81–84.
D. T. Ross,The AED approach to generalized computer-aided design, Proc. 22nd National ACM Conf., 1967.
V. B. Schneider,A system for designing fast programming language translators, Proc. 1969 Spring Joint Comp. Conf.
N. Wirth and H. Weber,A generalization of ALGOL and its formal definition: Parts I and II, Comm. ACM 9, 1 (Jan.–Feb. 1966), 89–99.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Schneider, V. On the number of registers needed to evaluate arithmetic expressions. BIT 11, 84–93 (1971). https://doi.org/10.1007/BF01935328
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01935328