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

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

Обзор

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

История ранних веков

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Язык удвоения демонстрируется следующим образом:[17]

<программа ↓г> → г↑ш> <тело ↓ {w-правило}>
где w-правило  = <тело ↓г’>         →   ш
г↑ch•ш> → <символ ↓г↑ch> г↑ш> > → <ε>  → a

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

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

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

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

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

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

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

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

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

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

Язык удвоения демонстрируется следующим образом:

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

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

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

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

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

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

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

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

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

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

Самомодифицирующиеся конечные автоматы (Shutt & Rubinstein)
Представленный в 1994 году Шаттом и Рубинштейном,[26] Самомодифицирующиеся автоматы с конечными состояниями (SMFA) показаны в ограниченной форме: Тьюринг мощный.
Адаптивные автоматы (Нето)
В 1994 г.[19] Нето представил машину, которую назвал структурированный автомат выталкивания, суть теории адаптивных автоматов, которую проводил Иваи,[13] Пистори,[23] Браво[14] и другие. Этот формализм допускает операции осмотр (похожий на синтаксические предикаты, как отмечалось выше в отношении адаптивных грамматик Иваи), дополнение, и удаление правил.

Смотрите также

использованная литература

  1. ^ Шатт, Джон Н. «Что такое адаптивная грамматика?». Получено 6 февраля 2019.
  2. ^ а б c Кристиансен, Хеннинг "А" Обзор адаптируемых грамматик," Уведомления ACM SIGPLAN, Vol. 25 No. 11, pp. 35-44, ноябрь 1990 г.
  3. ^ а б c d е ж г час Шатт, Джон Н., Рекурсивные адаптируемые грамматики, Магистерская работа, Вустерский политехнический институт, 1993 г. (исправленная редакция от 16 декабря 2003 г.)
  4. ^ а б c d е Джексон, Куинн Тайлер, Адаптация к Babel: адаптивность и контекстная чувствительность при синтаксическом анализе, Ibis Publications, Плимут, Массачусетс, март 2006 г.
  5. ^ Караччоло ди Форино, Альфонсо "Некоторые замечания по синтаксису символьных языков программирования," Коммуникации ACM, Vol. 6, No. 8., pp. 456-460, август 1963 г.
  6. ^ а б c Wegbreit, Бен, Исследования по расширяемым языкам программирования, ESD-TR-70-297, Гарвардский университет, Кембридж, Массачусетс, май 1970 г. В книжной форме, Garland Publishing, Inc., Нью-Йорк, 1980.
  7. ^ а б Хэнфорд, К. И Джонс, Си Би ",Динамический синтаксис: концепция определения синтаксиса языков программирования," Годовой обзор автоматического программирования 7, Pergamon Press, Oxford, стр. 115-142, 1973.
  8. ^ а б Бурштейн, Борис. "Об изменении формальной грамматики во время синтаксического анализа ", Уведомления ACM SIGPLAN, Vol. 25 No. 5, pp. 117-123, May 1990.
  9. ^ http://www.pcs.usp.br/~lta/union/index.php?cp=4&categoria=28[мертвая ссылка ]
  10. ^ а б Бурштейн, Борис "Генерация и распознавание формальных языков с помощью изменяемых грамматик," Уведомления ACM SIGPLAN, Vol. 25 No. 12, pp. 45-53, декабрь 1990 г.
  11. ^ а б Булье, Пьер "Динамические грамматики и семантический анализ, "Отчет об исследовании INRIA № 2322, август 1994 г.
  12. ^ Джон Шатт первоначально назвал свои рекурсивные адаптивные грамматики рекурсивными. Адаптируемый Грамматики и отмечает его изменение на адаптивный по этому URL: Докторская диссертация Джона Шатта.
  13. ^ а б c d е Иваи, Маргарет Кейко, Um формализм-грамматический адаптивно для лингвагенов, зависимых от контекстаДокторская диссертация на инженерном факультете Университета Сан-Паулу, Бразилия, январь 2000 г.
  14. ^ а б c d Браво, Сезар, Grámmaticas Livres de Contexto Adaptativas com verificação de aparência Докторская диссертация, факультет электротехники, Университет Сан-Паулу, январь 2004 г.
  15. ^ Шатт, Джон Н., Веб-страница "Imperative Adaptive Grammars" от 28 марта 2001 г. по адресу: http://web.cs.wpi.edu/~jshutt/adapt/imperative.html
  16. ^ Кристиансен, Хеннинг, "Синтаксис, семантика и стратегии реализации для языков программирования с мощными механизмами абстракции", Материалы 18-й Гавайской международной конференции по системным наукам, Vol. 2. С. 57-66, 1985.
  17. ^ а б Кристиансен, Хеннинг "Синтаксис и семантика расширяемых языков," Datalogiske skrifter 14, Университет Роскилле, 1988.
  18. ^ Бурштейн, Борис "USSA – Универсальный анализатор синтаксиса и семантики," Уведомления ACM SIGPLAN, Vol. 27 No. 1, pp. 42-60, январь 1992 г.
  19. ^ а б Нето, Жоао Хосе, «Адаптивные автоматы для контекстно-зависимых языков», Уведомления ACM SIGPLAN, Vol. 29 No. 9, pp. 115-124, сентябрь 1994 г.
  20. ^ Джексон, Куинн Тайлер "Адаптивные предикаты в синтаксическом анализе естественного языка," Совершенство, Vol. 1 No. 4, апрель 2000 г.
  21. ^ Охотин Александр, Булевы грамматики: выразительная сила и алгоритмыДокторская диссертация, Школа вычислительной техники Университета Квинс, Кингстон, Онтарио, август 2004 г.
  22. ^ Нету, Жоао Жозе "Адаптивные устройства, управляемые правилами: общая формулировка и практический пример[постоянная мертвая ссылка ], "Б. В. Уотсон, Д. Вуд (ред.): Внедрение и применение автоматов 6-я международная конференция, CIAA 2001, Конспект лекций по информатике, Vol. 2494, Претория, Южная Африка, Springer-Verlag, стр. 234–250, 23–25 июля 2001 г.
  23. ^ а б Пистори, Хемерсон, Tecnologia Adaptativa em Engenharia de Computação: Estado da Arte e Aplicações, Докторская диссертация, факультет электротехники, университет Сан-Паулу, 2003 г.
  24. ^ Карми, Адам "Адаптер: адаптивный синтаксический анализатор LALR (1)[постоянная мертвая ссылка ]," Израильский семинар по языкам программирования и средам разработки, Хайфа, Израиль, 1 июля 2002 г.
  25. ^ Саломаа, Арто, Формальные языки, Академик Пресс, 1973.
  26. ^ Шатт, Джон и Рубинштейн, Рой "Самомодифицирующиеся конечные автоматы, "в Б. Персон и И. Саймон, редакторы, Технологии и основы: обработка информации '94 Vol. I: Материалы 13-го Всемирного компьютерного конгресса ИФИП, Амстердам: Северная Голландия, стр. 493-498, 1994.