Finding Minimum Cost Derivation Trees for Regular Tree Grammars
Maya Madhavan and Priti Shankar

(September 1998)

Available formats: [ps] [ps.gz]

Updated on May 6, 2004

Regular tree grammars have been used extensively as specification mechanisms for re­ targetable code generation. Conventional code generation tools construct a finite state tree pattern matching automaton from a regular tree grammar specification. This automaton generates optimal code by traversing an intermediate code tree and constructing a mimimum cost derivation tree for it. Cost computations can be carried out either at the grammar preprocessing phase, or during the matching phase, the former choice usually resulting in larger tables. We propose a construction that augments the precomputation step of a regular tree pattern matching algorithm to include cost analysis. The matching device generated is a pushdown automaton in contrast with the conventionally generated tree pattern matching automaton. The technique can be viewed as an extension of the well known Graham­Glanville technique for table driven code generation, as it is essentially based on LR parsing techniques, augmented to handle ambiguous string grammars derived from regular tree grammars. Our technique can handle a larger class of cost augmented regular tree grammars than can be preprocessed by conventional methods, and has been tested on some input problem instances representing instruction sets of two processors.

Please bookmark this technical report as

Problems ? Contact
[Updated at 2009-10-22T06:42Z]