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