Адаптивный грамматик является формальной грамматикой , которая четко предусматривает механизмы в рамках формализма , чтобы его собственные правила производства манипулировать.
Обзор
Джон Н. Шатт определяет адаптивную грамматику как грамматический формализм, который позволяет явно манипулировать наборами правил (или наборами производственных правил) внутри грамматики. Типы манипуляций включают добавление, удаление и изменение правил. [1]
Ранняя история
Первым описанием адаптивности грамматики (хотя и не под этим названием) в литературе обычно [2] [3] [4] считается статья Альфонсо Караччоло ди Форино, опубликованная в 1963 году. [5] Следующая общепринятая ссылка к адаптивному формализму ( расширяемые контекстно-свободные грамматики ) пришли из Вегбрайта в 1970 году [6] при изучении расширяемых языков программирования , за которым последовал динамический синтаксис Хэнфорда и Джонса в 1973 году [7].
Совместные усилия
До недавнего времени большая часть исследований формальных свойств адаптивных грамматик не координировалась между исследователями, только впервые они были обобщены Хеннингом Кристиансеном в 1990 году [2] в ответ на статью Бориса Бурштейна в ACM SIGPLAN Notices . [8] На инженерном факультете Университета Сан-Паулу есть лаборатория адаптивных языков и методов , специализирующаяся на исследованиях и практике адаптивных технологий и теории. LTA также поддерживает исследователей именования страниц в этой области. [9]
Терминология и систематика
В то время как ранние попытки делали ссылки на динамический синтаксис [7] и расширяемые , [6] модифицируемые , [10] динамические , [11] и адаптируемые [2] [12] грамматики, в более поздних версиях использовался термин адаптивный ( или какой-либо вариант, такой как adaptativa , [13] [14] в зависимости от языка публикации литературы). [3] Иваи называет свой формализм адаптивными грамматиками , [13] но это конкретное использование просто адаптивных грамматик в настоящее время обычно не используется в литературе без уточнения имени. Более того, между различными исследователями не было предпринято никаких усилий по стандартизации или категоризации, хотя некоторые из них предпринимали усилия в этом направлении. [3] [4]
Классификация Шатта (и дополнения)
Шатт делит модели адаптивной грамматики на две основные категории: [3] [15]
- Императивные адаптивные грамматики изменяют свои правилаоснованные на глобальном состоянии изменяющегосятечение времени от поколения о наличии языка .
- Декларативные адаптивные грамматики меняют свои правила только в пространстве генерации языка (т. Е. Позиции в синтаксическом дереве сгенерированной строки).
Джексон уточняет таксономию Шатта, называя изменения во времени глобальными, а изменения в пространстве - локальными , и добавляет гибридную пространственно-временную категорию: [4]
- Адаптивные пространственно-временные грамматики ( гибриды ) изменяют свои правила в зависимости от времени или пространства (или обоих) генерации языка (и локальные и глобальные операции явно различаются по обозначениям для таких изменений).
Адаптивные формализмы в литературе
Адаптивные формализмы можно разделить на две основные категории: полные грамматические формализмы (адаптивные грамматики) и адаптивные машины, на которых были основаны некоторые грамматические формализмы.
Формализмы адаптивной грамматики
Ниже приводится список (ни в коем случае не полный) грамматических формализмов, которые, согласно приведенному выше определению Шатта, считаются (или были классифицированы их собственными изобретателями как таковые) адаптивными грамматиками. Они перечислены в порядке их первого упоминания в литературе.
Расширяемые контекстно-свободные грамматики (Wegbreit)
Описанная в докторской диссертации Вегбрайта в 1970 году [6] расширяемая контекстно-свободная грамматика состоит из контекстно-свободной грамматики , набор правил которой изменяется в соответствии с инструкциями, выдаваемыми преобразователем конечного состояния при чтении терминального префикса во время самого левого вывода. Таким образом, набор правил варьируется в зависимости от положения в сгенерированной строке, но этот вариант игнорирует иерархическую структуру синтаксического дерева. Расширяемые контекстно-свободные грамматики были классифицированы Шаттом как обязательные . [3]
Грамматики Кристиансена (Christiansen)
Впервые представленные в 1985 году как генеративные грамматики [16], а затем более развитые [17], грамматики Кристиансена (очевидно, названные так Шаттом, возможно, из-за конфликта с генеративными грамматиками Хомского) являются адаптивным расширением атрибутивных грамматик . Грамматики Кристиансена были классифицированы Shutt как декларативные . [3]
Язык удвоения демонстрируется следующим образом: [17]
<программа ↓ G > →G ↑ w > <тело ↓ { w-правило }>
где w-rule =<тело ↓ G '> → w
G ↑ ch • w > → G ↑ ch > G ↑ w > > → <ε> <символ ↓ G ↑ a> → a
Грамматики, изменяемые снизу вверх, грамматики, изменяемые сверху вниз, и USSA (Бурштейн)
Изменяемые грамматики, впервые представленные в мае 1990 г. [8] и позже расширенные в декабре 1990 г. [10], явно предоставляют механизм для добавления и удаления правил во время синтаксического анализа. В ответ на ответы ACM SIGPLAN Notices Бурштейн позже изменил свой формализм и представил свой адаптивный универсальный анализатор синтаксиса и семантики (USSA) в 1992 году. [18] Эти формализмы были классифицированы Шаттом как обязательные . [3]
Рекурсивные адаптивные грамматики (Shutt)
Представленные в 1993 году рекурсивные адаптивные грамматики (RAG) были попыткой ввести мощный формализм Тьюринга, который сохранил большую часть элегантности контекстно-свободных грамматик. [3] Шатт самостоятельно классифицирует RAG как декларативный формализм.
Динамические грамматики (Булье)
Динамические грамматики Булье , представленные в 1994 г. [11], по-видимому, являются первым семейством грамматик с адаптивной грамматикой, в котором строго введено понятие временного континуума синтаксического анализа как часть обозначений самого грамматического формализма. [4] Динамические грамматики - это последовательность грамматик, причем каждая грамматика G i каким-то образом отличается от других грамматик в этой последовательности с течением времени. Основная статья Булье по динамическим грамматикам также определяет динамический синтаксический анализатор, машину, которая выполняет синтаксический анализ этих грамматик, и показывает примеры того, как его формализм может обрабатывать такие вещи, как проверка типов , расширяемые языки , полиморфизм и другие конструкции, обычно рассматриваемые в семантическая область перевода языков программирования.
Адаптивные грамматики (Иваи)
Работа Иваи в 2000 г. [13] развивает адаптивные автоматы Нето [19] , применяя адаптивные автоматы к контекстно-зависимым грамматикам . Адаптивные грамматики Иваи (обратите внимание на квалификатор по имени) позволяют выполнять три операции во время синтаксического анализа:? запрос (в некоторых отношениях похож на синтаксический предикат , но привязанный к проверке правил, из которых выбираются модификации), + сложение и - удаление (которые он разделяет со своими предшественниками адаптивными автоматами).
§-исчисление (Джексон)
Представленный в 2000 г. [20] и наиболее полно обсуждавшийся в 2006 г. [4] §-исчисление (§ здесь произносится как meta-ess ) позволяет явным образом добавлять, удалять и изменять произведения внутри грамматики, а также обеспечивать синтаксические предикаты . Этот формализм сам классифицируется его создателем как императивный и адаптивный , или, более конкретно, как формализм пространственно-временной адаптивной грамматики, и был далее классифицирован другими как аналитический формализм. [14] [21]
Язык удвоения демонстрируется следующим образом:
грамматика ww { S :: = #phi (AX <- "") R; R :: = $ C ('[ab]') #phi (AX <-AX C) #phi (N <= AX) N | Р;};
(Обратите внимание на обозначении: В приведенном выше примере, #phi(...)
утверждение определить точки в производственном R , которые изменяют грамматику в явном виде. #phi(A.X<-A.X C)
Представляет собой глобальную модификацию (со временем) и #phi(N<=A.X)
выписку идентифицирует локальную модификацию (в пространстве) The. #phi(A.X<-"")
Заявление в S production фактически объявляет глобальную продукцию под названием AX , помещая пустую строку в эту продукцию перед ссылкой на нее R. )
Адаптивные устройства (Нето и Пистори)
Впервые описанные Нето в 2001 году [22] адаптивные устройства были позже усовершенствованы и расширены Пистори в 2003 году. [23]
Адаптер (Карми)
В 2002 г. [24] Адам Карми представил формализм адаптивной грамматики на основе LALR (1), известный как Adapser . Особенности формализма, похоже, не раскрываются.
Адаптивные CFG с проверкой внешнего вида (Bravo)
В 2004 году [14] Сезар Браво представил идею объединения концепции проверки внешнего вида [25] с адаптивными контекстно-свободными грамматиками , ограниченной формой адаптивных грамматик Иваи [13], демонстрируя эти новые грамматики, названные адаптивными CFG с проверкой внешнего вида. быть сильным по Тьюрингу .
Адаптивные машинные формализмы
Перечисленные ниже формализмы, хотя и не являются грамматическими формализмами, либо служат основой для полных грамматических формализмов, либо включены сюда, потому что они адаптивны по своей природе. Они перечислены в порядке их первого упоминания в литературе.
- Самомодифицирующиеся конечные автоматы (Шатт и Рубинштейн)
- Введенные в 1994 году Шаттом и Рубинштейном [26], самомодифицирующиеся автоматы с конечными состояниями (SMFA), как показано, в ограниченной форме являются мощными по Тьюрингу .
- Адаптивные автоматы (Нето)
- В 1994 году [19] Нето представил машину, которую он назвал структурированным автоматом с выталкиванием вниз , ядро теории адаптивных автоматов, разработанной Иваи, [13] Пистори, [23] Браво [14] и другими. Этот формализм позволяет выполнять операции проверки (аналогично синтаксическим предикатам , как отмечалось выше в отношении адаптивных грамматик Иваи), добавления и удаления правил.
Смотрите также
- Адаптивный алгоритм
- Искусственное изучение грамматики
- Введение в грамматику
- Категория: Языки программирования с расширяемым синтаксисом
Рекомендации
- ^ Шатт, Джон Н. "Что такое адаптивная грамматика?" . Проверено 6 февраля 2019 .
- ^ a b c Кристиансен, Хеннинг, " Обзор адаптируемых грамматик ", ACM SIGPLAN Notices , Vol. 25 No. 11, pp. 35-44, Nov.1990.
- ^ a b c d e f g h Шатт, Джон Н., Рекурсивные адаптируемые грамматики , магистерская работа, Вустерский политехнический институт, 1993 г. (исправленная редакция от 16 декабря 2003 г.).
- ^ a b c d e Джексон, Куинн Тайлер, Адаптация к Babel: адаптивность и контекстная чувствительность в синтаксическом анализе , Ibis Publications, Плимут, Массачусетс, март 2006 г.
- ^ Караччоло ди Форино, Альфонсо, " Некоторые замечания по синтаксису символьных языков программирования ", Связь ACM , Vol. 6, No. 8., pp. 456-460, август 1963 г.
- ^ a b c Вегбрайт, Бен, Исследования в области расширяемых языков программирования , ESD-TR-70-297, Гарвардский университет, Кембридж, Массачусетс, май 1970 г. В книжной форме, Garland Publishing, Inc., Нью-Йорк, 1980.
- ^ a b Хэнфорд, К.В. и Джонс, CB, « Динамический синтаксис: концепция определения синтаксиса языков программирования », Ежегодный обзор автоматического программирования 7 , Pergamon Press, Oxford, стр. 115-142, 1973.
- ^ а б Бурштейн, Борис. « Об изменении формальной грамматики во время синтаксического анализа », ACM SIGPLAN Notices , Vol. 25 No. 5, pp. 117-123, May 1990.
- ^ http://www.pcs.usp.br/~lta/union/index.php?cp=4&categoria=28 [ мертвая ссылка ]
- ^ a b Бурштейн, Борис, « Генерация и распознавание формальных языков с помощью изменяемых грамматик », Уведомления ACM SIGPLAN , Vol. 25 No. 12, pp. 45-53, декабрь 1990 г.
- ^ a b Булье, Пьер, " Динамические грамматики и семантический анализ ", Отчет об исследовании INRIA № 2322, август 1994.
- ^ Джон Шатт первоначально называл свои рекурсивные адаптивные грамматики рекурсивными адаптивными грамматиками и отмечает свое изменение на адаптивные по этому URL-адресу: MS Thesis Джона Шатта .
- ^ a b c d e Иваи, Маргарет Кейко, Um формализм-грамматический адаптивно для лингвагенов, зависимых от контекста , докторская диссертация, факультет инженерии, университет Сан-Паулу, Бразилия, январь 2000 г.
- ^ a b c d Браво, Сезар, Grámmaticas Livres de Contexto Adaptativas com verificação de aparência , докторская диссертация, факультет электротехники, Университет Сан-Паулу, январь 2004 г.
- ^ Шатт, Джон Н., «Императивные адаптивные грамматики», веб-страница от 28 марта 2001 г., по адресу: http://web.cs.wpi.edu/~jshutt/adapt/imperative.html
- ^ Кристиансен, Хеннинг, "Синтаксис, семантика и стратегии реализации для языков программирования с мощными механизмами абстракции", Труды 18-й Гавайской международной конференции по системным наукам , Vol. 2. С. 57-66, 1985.
- ^ a b Кристиансен, Хеннинг, " Синтаксис и семантика расширяемых языков ", Datalogiske skrifter 14 , Университет Роскилле, 1988.
- ^ Бурштейн, Борис, " USSA – Универсальный анализатор синтаксиса и семантики ", Уведомления ACM SIGPLAN , Vol. 27 No. 1, pp. 42-60, январь 1992 г.
- ^ a b Нету, Жоао Жозе, «Адаптивные автоматы для контекстно-зависимых языков», Уведомления ACM SIGPLAN , Vol. 29 No. 9, pp. 115-124, сентябрь 1994 г.
- ^ Джексон, Куинн Тайлер, « Адаптивные предикаты в синтаксическом анализе естественного языка» , « Совершенство» , Vol. 1 No. 4, апрель 2000 г.
- ^ Охотин, Александр, Булевы грамматики: выразительная сила и алгоритмы , докторская диссертация, Школа вычислительной техники, Куинсский университет, Кингстон, Онтарио, август 2004 г.
- ^ Нето, Жуан Жозе, « Адаптивные устройства, управляемые правилами: общая формулировка и тематическое исследование [ постоянная мертвая ссылка ] », Б. В. Уотсон, Д. Вуд (ред.): Внедрение и применение автоматов 6-я Международная конференция , CIAA 2001 , Лекционные заметки в области компьютерных наук , Vol. 2494, Претория, Южная Африка, Springer-Verlag, стр. 234–250, 23–25 июля 2001 г.
- ^ a b Пистори, Хемерсон, Технологическая адаптация в инженерной инженерии: Estado da Arte e Aplicações , докторская диссертация, факультет электротехники, Университет Сан-Паулу, 2003.
- ^ Карми, Адам, " Adapser: LALR (1) Adaptive Parser [ постоянная мертвая ссылка ] ", Израильский семинар по языкам программирования и средам разработки, Хайфа, Израиль, 1 июля 2002 г.
- ^ Salomaa, Арто, Формальные Языки , Academic Press, 1973.
- ^ Шатт, Джон и Рубинштейн, Рой, « Самомодифицирующиеся конечные автоматы », в Б. Персон и И. Саймон, редакторы, Технология и основы: обработка информации '94 Vol. I: Материалы 13-го Всемирного компьютерного конгресса IFIP , Амстердам: Северная Голландия, стр. 493-498, 1994.