Two-Level van Wijngaarden Grammars

BNF cannot express context conditions ("declared before use", "modes match").

38.1 Why two levels?

BNF cannot express context conditions ("declared before use", "modes match"). Adriaan van Wijngaarden's solution: a grammar with two levels:

Metaproduction rules (the first level) define metanotions (written in CAPITALS), each generating a possibly infinite set of strings called protonotions (written in lower case).

Hyper-rules (the second level) are rule *templates* containing metanotions. Substituting protonotions for the metanotions — consistently, the same value for every occurrence of a metanotion in a rule — yields the (infinitely many) ordinary production rules.

38.2 A tiny example: a^n b^n c^n

The language { a^n b^n c^n | n ≥ 1 } is not context-free, but a W-grammar describes it easily:

N generates i, ii, iii, ... (unary numbers). Because N must be replaced consistently throughout the sentence rule, all three sequences have the same length. For N = ii:

so sentence derives a a b b c c.

Metaproduction rules:
   N     :: i ; N i.
   ALPHA :: a ; b ; c.

Hyper-rules:
   sentence : letter a sequence N, letter b sequence N, letter c sequence N.
   letter ALPHA sequence N i : letter ALPHA sequence N, letter ALPHA symbol.
   letter ALPHA sequence i   : letter ALPHA symbol.

sentence : letter a sequence ii, letter b sequence ii, letter c sequence ii.
letter a sequence ii : letter a sequence i, letter a symbol.
letter a sequence i  : letter a symbol.

38.3 Notation used in the Report

metaproduction ("is one of") concatenation of members the empty protonotion where..., unless...

predicates: notions that produce EMPTY when a condition holds and are blind alleys otherwise

38.4 Modes in the grammar (abridged from the Revised Report)

So long long integral and reference to real are protonotions produced by MODE — modes are *strings in the grammar*.

MODE :: PLAIN ; STOWED ; REF to MODE ; PROCEDURE ; UNITED ;
        MU definition of MODE ; MU application.
PLAIN :: INTREAL ; boolean ; character.
INTREAL :: SIZETY integral ; SIZETY real.
SIZETY :: long LONGSETY ; short SHORTSETY ; EMPTY.
LONGSETY :: long LONGSETY ; EMPTY.

38.5 Contexts in the grammar (simplified)

The metanotion NEST carries the declarations visible at that point (the symbol table!) through the derivation, so "identifier declared with the right mode" becomes a syntactic condition. Words like soft and strong select which coercion rules may apply — Chapter 27's contexts are literally part of the syntax.

REF to MODE NEST assignation :
   REF to MODE NEST destination, becomes token, MODE NEST source.
REF to MODE NEST destination : soft REF to MODE NEST TERTIARY.
MODE NEST source : strong MODE NEST unit.

38.6 Strengths and criticisms

Strengths: a single formalism defines both context-free and context-sensitive syntax; it is precise; W-grammars are Turing-complete (they can describe any recursively enumerable language).

Criticisms: very hard to read (a major complaint of the Minority Report), hard to use for building parsers, and Turing-completeness means questions about the grammar can be undecidable.

Legacy: affix grammars (Koster), attribute grammars (Knuth, 1968), and later formal semantics work all address the same problem in more tractable ways. Compiler-construction tools today use context-free parsing plus attribute/semantic analysis — the practical descendant of this idea.