Accession Number : ADA611543


Title :   Rewrite Systems, Pattern Matching, and Code Generation


Descriptive Note : Doctoral thesis


Corporate Author : CALIFORNIA UNIV BERKELEY DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES


Personal Author(s) : Pelegri-Llopart, Eduardo


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a611543.pdf


Report Date : 09 Jun 1988


Pagination or Media Count : 223


Abstract : Trees are convenient representations because of their hierarchical structure, which models many situations, and the ease with which they can be manipulated. A rewrite system is a collection of rewrite rules of the form Alpha to Beta where Alpha and Beta are tree patterns. A rewrite system defines a transformation between trees by the repeated application of its rewrite rules. Two research directions are pursued in this dissertation: augmenting the expressive power of individual rewrite rules by using new types of patterns, and analyzing the interaction of the rewrite rules. The dissertation contains new algorithms for linear and non-linear patterns, for a new type of non-local pattern, and for typed patterns in which the variables are restricted to tree languages. The REACHABILITY problem for a rewrite system R is, given an input tree T and a fixed goal tree G, to determine whether there exists a rewrite sequence in R, rewriting T into G and, if so, to obtain one such sequence. REACHABILITY can be used to solve problems related to the mapping between concrete and abstract syntax trees, to construct a pattern matching algorithm for typed non-local patterns, and to provide algorithms for compiler code generation. A new class of rewrite system called finite bottom-up rewrite system (finite-BURS) is introduced for which the REACHABILITY problem can be solved efficiently with a table-driven algorithm. The C-REACHABILITY problem is similar to REACHABILITY except that rewrite sequences are assigned costs, and the obtained sequence is required to have minimum cost over all candidates. If the cost of a rewrite sequence is defined as the sum of the costs of its rewrite rules, the algorithm for REACHABILITY can be modified for a subclass of finite-BURS to solve C-REACHABILITY in such a way that all cost manipulation is done at table-creation time. The subclass extends the machine grammars used by Graham and Glanville for code generation.


Descriptors :   *TOPOLOGY , ALGORITHMS , CODING , COMPILERS , PATTERN RECOGNITION , PATTERNS , THESES , TRANSFORMATIONS


Subject Categories : Theoretical Mathematics
      Computer Programming and Software


Distribution Statement : APPROVED FOR PUBLIC RELEASE