Разбор дерева
Дерево синтаксического анализа или дерево синтаксического анализа [1] , или дерево вывода, или конкретное синтаксическое дерево — это упорядоченное корневое дерево , представляющее синтаксическую структуру строки в соответствии с некоторой контекстно-свободной грамматикой . Сам термин « дерево синтаксического анализа » используется в первую очередь в компьютерной лингвистике ; в теоретическом синтаксисе более распространен термин синтаксическое дерево .
Конкретные синтаксические деревья отражают синтаксис входного языка, что отличает их от абстрактных синтаксических деревьев, используемых в компьютерном программировании. В отличие от диаграмм предложений Рида-Келлогга , используемых для обучения грамматике, деревья синтаксического анализа не используют различные формы символов для разных типов составляющих .
Деревья синтаксического анализа обычно строятся либо на основе отношения составляющих грамматик составляющих (грамматик структуры фразы ), либо на основе отношения зависимости грамматик зависимостей . Деревья синтаксического анализа могут быть созданы для предложений на естественных языках (см. Обработка естественного языка ), а также во время обработки компьютерных языков, таких как языки программирования .
Родственным понятием является маркер фразы или P-маркер , используемый в трансформационной порождающей грамматике . Маркер фразы - это языковое выражение, отмеченное в соответствии с его структурой фразы. Это может быть представлено в виде дерева или в виде выражения в квадратных скобках. Фразовые маркеры генерируются путем применения правил структуры фраз и сами подчиняются дальнейшим правилам преобразования. [2] Набор возможных деревьев синтаксического анализа для синтаксически неоднозначного предложения называется «лесом синтаксического анализа». [3]
Дерево синтаксического анализа состоит из узлов и ветвей. [4] На рисунке дерево синтаксического анализа — это вся структура, начинающаяся с S и заканчивающаяся каждым из листовых узлов (John, ball, the, hit). В дереве синтаксического анализа каждый узел является корневым узлом, узлом ветви или конечным узлом. В приведенном выше примере S — это корневой узел, NP и VP — узлы-ветви, а John, ball, the и hit — конечные узлы.
Узлы также могут называться родительскими узлами и дочерними узлами. Родительский узел — это тот, у которого есть хотя бы один другой узел, связанный ветвью под ним. В примере S является родителем как NP, так и VP. Дочерний узел — это тот, у которого есть по крайней мере один узел непосредственно над ним, с которым он связан ветвью дерева. Опять же из нашего примера, хит является дочерним узлом V.
