Грамматика ван Вейнгаардена

В-грамматика состоит из конечного числа метаправил, которые используются для выведения (потенциально бесконечного числа) правил вывода из конечного числа гиперправил. Задание метаправил ограничено контекстно-свободной грамматикой. Гиперправила ограничивают допустимые контексты на более высоком уровне. В сущности, консистентная подстановка, используемая в процессе вывода, эквивалентна процессу унификации, например из языка Пролог, что было отмечено Аланом Колмероэ.

До языка ALGOL 68 был формализован ALGOL 60 посредством контекстно-свободных форм Бекуса-Наура. Появление новых контекстно-зависимых двухуровневых грамматик представляло трудность для некоторых читателей «Финального отчёта» по ALGOL 68 в 1968 году. Впоследствии финальный отчёт был отредактирован Вейнгаарденом и коллегами и опубликован как «Отредактированный отчёт» по ALGOL 68 в 1973 году.

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

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.

В-грамматики основаны на идее дополнения нетерминальных символов КС-грамматик атрибутами (или аффиксами), которые передают информацию между узлами дерева разбора и используются для ограничения синтаксиса и указания семантики. Эта идея была хорошо известна в то время, в частности Дональд Кнут посетил комитет по разработке ALGOL 68 во время разработки собственной его версии.[1] Интересной особенностью В-грамматик является их строгое отношение к атрибутам к строкам, задаваемым КС-грамматикой, в которой конкатенация является единственной возможной операцией. В грамматиках атрибутов атрибуты могут быть любого типа и к ним можно применить любую операцию.

После введения в отчёт об Algol 68 В-грамматики были сочтены слишком мощными и неограниченными для практического использования. Частично на это повлияло то, как они были применены, отредактированный отчёт об Algol 68 содержал намного более читаемую грамматику при неизменном собственно формализме В-грамматики.

В это время стало понятно, что В-грамматики действительно слишком мощны. Они являются полными по Тьюрингу, что делает невозможным их синтаксический анализ вообще: задача проверки, может ли данная строка быть порождена данной В-грамматикой, алгоритмически неразрешима. Использование их должно быть серьёзно ограничено для применения в автоматическом анализе или трансляции. Были разработаны ограниченные и модифицированные варианты В-грамматик для решения этой проблемы, в частности

• расширенный аффиксные грамматики, применяемые для описания грамматик естественных языков,
• Q-системы, также используемые для обработки естественных языков,
• серия языков Compiler Description Language, применяемых в качестве языков конструирования компиляторов языков программирования.

Энтони Фишер написал синтаксический анализатор для большого класса В-грамматик Архивная копия от 14 декабря 2007 на Wayback Machine.

Дик Груне создал программу на C, которая генерирует всевозможные правила вывода для двухуровневой грамматики .

Применения расширенных аффиксных грамматик, упомянутые выше, могут быть сочтены применениями В-грамматик, поскольку РА-грамматики довольно к ним близки.

В-грамматики также было предложены к использованию для описания сложных человеческих действий в эргономике.