[Boost-users] [Proto] Extracting types of sub-expression in transform

Subject: [Boost-users] [Proto] Extracting types of sub-expression in transform
From: Ivan Godard (igodard_at_[hidden])
Date: 2008-10-20 22:38:42

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!  :-)