## On the time required to parse an arithmetic
statement for parallel processing

38. R. Towle and R. P. Brent,
On the time required to parse an arithmetic
statement for parallel processing,
* Proceedings of the 1976
International Conference on Parallel Processing*
(edited by P.H. Enslow),
IEEE, New York, 1976, 254.
Paper: pdf (74K).

## Abstract

This paper announces a result on the time required to parse an
arithmetic expression (containing *N* tokens)
using the associative, commutative and distributive
laws valid over a ring. Upper bounds on the time required for
Beatty's algorithm
[*J. ACM* 21 (1974), 613-640] and for
Brent's algorithm [22] are given.
The use of the associative and commutative laws adds O(*N*) time to
the parsing process, and the use of all three laws
adds O(*N* log *N*) time.
## Comment

Further details are given in Ross Towle's thesis,
* Control and data dependence for program transformations*,
Dept. of Computer Science, University of Illinois at Urbana-Champaign,
UIUCDCS-R-76-788, March 1976, 113 pp.
Go to next publication

Return to Richard Brent's index page