Skip to content
TopicTracker
From HackerNewsView original
TranslationTranslation

Van Wijngaarden Grammar

Van Wijngaarden grammar is a two-level grammar formalism for defining programming language syntax. It uses metarules to generate production rules, enabling context-sensitive constraints like type checking. It was notably used to define ALGOL 68.

Background

Van Wijngaarden grammars (also called two-level grammars or W-grammars) are a formal system for defining the syntax of programming languages, invented by Dutch computer scientist Adriaan van Wijngaarden in the 1960s. They are most famous for their use in defining ALGOL 68, a landmark but complex programming language. Unlike a typical "context-free" grammar (like Backus-Naur Form, used for most languages), a W-grammar is "context-sensitive" — it can express rules about types and contexts that simpler grammars cannot. This made ALGOL 68's definition extremely precise but also notoriously difficult to read. Van Wijngaarden was a key figure in early European computing and led the influential IFIP Working Group 2.1 on算法 Languages (Algol). The grammar's main legacy is showing how to formally define complex language semantics, influencing later work in attribute grammars and language specification.

Related stories