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

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

Обзор

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

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

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

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

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

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

Хотя ранние попытки ссылались на динамический синтаксис ^[7] и расширяемый , ^[6] модифицируемый , ^[10] динамичный , ^[11] и адаптируемый ^[2]^[12] В грамматиках в последнее время наблюдается тенденция к использованию термина «адаптивный» (или какого-либо его варианта, такого как «адаптива» , ^[13]^[14] в зависимости от языка издания литературы). ^[3] Иваи называет свой формализм адаптивными грамматиками . ^[13] но такое специфическое использование просто адаптивных грамматик в настоящее время обычно не используется в литературе без уточнения имени. Более того, между различными исследователями не предпринималось никаких усилий по стандартизации или категоризации, хотя некоторые предпринимали усилия в этом направлении. ^[3]^[4]

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

Шатт делит модели адаптивной грамматики на две основные категории: ^[3]^[15]

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

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

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

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

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

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

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

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

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

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

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

Язык удвоения $L=\{ww|w{\mbox{ is a letter}}\}$ демонстрируется следующим образом: ^[17]

<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 г. ^[8] и позже расширенный в декабре 1990 г. ^[10] модифицируемые грамматики явно предоставляют механизм добавления и удаления правил во время синтаксического анализа. В ответ на ответы ACM SIGPLAN Notifications Бурштейн позже изменил свой формализм и в 1992 году представил свой адаптивный универсальный анализатор синтаксиса и семантики (USSA). ^[18] Эти формализмы были классифицированы Шаттом как императивные . ^[3]

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

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

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

Булье Динамические грамматики , представленные в 1994 году, ^[11] по-видимому, являются первым семейством адаптивных грамматик, в котором строго введено понятие временного континуума синтаксического анализа как часть обозначения самого грамматического формализма. ^[4] Динамические грамматики представляют собой последовательность грамматик, каждая из которых с течением времени каким-то образом _{отличается} от других грамматик в этой последовательности. В основной статье Булье о динамических грамматиках также дается определение динамического парсера, машины, которая выполняет синтаксический анализ этих грамматик, и показаны примеры того, как его формализм может обрабатывать такие вещи, как проверка типов , расширяемые языки , полиморфизм и другие конструкции, которые обычно считаются семантическая область перевода языка программирования.

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

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

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

Представлен в 2000 году ^[20] и наиболее полно обсуждалось в 2006 г. ^[4] §-исчисление (§ здесь произносится как мета-эсс ) допускает явное добавление, удаление и модификацию продукций в грамматике, а также обеспечивает синтаксические предикаты . Этот формализм классифицируется его создателем как императивный и адаптивный , или, более конкретно, как грамматический формализм, адаптивный во времени и пространстве , а другие классифицируются как аналитический формализм. ^[14]^[21]

Язык удвоения $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) оператор идентифицирует локальную модификацию (в пространстве). #phi(A.X<-"") Оператор в продукции S фактически объявляет глобальную продукцию под названием AX , помещая пустую строку в эту продукцию перед ссылкой на нее со стороны R. )

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

Впервые описан Нето в 2001 году. ^[22] Адаптивные устройства были позже усовершенствованы и расширены Пистори в 2003 году. ^[23]

Адаптироваться (Очарование)

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

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

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

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

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

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

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

См. также

Ссылки

^ Шатт, Джон Н. «Что такое адаптивная грамматика?» . Проверено 6 февраля 2019 г.
^ Перейти обратно: ^а ^б ^с Кристиансен, Хеннинг, « Обзор адаптивных грамматик », Уведомления ACM SIGPLAN , Vol. 25 № 11, стр. 35–44, ноябрь 1990 г.
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Шатт, Джон Н., Рекурсивные адаптируемые грамматики , магистерская диссертация, Вустерский политехнический институт, 1993 г. (исправленная редакция от 16 декабря 2003 г.).
^ Перейти обратно: ^а ^б ^с ^д ^и Джексон, Куинн Тайлер, Адаптация к Вавилону: адаптивность и контекстная чувствительность при синтаксическом анализе , Ibis Publications, Плимут, Массачусетс, март 2006 г.
^ Караччоло ди Форино, Альфонсо, « Некоторые замечания о синтаксисе языков символического программирования », Communications of the ACM , Vol. 6, № 8., стр. 456–460, август 1963 г.
^ Перейти обратно: ^а ^б ^с Вегбрайт, Бен, Исследования расширяемых языков программирования ^{[ мертвая ссылка ]}, ESD-TR-70-297, Гарвардский университет, Кембридж, Массачусетс, май 1970 г. В виде книги, Garland Publishing, Inc., Нью-Йорк, 1980 г.
^ Перейти обратно: ^а ^б Хэнфорд, К.В. и Джонс, CB, « Динамический синтаксис: концепция определения синтаксиса языков программирования », Ежегодный обзор автоматического программирования 7 , Pergamon Press, Oxford, стр. 115–142, 1973.
^ Перейти обратно: ^а ^б Бурштейн Борис. « Об изменении формальной грамматики во время синтаксического анализа », Уведомления ACM SIGPLAN , Vol. 25 № 5, стр. 117–123, май 1990 г.
^ http://www.pcs.usp.br/~lta/union/index.php?cp=4&categoria=28 ^{[ мертвая ссылка ]}
^ Перейти обратно: ^а ^б Бурштейн, Борис, « Генерация и распознавание формальных языков с помощью модифицируемых грамматик », Уведомления ACM SIGPLAN , Vol. 25 № 12, стр. 45–53, декабрь 1990 г.
^ Перейти обратно: ^а ^б Булье, Пьер, « Динамические грамматики и семантический анализ », Отчет об исследовании INRIA № 2322, август 1994 г.
^ Джон Шатт первоначально назвал свои рекурсивные адаптивные грамматики именем «Рекурсивные адаптируемые грамматики» и отмечает свой переход на адаптивные по этому URL: MS Thesis Джона Шатта .
^ Перейти обратно: ^а ^б ^с ^д ^и Иваи, Маргарет Кейко, Адаптивный грамматический формализм для контекстно-зависимых языков , докторская диссертация, инженерный факультет, Университет Сан-Паулу, Бразилия, январь 2000 г.
^ Перейти обратно: ^а ^б ^с ^д Браво, Сезар, Адаптивные контекстно-свободные грамматики с проверкой внешнего вида , докторская диссертация, факультет электротехники, Университет Сан-Паулу, январь 2004 г.
^ Шатт, Джон Н., Веб-страница «Императивная адаптивная грамматика» от 28 марта 2001 г., URL: http://web.cs.wpi.edu/~jshutt/adapt/imperative.html
^ Кристиансен, Хеннинг, «Синтаксис, семантика и стратегии реализации языков программирования с мощными механизмами абстракции», Труды 18-й Гавайской международной конференции по системным наукам , Vol. 2, стр. 57–66, 1985.
^ Перейти обратно: ^а ^б Кристиансен, Хеннинг, « Синтаксис и семантика расширяемых языков », Computer Letters 14 , Университет Роскилле, 1988.
^ Бурштейн, Борис, « USSA – универсальный анализатор синтаксиса и семантики », Уведомления ACM SIGPLAN , Vol. 27 № 1, стр. 42–60, январь 1992 г.
^ Перейти обратно: ^а ^б Нето, Жоау Хосе, «Адаптивные автоматы для контекстно-зависимых языков», Уведомления ACM SIGPLAN , Vol. 29 № 9, стр. 115–124, сентябрь 1994 г.
^ Джексон, Куинн Тайлер, « Адаптивные предикаты в анализе естественного языка », Perfection , Vol. 1 № 4, апрель 2000 г.
^ Охотин, Александр, Булевы грамматики: выразительная сила и алгоритмы , докторская диссертация, Школа вычислительной техники, Университет Квинса, Кингстон, Онтарио, август 2004 г.
^ Нето, Жоау Хосе, « Адаптивные устройства, основанные на правилах: общая формулировка и практический пример». ^{[ постоянная мертвая ссылка ]}», Б. В. Уотсон, Д. Вуд (ред.): Реализация и применение автоматов, 6-я Международная конференция , CIAA 2001 , Конспекты лекций по информатике , Том 2494, Претория, Южная Африка, Springer-Verlag, стр. 234–250, 23–25 июля 2001 г.
^ Перейти обратно: ^а ^б Пистори, Хемерсон, Адаптивная технология в компьютерной инженерии: современное состояние и применение , докторская диссертация, факультет электротехники, Университет Сан-Паулу, 2003.
^ Карми, Адам, « Адапсер: адаптивный парсер LALR (1)» ^{[ постоянная мертвая ссылка ]}», Израильский семинар по языкам программирования и средам разработки, Хайфа, Израиль, 1 июля 2002 г.
^ Саломаа, Арто, Формальные языки , Academic Press, 1973.
^ Шатт, Джон и Рубинштейн, Рой, « Самомодифицирующиеся конечные автоматы », в книге Б. Персона и И. Саймона, редакторов, « Технологии и основы: обработка информации», том 94, том 94, с. I: Материалы 13-го Всемирного компьютерного конгресса ИФИП , Амстердам: Северная Голландия, стр. 493-498, 1994. ( архив )

[1] Шатт, Джон Н. «Что такое адаптивная грамматика?» . Проверено 6 февраля 2019 г.

[Christiansen1990-2] Перейти обратно: ^а ^б ^с Кристиансен, Хеннинг, « Обзор адаптивных грамматик », Уведомления ACM SIGPLAN , Vol. 25 № 11, стр. 35–44, ноябрь 1990 г.

[Shutt1993-3] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час Шатт, Джон Н., Рекурсивные адаптируемые грамматики , магистерская диссертация, Вустерский политехнический институт, 1993 г. (исправленная редакция от 16 декабря 2003 г.).

[Jackson2006-4] Перейти обратно: ^а ^б ^с ^д ^и Джексон, Куинн Тайлер, Адаптация к Вавилону: адаптивность и контекстная чувствительность при синтаксическом анализе , Ibis Publications, Плимут, Массачусетс, март 2006 г.

[Caracciolo1963-5] Караччоло ди Форино, Альфонсо, « Некоторые замечания о синтаксисе языков символического программирования », Communications of the ACM , Vol. 6, № 8., стр. 456–460, август 1963 г.

[Wegbreit-6] Перейти обратно: ^а ^б ^с Вегбрайт, Бен, Исследования расширяемых языков программирования ^{[ мертвая ссылка ]}, ESD-TR-70-297, Гарвардский университет, Кембридж, Массачусетс, май 1970 г. В виде книги, Garland Publishing, Inc., Нью-Йорк, 1980 г.

[Hanford&Jones-7] Перейти обратно: ^а ^б Хэнфорд, К.В. и Джонс, CB, « Динамический синтаксис: концепция определения синтаксиса языков программирования », Ежегодный обзор автоматического программирования 7 , Pergamon Press, Oxford, стр. 115–142, 1973.

[Burshteyn1990a-8] Перейти обратно: ^а ^б Бурштейн Борис. « Об изменении формальной грамматики во время синтаксического анализа », Уведомления ACM SIGPLAN , Vol. 25 № 5, стр. 117–123, май 1990 г.

[9] ttp://www.pcs.usp.br/~lta/union/index.php?cp=4&categoria=28 ^{[ мертвая ссылка ]}

[Burshteyn1990b-10] Перейти обратно: ^а ^б Бурштейн, Борис, « Генерация и распознавание формальных языков с помощью модифицируемых грамматик », Уведомления ACM SIGPLAN , Vol. 25 № 12, стр. 45–53, декабрь 1990 г.

[Boullier1994-11] Перейти обратно: ^а ^б Булье, Пьер, « Динамические грамматики и семантический анализ », Отчет об исследовании INRIA № 2322, август 1994 г.

[12] Джон Шатт первоначально назвал свои рекурсивные адаптивные грамматики именем «Рекурсивные адаптируемые грамматики» и отмечает свой переход на адаптивные по этому URL: MS Thesis Джона Шатта .

[Iwai2000-13] Перейти обратно: ^а ^б ^с ^д ^и Иваи, Маргарет Кейко, Адаптивный грамматический формализм для контекстно-зависимых языков , докторская диссертация, инженерный факультет, Университет Сан-Паулу, Бразилия, январь 2000 г.

[Bravo2004-14] Перейти обратно: ^а ^б ^с ^д Браво, Сезар, Адаптивные контекстно-свободные грамматики с проверкой внешнего вида , докторская диссертация, факультет электротехники, Университет Сан-Паулу, январь 2004 г.

[Shutt2001b-15] Шатт, Джон Н., Веб-страница «Императивная адаптивная грамматика» от 28 марта 2001 г., URL: http://web.cs.wpi.edu/~jshutt/adapt/imperative.html

[Christiansen1985-16] Кристиансен, Хеннинг, «Синтаксис, семантика и стратегии реализации языков программирования с мощными механизмами абстракции», Труды 18-й Гавайской международной конференции по системным наукам , Vol. 2, стр. 57–66, 1985.

[Christiansen1988-17] Перейти обратно: ^а ^б Кристиансен, Хеннинг, « Синтаксис и семантика расширяемых языков », Computer Letters 14 , Университет Роскилле, 1988.

[Burshteyn1992-18] Бурштейн, Борис, « USSA – универсальный анализатор синтаксиса и семантики », Уведомления ACM SIGPLAN , Vol. 27 № 1, стр. 42–60, январь 1992 г.

[Neto1994-19] Перейти обратно: ^а ^б Нето, Жоау Хосе, «Адаптивные автоматы для контекстно-зависимых языков», Уведомления ACM SIGPLAN , Vol. 29 № 9, стр. 115–124, сентябрь 1994 г.

[Jackson2000a-20] Джексон, Куинн Тайлер, « Адаптивные предикаты в анализе естественного языка », Perfection , Vol. 1 № 4, апрель 2000 г.

[Okhotin2004-21] Охотин, Александр, Булевы грамматики: выразительная сила и алгоритмы , докторская диссертация, Школа вычислительной техники, Университет Квинса, Кингстон, Онтарио, август 2004 г.

[Neto2001-22] Нето, Жоау Хосе, « Адаптивные устройства, основанные на правилах: общая формулировка и практический пример». ^{[ постоянная мертвая ссылка ]}», Б. В. Уотсон, Д. Вуд (ред.): Реализация и применение автоматов, 6-я Международная конференция , CIAA 2001 , Конспекты лекций по информатике , Том 2494, Претория, Южная Африка, Springer-Verlag, стр. 234–250, 23–25 июля 2001 г.

[Pistori2003-23] Перейти обратно: ^а ^б Пистори, Хемерсон, Адаптивная технология в компьютерной инженерии: современное состояние и применение , докторская диссертация, факультет электротехники, Университет Сан-Паулу, 2003.

[24] Карми, Адам, « Адапсер: адаптивный парсер LALR (1)» ^{[ постоянная мертвая ссылка ]}», Израильский семинар по языкам программирования и средам разработки, Хайфа, Израиль, 1 июля 2002 г.

[Salomaa1973-25] Саломаа, Арто, Формальные языки , Academic Press, 1973.

[Shutt&Rubinstein-26] Шатт, Джон и Рубинштейн, Рой, « Самомодифицирующиеся конечные автоматы », в книге Б. Персона и И. Саймона, редакторов, « Технологии и основы: обработка информации», том 94, том 94, с. I: Материалы 13-го Всемирного компьютерного конгресса ИФИП , Амстердам: Северная Голландия, стр. 493-498, 1994. ( архив )

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]