Аффиксная грамматика

Аффиксальная грамматика — это двухуровневый грамматический формализм, используемый для описания синтаксиса языков, в основном компьютерных языков , с использованием подхода, основанного на том, как обычно описывается естественный язык.

Этот формализм был изобретен в 1962 году Ламбертом Мертенсом при разработке грамматики для построения английских предложений. Меертенс также применил аффиксную грамматику к описанию и составлению музыки и получил специальный приз от жюри на Конгрессе Международной федерации обработки информации (IFIP) 1968 года в Эдинбурге за созданный на компьютере струнный квартет «Квартет № 1 до мажор». для 2-х скрипок, альта и виолончели на основе первой неконтекстно -свободной грамматики аффиксов. Струнный квартет был опубликован в 1968 году как Отчет Математического центра MR 96 .

Грамматические правила аффиксной грамматики аналогичны правилам контекстно-свободной грамматики , за исключением того, что определенные части нетерминалов ( аффиксы ) используются в качестве аргументов. Если один и тот же аффикс встречается в правиле несколько раз, его значение должно совпадать , т. е. оно должно быть везде одинаковым. В некоторых типах грамматики аффиксов возможны более сложные отношения между значениями аффиксов.

Пример

Мы можем описать чрезвычайно простой фрагмент английского языка следующим образом:

Предложение → подлежащего Предикат

Тема → Существительное

Предикат → Глагольный объект

Объект → Существительное

Существительное → Джон

Существительное → Мэри

существительное → дети

Существительное → родители

Глагол → нравится

Глагол → нравится

Глагол → помочь

Глагол → помогает

Эта контекстно-свободная грамматика описывает простые предложения, такие как

Джон любит детей

Мэри помогает Джону

дети помогают родителям

такие родители, как Джон

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

Однако данная грамматика описывает и такие предложения, как

Джон любит детей

дети помогают родителям

Эти предложения неправильные: в английском языке подлежащее и глагол имеют грамматическое число , которое должно совпадать.

Грамматика аффиксов может выразить это напрямую:

Предложение → Подлежащее + число Сказуемое + число

Тема + номер → Имя существительное + номер

Сказуемое + число → Глагол + число Дополнение

Объект → Имя существительное + число

Существительное + единственное число → Джон

Существительное + единственное число → Мэри

Существительное + множественное число → дети

Существительное + множественное число → родители

Глагол + единственное число → нравится

Глагол + множественное число → нравится

Глагол + единственное число → помогает

Глагол + множественное число → помочь

Эта грамматика описывает только правильные английские предложения, хотя можно утверждать, что

Джону нравится Джон

все еще неверно и вместо этого следует читать

Джон любит себя

Это также можно реализовать с помощью аффиксов, если средства описания отношений между различными значениями аффиксов достаточно эффективны. Как отмечалось выше, эти средства зависят от типа выбранной аффиксной грамматики.

Типы

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

Другой подход — разрешить аффиксам принимать произвольные строки в качестве значений и разрешить использование конкатенаций аффиксов в правилах. Диапазоны допустимых значений аффиксов можно описать с помощью контекстно-свободных грамматических правил. Это создает формализм двухуровневых грамматик , также известных как грамматики Ван Вейнгаардена или 2VW грамматики . Они успешно использовались для описания сложных языков, в частности, синтаксиса Алгол 68 языка программирования . Однако оказывается, что, хотя значениями аффиксов можно манипулировать только с помощью конкатенации строк, этот формализм является полным по Тьюрингу ; следовательно, даже самые основные вопросы о языке, описываемом произвольной 2VW-грамматикой, вообще говоря, неразрешимы .

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

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

• В грамматиках атрибутов аффиксы (называемые атрибутами) могут принимать значения из произвольных областей (например, целые или действительные числа, сложные структуры данных), а также могут быть указаны произвольные функции, написанные на выбранном языке, чтобы описать, как получаются значения аффиксов в правилах. друг от друга.
• В CDL ( языке описания компилятора ) и его преемнике CDL2 , разработанном в 1970-х годах, фрагменты исходного кода (обычно на языке ассемблера ) могут использоваться в правилах вместо обычных правых частей, что позволяет использовать примитивы для сканирования ввода и вычисления значений аффиксов. выражаться напрямую. Этот подход , задуманный как основа для практического построения компиляторов , использовался для написания компиляторов и другого программного обеспечения, например текстового редактора .