Введение

В информатике расширенные грамматики аффиксов (EAGs) — это формальный грамматический формализм для описания контекстно-свободного и контекстно-зависимого синтаксиса языка, как естественного, так и языков программирования. EAGs относятся к семейству двухуровневых грамматик; точнее, это ограничение грамматик Ван Вийнгардена, разработанное с конкретной целью обеспечения возможности синтаксического анализа. Как и грамматики Ван Вийнгардена, EAGs используют гиперправила, формирующие контекстно-свободную грамматику, за исключением того, что их нетерминалы могут иметь аргументы, известные как аффиксы, возможные значения которых задаются другой контекстно-свободной грамматикой – метаправилами. EAGs были введены и исследованы Д. А. Ваттом в 1974 году, а распознаватели были разработаны в Университете Неймегена в период с 1985 по 1995 год. Компилятор EAG, разработанный там, генерирует либо распознаватель, преобразователь, переводчик, либо синтаксически ориентированный редактор для языка, описанного в формализме EAG. Формализм весьма похож на Prolog, настолько, что позаимствовал у него оператор отсечения. EAGs использовались для создания грамматик естественных языков, таких как английский, испанский и венгерский. Целью было верифицировать грамматики путем их применения к корпусам текстов (корпусной лингвистике); следовательно, синтаксический анализ должен был быть достаточно эффективным. Однако проблема взрыва дерева разбора, возникающая из-за неоднозначности в естественном языке при использовании этого подхода, усугубляется в EAGs, поскольку каждый выбор значения аффикса может приводить к отдельному разбору, даже если несколько различных значений эквивалентны. Предлагаемым решением было перейти к гораздо более простой грамматике аффиксов над конечной решеткой (AGFL), в которой метаграмматики могут генерировать только простые конечные языки.