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-х детей, найти все узлы, чьи данные начинаются с «а» и заменить его «Ъ», если поддеревьям по крайней мере 2 других брата и т. д. должны поддерживаться.

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

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

Answer 1

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

Answer 2

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

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

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

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

Answer 3

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

Answer 4

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

Дерево переписывания с узорами также делается с парсер инструментарии, такие как ANTLR

генерации кода с нижней до дерева переписывания, Google боров или BURG.

Answer 5

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

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

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

Answer 6

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

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

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

Answer 7

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