Degree Type

Dissertation

Date of Award

1981

Degree Name

Doctor of Philosophy

Department

Computer Science

Abstract

This thesis describes the design of an idiom matching technique in a compiler for APL. Idioms are programming language constructs used by programmers for the logical primitive operations for which no language primitives exist. Due to APL's richness of operators, idioms tend to appear at the "expression level." APL users have to pay a very high price to execute their APL programs with operator-by-operator execution in conventional translators. However, each idiom can be treated as a unit. It has been shown (2) that the saving from optimizing such idioms can be very impressive. Other researchers (1,3) have collected lists of idioms for APL;Idiom matching consists of two problems, recognition and selection, which are dealt with in this work. The idiom recognition problem is solved by a finite tree automaton. This approach constructs an automaton directly from a regular tree expression for a set of idioms. A practical automaton minimization algorithm is developed that obtains a time bound of O(n('2)(.)log n) for any binary tree automaton with n states. The selection problem, locating the best non-overlapping idioms in an expression tree, is solved in O(n) time;1. Brown, W. E. "Toward an Optimizing Compiler for a Very HighLevel Language." Ph.D. dissertation, Iowa State University, 1979;2. Miller, T. C. "Tentative Compilation: A Design for an APLCompiler." Ph.D. dissertation, Yale University, 1978;3. Perlis, A. J. and Rugaber, S. "The APL Idiom List." ResearchReport #87, Department of Computer Science, Yale University,April, 1977.

DOI

https://doi.org/10.31274/rtd-180813-4667

Publisher

Digital Repository @ Iowa State University, http://lib.dr.iastate.edu/

Copyright Owner

Feng Sheng Cheng

Language

en

Proquest ID

AAI8128808

File Format

application/pdf

File Size

132 pages

Share

COinS