Van Wijngaarden grammar

A Van Wijngaarden grammar (also vW-grammar or W-grammar) is a two-level grammar which provides a technique to define potentially infinite grammars in a finite number of rules. It was invented by Adriaan van Wijngaarden to define rigorously some syntactic restrictions which previously had to be formulated in natural language, despite their essentially syntactical content. One of these is the requirement of uniqueness of identifiers in program units and the unification of application and definition of these identifiers.

The technique was used and developed in the definition of the programming language ALGOL 68.

Overview

A W-grammar consists of a finite set of meta-rules, which are used to derive (possibly infinitely many) production rules from a finite set of hyper-rules. Meta-rules are restricted to those defined by a context-free grammar. Hyper-rules restrict the admissible contexts at the upper level. Essentially, the "consistent substitution" used in the derivation process is equivalent to unification, as in Prolog, as was noted by Alain Colmerauer.

ALGOL 68 examples

Prior to ALGOL 68 the language ALGOL 60 was formalised using the context-free Backus–Naur form. And so the appearance of new context-sensitive two-level grammar presented a challenge to some readers of the 1968 ALGOL 68 "Final Report". Subsequently the final report was revised by Wijngaarden and his colleagues and published as the 1973 ALGOL 68 "Revised Report".

ALGOL 68 as in the 1968 Final Report §2.1

a) program : open symbol, standard prelude, library prelude option, particular program, exit, library postlude option, standard postlude, close symbol. b) standard prelude : declaration prelude sequence. c) library prelude : declaration prelude sequence. d) particular program : label sequence option, strong CLOSED void clause. e) exit : go on symbol , letter e letter x letter i letter t, label symbol. f) library postlude : statement interlude. g) standard postlude : strong void clause train

ALGOL 68 as in the 1973 Revised Report §2.2.1, §10.1.1

program : strong void new closed clause

A) EXTERNAL :: standard ; library ; system ; particular. B) STOP :: label letter s letter t letter o letter p.

a) program text : STYLE begin token, new LAYER1 preludes, parallel token, new LAYER1 tasks PACK, STYLE end token. b) NEST1 preludes : NEST1 standard prelude with DECS1, NEST1 library prelude with DECSETY2, NEST1 system prelude with DECSETY3, where (NEST1) is (new EMPTY new DECS1 DECSETY2 DECSETY3). c) NEST1 EXTERNAL prelude with DECSETY1 : strong void NEST1 series with DECSETY1, go on token ; where (DECSETY1) is (EMPTY), EMPTY. d) NEST1 tasks : NEST1 system task list, and also token, NEST1 user task PACK list. e) NEST1 system task : strong void NEST1 unit. f) NEST1 user task : NEST2 particular prelude with DECS, NEST2 particular program PACK, go on token, NEST2 particular postlude, where (NEST2) is (NEST1 new DECS STOP). g) NEST2 particular program : NEST2 new LABSETY3 joined label definition of LABSETY3, strong void NEST2 new LABSETY3 ENCLOSED clause. h) NEST joined label definition of LABSETY : where (LABSETY) is (EMPTY), EMPTY ; where (LABSETY) is (LAB1 LABSETY1), NEST label definition of LAB1, NEST joined label definition of$ LABSETY1. i) NEST2 particular postlude : strong void NEST2 series with STOP.

Applications outside of ALGOL 68

It was noted that two-level grammars are Turing complete and therefore had the potential to be used beyond their original field of application.

Anthony Fisher tried to construct a parser for general W-grammars [http://www-users.cs.york.ac.uk/~fisher/software/yoyovwg/] .

Dick Grune created a C program that would generate all possible productions of a 2-level grammar [http://www.cs.vu.nl/~dick/utils.html] .

Use of the method has been proposed for the description of complex human actions in ergonomics.

External links

* [http://www.bookrags.com/sciences/computerscience/algol-68-wcs.html Use in Algol68]
* [http://www.cwi.nl/~steven/vw.html Tutorial introduction] by Steven Pemberton.