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