Дерево разбора или дерево синтаксического анализа [1] , или дерево вывода , или конкретное синтаксическое дерево — это упорядоченное корневое дерево , которое представляет синтаксическую структуру строки в соответствии с некоторой контекстно-свободной грамматикой . Сам термин «дерево разбора» используется главным образом в компьютерной лингвистике ; в теоретическом синтаксисе более распространен термин « синтаксическое дерево» .
Конкретные синтаксические деревья отражают синтаксис языка ввода, что отличает их от абстрактных синтаксических деревьев, используемых в компьютерном программировании. В отличие от диаграмм предложений Рида-Келлога, используемых для обучения грамматике, деревья синтаксического анализа не используют отдельные формы символов для разных типов составляющих .
Деревья синтаксического анализа обычно строятся на основе либо отношения избирательного округа грамматик округа ( грамматики фразовой структуры ), либо отношения зависимости грамматик зависимостей . Деревья разбора могут быть созданы для предложений на естественных языках (см. «Обработка естественного языка »), а также во время обработки компьютерных языков, таких как языки программирования .
Родственной концепцией является фразовый маркер или P-маркер , используемый в трансформационной генеративной грамматике . Маркер фразы — это лингвистическое выражение, отмеченное в соответствии с его фразовой структурой. Это может быть представлено в виде дерева или выражения в квадратных скобках. Маркеры фраз генерируются путем применения правил структуры фраз и сами подлежат дальнейшим правилам трансформации. [2] Набор возможных деревьев разбора синтаксически неоднозначного предложения называется «лесом разбора». [3]
Дерево разбора состоит из узлов и ветвей. [4] На рисунке дерево разбора представляет собой всю структуру, начиная с S и заканчивая каждым из листовых узлов (Джон, мяч, хит). В дереве синтаксического анализа каждый узел является корневым узлом, узлом ветвления или листовым узлом. В приведенном выше примере S — корневой узел, NP и VP — узлы ветвления, а John, ball, the и hit — все конечные узлы.
Узлы также можно называть родительскими узлами и дочерними узлами. Родительский узел — это узел, под которым есть хотя бы еще один узел , связанный ветвью. В этом примере S является родительским элементом как NP, так и VP. Дочерним узлом является узел , над которым имеется хотя бы один узел, с которым он связан ветвью дерева. Опять же, из нашего примера, hit является дочерним узлом V.
Нетерминальная функция — это функция (узел), которая является либо корнем, либо ветвью этого дерева, тогда как терминальная функция — это функция (узел) в дереве разбора, которое является листом.
Для бинарных деревьев (где каждый родительский узел имеет два непосредственных дочерних узла) количество возможных деревьев разбора предложения из n слов определяется каталонским числом .
Деревья разбора грамматик округов на основе округов ( грамматики фразовой структуры ) различают терминальные и нетерминальные узлы. Внутренние узлы помечены нетерминальными категориями грамматики, а листовые узлы помечены терминальными категориями. На изображении ниже представлено дерево разбора на основе округов; он показывает синтаксическую структуру английского предложения John hit the ball :
Дерево разбора — это вся структура, начиная с S и заканчивая каждым из листовых узлов ( John , hit , the , ball ). В дереве используются следующие сокращения:
Каждый узел в дереве является корневым узлом, узлом ветвления или листовым узлом. [5] Корневой узел — это узел, не имеющий ветвей над ним. В предложении всегда есть только один корневой узел. Узел ветвления — это родительский узел, который соединяется с двумя или более дочерними узлами. Однако листовой узел — это конечный узел, который не доминирует над другими узлами дерева. S — корневой узел, NP и VP — узлы ветвления, а Джон (N), хит (V), ( D ) и мяч (N) — все это конечные узлы. Листья являются лексическими лексемами предложения. Родительский узел — это узел, под которым есть хотя бы еще один узел, связанный ветвью. В этом примере S является родительским элементом как N, так и VP. Дочерний узел — это узел, над которым имеется хотя бы один узел, с которым он связан ветвью дерева. В примере hit является дочерним узлом V. Для этих отношений также иногда используются термины мать и дочь .
Деревья анализа грамматик зависимостей на основе зависимостей [6] рассматривают все узлы как терминальные, что означает, что они не признают различия между терминальными и нетерминальными категориями. В среднем они проще, чем деревья синтаксического анализа на основе округов, поскольку содержат меньше узлов. Дерево анализа на основе зависимостей для приведенного выше примера предложения выглядит следующим образом:
В этом дереве синтаксического анализа отсутствуют фразовые категории (S, VP и NP), которые можно увидеть в приведенном выше аналоге на основе округов. Как и в случае с деревом на основе округов, признается составная структура. Любое полное поддерево дерева является его составной частью. Таким образом, это дерево синтаксического анализа на основе зависимостей признает существительное-субъект Джон и существительное-объект словосочетание мяч в качестве составляющих, так же, как это делает дерево синтаксического анализа на основе округов.
Различие между избирателями и зависимостями имеет далеко идущие последствия. Вопрос о том, необходима ли или полезна дополнительная синтаксическая структура, связанная с деревьями синтаксического анализа на основе округов, является предметом споров.
Фразовые маркеры, или P-маркеры, были введены в раннюю трансформационную порождающую грамматику , разработанную Ноамом Хомским и другими. Маркер фразы, представляющий глубокую структуру предложения, создается путем применения правил структуры фразы . Затем это приложение может подвергнуться дальнейшим преобразованиям.
Маркеры фраз могут быть представлены в виде деревьев (как в приведенном выше разделе о деревьях синтаксического анализа на основе округов), но вместо этого часто задаются в форме «выражений в квадратных скобках», которые занимают меньше места в памяти. Например, выражение в квадратных скобках, соответствующее приведенному выше дереву на основе округов, может выглядеть примерно так:
Как и в случае с деревьями, точная конструкция таких выражений и количество отображаемых деталей могут зависеть от применяемой теории и от моментов, которые автор запроса желает проиллюстрировать.
![{\displaystyle [_{S}\ [_{\mathit {N}}\ {\text{Джон}}]\ [_{\mathit {VP}}\ [_{V}\ {\text{hit} }]\ [_{\mathit {NP}}\ [_{\mathit {D}}\ {\text{the}}]\ [_{N}\ {\text{ball}}]]]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/995d5d3a584be537cf98b07b8f03f44656fd826c)