Van Wijngaarden grammar

Van Wijngaarden grammar is a 2-level formal grammar, also W-grammar or vW-grammar, is a technique to define potentially infinite grammars in a finite number of rules. Adriaan van Wijngaarden invented this to define rigorously some syntactic restrictions which previously had to be formulated in natural language, despite of their essentially syntactical content. One of these is the requirement of uniqueness of identifiers in program units and the unification of application and definition of these identifiers.

The technique was used and developed in the definition of the programming language ALGOL 68.

Overview

A W-grammar consists a finite set of meta-rules, which are used to derive, possibly infinite many, production rules out of a finite set of hyper-rules. Meta-rules are restricted to be defined in 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 .

Outside ALGOL 68

It was noted that 2-level grammars had potential to be used outside the primary application field.

Anthony Fisher tried to construct a parser for general W-grammars (http://www-users.cs.york.ac.uk/~fisher/software/yoyvwg/).

It has been proposed using the method in describing complex human actions in ergonomics.