Грамматика примыкания к дереву
Грамматика, примыкающая к дереву ( TAG ) — это формализм грамматики , определенный Аравиндом Джоши . Примыкающие к дереву грамматики чем-то похожи на контекстно-свободные грамматики , но элементарной единицей перезаписи является дерево, а не символ. В то время как в контекстно-свободных грамматиках есть правила перезаписи символов как строк других символов, в грамматиках, примыкающих к дереву, есть правила перезаписи узлов деревьев как других деревьев (см. дерево (теория графов) и дерево (структура данных) ).
TAG возникла в результате исследований Джоши и его учеников семейства грамматик присоединения (AG), [1] «строковой грамматики» Зеллига Харриса . [2] АГ обрабатывают экзоцентрические свойства языка естественным и эффективным способом, но не имеют хорошей характеристики эндоцентрических конструкций; обратное верно для грамматик перезаписи или грамматики фразовой структуры (PSG). В 1969 году Джоши представил семейство грамматик, использующих эту взаимодополняемость путем смешивания двух типов правил. Достаточно нескольких очень простых правил перезаписи, чтобы сгенерировать словарь строк для правил присоединения. Это семейство отличается отХомского-Шютценбергера, но пересекает ее интересными и лингвистически значимыми способами. [3] Центральные строки и дополнительные строки также могут быть сгенерированы с помощью грамматики зависимостей , полностью избегая ограничений систем перезаписи. [4] [5]
Правила в TAG — это деревья со специальным конечным узлом, известным как нижний узел , который привязан к слову. В TAG есть два типа основных деревьев: начальные деревья (часто обозначаемые как ' ') и вспомогательные деревья (' '). Исходные деревья представляют основные отношения валентности, а вспомогательные деревья допускают рекурсию. [6] Вспомогательные деревья имеют корневой (верхний) узел и нижний узел, помеченные одним и тем же символом. Вывод начинается с начального дерева, объединяясь либо заменой , либо присоединением .. Подстановка заменяет граничный узел другим деревом, верхний узел которого имеет ту же метку. Метка корня/подошвы вспомогательного дерева должна совпадать с меткой узла, к которому оно примыкает. Таким образом, присоединение может привести к вставке вспомогательного дерева в центр другого дерева. [4]
Другие варианты TAG допускают многокомпонентные деревья , деревья с несколькими опорными узлами и другие расширения.
Примыкающие к дереву грамматики являются более мощными (с точки зрения слабой порождающей способности ), чем контекстно-свободные грамматики , но менее мощными, чем линейные контекстно-свободные системы перезаписи , [7] , индексированные [примечание 1] или контекстно-зависимые грамматики.
TAG может описывать язык квадратов (в котором повторяется некоторая произвольная строка) и язык . Этот тип обработки может быть представлен встроенным автоматом выталкивания вниз . Языки с кубами (т. е. тройными строками) или с более чем четырьмя отдельными строками символов одинаковой длины не могут быть сгенерированы грамматиками с примыканием к дереву.
