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

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

• 1 Обзор
  • 1.1 Ранняя история
  • 1.2 Совместные усилия
  • 1.3 Терминология и таксономия
    • 1.3.1 Классификация Шатта (и расширения)
• 2 Адаптивные формализмы в литературе
  • 2.1 Адаптивные грамматические формализмы
    • 2.1.1 Расширяемые контекстно-свободные грамматики (Wegbreit)
    • 2.1.2 Грамматики Кристиансена (Christiansen)
    • 2.1.3 Грамматики, изменяемые снизу вверх, грамматики, изменяемые сверху вниз, и USSA (Бурштейн)
    • 2.1.4 Рекурсивные адаптивные грамматики (Shutt)
    • 2.1.5 Динамические грамматики (Булье)
    • 2.1.6 Адаптивные грамматики (Иваи)
    • 2.1.7 §-исчисление (Джексон)
    • 2.1.8 Адаптивные устройства (Neto Pistori)
    • 2.1.9 Адаптер (Carmi)
    • 2.1.10 Адаптивные CFG с проверкой внешнего вида (Bravo)
  • 2.2 Адаптивные машинные формализмы
• 3 См. также
• 4 Ссылки

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

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

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

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

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

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

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

Классификация (и расширения) Шатта

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

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

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

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

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

Адаптивные грамматические формализмы

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

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

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

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

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

Удвоенный язык $L\; =\; \{w\; w\; |\; w\; -\; буква\}\; \{\backslash \; displaystyle\; L\; =\; \backslash \; \{ww\; |\; w\; \{\backslash \; t\_dv\; \{-\; буква\}\}\; \backslash \}\}$демонстрируется следующим образом:

→ 

где w-rule = → w

→ >→ <ε>→ a

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

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

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

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

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

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

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

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

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

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

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

грамматика ww {S :: = #phi (AX <-"") R; R ::= $C('[ab]') #phi(A.X<-A.X C) #phi(N<=A.X) N | R; };

(Примечание к обозначениям: в приведенном выше примере операторы #phi (...) идентифицируют точки в продукте R, которые явно изменяют грамматику. #phi (AX <-A.X C) represents a global modification (over time) and the #phi(N<=A.X) statement identifies a local modification (over space). The #phi(A.X<-"") statement in the S production effectively declares a global production called A.X by placing the пустая строка в этом продукте до его ссылки на R.)

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

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

Adapser (Carmi)

В 2002 году Адам Карми представил формализм адаптивной грамматики на основе LALR (1)

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

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

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

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

Самомодифицирующиеся конечные автоматы (Shutt Rubinstein)

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

Адаптивные автоматы (Нето)

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

• Адаптивный алгоритм
• Искусственное изучение грамматики
• Введение в грамматику
• Категория: Языки программирования с расширяемым синтаксисом