Eric Niebler wrote:

Anybody who understands van Wijngaarden grammars can help by explaining 
them to me in small words.  :-)

A van Wijngaarden Grammar definition for some target language (Algol68 in this case) is essentially an executable program written in a text substitution language i.e. VWG itself. If a candidate program purportedly written in the language defined by the grammar (Algol68) is submitted to an interpreter for the VWG language definition and the result is the empty string then the submitted program is well formed according to the grammar. If the result of the exercise is not the empty string then the submitted program contains an error.

The content of the left-over string (if one happens) is a clue about what was wrong in the submitted program, but practical compilers do not just run the submitted program against the grammar and tell you the result if any. Instead, the grammar is turned into a more conventional parser (automatically one hopes) so that actions can be performed as the grammar engine does the substitutions. These actions kick out the intermediate code for conventional middle- and back-ends. Note that such a parser is not pure syntax - because the VWG grammar embeds type and semantic constraints as well as syntactic ones, the actions can contain type and semantic behavior as well as conventional ASTs (Abstract Syntax Trees) - no separate bug-ridden semantic pass is needed.

You can validly see the VWG definitional mechanism as merely writing a canonical compiler for the target language and then using that compiler for the definition. The advantage of writing this compiler in VWG instead of say C is the brevity and rigor of the grammar representation. However, VWG does not remove the fundamental ontological paradox involved in language definition and indeed involved in mathematics itself, where the problem of axioms remains since the Greeks.

Ivan

p.s. a tutorial for two-level Grammars is at http://homepages.cwi.nl/~steven/vw.html, but the surface syntax (of the Grammar) is somewhat different from that used in the Report.

p.p.s. Also note that VWG is only a notational device for language definition; it still leaves the definition of the language itself up to the designer. Consequently designing a practical language remains. Thus it is trivial to write a VWG grammar that contains free non-terminals such that the syntax check of a candidate program in the defined language is equivalent to the halting problem. You thought gcc was slow? As a practical matter Algol68 was carefully defined to be LL(1) and compilable by a one-pass compiler with single-symbol lookahead, but that was the choice of the designers and not required by VWG. Would that C had been so designed! :-)