1984 Reports

The Automatic Inversion of Attribute Grammars

Yellin, Daniel; Mueckstein, Eva-Maria M.

Over the last decade there has developed an acute awareness of the need to introduce abstraction and mathematical rigor into the programming process. This increased formality allows for the automatic manipulation of software, increasing productivity and, even more importantly, the manageability of complex systems. Along these lines, attribute grammars constitute a formal mechanism (or specifying translations between languages; from a Cormal description of the translation a translator can be automatically constructed. In this paper we consider taking this process one step further: given an attribute grammar specifying the translation from language L1 to the language L2, we address the question of whether the inverse attribute grammar specifying the inverse translation from L2 to L1 can be automatically generated. We show how to solve this problem for a restricted subset of attribute grammars. This inversion process allows for compatible two-way translators to be generated from a single description. To show the practical feasibility of attribute grammar inversion, we relate our experience in inverting an attribute grammar used as an interface for a formal database accessing language, SQL. The attribute grammar is used to paraphrase SQL database queries in English.