Дерево синтаксического анализа - Parse tree

Разобрать дерево до SAAB.

А дерево синтаксического анализа или дерево разбора[1] или дерево происхождения или конкретное синтаксическое дерево упорядоченный, укорененный дерево что представляет собой синтаксический структура строка согласно некоторым контекстно-свободная грамматика. Период, термин дерево синтаксического анализа сам по себе используется в основном в компьютерная лингвистика; в теоретическом синтаксисе термин синтаксическое дерево встречается чаще.

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

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

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

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

Просто дерево синтаксического анализа.

А дерево синтаксического анализа состоит из узлов и ветвей.[4] На рисунке дерево синтаксического анализа - это вся структура, начиная с S и заканчивая каждым из листовых узлов (John, ball, the, hit). В дереве синтаксического анализа каждый узел является либо корень узел, а ветвь узел, или лист узел. В приведенном выше примере S - корневой узел, NP и VP - узлы ветвления, а John, ball, the и hit - все листовые узлы.

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

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

Деревья синтаксического анализа на основе избирательных округов

Деревья разбора грамматик избирательных округов на основе избирательных округов (= грамматики фразовой структуры ) различают терминальные и нетерминальные узлы. В внутренние узлы помечены нетерминальный категории грамматики, а листовые узлы помечены Терминал категории. Изображение ниже представляет дерево синтаксического анализа на основе избирательных округов; он показывает синтаксическую структуру английский предложение Джон ударил по мячу:

Дерево синтаксического анализа PSG

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

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

Деревья синтаксического анализа на основе зависимостей

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

Дерево синтаксического анализа DG

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

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

Маркеры фраз

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

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

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

Смотрите также

Заметки

  1. ^ См. Chiswell and Hodges 2007: 34.
  2. ^ Ноам Хомский (26 декабря 2014 г.). Аспекты теории синтаксиса. MIT Press. ISBN  978-0-262-52740-8.
  3. ^ Билло, Сильви и Бернар Лэнг. "Структура общих лесов в неоднозначном разборе."
  4. ^ "Пакет parsetree для рисования деревьев в LaTeX". www1.essex.ac.uk.
  5. ^ См. Карни (2013: 118 и далее) для введения в основные концепции синтаксических деревьев (например, корневой узел, конечный узел, нетерминальный узел и т. Д.).
  6. ^ См. Aho et al. 1986 г.
  7. ^ См., Например, Ágel et al. 2003/2006.

использованная литература

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