Войти
В информатике, грамматика Ван Вейнгаардена (также vW -grammar или W-грамматика ) - это двухуровневая грамматика, которая предоставляет метод определения потенциально бесконечных контекстно-свободных грамматик в конечном числе правил. Формализм был изобретен Адрианом ван Вейнгарденом, чтобы строго определить некоторые синтаксические ограничения, которые ранее приходилось формулировать на естественном языке, несмотря на их синтаксическое содержание.
Типичными приложениями являются обработка пола и числа в синтаксисе естественного языка и четко определенных идентификаторов в языках программирования.. Например, «есть один человек» и «есть два человека» оба грамматически правильны, но «есть один человек» неверно по причинам, зависящим от контекста, которые может представлять W-грамматика.
Этот метод использовался и развивался при определении языка программирования АЛГОЛ 68. Это пример более крупного класса аффиксных грамматик.
W-грамматика состоит из конечного набора мета -правил, которые используются для получения (возможно, бесконечного множества) производственных правил из конечного набора гипер -правила. Мета-правила ограничены правилами, определенными контекстно-свободной грамматикой. Гиперправила ограничивают допустимые контексты на верхнем уровне. По сути, последовательная замена, используемая в процессе деривации, эквивалентна унификации, как в Prolog, как было отмечено Аленом Колмерауэром.
. Например, присвоение x: = 1допустимо, только если переменная x может содержать целое число. Следовательно, контекстно-свободный синтаксис переменная: = значениеявляется неполным. В двухуровневой грамматике это может быть указано контекстно-зависимым образом как переменная REF TYPE: = значение TYPE. Тогда целочисленная переменная ref: = целочисленное значениеможет быть производственным правилом, но ref Boolean variable: = integer valueне является возможным производственным правилом. Это также означает, что присвоение несовместимых типов становится синтаксической ошибкой, которая может быть обнаружена во время компиляции. Аналогично,
начальный токен STYLE, новые прелюдии LAYER1, параллельный токен, новые задачи LAYER1 PACK, конечный токен STYLE
позволяет begin... endи {...}но не begin...}.
До ALGOL 68 язык ALGOL 60 был формализована с помощью контекстно-свободной формы Бэкуса – Наура. Появление новой контекстно-зависимой двухуровневой грамматики стало проблемой для некоторых читателей «Итогового отчета» АЛГОЛА 68 1968 года. Впоследствии окончательный отчет был отредактирован Вейнгаарденом и его коллегами и опубликован как «Пересмотренный отчет» АЛГОЛ 68 1973 года.
Грамматика для АЛГОЛА 68 официально определена в двухуровневой грамматике Ван Вейнгардена, но подмножество было выполнено в одноуровневой форме Бэкуса – Наура, сравните:
а) программа: открытый символ, стандартная прелюдия, библиотечная прелюдия опция, конкретная программа, выход, опция постлуда библиотеки, стандартная постлюдия, символ закрытия. б) стандартная прелюдия: последовательность вступления к декларации. c) прелюдия к библиотеке: последовательность вступления к объявлению. d) конкретная программа: опция последовательности меток, строгое условие недействительности CLOSED. д) выход: перейти на символ, буква е, буква х, буква, буква т, метка, символ f) библиотечная постлюдия: интерлюдия утверждения g) стандартная постлюдия: сильная недействительная статья
программа: сильная недействительная новая закрытая статья
А) ВНЕШНИЙ :: стандартный; библиотека; система; специфический. Б) СТОП: обозначьте букву s букву t букву o букву p.
a) текст программы: начальный токен STYLE, новые прелюдии LAYER1, параллельный токен, новый PACK задач LAYER1, конечный токен STYLE. б) прелюдия NEST1: стандартная прелюдия NEST1 с DECS1, прелюдия библиотеки NEST1 с DECSETY2, системная прелюдия NEST1 с DECSETY3, где (NEST1) - (новый EMPTY new DECS1 DECSETY2 DECSETY3). c) ВНЕШНЯЯ прелюдия NEST1 с DECSETY1: сильная недействительность серии NEST1 с DECSETY1, перейти на маркер; где (DECSETY1) равно (EMPTY), EMPTY. г) Задачи NEST1: список системных задач NEST1, а также токен, список PACK пользовательских задач NEST1. д) Системная задача NEST1: блок NEST1 с сильной недействительностью. f) Пользовательская задача NEST1: конкретная прелюдия NEST2 с DECS, конкретная программа PACK NEST2, переход по токену, конкретная постлюдия NEST2, где (NEST2) - (NEST1 новая остановка DECS). g) Специальная программа NEST2: NEST2 new LABSETY3 объединила определение метки LABSETY3, сильное недействительное предложение NEST2 new LABSETY3 ENCLOSED. h) определение присоединенной метки NEST для LABSETY: где (LABSETY) равно (EMPTY), EMPTY; где (LABSETY) равно (LAB1 LABSETY1), определение метки NEST для LAB1, определение присоединенной метки NEST для $ LABSETY1. i) Особый постлюд NEST2: серия NEST2 с сильной недействительностью с STOP.
yo-yo parser для грамматик van Wijngaarden с примерами грамматик для выражений, eva, sal и Pascal (действующий стандарт ISO 7185 для Паскаля используется расширенная форма Бэкуса – Наура ).
W-грамматики основаны на идее обеспечения нетерминальных символов контекстно-свободных грамматик с атрибутами (или аффиксами), передающими информацию между узлами дерева синтаксического анализа , используется для ограничения синтаксиса и определения семантики. В то время эта идея была хорошо известна; например Дональд Кнут посетил комитет по проектированию Алгола 68 при разработке своей собственной версии, грамматик атрибутов. Совершенно особенным для W-грамматик было их строгое обращение с атрибутами как со строками, определенными контекстно-независимой грамматикой, в которой объединение является единственной возможной операцией; в грамматиках атрибутов атрибуты могут иметь любой тип данных, и к ним можно применять любые операции.
После того, как W-грамматики были представлены в отчете Algol 68, многие считали их слишком мощными и неограниченными, чтобы их можно было использовать на практике. Отчасти это было следствием того, как они применялись; исправленный отчет Algol 68 содержал гораздо более читаемую грамматику без изменения самого формализма W-грамматики.
Между тем стало ясно, что W-грамматики, когда они используются в их полной общности, действительно слишком мощны для таких практических целей, как использование в качестве входных данных для генератора синтаксического анализатора. Они точно описывают все рекурсивно перечислимые языки, что делает синтаксический анализ в целом невозможным: неразрешимая проблема решить, может ли данная строка быть сгенерирована заданным W-грамматика. Их использование должно быть серьезно ограничено при использовании для автоматического синтаксического анализа или перевода. Для решения этой проблемы были разработаны ограниченные и модифицированные варианты W-грамматик, например
Энтони Фишер написал синтаксический анализатор для большого класса W-грамматик.
Дик Грюн создал программу C, которая будет генерировать все возможные продукты двухуровневой грамматики.
Приложения Упомянутые выше EAG могут эффективно рассматриваться как приложения W-грамматик, поскольку EAG очень близки к W-грамматикам.
W-грамматики также были предложены для описания сложных человеческих действий в эргономике.
