Van Wijngaarden grammar

In computer science, a Van Wijngaarden grammar (also vW-grammar or W-grammar) is a two-level grammar which provides a technique to define potentially infinite context-free grammars in a finite number of rules. The formalism was invented by Adriaan van Wijngaarden to define rigorously some syntactic restrictions which previously had to be formulated in natural language, despite their essentially syntactical content. Typical applications are the treatment of gender and number in natural language syntax and the well-definedness of identifiers in programming languages.

The technique was used and developed in the definition of the programming language ALGOL 68. It is an example of the larger class of affix grammars.

A W-grammar consists of a finite set of meta-rules, which are used to derive (possibly infinitely many) production rules from a finite set of -rules. Meta-rules are restricted to those defined by a context-free grammar. Hyper-rules restrict the admissible contexts at the upper level. Essentially, the consistent substitution used in the derivation process is equivalent to unification, as in Prolog, as was noted by Alain Colmerauer.

For example, the assignment x:=1 is only valid if the variable x can contain an integer. Therefore, the context-free syntax variable := value is incomplete. In a two-level grammar, this might be specified in a context-sensitive manner as REF TYPE variable := TYPE value. Then ref integer variable := integer value could be a production rule but ref Boolean variable := integer value is not a possible production rule. This also means that assigning with incompatible types becomes a syntax error which can be caught at compile-time. Similarly,

...
Wikipedia