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

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

Вот пример процедурного сопоставления с использованием Common 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)))))))))))

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

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

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, то вы можете пойти и сделать это.

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

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

Данные такие же, как в моем другом ответе.

Функция сопоставления дерева изменена, чтобы использовать сопоставление с образцом. Функция 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)))

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

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

Преобразователь — это шаблон, который будет создан с помощью привязок.

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

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