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

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

Метод был использован и разработан при определении языка программирования ALGOL 68. Это пример более широкого класса аффиксных грамматик.

ОбзорПравить

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

Примеры из ALGOL 68Править

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

ALGOL 68 в отчёте 1968 года § 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 в отредактированном отчёте 1973 года § 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.

ИсторияПравить

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

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

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

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

Применения кроме ALGOL 68Править

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

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

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

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