Regex for tree structures?

Question

Are there regular expression equivalents for finding and modifying tree structures? Vibrant mini-languages ​​(like perl regex) are what I'm looking for.

Here is an example that can clarify what I'm looking for.

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

The operation that would be possible on the aforementioned tree is “moving the subtree in node 2.1 to the subtree in node 1.” The result of the operation may look something like this.

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

Search and replace operations, such as searching for all nodes with 2 children, find all nodes whose data begin with “a” and replace them with “b” if the subtrees have at least 2 other brothers, etc., should be supported.

For strings where the only dimension is along the entire length of the string, we can perform many of the above operations (or their 1D equivalents) using regular expressions. I wonder if equivalents exist for trees. (instead of a single regular expression, you may need to write a set of conversion rules, but this is normal).

I would like to know if there is some simple mini-language (not a regular expression per.se, but something accessible, like regex through libraries, etc.). to perform these operations? Preferably, as a python library.

Answer 1

TSurgeon and Tregex from Stanford can do this. You can download the library from http://nlp.stanford.edu/software/tregex.shtml

Answer 2

I don’t know the universal langugae that can do this, but it seems to me that you are looking for something like XPath .

Answer 3

There is TXL for rewriting a tree based on patterns.

Tree editing using templates is also performed using parser toolkits such as ANTLR

Generate code by recreating the tree up, google BURS or BURG.

Answer 4

Navigating through the binary search tree requires a state (in which node am I?) And comparisons (is this value less or greater than this?), Something that cannot be done by a state machine.

Of course, you can search for a node with a given value, but how could you, for example, delete a node that is not a leaf if you do not know its parent?

And even if you know the parent through the information provided by node, how do you determine the minimum of the left subtree, delete it and put it in node?

I think you ask the FSA too much.

Answer 5

This article provides some tasty tips on Perl recursive regular expressions, but to be honest, it's rare to see a tree structure that fit that way.

Typically, one could write a machine-style parser in a state computer that could use regular expressions to parse each particular node in the tree.

Expat is probably a good example to view.

Answer 6

Pattern matching provided by languages ​​like Scala, F #, Erlang, and Haskell (I'm sure there are more) is for short-term management of data structures such as trees, esp when used with recursion.

here is a very high level of representation of what pattren can be matched in Scala. The examples shown really are not fair.

Wikipedia has several links to pattern matching. Here and here .

Answer 7

I am somewhat surprised that XSLT did not find the answer. Of course, I don’t think this is a particularly elegant language, and most existing solutions tend to prefer procedural approaches rather than pattern matching, and it got a mighty bad reputation from blind use just because XML is applied to XML, but otherwise it corresponds to the account. It is a pity that his canonical representation is so verbose, though ...