Как я могу манипулировать деревьями синтаксического анализа?

Ответ 1

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

Вот пример процедурного соответствия с использованием Common Lisp. В Lisp есть шаблоны, которые работают над структурами списков, которые могут быть использованы вместо этого. Использование сопоставления списков упростит пример (см. Мой другой ответ для примера с использованием сопоставления шаблонов).

Код:

(defun node-children (node)
  (rest node))

(defun node-name (node)
  (second node))

(defun node-type (node)
  (first node))


(defun treemap (tree matcher transformer)
  (cond ((null tree) nil)
        ((consp tree)
         (if (funcall matcher tree)
             (funcall transformer tree)
           (cons (node-type tree)
                 (mapcar (lambda (child)
                           (treemap child matcher transformer))
                         (node-children tree)))))
        (t tree))))

Пример:

(defvar *tree*
  '(ROOT
    (S
     (NP
      (NP (NNP Bank))
      (PP (IN of)
          (NP (NNP America))))
     (VP (VBD used)
         (S
          (VP (TO to)
              (VP (VB be)
                  (VP (VBN called)
                      (NP
                       (NP (NNP Bank))
                       (PP (IN of)
                           (NP (NNP Italy))))))))))))



(defun example ()
  (pprint
   (treemap *tree*
            (lambda (node)
              (and (= (length (node-children node)) 2)
                   (eq (node-type (first (node-children node))) 'np)
                   (some (lambda (node)
                           (eq (node-name node) 'bank))
                         (children (first (node-children node))))
                   (eq (first (second (node-children node))) 'pp)))
            (lambda (node)
              (list (node-type node)
                    (append (first (node-children node))
                            (node-children (second (node-children node)))))))))

Запуск примера:

CL-USER 75 > (example)

(ROOT
 (S
  (NP
   (NP (NNP BANK) (IN OF) (NP (NNP AMERICA))))
  (VP
   (VBD USED)
   (S
    (VP
     (TO TO)
     (VP
      (VB BE)
      (VP
       (VBN CALLED)
       (NP
        (NP
         (NNP BANK)
         (IN OF)
         (NP (NNP ITALY)))))))))))

Ответ 2

Красота находится в глазах смотрящего. Но вы никогда не говорите , как код Tregex или Tsuggeon - это беспорядок. Это похоже на то, что вы не можете заниматься Java или большей абстракцией, и поэтому вы ищете что-то конкретное, написанное на Python.

Там нет ничего плохого в том, что функции сопоставления и преобразования дерева вручную записываются. Действительно, мы это делали все время. Но после первых двух сотен казалось, что должен быть лучший способ, и поэтому мы перешли к использованию доменных языков Tregex и Tsuggeon. Это обычно рассматривается как похвальный стиль программирования. См. Wikipedia. Они хорошо обозначенные языки с точной спецификацией синтаксиса и т.д. Вот ваш пример, используя их.

Tree t = Tree.valueOf("(ROOT (S (NP (NP (NNP Bank)) (PP (IN of) (NP (NNP America)))) (VP (VBD used) (S (VP (TO to) (VP (VB be) (VP (VBN called) (NP (NP (NNP Bank)) (PP (IN of) (NP (NNP Italy)))))))))))");
TregexPattern pat = TregexPattern.compile("NP <1 (NP << Bank) <2 PP=remove");
TsurgeonPattern surgery = Tsurgeon.parseOperation("excise remove remove");
Tsurgeon.processPattern(pat, surgery, t).pennPrint();

Обратите внимание, что код Java на самом деле короче кода Lisp, именно из-за использования языка, специфичного для домена. Трудно понять, как это может быть проще: укажите шаблон, укажите операцию, примените.

Но если вы предпочитаете использовать методы ручной записи, которые соответствуют шаблонам на деревьях и заменяют их на другие деревья в Python, тогда вам больше всего нравится уходить и делать это.

Ответ 3

Вот вторая версия в Common Lisp. На этот раз я использую шаблонный шаблон.

Я использую функцию, которая сопоставляет шаблон с данными Lisp. PMATCH: MATCH - расширенная версия шаблона, найденного в книге Winston/Horn, Lisp, 3rd Edition. Доступны аналогичные функции соответствия шаблону.

Данные приведены в моем другом ответе.

Функция отображения дерева изменяется для использования шаблона. Функция PMATCH: MATCH возвращает T или список привязок, если совпадение выполнено успешно. Он возвращает NIL, если совпадение не выполняется. PMATCH: INSTANTIATE-PATTERN принимает шаблон и набор привязок. Он возвращает новую структуру списка, где переменные шаблона заменяются привязками.

(defun treemapp (tree pattern transformer)
  (cond ((null tree) nil)
        ((consp tree)
         (let ((bindings (pmatch:match pattern tree)))
           (if bindings
               (pmatch:instantiate-pattern transformer bindings)
             (cons (node-type tree)
                   (mapcar (lambda (child)
                             (treemapp child pattern transformer))
                           (node-children tree))))))
        (t tree)))

пример теперь использует шаблоны.

Шаблон представляет собой структуру списка. Символ #? соответствует одному элементу и создает привязку для символа. Символ # $соответствует списку элементов и создает привязку для символа.

Трансформатор - это шаблон, который будет создан с привязками.

(defun example1 ()
  (pprint (treemapp *tree*
                    '(NP (NP (#?type bank)) (PP #$children))
                    '(NP (NP (#?type bank) #$children)))))

Запуск этого кода возвращает тот же результат, что и в моем другом ответе.