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

редактировать

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

Содержание

  • 1 История
  • 2 Описание
  • 3 Сложность и применение
    • 3.1 Эквивалентность
  • 4 Лексикализация
  • 5 Примечания
  • 6 Ссылки
  • 7 Внешние ссылки

История

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

Описание

Правила в TAG - это деревья с специальный листовой узел, известный как нижний узел, который привязан к слову. В TAG есть два типа основных деревьев: исходные деревья (часто представляемые как 'α {\ displaystyle \ alpha}\ alpha ') и вспомогательные деревья ('β {\ displaystyle \ beta}\ beta '). Исходные деревья представляют собой основные отношения валентности, а вспомогательные деревья допускают рекурсию. Вспомогательные деревья имеют корневой (верхний) узел и нижний узел, помеченные одним и тем же символом. Деривация начинается с начального дерева, комбинируемого посредством замены или присоединения. Подстановка заменяет пограничный узел другим деревом, верхний узел которого имеет ту же метку. Метка корня / основания вспомогательного дерева должна совпадать с меткой узла, к которому оно примыкает. Таким образом, присоединение может иметь эффект вставки вспомогательного дерева в центр другого дерева.

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

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

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

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

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

Эквивалентности

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

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

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

Примечания

Ссылки

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

  • Проект XTAG, в котором для обработки естественного языка используется TAG.
  • Учебное пособие по TAG
  • Документация SemConst Краткий обзор проблем синтаксиса и семантического интерфейса в рамках TAG.
  • Проект TuLiPa Архитектура лингвистического анализа Тюбингена (TuLiPA) - это мультиформализмная синтаксическая (и семантическая) среда синтаксического анализа, разработанная в основном для
  • The Metagrammar Toolkit, которая предоставляет несколько инструментов для редактирования и компиляции в теги. Он также включает французские метаграммы широкого охвата.
  • LLP2 Парсер, который обеспечивает простую в использовании графическую среду (страница на французском языке)
Последняя правка сделана 2021-06-11 10:40:39
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте