Грамматика Ван Вейнгаардена - Van Wijngaarden grammar

В информатике , грамматика Ван Вейнгаарден (также Vw-грамматика или W-грамматика ) является грамматикой два уровня , который обеспечивает метод для определения потенциально бесконечные контекстно-свободных грамматик в конечном числе правил. Формализм был изобретен Адрианом ван Вейнгаарденом, чтобы строго определить некоторые синтаксические ограничения, которые ранее приходилось формулировать на естественном языке , несмотря на их синтаксическое содержание.

Типичные приложения - это обработка пола и числа в синтаксисе естественного языка и четкое определение идентификаторов в языках программирования . Например, «есть один человек» и «есть два человека» оба грамматически правильны, но «есть один человек» неверно по причинам, зависящим от контекста, которые может представлять W-грамматика.

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

Обзор

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

Например, присвоение x:=1 допустимо только в том случае, если переменная x может содержать целое число. Следовательно, контекстно-свободный синтаксис variable := valueявляется неполным. В двухуровневой грамматике это может быть указано контекстно-зависимым образом как REF TYPE variable := TYPE value. Тогда это ref integer variable := integer valueмогло бы быть производственным правилом, но ref Boolean variable := integer valueне возможным производственным правилом. Это также означает, что присвоение несовместимых типов становится синтаксической ошибкой, которая может быть обнаружена во время компиляции. Сходным образом, 

STYLE begin token, new LAYER1 preludes, 
       parallel token, new LAYER1 tasks PACK, 
       STYLE end token

позволяет begin ... endи { ... }но нет begin ... }.

Примеры на Алголе 68

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

Грамматика для АЛГОЛА 68 официально определена в двухуровневой грамматике Ван Вейнгаардена, но подмножество было выполнено в одноуровневой форме Бэкуса – Наура , сравните:

  • Грамматика Ван Вейнгаардена;
  • Форма Бэкуса – Наура / Yacc

АЛГОЛ 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

АЛГОЛ 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.

Реализации

yo-yo синтаксический анализатор грамматик van Wijngaarden с примерами грамматик для выражений , eva , sal и Pascal (действующий стандарт ISO 7185 для Pascal использует расширенную форму Бэкуса – Наура ).

История

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

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

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

Приложения вне АЛГОЛА 68

Энтони Фишер написал синтаксический анализатор для большого класса W-грамматик.

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

Упомянутые выше приложения EAG можно эффективно рассматривать как приложения W-грамматик, поскольку EAG очень близки к W-грамматикам.

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

  • Описание W-грамматики для Ada - «Описание W-грамматики Ada по-прежнему полезно для компьютерных ученых, которым нужно нечто большее, чем простое понимание синтаксиса и элементарное описание семантики»

Смотрите также

использованная литература

внешние ссылки