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

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

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

Этот метод был использован и развит при определении язык программирования АЛГОЛ 68. Это пример более широкого класса аффиксные грамматики.

Обзор

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

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

Начальный токен STYLE, новые прелюдии LAYER1, параллельный токен, новые задачи LAYER1 PACK, STYLE end token

позволяет начало ... конец и { ... } но нет начинать ... }.

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

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

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

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

АЛГОЛ 68, как в Заключительном отчете 1968 года §2.1

a) программа: символ открытия, стандартная прелюдия, опция прелюдии к библиотеке, конкретная программа, выход, опция постлуда библиотеки, стандартная постлюдия, символ закрытия. b) стандартная прелюдия: последовательность прелюдии объявления. c) прелюдия библиотеки: последовательность прелюдии объявления. d) конкретная программа: опция последовательности меток, строгое предложение CLOSED void. e) выход: символ продолжения, буква e, буква x, буква i, буква t, символ метки. f) пост-вставка библиотеки: промежуточный оператор. g) стандартный постлук: поезд строгого предложения void

АЛГОЛ 68, как в Пересмотренном отчете 1973 г., §2.2.1, §10.1.1

программа: сильное недействительное новое закрытое предложение
А) ВНЕШНИЙ :: стандартный; библиотека; система ; В) СТОП: обозначьте букву s букву t букву o букву p.
a) текст программы: начальный токен STYLE, новые прелюдии LAYER1, параллельный токен, новые задачи LAYER1 PACK, конечный токен STYLE. b) прелюдия NEST1: стандартная прелюдия NEST1 с DECS1, прелюдия библиотеки NEST1 с DECSETY2, системная прелюдия NEST1 с DECSETY3, где ( NEST1) это (новый EMPTY новый DECS1 DECSETY2 DECSETY3) .c) NEST1 EXTERNAL прелюдия с DECSETY1: сильная недействительность NEST1 серия с DECSETY1, перейти на токен; где (DECSETY1) равно (EMPTY), EMPTY. d) Задачи NEST1: список системных задач NEST1, а также токен, список PACK пользовательских задач NEST1. e) Системная задача NEST1: строгая недействительность NEST1 unit. f) Пользовательская задача NEST1: конкретная NEST2. прелюдия с DECS, конкретная программа NEST2 PACK, переход по токену, конкретная постлюдия NEST2, где (NEST2) - (NEST1 new DECS STOP) .g) конкретная программа NEST2: NEST2 новая LABSETY3 присоединилась к определению метки LABSETY3, сильная пустота NEST2 новая LABSETY3 ENCLOSED clause.h) определение присоединенной метки NEST для LABSETY: где (LABSETY) равно (EMPTY), EMPTY; где (LABSETY) равно (LAB1 LABSETY1), определение метки NEST для LAB1, определение присоединенной метки NEST для $ LABSETY1. i) Особый постлюд NEST2: серия NEST2 с сильной недействительностью с STOP.

Реализации

йо Йо[5] парсер грамматик van Wijngaarden с примерами грамматик для выражения, ева, Сал и Паскаль (Настоящий ISO 7185 стандарт для использования Паскаля расширенная форма Бэкуса – Наура ).

История

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

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

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

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

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

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

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

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

  • Описание W-грамматики для Ады [9] - "W-грамматическое описание Ада по-прежнему полезен компьютерным специалистам, которым нужно нечто большее, чем простое понимание синтаксиса и элементарное описание семантики "

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

Рекомендации

  1. ^ Кливленд, Дж. Крейг; Узгалис, Роберт К. (1977). Грамматики языков программирования. Эльзевир. ISBN  978-0-444-00199-3.
  2. ^ ван Вейнгаарден, Адриан (1965), MR 76: Ортогональный дизайн и описание формального языка (PDF), Амстердам, Нидерланды: CWI.
  3. ^ Клейне, «Алгол 68», История языков (PDF) (приложение к отчету), DE: FH Jena.
  4. ^ "Синтаксис", Алгол 68, FR: Университет Пуатье.
  5. ^ а б Фишер, Энтони, "йо-йо", Программного обеспечения, Великобритания: Йорк.
  6. ^ Кнут, Дональд Э (1990), «Генезис атрибутных грамматик» (gZiped простой текст), Труды международной конференции по атрибутивным грамматикам и их приложениям., нас: Стэнфорд: 1–12.
  7. ^ Синцов, М. (1967). «Существование синтаксиса Ван Вейнгаардена для каждого рекурсивно перечислимого набора». Annales de la Société scientifique de Bruxelles. 81: 115–118.
  8. ^ Грун, Дик, Двухуровневый генератор предложений, NL: VU.
  9. ^ ADA177802: Описание W-грамматики для Ada, США: DTIC.

внешняя ссылка