Дерево разбора

Дерево разбора в SAAB

Дерево разбора или дерево разбора (также известное как дерево вывода или конкретное синтаксическое дерево ) — это упорядоченное корневое дерево , которое представляет синтаксическую структуру строки в соответствии с некоторой контекстно-свободной грамматикой . Сам термин «дерево разбора» используется главным образом в компьютерной лингвистике ; термин «синтаксическое дерево» в теоретическом синтаксисе более распространен .

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

Деревья синтаксического анализа обычно строятся на основе либо отношения избирательного округа грамматик округа ( грамматики фразовой структуры ), либо отношения зависимости грамматик зависимостей . Деревья разбора могут быть созданы для предложений на естественных языках (см. «Обработка естественного языка» ), а также во время обработки компьютерных языков, таких как языки программирования .

Родственной концепцией является фразовый маркер или P-маркер , используемый в трансформационной генеративной грамматике . Маркер фразы — это лингвистическое выражение, отмеченное в соответствии с его фразовой структурой. Это может быть представлено в виде дерева или выражения в квадратных скобках. Маркеры фраз генерируются путем применения правил структуры фраз и сами подлежат дальнейшим правилам трансформации. Набор возможных деревьев разбора синтаксически неоднозначного предложения называется «лесом разбора».

Номенклатура

Простое дерево разбора

Дерево разбора состоит из узлов и ветвей. На рисунке дерево разбора представляет собой всю структуру, начиная с S и заканчивая каждым из листовых узлов (Джон, мяч, хит). В дереве синтаксического анализа каждый узел является корневым узлом, узлом ветвления или листовым узлом. В приведенном выше примере S — корневой узел, NP и VP — узлы ветвления, а John, ball, the и hit — все листовые узлы.

Узлы также можно называть родительскими узлами и дочерними узлами. узел Родительский — это узел, под которым есть хотя бы еще один узел, связанный ветвью. В этом примере S является родительским элементом как NP, так и VP. Дочерним узлом является узел, над которым имеется хотя бы один узел, с которым он связан ветвью дерева. Опять же, из нашего примера, hit является дочерним узлом V.

— Нетерминальная функция это функция (узел), которая является либо корнем, либо ветвью этого дерева, тогда как терминальная функция — это функция (узел) в дереве разбора, которое является листом.

Для бинарных деревьев (где каждый родительский узел имеет два непосредственных дочерних узла) количество возможные деревья разбора предложения из n слов задаются каталонским числом $C_{n}$.

Деревья разбора на основе округов

Деревья разбора грамматик округов на основе округов ( грамматики фразовой структуры ) различают терминальные и нетерминальные узлы. Внутренние узлы помечены нетерминальными категориями грамматики, а листовые узлы помечены терминальными категориями. На изображении ниже представлено дерево разбора на основе округов; он показывает синтаксическую структуру английского предложения John hit the ball :

Дерево разбора — это вся структура, начиная с S и заканчивая каждым из листовых узлов ( John , hit , the , ball ). В дереве используются следующие сокращения:

• S — предложение , структура верхнего уровня в этом примере.

• NP для именной группы . Первый (крайний левый) NP, единственное существительное «Джон», служит подлежащим в предложении. Второе – объект предложения.

• ВП для глагольной фразы , которая служит сказуемым

• V для глагола . В данном случае это переходный глагол hit .

• D — определитель , в данном случае определенный артикль «the».

• N для существительного

Каждый узел в дереве является корневым узлом, узлом ветвления или листовым узлом. Корневой узел — это узел, не имеющий над собой ветвей. В предложении всегда есть только один корневой узел. Узел ветвления — это родительский узел, который соединяется с двумя или более дочерними узлами. Однако листовой узел — это конечный узел, который не доминирует над другими узлами дерева. S — корневой узел, NP и VP — узлы ветвления, а Джон (N), хит (V), мяч (D) и (N ) — все это конечные узлы. Листья являются лексическими лексемами предложения. Родительский узел — это узел, под которым есть хотя бы еще один узел, связанный ветвью. В этом примере S является родительским элементом как N, так и VP. Дочерний узел — это узел, непосредственно над которым имеется хотя бы один узел, с которым он связан ветвью дерева. В примере hit термины мать и дочь является дочерним узлом V. Для этих отношений также иногда используются .

Деревья разбора на основе зависимостей

на основе зависимостей Деревья разбора грамматик зависимостей рассматривают все узлы как терминальные, что означает, что они не признают различия между терминальными и нетерминальными категориями. В среднем они проще, чем деревья синтаксического анализа на основе округов, поскольку содержат меньше узлов. Дерево анализа на основе зависимостей для приведенного выше примера предложения выглядит следующим образом:

В этом дереве синтаксического анализа отсутствуют фразовые категории (S, VP и NP), которые можно увидеть в приведенном выше аналоге на основе округов. Как и в случае с деревом на основе округов, составная признается структура. Любое полное поддерево дерева является его составной частью. Таким образом, это дерево синтаксического анализа на основе зависимостей признает существительное-субъект Джон и существительное-объект словосочетание мяч в качестве составляющих, как это делает дерево синтаксического анализа на основе округов.

Различие между избирателями и зависимостями имеет далеко идущие последствия. Вопрос о том, необходима ли или полезна дополнительная синтаксическая структура, связанная с деревьями синтаксического анализа на основе округов, является предметом споров.

Фразовые маркеры

Фразовые маркеры, или P-маркеры, были введены в раннюю трансформационную порождающую грамматику , разработанную Ноамом Хомским и другими. Маркер фразы, представляющий глубокую структуру предложения, создается путем применения правил структуры фразы . Затем это приложение может подвергнуться дальнейшим преобразованиям.

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

$[_{S}\ [_{\mathit {N}}\ {\text{John}}]\ [_{\mathit {VP}}\ [_{V}\ {\text{hit}}]\ [_{\mathit {NP}}\ [_{\mathit {D}}\ {\text{the}}]\ [_{N}\ {\text{ball}}]]]]$

Как и в случае с деревьями, точная конструкция таких выражений и количество отображаемых деталей могут зависеть от применяемой теории и от моментов, которые автор запроса желает проиллюстрировать.

См. также

• Абстрактное синтаксическое дерево
• Составляющая (лингвистика)
• Грамматика зависимостей
• Компьютерная лингвистика
• Парсинг (синтаксический анализ)
• Грамматика фразовой структуры
• Схема предложения
• Терминальные и нетерминальные символы

Ссылки

• Агель, В. , Людвиг Эйхингер, Ханс-Вернер Эромс, Питер Хеллвиг, Ханс Херингер и Хенниг Лобин (ред.) 2003/6. Зависимость и валентность: Международный справочник современных исследований . Берлин: Вальтер де Грюйтер.
• Карни, А. 2013. Синтаксис: генеративное введение , 3-е издание. Молден, Массачусетс: Уайли-Блэквелл.
• Чизуэлл, Ян и Уилфрид Ходжес 2007. Математическая логика. Оксфорд: Издательство Оксфордского университета.
• Ахо А.В., Сетхи Р. и Ульман Дж.Д. 1986. Составители: принципы, методы и инструменты . Ридинг, Массачусетс: Аддисон-Уэсли.

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

• Редактор синтаксического дерева
• Конструктор лингвистического дерева
• phpSyntaxTree — онлайн-сайт рисования дерева синтаксического анализа.
• phpSyntaxTree (Unicode) — сайт рисования дерева онлайн-анализа (улучшенная версия с поддержкой Unicode)
• rSyntaxTree Расширенная версия phpSyntaxTree в Ruby с поддержкой Unicode и векторизованной графикой.
• Qtree — LaTeX для рисования деревьев разбора. пакет
• Программное обеспечение для рисования синтаксического дерева TreeForm
• Визуальное введение в деревья разбора. Введение и преобразование.
• OpenCourseOnline (Кристофер Мэннинг) Введение в анализ зависимостей
• Составные части Penn Treebank II Tags