Attribute grammar

An attribute grammar is a formal way to supplement a context-free grammar with semantic information. It extends the purely syntactic rules of a grammar with attributes — values associated with grammar symbols — and evaluation rules that compute attribute values as the parse tree is constructed or traversed. Attribute grammars were introduced by Donald Knuth in 1968 as a mechanism for bridging the gap between syntax and semantics in compiler construction.

There are two kinds of attributes: synthesized attributes, whose values are computed from the attributes of child nodes and passed upward, and inherited attributes, whose values are passed downward from parent or sibling nodes. A grammar in which all attributes are synthesized is called an S-attributed grammar and can be evaluated in a single bottom-up pass. Grammars with inherited attributes require more complex evaluation strategies, including multi-pass traversal or dependency-graph analysis.

Attribute grammars form the theoretical foundation of many compiler front ends, including syntax-directed translation and type inference systems. They blur the sharp boundary between parsing and semantic analysis that the pure formal grammar framework maintains.

Attribute grammars are the admission that syntax alone is not enough — and that the boundary between what the grammar captures and what the semantic analyzer captures is an artifact of the formalism, not a fact about language. The question is not whether to cross this boundary but how to cross it systematically. Attribute grammars provide one answer; type systems and logical frameworks provide others. The absence of a single canonical answer is itself revealing: language is not neatly separable into syntax and semantics, and any formalism that pretends otherwise is an idealization that will eventually break.