библиотека для преобразования дерева узлов

Question

Я хотел бы иметь возможность выразить общее преобразование одного дерева в другое без написания связки повторяющегося кода спагетти. Есть ли библиотеки, чтобы помочь с этой проблемой? Моим целевым языком является Python, но я буду смотреть на другие языки, если возможно перенести на Python.

Пример: я хотел бы преобразовать это дерево узлов: (прошу прощения за S-выражения )

(A (B) (C) (D))

В этот:

(C (B) (D))

Пока родитель - это А, а второй предок - С, независимо от контекста (может быть больше родителей или предков). Я хотел бы выразить это преобразование простым, кратким и многократно используемым способом. Конечно, этот пример очень специфичен. Пожалуйста, попробуйте рассмотреть общий случай.

Редактировать: RefactoringNG - это то, что я ищу, хотя и вводит совершенно новую грамматику для решения проблемы, которую я хотел бы избежать. Я все еще ищу больше и / или лучших примеров.

---

Справочная информация:

Я могу конвертировать файлы python и cheetah (не спрашивайте!) В представления дерева маркеров и, в свою очередь, конвертировать их в lxml деревья. Затем я планирую реорганизовать дерево и записать результаты, чтобы внедрить автоматизированный рефакторинг. XSLT, кажется, является стандартным инструментом для переписывания XML, но синтаксис ужасен (на мой взгляд, очевидно), и никто в нашем магазине этого не поймет.

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

Answer 1

Давайте попробуем это в коде Python.Я использовал строки для листьев, но это будет работать с любыми объектами.

def lift_middle_child(in_tree):
    (A, (B,), (C,), (D,)) = in_tree

    return (C, (B,), (D,))

print lift_middle_child(('A', ('B',), ('C',), ('D',))) # could use lists too

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

Поскольку вы использовали s-выражения, я предполагаю, что вам удобно представлять деревья в виде вложенных списков (илиэквивалентно - если я не ошибаюсь, lxml узлы итеративны таким образом).Очевидно, этот пример опирается на известную структуру ввода, но ваш вопрос подразумевает это.Вы можете написать более гибкие функции и по-прежнему составлять их, если у них есть этот унифицированный интерфейс.

Вот код в действии: http://ideone.com/02Uv0i

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

def compose2(a,b): # might want to get this from the functional library
    return lambda *x: a(b(*x))

def compose(*funcs): #compose(a,b,c) = a(b(c(x))) - you might want to reverse that
    return reduce(compose2,funcs)

def reverse_children(in_tree):
    return in_tree[0:1] + in_tree[1:][::-1] # slightly cryptic, but works for anything subscriptable

lift_and_reverse = compose(reverse_children,lift_middle_child) # right most function applied first - if you find this confusing, reverse order in compose function.

print lift_and_reverse(('A', ('B',), ('C',), ('D',)))

Answer 2

Что вам действительно нужно? IMHO - это система преобразования программ , которая позволяет вам анализировать и преобразовывать код, используя шаблоны, выраженные в поверхностном синтаксисе исходного кода (и даже вцелевой язык), чтобы выразить переписанные тексты напрямую.

Вы обнаружите, что даже если вы сможете получить XML-представление дерева Python, усилия по написанию преобразования XSLT / XPath будут больше, чем вы ожидаете;деревья, представляющие реальный код, сложнее, чем вы ожидаете, XSLT - не такая удобная нотация, и она не может напрямую выражать общие условия для деревьев, которые вы хотите проверить (например, два поддерева одинаковы).Последнее осложнение с XML: предположим, что он был преобразован.Как вы восстанавливаете синтаксис исходного кода, с которого пришли?Вам нужен какой-то симпатичный принтер.

Общая проблема, независимо от того, как представлен код, состоит в том, что без информации о областях и типах (где вы можете ее получить) написать правильные преобразования довольно сложно.В конце концов, если вы собираетесь преобразовать python в язык, который использует разные операторы для строки concat и арифметики (в отличие от Java, который использует «+» для обоих), вам необходимо решить, какой оператор генерировать.Так что вам нужна информация о типе, чтобы решить.В Python, возможно, нет типов, но на практике большинство выражений включают в себя переменные, которые имеют только один тип в течение всей их жизни.Поэтому вам также понадобится анализ потока для вычисления типов.

Наш набор инструментов для реинжиниринга программного обеспечения DMS обладает всеми этими возможностями (синтаксический анализ, анализ потока, сопоставление / перезапись шаблонов, prettyprint) и Надежные парсеры для многих языков, включая Python.(Хотя он имеет возможность анализа потока, созданного для C, COBOL, Java, он не создан для Python. Но затем вы сказали, что хотите выполнить преобразование независимо от контекста).

Чтобы выразить свое переписывание в DMSв синтаксисе Python, близком к вашему примеру (что не является Python?)

  domain Python;

  rule revise_arguments(f:IDENTIFIER,A:expression,B:expression,
                                     C:expression,D:expression):primary->primary
  =  " \f(\A,(\B),(\C),(\D)) "
  -> " \f(\C,(\B),(\D)) ";

Обозначение выше - это язык перезаписи правил DMS (RSL).«...» - это мета-кавычки, которые отделяют синтаксис Python (внутри этих кавычек DMS знает, что это Python из-за объявления нотации домена) от языка DMS RSL.\ N внутри мета-кавычки относится к заполнителям синтаксической переменной именованного нетерминального типа, определенного в списке параметров правила.Да, (...) внутри мета-кавычек есть Python () ... они существуют в синтаксических деревьях, что касается DMS, потому что они, как и остальная часть языка, являются просто синтаксисом.

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

С этим правилом DMS может анализировать Python (используя его синтаксический анализатор Python), например,

        foobar(2+3,(x-y),(p),(baz()))

построить AST, сопоставить правило (анализируемое с AST) с этим AST, переписать его в другоеAST соответствует:

        foobar(p,(x-y),(baz()))

, а затем довольно распечатывает синтаксис поверхности (действительный) Python обратно.

Если вы хотите, чтобы ваш пример был преобразованием кода LISP, вам понадобитсяГрамматика LISP для DMS (не сложно построить, но у нас нет особых требований к этому), и написать соответствующий синтаксис поверхности:

 domain Lisp;

  rule revise_form(A:form,B:form, C:form, D:form):form->form
  =  " (\A,(\B),(\C),(\D)) "
  -> " (\C,(\B),(\D)) ";

Вы можете почувствовать это лучше, посмотрев на Алгебра какдомен DMS .

Если ваша цель состоит в том, чтобы реализовать все это в Python ... У меня нет особой помощи.DMS - довольно большая система, и для ее репликации потребуется много усилий.