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]

  1. ^ Cleaveland, J. Craig; Uzgalis, Robert C. (1977). Grammars for Programming Languages. Elsevier. ISBN 978-0-444-00199-3.
  2. ^ 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.
  3. ^ van Wijngaarden, A.; et al. (eds.). "Revised Report on the Algorithmic Language ALGOL 68". Archived from the original on 24 January 2002.
  4. ^ 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.