Аффиксальная грамматика — это двухуровневый грамматический формализм, используемый для описания синтаксиса языков, в основном компьютерных языков , с использованием подхода, основанного на том, как обычно описывается естественный язык. [1]
Формализм был изобретен в 1962 году Ламбертом Меертенсом при разработке грамматики для создания английских предложений. [2] Меертенс также применял аффиксные грамматики к описанию и сочинению музыки и получил специальный приз от жюри на Конгрессе Международной федерации по обработке информации (IFIP) 1968 года в Эдинбурге за свой сгенерированный компьютером струнный квартет , Квартет № 1 до мажор для 2 скрипок, альта и виолончели, основанный на первой неконтекстно -свободной аффиксной грамматике. [3] [4] Струнный квартет был опубликован в 1968 году как Отчет Математического центра MR 96. [ 5]
Грамматические правила аффиксной грамматики являются правилами контекстно-свободной грамматики , за исключением того, что определенные части в нетерминалах ( аффиксах ) используются в качестве аргументов. Если один и тот же аффикс встречается в правиле несколько раз, его значение должно совпадать , т. е. оно должно быть одинаковым везде. В некоторых типах аффиксной грамматики возможны более сложные отношения между значениями аффиксов.
Мы можем описать чрезвычайно простой фрагмент английского языка следующим образом:
Эта контекстно-свободная грамматика описывает простые предложения, такие как
Используя больше существительных и глаголов, а также больше правил для введения других частей речи, можно описать большой диапазон английских предложений; поэтому это многообещающий подход к описанию синтаксиса английского языка.
Однако данная грамматика также описывает такие предложения, как
Эти предложения неверны: в английском языке подлежащее и глагол имеют грамматическое число , которое должно согласовываться.
Аффиксальная грамматика может выразить это напрямую:
Эта грамматика описывает только правильные английские предложения, хотя можно утверждать, что
все еще неверно и вместо этого следует читать
Это также может быть включено с использованием аффиксов, если средства описания отношений между различными значениями аффиксов достаточно мощные. Как было отмечено выше, эти средства зависят от типа выбранной аффиксной грамматики.
В простейшем типе аффиксной грамматики аффиксы могут принимать значения только из конечной области, а значения аффиксов могут быть связаны только посредством соглашения, как в примере. Применяемые таким образом, аффиксы увеличивают компактность грамматик, но не добавляют выразительной силы.
Другой подход заключается в том, чтобы разрешить аффиксам принимать произвольные строки в качестве значений и разрешить использовать конкатенации аффиксов в правилах. Диапазоны допустимых значений для аффиксов можно описать с помощью контекстно-свободных правил грамматики. Это создает формализм двухуровневых грамматик , также известных как грамматики Ван Вейнгаардена или грамматики 2VW . Они успешно использовались для описания сложных языков, в частности, синтаксиса языка программирования Algol 68. Однако оказывается, что, хотя значения аффиксов можно изменять только с помощью конкатенации строк, этот формализм является полным по Тьюрингу ; следовательно, даже самые элементарные вопросы о языке, описываемом произвольной грамматикой 2VW, в общем случае неразрешимы .
Расширенные аффиксные грамматики , разработанные в 1980-х годах, являются более ограниченной версией той же идеи. Они в основном применялись для описания грамматики естественного языка, например, английского.
Другая возможность — позволить значениям аффиксов вычисляться с помощью кода, написанного на каком-либо языке программирования. Были использованы два основных подхода: