Адаптивная грамматика - Adaptive grammar

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

Обзор

Джон Н. Шатт определяет адаптивную грамматику как грамматический формализм, который позволяет явно манипулировать наборами правил (или наборами производственных правил) внутри грамматики. Типы манипуляций включают добавление, удаление и изменение правил.

Ранняя история

Первым описанием адаптивности грамматики (хотя и не под этим названием) в литературе обычно считается статья Альфонсо Караччоло ди Форино, опубликованная в 1963 году. Следующая общепринятая ссылка на адаптивный формализм ( расширяемые контекстно-свободные грамматики ) пришла. от Вегбрайта в 1970 году при изучении расширяемых языков программирования , за которым последовал динамический синтаксис Хэнфорда и Джонса в 1973 году.

Совместные усилия

До недавнего времени большая часть исследований формальных свойств адаптивных грамматик не координировалась между исследователями, и только впервые было обобщено Хеннингом Кристиансеном в 1990 году в ответ на статью Бориса Бурштейна в ACM SIGPLAN Notices . На инженерном факультете Университета Сан-Паулу есть лаборатория адаптивных языков и методов , специализирующаяся на исследованиях и практике в области адаптивных технологий и теории. LTA также поддерживает исследователей именования страниц в этой области.

Терминология и систематика

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

Классификация Шатта (и дополнения)

Шатт делит модели адаптивной грамматики на две основные категории:

Императивные адаптивные грамматики изменяют свои правила основанные на глобальном состоянии изменяющегося течение времени от поколения о наличии языка .
Декларативные адаптивные грамматики изменяют свои правила только в пространстве генерации языка (т. Е. Позиции в синтаксическом дереве сгенерированной строки).

Джексон уточняет таксономию Шатта, называя изменения во времени глобальными, а изменения в пространстве - локальными и добавляя гибридную пространственно-временную категорию:

Адаптивные пространственно-временные грамматики ( гибриды ) изменяют свои правила в зависимости от времени или пространства (или обоих) генерации языка (и локальные и глобальные операции явно различаются по обозначениям для таких изменений).

Адаптивные формализмы в литературе

Адаптивные формализмы можно разделить на две основные категории: полные грамматические формализмы (адаптивные грамматики) и адаптивные машины, на которых были основаны некоторые грамматические формализмы.

Формализмы адаптивной грамматики

Ниже приводится список (ни в коем случае не полный) грамматических формализмов, которые, согласно приведенному выше определению Шатта, считаются (или были классифицированы их собственными изобретателями как таковые) адаптивными грамматиками. Они перечислены в порядке их первого упоминания в литературе.

Расширяемые контекстно-свободные грамматики (Wegbreit)

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

Грамматики Кристиансена (Christiansen)

Впервые представленные в 1985 году как генеративные грамматики, а затем более развитые, грамматики Кристиансена (очевидно, названные так Шаттом, возможно, из-за конфликта с генеративными грамматиками Хомского) являются адаптивным расширением атрибутивных грамматик . Грамматики Кристиансена были классифицированы Shutt как декларативные .

Язык удвоения демонстрируется следующим образом: ${\ displaystyle L = \ {ww | w {\ mbox {это буква}} \}}$

<program↓G>       →   <dcl↓G↑w> <body↓{w-rule}>

where w-rule  =
<body↓G’>         →   w

<dcl↓G↑ch•w>     →   <char↓G↑ch> <dcl↓G↑w>
<dcl↓G↑<>>       →   <ε>
<char↓G↑a>       →   a

Грамматики, изменяемые снизу вверх, грамматики, изменяемые сверху вниз, и USSA (Бурштейн)

Изменяемые грамматики, впервые представленные в мае 1990 г. и позже расширенные в декабре 1990 г., явно предоставляют механизм для добавления и удаления правил во время синтаксического анализа. В ответ на ответы ACM SIGPLAN Notices Бурштейн позже изменил свой формализм и представил свой адаптивный универсальный анализатор синтаксиса и семантики (USSA) в 1992 году. Эти формализмы были классифицированы Шаттом как обязательные .

Рекурсивные адаптивные грамматики (Shutt)

Представленные в 1993 году рекурсивные адаптивные грамматики (RAG) были попыткой ввести мощный формализм Тьюринга, который сохранил большую часть элегантности контекстно-свободных грамматик. Шатт самостоятельно классифицирует RAG как декларативный формализм.

Динамические грамматики (Булье)

Динамические грамматики Булье , представленные в 1994 году, по-видимому, являются первым семейством грамматик с адаптивной грамматикой, строго вводящим понятие временного континуума синтаксического анализа как части записи самого грамматического формализма. Динамические грамматики - это последовательность грамматик, причем каждая грамматика G _i каким-то образом отличается от других грамматик в этой последовательности с течением времени. Основная статья Булье по динамическим грамматикам также определяет динамический синтаксический анализатор, машину, которая выполняет синтаксический анализ этих грамматик, и показывает примеры того, как его формализм может обрабатывать такие вещи, как проверка типов , расширяемые языки , полиморфизм и другие конструкции, обычно рассматриваемые в семантическая область перевода языков программирования.

Адаптивные грамматики (Иваи)

Работа Иваи в 2000 году развивает адаптивные автоматы Нето, применяя адаптивные автоматы к контекстно-зависимым грамматикам . Адаптивные грамматики Иваи (обратите внимание на квалификатор по имени) позволяют выполнять три операции во время синтаксического анализа:? запрос (в некоторых отношениях похож на синтаксический предикат , но привязанный к проверке правил, из которых выбираются модификации), + сложение и - удаление (которые он разделяет со своими предшественниками адаптивными автоматами).

§-исчисление (Джексон)

Представленное в 2000 году и наиболее полно обсуждавшееся в 2006 году, §-исчисление (§ здесь произносится как мета-есс ) позволяет явным образом добавлять, удалять и изменять продукты внутри грамматики, а также обеспечивать синтаксические предикаты . Этот формализм сам классифицируется его создателем как императивный и адаптивный , или, более конкретно, как формализм пространственно-временной адаптивной грамматики, и был далее классифицирован другими как аналитический формализм.

Язык удвоения демонстрируется следующим образом: ${\ displaystyle L = \ {ww | w \ in \ {a, b \} ^ {+} \}}$

grammar ww {
 S ::= #phi(A.X<-"") R;
 R ::= $C('[ab]') #phi(A.X<-A.X C) #phi(N<=A.X) N | R;
};

(Обратите внимание на обозначении: В приведенном выше примере, #phi(...) утверждение определить точки в производственном R , которые изменяют грамматику в явном виде. #phi(A.X<-A.X C) Представляет собой глобальную модификацию (со временем) и #phi(N<=A.X) выписку идентифицирует локальную модификацию (в пространстве) The. #phi(A.X<-"") Заявление в S production фактически объявляет глобальную продукцию под названием AX , помещая пустую строку в эту продукцию перед ссылкой на нее R. )

Адаптивные устройства (Нето и Пистори)

Впервые описанные Нето в 2001 году, адаптивные устройства были позже усовершенствованы и расширены Пистори в 2003 году.

Адаптер (Карми)

В 2002 году Адам Карми представил формализм адаптивной грамматики на основе LALR (1), известный как Adapser . Особенности формализма, похоже, не раскрываются.

Адаптивные CFG с проверкой внешнего вида (Bravo)

В 2004 году Сезар Браво представил идею объединения концепции проверки внешнего вида с адаптивными контекстно-независимыми грамматиками , ограниченной формой адаптивных грамматик Иваи, демонстрируя эти новые грамматики, названные адаптивными CFG с проверкой внешнего вида, чтобы быть мощными по Тьюрингу .

Адаптивные машинные формализмы

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

Самомодифицирующиеся конечные автоматы (Шатт и Рубинштейн): Представленные в 1994 году Шаттом и Рубинштейном, самомодифицирующиеся автоматы с конечными состояниями (SMFA), в ограниченной форме, являются мощными по Тьюрингу .

Адаптивные автоматы (Нето): В 1994 году Нето представил машину, которую он назвал структурированным автоматом выталкивания , ядро теории адаптивных автоматов, разработанной Иваи, Пистори, Браво и другими. Этот формализм позволяет выполнять операции проверки (аналогично синтаксическим предикатам , как отмечалось выше в отношении адаптивных грамматик Иваи), добавления и удаления правил.

Languages

In other projects