Regex для древовидных структур?

Question

Существуют ли регулярные выражения для поиска и изменения древовидных структур? Я ищу краткие мини-языки (например, Perl Regex).

Вот пример, который может прояснить то, что я ищу.

<root>
  <node name="1">
    subtrees ....
  </node>
  <node name="2">
    <node name="2.1">
     data
    </node>
    other subtrees...
  </node>
</root>

Операция, которая была бы возможна в вышеприведенном дереве, это «переместить поддерево в узле 2.1 в поддерево в узле 1. "Результат операции может выглядеть примерно так ...

<root>
  <node name="1">
    subtrees ....
    <node name="2.1">
     data
    </node>
  </node>
  <node name="2">
    other subtrees...
  </node>
</root>

Операции поиска и замены, такие как поиск всех узлов, имеющих не менее 2 дочерних элементов, поиск всех узлов, данные которых начинаются с «a», и замена их на «b», если поддеревья имеют как минимум 2 других родных элемента и т. Д. И т. Д.

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

Я хотел бы знать, есть ли какой-нибудь простой мини-язык (не regex per.se, а такой же доступный, как regex через библиотеки и т. Д.). выполнить эти операции? Предпочтительно, как библиотека питона.

Answer 1

TSurgeon и Tregex из Стэнфорда способны сделать это. Вы можете скачать библиотеку с http://nlp.stanford.edu/software/tregex.shtml

Answer 2

Я не знаю языков общего назначения, которые могут это сделать, но мне кажется, что вы ищете что-то вроде XPath .

Answer 3

Существует TXL для переписывания дерева на основе шаблона.

Переписывание дерева с использованием шаблонов также выполняется с помощью таких инструментов, как ANTLR

Генерация кода с перезаписью дерева снизу вверх, Google BURS или BURG.

Answer 4

Я несколько удивлен, что XSLT не пришел в качестве ответа. Конечно, я не думаю, что это особенно элегантный язык, и большинство существующих решений склонны предпочитать процедурные подходы, а не сопоставление с образцом, и он получил очень плохую репутацию от слепого применения только потому, что это XML, применяемый к XML - но в остальном это отвечает всем требованиям. Жаль, что его каноническое представление настолько многословно, хотя ...

Answer 5

Pattern Matching, предоставляемый такими языками, как Scala, F #, Erlang и Haskell (я уверен, что есть и другие), предназначен для краткого манипулирования структурами данных, такими как деревья, особенно при использовании рекурсии

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

В Википедии также есть пара ссылок на сопоставление с образцом. Здесь и здесь .

Answer 6

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

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

Expat , вероятно, является хорошим примером для рассмотрения.

Answer 7

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

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

И даже если вы знаете родителя по информации, предоставленной узлом, как определить минимум левого поддерева, удалить его и поместить в узел?

Я думаю, что вы слишком много просите FSA.