Steven Pemberton, CWI, Amsterdam
www.cwi.nl/~steven/
steven.pemberton@cwi.nl
It has been long known that Two-Level Grammars (also known as Van Wijngaarden Grammars) can be used not only to define the syntax but also the semantics of programming languages. Here we give a quick introduction to the grammars and how they can be used to define the semantics of a programming language, and then present a technique for making those definitions executable.
1VWG′s are a notational variant of BNF: use ‘:’ instead of ‘::=’,
use ‘;’ instead of ‘|’, do not use ‘< ’ or ‘>’ but give
terminals a name ending in ‘symbol’, separate notions (terminals or
nonterminals) with ‘,’, end rules with ‘.’.
E.g.
<vwg> ::= <rule> | <rule> <vwg>now reads
vwg: rule; vwg, rule.Here is the rest of the 1VWG structure:
rule: notion, colon symbol, alternatives, stop symbol. alternatives: alternative option; alternative option, semicolon symbol, alternatives. alternative option: alternative; empty. alternative: notion; notion, comma symbol, alternative. empty: . notion: letter; letter, notion. letter: letter a symbol; letter b symbol; ... ; letter z symbol.Such a definition is also accompanied by a list of ‘representations’ of symbols.
A 2VWG can be regarded as a ‘parameterised’ 1VWG. The formal parameters are expressed in capital letters and digits, whose allowable values are defined by a second, context-free, grammar. Substituting values for these parameters gives a 1VWG, which can then be used to generate strings in the usual manner.
A formal parameter is called a ‘metanotion’, and is defined by a ‘metarule’:
THING:: letter; rule.A parameterised rule is called a ‘hyperrule’:
THING list: THING; THING, THING list.The essential process of substitution is called ‘Uniform Replacement’, or ‘Consistent Substitution’: an instance of a metanotion must be consistently replaced in a hyperrule.
Thus the above hyperrule stands for the two rules:
letter list: letter; letter, letter list. rule list: rule; rule, rule list.This is a typical use of hyperrules, for contractions. The process can be generalised, by using a metanotion that effectively produces any ‘notion’:
NOTION:: L; L NOTION. L:: a; b; c; d; e; f; g; h; i; j; k; l; m; n; o; p; q; r; s; t; u; v; x; y; z.then general contractions can be written:
NOTION list: NOTION; NOTION, NOTION list. NOTION option: NOTION; .etc. Note that these stand for an unbounded number of rules. Also note that consistent substitution only applies to hyperrules, and not to metarules.
‘NOTION list’ could alternatively have been defined like this:
NOTION list: NOTION, NOTION list option.
Sometimes you need to circumvent consistent substitution. There is a convention that if one or more digits are appended to a metanotion, for instance M1 (though some people use primes like M′) it assumes the existence of a metarule M1::M. (This actually makes them three level grammars). An example of using digits:
NOTION1 separated NOTION2 sequence: NOTION2;
NOTION2, NOTION1 symbol, NOTION1 separated NOTION2 sequence.
Using these metarules, we can now define a 1VWG as:
vwg: rule list. rule: notion, colon symbol, semicolon separated alternative sequence, stop symbol. alternative: comma separated notion sequence option. notion: letter list. letter: letter L symbol.
Note that as with any context-free grammar, you have to beware of creating ambiguous metarules. If you defined:
optional NOTION: NOTION; EMPTY. NOTION list: EMPTY; NOTION, NOTION list.then you wouldn't know whether an ‘optional rule list’ was an optional list of rules, or a list of optional rules.
Metanotions can be used for more than contractions. Here is an example producing an bn cn, well known for being non-context-free:
N:: ZERO; iN. ZERO:: . aNi: aN, letter a symbol. a ZERO: . bNi: bN, letter b symbol. b ZERO: . cNi: cN, letter c symbol. c ZERO: . anbncn: aN, bN, cN.This can be shortened:
N:: ;iN. A:: a; b; c. ANi: AN, letter A symbol. A: . anbncn: aN, bN, cN.Note that this example demonstrates why metarules use ‘::’ and not just ‘:’.
A final typical use of metanotions is for so-called ‘predicates’, which is a method of restricting or testing the value of a particular metanotion in a hyperrule. If it ‘succeeds’, it produces an empty sub-string, if not it produces a ‘blind alley’ which cannot be matched against any hyperrule, and is thus not used any further in the production process. A rather artificial example is:
anbncn: aN1, bN2, cN3, where N1 is N2, where N2 is N3. where N is N: .this is equivalent to the rule given above.
Since you can simulate a Turing machine with a VWG [van Wijngaarden], it is possible to define all aspects of a programming language, including its run-time semantics, with a VWG.
A major hurdle to automatically generating rules from a VWG is the traditional use of free metanotions in hyperrules, i.e. metanotions that occur on the right-hand side of a hyperrule, but not on its left-hand side. An example might be:
print EXPRESSION: evaluate EXPRESSION giving VALUE, represent VALUE.This causes a problem even for the human reader, since a VALUE must be dreamed up out of the blue that matches the required hyperrules. Sometimes the wording of the rule suggests a possible expansion (though of course this is no help to the mechanical generator), but often the process needs a lot of work and backtracking. A program could cope with such constructions, but only at a huge cost in time, since it would have to enumerate every expansion of the free metanotion to see if it fit, (and of course this may not, indeed usually would not, terminate).
Thus for a VWG definition of a language to be executable, some method has to be used that avoids free metanotions in hyperrules.
The idea presented here is to define a VWG whose start notion is a transliterated version of the program, and which generates a string of symbols representing the output of that program. For example, the ABC program [ABC],
PUT 1 IN a WRITE awould be written
put digit i number in letter a tag write letter a tagand the grammar would produce from this start notion
digit one symbolThe program must be transliterated in this way to prevent clashes between tags and the notions of the grammar. Otherwise consider the effect of
PUT ainbputb IN aThe grammar presented here, for obvious reasons, is only for a very simple language, and demonstrates the principles, and much work would be needed for a full definition.
The start notion will match the following hyperrule:
COMMANDS: execute COMMANDS in memory.This will start the execution process in an empty ‘memory’ which will be used for holding the values of variables. This needs a few metarules:
COMMANDS:: EMPTY; COMMAND COMMANDS.
EMPTY::.
COMMAND:: put EXPR in TARGET;
write EXPR;
if TEST indent COMMANDS outdent;
while TEST indent COMMANDS outdent.
So, we will only define put, write, if and while commands.
EXPR:: TERM; TERM plus EXPR. TERM:: FACT; FACT times TERM. FACT:: NUMBER; TAG. TEST:: EXPR COMP EXPR. COMP:: lt; le; eq; ne; ge; gt. TARGET:: TAG.Expressions will be restricted to addition and multiplication; tests to comparisons, and targets (variables) to simple tags. Note that the right recursion in the rules concerning expressions has no semantic effect, as it would in a BNF grammar: metarules are only used to define allowable strings for the metanotions, and how they do that is of no consequence.
NUMBER:: DIGIT number; DIGIT NUMBER. TAG:: LETTER tag; LETTER TAG. DIGIT:: digit D. LETTER:: letter L. D:: ZERO; i; ii; iii; iiii; iiiii; iiiii i; iiiii ii; iiiii iii; iiiii iiii. L:: a; b; c; d; e; f; g; h; i; j; k; l; m; n; o; p; q; r; s; t; u; v; w; x; y; z.(Note that apart from the start rule, we have only defined metarules up to now).
Now the definition process works by isolating the first COMMAND from a COMMANDS, executing (or transforming) that, and then executing the COMMANDS. Let us first consider the put command:
execute put EXPR in TARGET COMMANDS in memory VARS: ....Now the starting rule we gave above created the program in an empty memory, but of course, the put command in general works in a non-empty one. Let us define the memory:
VARS:: EMPTY; VAR VARS. VAR:: var TAG has VALUE. VALUE:: ZERO; iVALUE.Thus a VAR is a mapping from a TAG to a VALUE, and a VALUE for the purposes of this small language is a non-negative integer. Now, the purpose of our rule for a put command will be to transform the EXPR to a VALUE, and transform the VARS of the memory so that it contains the mapping from the tag to the value.
Let us assume for the moment that we have written the rules that transform
execute put EXPR in TARGET COMMANDS in memory VARSinto
execute put VALUE in TARGET COMMANDS in memory VARS(note that a VALUE is not an EXPR). Then we have two possibilities:
Thanks to consistent substitution, the first of these is the easier to define:
execute put VALUE1 in TAG COMMANDS in memory VARS1 var TAG has VALUE2 VARS2:
execute COMMANDS in memory VARS1 var TAG has VALUE1 VARS2.
The put command is complete: we can execute the following commands in a memory
where the only modification is a new value to TAG; nothing else has changed.
The case where this is the first use of the TAG requires a predicate:
execute put VALUE in TAG COMMANDS in memory VARS:
where TAG not in VARS,
execute COMMANDS in memory VARS var TAG has VALUE.
The predicate works by testing each TAG of the memory in turn:
where TAG1 not in var TAG2 has VALUE VARS2:
where TAG1 differs from TAG2, where TAG1 not in VARS2.
until it has tested them all:
where TAG not in EMPTY: where true. where true: .Checking that two tags are different uses the same method, testing each letter in turn, until two letters that do not match are found:
where LETTER1 TAG1 differs from LETTER2 TAG2:
where LETTER1 differs from LETTER2;
where LETTER1 is LETTER2, where TAG1 differs from TAG2.
or until it is discovered they were of different lengths:
where EMPTY tag differs from TAG: where true. where TAG differs from EMPTY tag: where true.A generalisation of ‘where ... is ...’ has been used here:
where ANY is ANY: where true. ANY:: EMPTY; NOTION.Testing if two letters are different is achieved by testing if the alphabet contains both letters:
where letter L1 differs from letter L2:
where L1 precedes L2 in abcdefghijklmnopqrstuvwxyz;
where L2 precedes L1 in abcdefghijklmnopqrstuvwxyz.
where L1 precedes L2 in ANY1 L1 ANY2 L2 ANY3: where true.
This definition of ‘differs from’ will be generalised later.
Now to define the transformation of EXPR into VALUE. We could define the evaluation of expressions only in the context of put commands. However shortly we shall need to evaluate them in other contexts, and furthermore they will have the same semantics there. Thus a more general method will be useful. This will be done by inserting markers in the production indicating expressions that should be evaluated:
execute put EXPR in TARGET COMMANDS in memory VARS:
execute put evaluate EXPR close in TARGET COMMANDS in memory VARS.
Both the beginning and the end of the expression need to be marked, since in
general such markers will be nested. From now on we will ignore the context
that an expression is evaluated in.
To evaluate an expression containing an operator, we first evaluate the operands:
ANY1 evaluate EXPR plus TERM close ANY2:
ANY1 evaluate evaluate EXPR close plus evaluate TERM close close ANY2.
ANY1 evaluate TERM times FACT close ANY2:
ANY1 evaluate evaluate TERM close times evaluate FACT close close ANY2.
(Strictly speaking this introduces an ambiguity, albeit a harmless one, since
either the left or the right operand could be evaluated first. To overcome
this, the following style of rules can be used:
ANY1 evaluate EXPR plus TERM close ANY2:
ANY1 evaluate evaluate EXPR close plus TERM close ANY2.
ANY1 evaluate VALUE plus TERM close ANY2:
ANY1 evaluate VALUE plus evaluate TERM close close ANY2.
)
Now we are left with the lowest level of expressions to evaluate: tags and numbers. To evaluate a tag we just map it to its value in the memory:
ANY1 evaluate TAG close ANY2 in memory VARS1 var TAG has VALUE VARS2:
ANY1 VALUE ANY2 in memory VARS1 var TAG has VALUE VARS2.
If the tag is not in the memory this rule does not apply, nor does any other,
meaning the program is undefined.
Evaluating numbers will be postponed until we have defined multiplication and addition. Suffice to say for now that it transforms a NUMBER to its corresponding VALUE.
This same method of inserting markers could be used for elaborating more complex variables then we have defined in this simple language.
The preceding section has now transformed expressions into bracketed pairs of values, with the values separated by ‘plus’ or ‘times’. Since integers to the base one are being used, addition is trivial, since it can be achieved by concatenation:
ANY1 evaluate VALUE1 plus VALUE2 close ANY2: ANY1 VALUE1 VALUE2 ANY2.Multiplication is achieved with repeated addition:
ANY1 evaluate VALUE1i times VALUE2 close ANY2:
ANY1 evaluate evaluate VALUE1 times VALUE2 close plus VALUE2 close ANY2.
ANY1 evaluate ZERO times VALUE close ANY2: ANY1 ZERO ANY2.
That is to say (a*b) = (((a-1)*b)+b), and (0*b)=0. Now we can define the
evaluation of NUMBERs:
ANY1 evaluate DIGITS digit D number close ANY2:
ANY1 evaluate evaluate evaluate DIGITS number close
times iiiii iiiii close plus D close ANY2.
ANY1 evaluate digit D number close ANY2: ANY1 D ANY2.
In brief, the first rule says
(ND)=(((N)*10)+D)It uses a new, if obvious, metarule:
DIGITS:: DIGIT; DIGIT DIGITS.
A write command evaluates its expression, and produces a representation of the resulting number:
execute write EXPR COMMANDS in memory VARS:
execute write evaluate EXPR close COMMANDS in memory VARS.
execute write VALUE COMMANDS in memory VARS:
repr VALUE, execute COMMANDS in memory VARS.
The representation of a number is traditional in VWG circles:
TEN:: iiiiiiiiii. VALUE1 repr TEN VALUE2: VALUE1i repr VALUE2. VALUEi repr D: repr VALUEi, repr D. repr D: digit D symbol.This can be seen as equivalent to the following function:
repr(v1, v2)=
if v2>=10: return repr(v1+1, v2-10)
if v1>=1 and v2 in {0..9}: return repr(0, v1) ++ repr(0, v2)
if v1=0 and v2 in {0..9}: return convert-to-text(v2)
These are rather straight-forward. The TEST is evaluated, and the COMMANDS executed accordingly:
execute if TEST indent COMMANDS1 outdent COMMANDS2 in memory VARS:
execute if test TEST close indent COMMANDS1 outdent COMMANDS2 in memory VARS.
Testing TESTs will either yield success or failure.
Assuming the definition of testing TESTs exists, if the test is successful we execute the controlled commands, and then the following ones. If the test is unsuccessful, only the following commands are executed:
execute if success indent COMMANDS1 outdent COMMANDS2 in memory VARS:
execute COMMANDS1 COMMANDS2 in memory VARS.
execute if failure indent COMMANDS1 outdent COMMANDS2 in memory VARS:
execute COMMANDS2 in memory VARS.
We can now define the testing of TESTs:
ANY1 test EXPR1 COMP EXPR2 close ANY2:
ANY1 test evaluate EXPR1 close COMP evaluate EXPR2 close close ANY2.
and the comparison operators:
ANY1 test VALUE eq VALUE close ANY2: ANY1 success ANY2.
ANY1 test VALUE1 eq VALUE2 close ANY2:
where VALUE1 differs from VALUE2, ANY1 failure ANY2.
This needs ‘differs from’ to be generalised:
where L1 NOTION1 differs from L2 NOTION2:
where L1 differs from L2;
where L1 is L2, where NOTION1 differs from NOTION2.
where L1 differs from L2:
where L1 precedes L2 in abcdefghijklmnopqrstuvwxyz;
where L2 precedes L1 in abcdefghijklmnopqrstuvwxyz.
The definition of ‘ne’ is left to the reader. Here are the order signs:
ANY1 test VALUE1 VALUE2 ge VALUE2 close ANY2: ANY1 success ANY2. ANY1 test VALUE1 ge VALUE1i VALUE2 close ANY2: ANY1 failure ANY2.
ANY1 test VALUE1 le VALUE2 close ANY2: ANY1 test VALUE2 ge VALUE1 close ANY2. ANY1 test VALUE1 lt VALUE2 close ANY2: ANY1 test VALUE1i le VALUE2 close ANY2. ANY1 test VALUE1 gt VALUE2 close ANY2: ANY1 test VALUE2 lt VALUE1 close ANY2.
Adding an ELSE part to the IF command is trivial and left to the reader.
Finally, we define the while command:
execute while TEST indent COMMANDS1 outdent COMMANDS2 in memory VARS:
execute if TEST indent COMMANDS1
while TEST indent COMMANDS1 outdent
outdent COMMANDS2 in memory VARS.
Easy.
One other thing remains to be defined, and that is what happens when the end of the program is reached:
execute EMPTY in memory VARS: EMPTY.
To give a short example of the progress of a notion through these rules, let us take the original example given. Each line shows one transformation:
put digit i number in letter a tag write letter a tag execute put digit i number in letter a tag write letter a tag in memory execute put evaluate digit i number close in letter a tag write letter a tag in memory execute put i in letter a tag write letter a tag in memory where letter a tag not in , execute write letter a tag in memory var letter a tag has i where true, execute write letter a tag in memory var letter a tag has i execute write letter a tag in memory var letter a tag has i execute write evaluate letter a tag close in memory var letter a tag has i execute write i in memory var letter a tag has i repr i, execute in memory var letter a tag has i digit i symbol, execute in memory var letter a tag has i digit i symbol
Many of the parts of a language not defined in the simple language above are just more of the same. Negative numbers, subtraction, division and so on are just quantitative differences, as are other types of values like strings, arrays etc. Substantial complications are caused by functions, and more complicated variables. Some solutions are sketched here.
All variables more complicated than a tag, have a tag at their root. Thus an array selection can be represented as a pair (TARGET, VALUE).
Calling functions can be done by assigning to the formal parameters and then executing the function's commands. A return is a case of substituting a value for the remaining body of the function.
Dick Grune [Grune] sometime ago wrote a program of just over 1000 lines of C, that takes a (restricted) two level grammar and a start notion, and prints all the strings generated from that start notion. The restrictions are that metanotions may only be a single letter, there may be no left recursion in metarules, and (essentially) predicates cannot be used.
I have translated that program into about 200 lines of ABC [ABC], but with only the left-recursion restriction remaining.
The traditional method of defining programming-language semantics with Van Wijngaarden Grammars has depended on the use of free metanotions, which is an essential barrier to creating executable definitions of languages.
Presented here has been a method for defining a programming language using a two-level grammar in such a way that the definition may be interpreted mechanically for any particular start notion. This has the advantage of allowing the reader to check a particular derivation automatically, but also appears to make the process of understanding the definition easier for the reader, through the absence of free metanotions.
[First published 1982; revised July 2014; error corrected Feb 2016]
[ABC] http://www.cwi.nl/~steven/abc/
[Grune] D. Grune. How to produce all sentences from a two-level grammar. Information Processing Letters, 19, pp. 181-185, 1984.
[van Wijngaarden] Adriaan van Wijngaarden, The Generative Power of Two-Level Grammars. In Proceedings of the 2nd Colloquium on Automata, Languages and Programming, Jacques Loeckx (Ed.). Springer-Verlag, London, UK, 9-16, 1974. http://link.springer.com/chapter/10.1007%2F3-540-06841-4_48