Attribute grammar inversion and source-to-source translation (Q1210738)

This book presents a new methodology for building source-to-source translation, based upon attribute grammar (AG, for short) inversion. The basic idea of this methodology is to construct a canonical form in which programs of all source languages can be represented and to write invertible AGs from each source language into this canonical form. Then, using the inversion technique, one can obtain the inverse translation from the canonical form into each programming language. A source-to- source translator between two languages is obtained by inversion and composition of translators. The book contains two parts. The first part presents the AG inversion approach and the second one deals with a real system, called INVERT used as a tool to produce source-to-source translators. Part one consists of chapters 2, 3 and 4. In chapter 2 a new grammar based translation methodology is introduced, namely restricted inverse form (RIF, for short) grammars. An RIF is a restricted AG that can be easily inverted to specify inverse translation. It is also proved that any translation expressible by an AG can be expressed by an RIF. Chapter 3 investigates the automatic inversion of RIFs, presenting the inversion algorithm for an arbitrary RIF. Some properties of the inverse grammar are also examined. An extension of RIF grammars is introduced in chapter 4. Part two of this book consists of chapters 5, 6 and 7. In chapter 7 the INVERT system is presented. This system accepts a restricted AG as input and produces the inverted grammar as output. Chapter 6 presents a methodology for building source-to-source translators, based upon AG inversion. The basic principles for constructing a canonical form in which programs of all source languages can be represented, are also discussed. The above methodology is used to build translators between Pascal and C programming languages and to create a canonical form, called ABSIM. The last chapter points out some conclusions and suggests directions for future research. The book ends with two appendices. The first studies the computational power of the AGs introduced in chapter 2. The second one presents some examples of translations produced by the Pascal-to-C and C-to-Pascal translators.