Грамматика, примыкающая к дереву

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

История

TAG возник в результате исследований Джоши и его учеников семейства грамматик присоединения (AG), ^[1] «строковая грамматика» Зеллига Харриса . ^[2] обрабатывают экзоцентрические АГ естественным и эффективным образом свойства языка, но не дают хорошей характеристики эндоцентрических конструкций; Обратное верно для переписанных грамматик или грамматик фразовой структуры (PSG). В 1969 году Джоши представил семейство грамматик, использующих эту взаимодополняемость путем смешивания двух типов правил. Нескольких очень простых правил перезаписи достаточно, чтобы сгенерировать словарь строк для правил соединения. Это семейство отличается от иерархии Хомского-Шютценбергера, но пересекается с ней интересным и лингвистически значимым образом. ^[3] Центральные строки и дополнительные строки также могут быть сгенерированы с помощью грамматики зависимостей , что полностью позволяет избежать ограничений систем перезаписи. ^[4]^[5]

Описание

Правила в TAG представляют собой деревья со специальным конечным узлом, известным как нижний узел , который привязан к слову. В TAG есть два типа базовых деревьев: начальные деревья (часто обозначаемые как ' $\alpha$ ') и вспомогательные деревья (' $\beta$ '). Начальные деревья представляют собой основные валентные отношения, а вспомогательные деревья допускают рекурсию. ^[6]Вспомогательные деревья имеют корневой (верхний) узел и нижний узел, помеченные одним и тем же символом.Вывод начинается с исходного дерева, объединяющегося посредством замены или присоединения . При замене пограничный узел заменяется другим деревом, верхний узел которого имеет ту же метку. Метка корня/ножки вспомогательного дерева должна совпадать с меткой узла, к которому оно примыкает. Таким образом, присоединение может привести к вставке вспомогательного дерева в центр другого дерева. ^[4]

Другие варианты TAG позволяют создавать многокомпонентные деревья , деревья с несколькими узлами и другие расширения.

Сложность и применение

Древовидные грамматики более мощные (с точки зрения слабой генеративной способности ), чем контекстно-свободные грамматики , но менее мощные, чем линейные контекстно-свободные системы переписывания . ^[7] индексируется ^{[примечание 1]} или контекстно-зависимые грамматики.

TAG может описывать язык квадратов (в котором повторяется некоторая произвольная строка), а также язык $\{a^{n}b^{n}c^{n}d^{n}|1\leq n\}$ . Этот тип обработки может быть представлен встроенным автоматом с выталкиванием .Языки с кубами (т.е. тройными строками) или с более чем четырьмя различными символьными строками одинаковой длины не могут быть созданы с помощью грамматик, прилегающих к дереву.

По этим причинам грамматики, примыкающие к деревьям, часто описываются как слегка контекстно-зависимые .Предполагается, что эти классы грамматики достаточно мощны для моделирования естественных языков , оставаясь при этом эффективно анализируемыми в общем случае. ^[8]

Эквиваленты

Виджай-Шанкер и Вейр (1994) ^[9] продемонстрировать, что линейные индексированные грамматики , комбинаторные категориальные грамматики , древовидные грамматики и головные грамматики являются слабо эквивалентными формализмами, поскольку все они определяют одни и те же строковые языки.

Лексикализованный

Лексикализованные древовидные грамматики (LTAG) — это вариант TAG, в котором каждое элементарное дерево (начальное или вспомогательное) связано с лексическим элементом. Лексикализованная грамматика английского языка была разработана исследовательской группой XTAG Института исследований когнитивных наук Пенсильванского университета. ^[5]

См. также

Строковая грамматика

Примечания

^ поскольку для каждой грамматики, примыкающей к дереву, можно найти линейную индексированную грамматику, производящую тот же язык, см. ниже , а для последней, в свою очередь, можно найти слабо эквивалентную (правильную) индексированную грамматику, см. Индексированная грамматика#Вычислительная мощность

Ссылки

^ Джоши, Аравинд; С.Р. Косараджу; Х. Ямада (1969). «Строковые дополнительные грамматики» (Документ). Труды десятого ежегодного симпозиума по теории автоматов, Ватерлоо, Канада. Джоши, Аравинд К.; Косараджу, С. Рао; Ямада, Х.М. (1972), «Строковые дополнительные грамматики: I. Локальное и распределенное присоединение», Information and Control , 21 (2): 93–116, doi : 10.1016/S0019-9958(72)90051-4 Джоши, Аравинд К.; Косараджу, С. Рао; Ямада, Х.М. (1972), «Строковые дополнительные грамматики: II. Эквациональное представление, нулевые символы и лингвистическая релевантность», Information and Control , 21 (3): 235–260, doi : 10.1016/S0019-9958(72)80005- 6
^ Харрис, Зеллиг С. (1962). Строковый анализ структуры предложения . Статьи по формальной лингвистике. Том. 1. Гаага: Мутон и Ко.
^ Джоши, Аравинд (1969). «Свойства формальных грамматик со смешанными типами правил и их лингвистическая значимость» (Документ). Труды Третьего международного симпозиума по компьютерной лингвистике, Стокгольм, Швеция.
^ Перейти обратно: ^а ^б Джоши, Аравинд; Оуэн Рэмбоу (2003). «Формализм грамматики зависимостей, основанный на грамматике, примыкающей к дереву» (PDF) . Материалы конференции по теории смысла текста .
^ Перейти обратно: ^а ^б «Лексикализированное дерево, примыкающее к грамматике английского языка» .
^ Юрафски, Дэниел ; Джеймс Х. Мартин (2000). Речевая и языковая обработка . Река Аппер-Седл, Нью-Джерси: Прентис-Холл. п. 354.
^ Калмейер, Лаура (2010). Анализ за пределами контекстно-свободных грамматик. Спрингер. Здесь: стр.215-216
^ Джоши, Аравинд (1985). «Насколько контекстная чувствительность необходима для характеристики структурных описаний». У Д. Даути; Л. Карттунен; А. Цвики (ред.). Обработка естественного языка: теоретические, вычислительные и психологические перспективы . Нью-Йорк, штат Нью-Йорк: Издательство Кембриджского университета. стр. 206–250 . ISBN 9780521262033 .
^ Виджей-Шанкер, К. и Вейр, Дэвид Дж. 1994. Эквивалентность четырех расширений контекстно-свободных грамматик . Теория математических систем 27 (6): 511–546.

Внешние ссылки

Проект XTAG , который использует TAG для обработки естественного языка.
Учебник по TAG
Документация SemConst. Краткий обзор проблем синтаксиса и семантического интерфейса в рамках TAG.
Проект TuLiPa Тюбингенская лингвистическая архитектура синтаксического анализа (TuLiPA) — это мультиформализмная среда синтаксического (и семантического) синтаксического анализа, разработанная в основном для многокомпонентных древовидных грамматик, соприкасающихся с кортежами деревьев.
Набор инструментов для метаграмматики , который предоставляет несколько инструментов для редактирования и компиляции метаграмматик в теги. Он также включает широкий охват французских метаграмматик.
LLP2 Синтаксический анализатор грамматики, граничащий с лексикализованным деревом , который обеспечивает простую в использовании графическую среду (страница на французском языке).

[8] поскольку для каждой грамматики, примыкающей к дереву, можно найти линейную индексированную грамматику, производящую тот же язык, см. ниже , а для последней, в свою очередь, можно найти слабо эквивалентную (правильную) индексированную грамматику, см. Индексированная грамматика#Вычислительная мощность

[JoshiKosarajuYamada1969-1] Джоши, Аравинд; С.Р. Косараджу; Х. Ямада (1969). «Строковые дополнительные грамматики» (Документ). Труды десятого ежегодного симпозиума по теории автоматов, Ватерлоо, Канада. Джоши, Аравинд К.; Косараджу, С. Рао; Ямада, Х.М. (1972), «Строковые дополнительные грамматики: I. Локальное и распределенное присоединение», Information and Control , 21 (2): 93–116, doi : 10.1016/S0019-9958(72)90051-4 Джоши, Аравинд К.; Косараджу, С. Рао; Ямада, Х.М. (1972), «Строковые дополнительные грамматики: II. Эквациональное представление, нулевые символы и лингвистическая релевантность», Information and Control , 21 (3): 235–260, doi : 10.1016/S0019-9958(72)80005- 6

[2] Харрис, Зеллиг С. (1962). Строковый анализ структуры предложения . Статьи по формальной лингвистике. Том. 1. Гаага: Мутон и Ко.

[Joshi1969-3] Джоши, Аравинд (1969). «Свойства формальных грамматик со смешанными типами правил и их лингвистическая значимость» (Документ). Труды Третьего международного симпозиума по компьютерной лингвистике, Стокгольм, Швеция.

[joshi-rambow2003-4] Перейти обратно: ^а ^б Джоши, Аравинд; Оуэн Рэмбоу (2003). «Формализм грамматики зависимостей, основанный на грамматике, примыкающей к дереву» (PDF) . Материалы конференции по теории смысла текста .

[xtagenglish-5] Перейти обратно: ^а ^б «Лексикализированное дерево, примыкающее к грамматике английского языка» .

[jurafsky-martin2000-6] Юрафски, Дэниел ; Джеймс Х. Мартин (2000). Речевая и языковая обработка . Река Аппер-Седл, Нью-Джерси: Прентис-Холл. п. 354.

[7] Калмейер, Лаура (2010). Анализ за пределами контекстно-свободных грамматик. Спрингер. Здесь: стр.215-216

[joshi1985-9] Джоши, Аравинд (1985). «Насколько контекстная чувствительность необходима для характеристики структурных описаний». У Д. Даути; Л. Карттунен; А. Цвики (ред.). Обработка естественного языка: теоретические, вычислительные и психологические перспективы . Нью-Йорк, штат Нью-Йорк: Издательство Кембриджского университета. стр. 206–250 . ISBN 9780521262033 .

[vijayshankarAndWeir1995-10] Виджей-Шанкер, К. и Вейр, Дэвид Дж. 1994. Эквивалентность четырех расширений контекстно-свободных грамматик . Теория математических систем 27 (6): 511–546.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[примечание 1]

[8]

[9]