A Survey of Tree-Walk Evaluation Strategies for Attribute Grammars

Yellin, Daniel

Since the time that Knuth's seminal paper on attribute grammars (AGs) first appeared [24], the AG formalism for specifying the translation process has received much attention and has become the basis for several real translator-writing systems [12, 15, 19, 20, 25]. It seems to be a promising vehicle for automating the construction of compilers, in addition to its various other uses currently under investigation which includes syntax directed editors [5], attributed parsing [18, 39], interactive proof checking [35], waveform analysis [30], natural language translation into SQL data base code [31] and SQL data base code translation into natural language [27]. Given a sentence in a source language, an AG specifies a unique semantic tree for that sentence. The translation is found by evaluating the attribute-instances of the semantic tree. Upon completion, certain distinguished attributes of the root contain the translated string. Due to the declarative nature of the AG, there is no unique way to evaluate the semantic tree. Determining strategies to evaluate the semantic trees of an AG has been the focus of much discussion in the literature. It has both theoretical and practical importance: Bad strategies of evaluating semantic trees can be very inefficient in terms of both space and time making AGs less attractive for real translator-writing systems. In this paper we survey static tree-walk evaluator strategies that have been developed for evaluating semantic trees. We compare the evaluators to each other on the basis of several performance criteria. We develop the notion of optimality of an evaluator and determine how close a given evaluation strategy comes to optimal. By considering different strategies we find a natural taxonomy of AGs: as not every AG will give rise to semantic trees evaluable by a given strategy S, we can define the class of S-evaluable AGs as exactly those AGs whose semantic trees are evaluable by strategy S. In this way we will discover a hierarchy of strategies of increasing power, the strongest strategy being one capable of evaluating the semantic trees of any well-defined AG. In section 1 we present a brief introduction to AGs and set forth some terminology to be used in the rest of the paper. In section 2 we introduce the general idea of tree-walk evaluators and we formalize the concept of an optimal tree-walk evaluator for a semantic tree. In section 3 we define an especially useful class of evaluators called static evaluators. In the next three sections we survey three types of static evaluators: pass-oriented evaluators, uniform evaluators and multi-protocol evaluators. In section 7 we summarize our conclusions and review the taxonomy of AGs we have developed. The appendix presents the proofs of two NP-complete problems cited in the survey.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-134-84
Published Here
February 22, 2012