Van Wijngaarden grammar

In computer science, a Van Wijngaarden grammar (also vW-grammar or W-grammar^[1]) is a formalism for defining formal languages. The name derives from the formalism invented by Adriaan van Wijngaarden^[2] for the purpose of defining the ALGOL 68 programming language. The resulting specification^[3] remains its most notable application.

Van Wijngaarden grammars address the problem that context-free grammars cannot express agreement or reference, where two different parts of the sentence must agree with each other in some way. For example, the sentence "The birds was eating" is not Standard English because it fails to agree on number. A context-free grammar would parse "The birds was eating" and "The birds were eating" and "The bird was eating" in the same way. However, context-free grammars have the benefit of simplicity whereas van Wijngaarden grammars are considered highly complex.^[4]

Two levels

W-grammars are two-level grammars: they are defined by a pair of grammars, that operate on different levels:

the hypergrammar is an attribute grammar, i.e. a set of context-free grammar rules in which the nonterminals may have attributes; and
the metagrammar is a context-free grammar defining possible values for these attributes.

The set of strings generated by a W-grammar is defined by a two-stage process:

within each hyperrule, for each attribute that occurs in it, pick a value for it generated by the metagrammar; the result is a normal context-free grammar rule; do this in every possible way;
use the resulting (possibly infinite) context-free grammar to generate strings in the normal way.

The consistent substitution used in the first step is the same as substitution in predicate logic, and actually supports logic programming; it corresponds to unification in Prolog, as noted by Alain Colmerauer^[where?].

W-grammars are Turing complete;^[5] hence, all decision problems regarding the languages they generate, such as

whether a W-grammar generates a given string
whether a W-grammar generates no strings at all

are undecidable.

Curtailed variants, known as affix grammars, were developed, and applied in compiler construction and to the description of natural languages.

Definite logic programs, that is, logic programs that make no use of negation, can be viewed as a subclass of W-grammars.^[6]

Motivation and history

In the 1950s, attempts started to apply computers to the recognition, interpretation and translation of natural languages, such as English and Russian. This requires a machine-readable description of the phrase structure of sentences, that can be used to parse and interpret them, and to generate them. Context-free grammars, a concept from structural linguistics, were adopted for this purpose; their rules can express how sentences are recursively built out of parts of speech, such as noun phrases and verb phrases, and ultimately, words, such as nouns, verbs, and pronouns.

This work influenced the design and implementation of programming languages, most notably, of ALGOL 60, which introduced a syntax description in Backus–Naur form.

However, context-free rules cannot express agreement or reference (anaphora), where two different parts of the sentence must agree with each other in some way.

These can be readily expressed in W-grammars. (See example below.)

Programming languages have the analogous notions of typing and scoping. A compiler or interpreter for the language must recognize which uses of a variable belong together (refer to the same variable). This is typically subject to constraints such as:

A variable must be initialized before its value is used.
In strongly typed languages, each variable is assigned a type, and all uses of the variable must respect its type.
Often, its type must be declared explicitly, before use.

W-grammars are based on the idea of providing the nonterminal symbols of context-free grammars with attributes (or affixes) that pass information between the nodes of the parse tree, used to constrain the syntax and to specify the semantics.

This idea was well known at the time; e.g. Donald Knuth visited the ALGOL 68 design committee while developing his own version of it, attribute grammars.^[7]

By augmenting the syntax description with attributes, constraints like the above can be checked, ruling many invalid programs out at compile time. As Van Wijngaarden wrote in his preface:^[2]

My main objections were certain to me unnecessary restrictions and the definition of the syntax and semantics. Actually the syntax viewed in MR 75 produces a large number of programs, whereas I should prefer to have the subset of meaningful programs as large as possible, which requires a stricter syntax. [...] it soon became clear that some better tools than the Backus notation might be advantageous [...]. I developed a scheme [...] which enables the design of a language to carry much more information in the syntax than is normally carried.

Quite peculiar to W-grammars was their strict treatment of attributes as strings, defined by a context-free grammar, on which concatenation is the only possible operation; complex data structures and operations can be defined by pattern matching. (See example below.)

After their introduction in the 1968 ALGOL 68 "Final Report", W-grammars were widely considered as too powerful and unconstrained to be practical.^{[citation needed]}

This was partly a consequence of the way in which they had been applied; the 1973 ALGOL 68 "Revised Report" contains a much more readable grammar, without modifying the W-grammar formalism itself.

Meanwhile, it became clear that W-grammars, when used in their full generality, are indeed too powerful for such practical purposes as serving as the input for a parser generator. They describe precisely all recursively enumerable languages,^[8] which makes parsing impossible in general: it is an undecidable problem to decide whether a given string can be generated by a given W-grammar.

Hence, their use must be seriously constrained when used for automatic parsing or translation. Restricted and modified variants of W-grammars were developed to address this, e.g.

Extended Affix Grammars (EAGs), applied to describe the grammars of natural language such as English and Spanish);
Q-systems, also applied to natural language processing;
the CDL series of languages, applied as compiler construction languages for programming languages.

After the 1970s, interest in the approach waned; occasionally, new studies are published.^[9]

Examples

Agreement in English grammar

In English, nouns, pronouns and verbs have attributes such as grammatical number, gender, and person, which must agree between subject, main verb, and pronouns referring to the subject:

I wash myself.
She washes herself.
We wash ourselves.

are valid sentences; invalid are, for instance:

*I washes ourselves.
*She wash himself.
*We wash herself.

Here, agreement serves to stress that both pronouns (e.g. I and myself) refer to the same person.

A context-free grammar to generate all such sentences:

 <sentence> ::= <subject> <verb> <object>
 <subject>  ::= I | You | He | She | We | They
 <verb>     ::= wash | washes
 <object>   ::= myself | yourself | himself | herself | ourselves | yourselves | themselves

From <sentence>, we can generate all combinations:

I wash myself
I wash yourself
I wash himself
[...]
They wash yourselves
They wash themselves

A W-grammar to generate only the valid sentences:

 <sentence <NUMBER> <GENDER> <PERSON>>
   ::= <subject <NUMBER> <GENDER> <PERSON>>
       <verb <NUMBER> <PERSON>>
       <object <NUMBER> <GENDER> <PERSON>>

 <subject singular <GENDER> 1st> ::= I
 <subject <NUMBER> <GENDER> 2nd> ::= You
 <subject singular male 3rd>     ::= He
 <subject singular female 3rd>   ::= She
 <subject plural <GENDER> 1st>   ::= We
 <subject singular <GENDER> 3rd> ::= They

 <verb singular 1st>    ::= wash
 <verb singular 2nd>    ::= wash
 <verb singular 3rd>    ::= washes
 <verb plural <PERSON>> ::= wash

 <object singular <GENDER> 1st> ::= myself
 <object singular <GENDER> 2nd> ::= yourself
 <object singular male 3rd>     ::= himself
 <object singular female 3rd>   ::= herself
 <object plural <GENDER> 1st>   ::= ourselves
 <object plural <GENDER> 2nd>   ::= yourselves
 <object plural <GENDER> 3rd>   ::= themselves

 <NUMBER> ::== singular | plural
 <GENDER> ::== male | female
 <PERSON> ::== 1st | 2nd | 3rd

A standard non-context-free language

A well-known non-context-free language is

\{a^{n}b^{n}a^{n}|n\geq 1\}.

A two-level grammar for this language is the metagrammar

N ::= 1 | N1

X ::= a | b

together with grammar schema

Start ::= ⟨a^N⟩⟨b^N⟩⟨a^N⟩

⟨X^N1⟩ ::= ⟨X^N⟩ X

⟨X¹⟩ ::= X

Questions. If one substitutes a new letter, say C, for N1, is the language generated by the grammar preserved? Or N1 should be read as a string of two symbols, that is, N followed by 1? End of questions.

Requiring valid use of variables in ALGOL

The Revised Report on the Algorithmic Language Algol 60^[10] defines a full context-free syntax for the language.

Assignments are defined as follows (section 4.2.1):

 <left part>
   ::= <variable> :=
     | <procedure identifier> :=
 
 <left part list>
   ::= <left part>
     | <left part list> <left part>
 
 <assignment statement>
   ::= <left part list> <arithmetic expression>
     | <left part list> <Boolean expression>

A <variable> can be (amongst other things) an <identifier>, which in turn is defined as:

<identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>

Examples (section 4.2.2):

s:=p[0]:=n:=n+1+s
n:=n+1
A:=B/C-v-q×S
S[v,k+2]:=3-arctan(sTIMESzeta)
V:=Q>Y^Z

Expressions and assignments must be type checked: for instance,

in n:=n+1, n must be a number (integer or real);
in A:=B/C-v-q×S, all variables must be numbers;
in V:=Q>Y^Z, all variables must be of type Boolean.

The rules above distinguish between <arithmetic expression> and <Boolean expression>, but they cannot verify that the same variable always has the same type.

This (non-context-free) requirement can be expressed in a W-grammar by annotating the rules with attributes that record, for each variable used or assigned to, its name and type.

This record can then be carried along to all places in the grammar where types need to be matched, and implement type checking.

Similarly, it can be used to checking initialization of variables before use, etcetera.

One may wonder how to create and manipulate such a data structure without explicit support in the formalism for data structures and operations on them. It can be done by using the metagrammar to define a string representation for the data structure and using pattern matching to define operations:

 <left part with <TYPED> <NAME>>
   ::= <variable with <TYPED> <NAME>> :=
     | <procedure identifier with <TYPED> <NAME>> :=
 
 <left part list <TYPEMAP1>>
   ::= <left part with <TYPED> <NAME>>
       <where <TYPEMAP1> is <TYPED> <NAME> added to sorted <EMPTY>>
     | <left part list <TYPEMAP2>>
       <left part with <TYPED> <NAME>>
       <where <TYPEMAP1> is <TYPED> <NAME> added to sorted <TYPEMAP2>>
 
 <assignment statement <ASSIGNED TO> <USED>>
   ::= <left part list <ASSIGNED TO>> <arithmetic expression <USED>>
     | <left part list <ASSIGNED TO>> <Boolean expression <USED>>
 
 <where <TYPED> <NAME> is <TYPED> <NAME> added to sorted <EMPTY>>
   ::=
 
 <where <TYPEMAP1> is <TYPED1> <NAME1> added to sorted <TYPEMAP2>>
   ::= <where <TYPEMAP2> is <TYPED2> <NAME2> added to sorted <TYPEMAP3>>
       <where <NAME1> is lexicographically before <NAME2>>
 
 <where <TYPEMAP1> is <TYPED1> <NAME1> added to sorted <TYPEMAP2>>
   ::= <where <TYPEMAP2> is <TYPED2> <NAME2> added to sorted <TYPEMAP3>>
       <where <NAME2> is lexicographically before <NAME1>>
       <where <TYPEMAP3> is <TYPED1> <NAME1> added to sorted <TYPEMAP4>>
 
 <where <EMPTY> is lexicographically before <NAME1>>
   ::= <where <NAME1> is <LETTER OR DIGIT> followed by <NAME2>>
  
 <where <NAME1> is lexicographically before <NAME2>>
   ::= <where <NAME1> is <LETTER OR DIGIT> followed by <NAME3>>
       <where <NAME2> is <LETTER OR DIGIT> followed by <NAME4>>
       <where <NAME3> is lexicographically before <NAME4>>
 
 <where <NAME1> is lexicographically before <NAME2>>
   ::= <where <NAME1> is <LETTER OR DIGIT 1> followed by <NAME3>>
       <where <NAME2> is <LETTER OR DIGIT 2> followed by <NAME4>>
       <where <LETTER OR DIGIT 1> precedes+ <LETTER OR DIGIT 2>
 
 <where <LETTER OR DIGIT 1> precedes+ <LETTER OR DIGIT 2>
   ::= <where <LETTER OR DIGIT 1> precedes <LETTER OR DIGIT 2>
 
 <where <LETTER OR DIGIT 1> precedes+ <LETTER OR DIGIT 2>
   ::= <where <LETTER OR DIGIT 1> precedes+ <LETTER OR DIGIT 3>
       <where <LETTER OR DIGIT 3> precedes+ <LETTER OR DIGIT 2>
 
 <where a precedes b> :==
 <where b precedes c> :==
 [...]
 
 <TYPED>       ::== real | integer | Boolean
 
 <NAME>        ::== <LETTER> | <NAME> <LETTER> | <NAME> <DIGIT>
 <LETTER OR DIGIT> ::== <LETTER> | <DIGIT>
 <LETTER OR DIGIT 1> ::= <LETTER OR DIGIT>
 <LETTER OR DIGIT 2> ::= <LETTER OR DIGIT>
 <LETTER OR DIGIT 3> ::= <LETTER OR DIGIT>
 <LETTER>      ::== a | b | c | [...]
 <DIGIT>       ::== 0 | 1 | 2 | [...]
 
 <NAMES1>      ::== <NAMES>
 <NAMES2>      ::== <NAMES>
 <ASSIGNED TO> ::== <NAMES>
 <USED>        ::== <NAMES>
 <NAMES>       ::== <NAME> | <NAME> <NAMES>
 
 <EMPTY>       ::==
 <TYPEMAP>     ::== (<TYPED> <NAME>) <TYPEMAP>
 <TYPEMAP1>    ::== <TYPEMAP>
 <TYPEMAP2>    ::== <TYPEMAP>
 <TYPEMAP3>    ::== <TYPEMAP>

When compared to the original grammar, three new elements have been added:

attributes to the nonterminals in what are now the hyperrules;
metarules to specify the allowable values for the attributes;
new hyperrules to specify operations on the attribute values.

The new hyperrules are $ε$ -rules: they only generate the empty string.

ALGOL 68 examples

The ALGOL 68 reports use a slightly different notation without <angled brackets>.

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.

A simple example of the power of W-grammars is clause

a) program text : STYLE begin token, new LAYER1 preludes, 
       parallel token, new LAYER1 tasks PACK, 
       STYLE end token.

This allows BEGIN ... END and { } as block delimiters, while ruling out BEGIN ... } and { ... END.

One may wish to compare the grammar in the report with the Yacc parser for a subset of ALGOL 68 by Marc van Leeuwen.^[11]

Implementations

Anthony Fisher wrote yo-yo,^[12] a parser for a large class of W-grammars, with example grammars for expressions, eva, sal and Pascal (the actual ISO 7185 standard for Pascal uses extended Backus–Naur form).

Dick Grune created a C program that would generate all possible productions of a W-grammar.^[13]

Applications outside of ALGOL 68

The applications of Extended Affix Grammars (EAG)s mentioned above can effectively be regarded as applications of W-grammars, since EAGs are so close to W-grammars.^[14]

W-grammars have also been proposed for the description of complex human actions in ergonomics.^{[citation needed]}

A W-Grammar Description has also been supplied for Ada.^[15]

References

^ Cleaveland, J. Craig; Uzgalis, Robert C. (1977). Grammars for Programming Languages. Elsevier. ISBN 978-0-444-00199-3.
^ ^a ^b van Wijngaarden, Adriaan (1972-04-04) [Premature and preliminary edition 1965-10-22]. MR 76: Orthogonal design and description of a formal language (PDF) (Technical report). Amsterdam: CWI. Archived from the original (PDF) on 2017-10-02.
^ van Wijngaarden, A.; et al. (eds.). "Revised Report on the Algorithmic Language ALGOL 68". Archived from the original on 24 January 2002.
^ Koster, C.H.A (1996). "The making of Algol 68". In Bjørner, D; Broy, M.; Pottosin, I.V. (eds.). Perspectives of System Informatics. Lecture Notes in Computer Science. Vol. 1181. Berlin: Springer. pp. 55–67. doi:10.1007/3-540-62064-8_6. ISBN 978-3-540-62064-8.
^ Sintzoff, M. (1967). "Existence of van Wijngaarden syntax for every recursively enumerable set". Annales de la Société Scientifique de Bruxelles. 2: 115–118.
^ Deransart, Pierre; Maluszynski, Jan (1993), "Grammatical Extensions of Logic Programs", A Grammatical View of Logic Programming, The MIT Press, pp. 109–140, doi:10.7551/mitpress/3345.003.0008, ISBN 9780262290845, retrieved 2023-06-14
^ Knuth, Donald E (1990), "The genesis of attribute grammars" (Plain TeX, gZiped), Proceedings of the International Conference on Attribute Grammars and Their Applications, Springer Verlag: 1–12.
^ Sintzoff, M. (1967). "Existence of a van Wijngaarden syntax for every recursively enumerable set". Annales de la Société scientifique de Bruxelles. 81: 115–118.
^ Augusto, L. M. (2023). "Two-level grammars: Some interesting properties of van Wijngaarden grammars" (PDF). Omega - Journal of Formal Languages. 1: 3–34.
^ Backus, J.W.; et al. (1963). "Revised report on the algorithmic language ALGOL 60". The Computer Journal. 5 (4): 349–367. doi:10.1093/comjnl/5.4.349.
^ "Syntax", Algol 68, FR: Univ Poitiers
^ Fisher, Anthony (30 July 2024), "yo-yo", Software, UK: York.
^ Grune, Dick, A Two-Level Sentence Generator, NL: VU.
^ Alblas, Henk; Melichar, Borivoj (1991). Attribute Grammars, Applications and Systems. Lecture Notes in Computer Science. Vol. 545. Springer. p. 371. ISBN 978-3540545729.
^ Flowers, Roy, A W-grammar description for Ada (PDF) (Master thesis), Air Force Institute of Technology, Air University