EAGs (Extended Attribute Grammars)

This page is Copyright John N. Shutt 1996–2001, 2007.  Here's what you're allowed to do with it.
Last modified:  05-Jul-07.

Extended attribute grammars (EAGs) are a reformulation of Knuth's attribute grammars, suggested by Watt and Madsen in 1977.  Although clearly not adaptive by my definition, EAGs are important for their conceptual role in the development of Christiansen grammars (and thus, indirectly, of RAGs).  They also figure prominently in my speculations on the nature of grammar.

EAGs differ from Knuth's original model in three ways:

  1. Semantic function domains are treated more rigorously, by means of many-sorted algebras.
  2. Attribute evaluation, which for Knuth was logically separate from context-free derivation, is integrated directly into the EAG derivation relation.
  3. Knuth's semantic equations are replaced by a more declarative form.
EAGs eliminate the semantic equations by attaching polynomials (over suitable domains of attribute values) directly to the nonterminals in the context-free rules; the result of embedding these polynomials in a context-free rule is called a rule form.  Substituting values for the variables in a rule form produces a rule instance, which has embedded attribute values rather than embedded polynomials.  Derivations use rule instances; hence, the selection of attribute values is not logically distinct from the construction of derivations.

It is also possible to view EAGs as a kind of two-level grammar.  The rule forms generate an infinite set of rule instances, which may be treated as the rule set of an infinite context-free grammar whose nonterminals are the attributed nonterminals of the EAG.  (There seems to me to be a difference in emphasis, however, between EAGs, which fall within the philosophical tradition of attribute grammars, and e.g. van Wijngaarden grammars, which have always had a separate tradition.)

There's a much more extensive treatment of EAGs in my Master's thesis.

Offline sources:  The original paper is [Watt 77], the principal reference used here is [Mads 80].

Up: Adaptive Grammars