Overview

In the field of programming language description, it is widely accepted that van-Wi1ngaarden grammars (vWGs, [Ba72), [A68R) provide a powerful and yet simple formalism to describe the syntax and context conditions of programming languages. (See, for instance, the comparison of definition techniques given in [MBL76).) However, vWGs cannot be used for automatic compiler generation, since the "referencing problem" [K074) is not decidable in general. Several proposals have been made to restrict vWGs to decidable subclasses that are suited for automatic parser generation, for example [Ba72), [De7S), [KS77), and [We78). Extended Affix grammars (EAGs, defined in [Wa7S) are of particular interest, since they fill the gap between Two-Level language description in vWG-style, and more compiler-oriented description tools, such as affix grammars (AGs, [K07I), and attribute grammars (AttrGs, [Kn68): EAGs preserve most of the descriptive properties of vWGs, but allow to generate parsers that are as efficient as those generated from AGs and AttrGs. The EAGLE project is a compiler generator project aiming at using EAG language descriptions for automatic compiler generation. One of the sub tasks is to develop a notation which resembles vWGs as closely as possible [FHS78), so that it may serve as a appropriate descriptive tool for both languages and compilers. In the following, we describe a result which liberates the notation of EAGs from all explicit "data flow information".