The name derives from the formalism invented by Adriaan van Wijngaarden[2] for the purpose of defining the ALGOL 68 programming language.
[4] W-grammars are two-level grammars: they are defined by a pair of grammars, that operate on different levels: The set of strings generated by a W-grammar is defined by a two-stage process: The consistent substitution used in the first step is the same as substitution in predicate logic, and actually supports logic programming; it corresponds to unification in Prolog, as noted by Alain Colmerauer[where?].
Curtailed variants, known as affix grammars, were developed, and applied in compiler construction and to the description of natural languages.
This work influenced the design and implementation of programming languages, most notably, of ALGOL 60, which introduced a syntax description in Backus–Naur form.
This is typically subject to constraints such as: W-grammars are based on the idea of providing the nonterminal symbols of context-free grammars with attributes (or affixes) that pass information between the nodes of the parse tree, used to constrain the syntax and to specify the semantics.
This idea was well known at the time; e.g. Donald Knuth visited the ALGOL 68 design committee while developing his own version of it, attribute grammars.
[citation needed] This was partly a consequence of the way in which they had been applied; the 1973 ALGOL 68 "Revised Report" contains a much more readable grammar, without modifying the W-grammar formalism itself.
Meanwhile, it became clear that W-grammars, when used in their full generality, are indeed too powerful for such practical purposes as serving as the input for a parser generator.
They describe precisely all recursively enumerable languages,[8] which makes parsing impossible in general: it is an undecidable problem to decide whether a given string can be generated by a given W-grammar.
Restricted and modified variants of W-grammars were developed to address this, e.g. After the 1970s, interest in the approach waned; occasionally, new studies are published.