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

• Определение и история древовидных грамматик

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

• Описание и правила

  • Правила TAG представляют собой деревья с особым нижним узлом, связанным со словом. 
  • Существуют два типа базовых деревьев: исходные и вспомогательные. 
  • Исходные деревья описывают основные валентности, а вспомогательные деревья допускают рекурсию. 
  • Вывод начинается с исходного дерева и может включать замену или присоединение. 

• Сложность и область применения

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

• Эквивалентности и лексикализованные грамматики

  • Линейно-индексированные, комбинаторно-категориальные, древовидные и головные грамматики слабо эквивалентны. 
  • Лексикализованные древовидные грамматики (LTAG) связывают каждое дерево с лексическим элементом. 

• Дополнительные ресурсы

  • Проект XTAG использует TAG для обработки естественного языка. 
  • Учебное пособие по TAG доступно. 
  • Документация SemConst описывает проблемы синтаксиса и семантического интерфейса в рамках TAG. 
  • Проект TuLiPa предоставляет мультиформалистическую среду для анализа многокомпонентных древовидных грамматик. 
  • Инструментарий Metagrammar предоставляет инструменты для редактирования и компиляции метаграмм. 
  • LL2P2 — лексикализованный древовидный грамматический анализатор с графической средой.