Regex para estructuras de árboles?

Question

¿Hay equivalentes de expresiones regulares para buscar y modificar estructuras de árbol? Los mini-idiomas concisos (como perl regex) son lo que estoy buscando.

Aquí hay un ejemplo que podría aclarar lo que estoy buscando.

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

Una operación que sería posible en el árbol de arriba es "mover subárbol en el nodo 2.1 en el subárbol en el nodo 1." El resultado de la operación podría ser algo como ..

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

Buscar y reemplazar operaciones como encontrar todos los nodos con al menos 2 hijos, encontrar todos los nodos cuyos datos comienza con "a" y sustituirla por "b" si el los subárboles tienen al menos 2 otros hermanos, etc. deben ser compatibles.

Para las cadenas, donde la única dimensión se encuentra a lo largo de la cadena, podemos hacer muchas de las operaciones anteriores (o sus equivalentes 1D) usando expresiones regulares. Me pregunto si hay equivalentes para los árboles. (En lugar de una sola expresión regular, es posible que deba escribir un conjunto de reglas de transformación, pero eso está bien).

Me gustaría saber si hay algún mini lenguaje simple (no regex per.se, pero algo que es tan accesible como regex a través de bibliotecas, etc.). para realizar estas operaciones? Preferiblemente, como una biblioteca de Python.

Answer 1

TSurgeon y Tregex de Stanford es capaz de hacer eso. Puede descargar la biblioteca desde http://nlp.stanford.edu/software/tregex.shtml

Answer 2

Navegar a través de un árbol de búsqueda binario requiere estado (¿en qué nodo estoy?) Y comparaciones (¿ese valor es menor o mayor que eso?), Cosas que un autómata de estado finito no puede hacer.

Claro, puede buscar el nodo con un valor dado, pero ¿cómo podría, por ejemplo, eliminar un nodo que no sea una hoja si no conoce su elemento primario?

E incluso si conoce al padre a través de la información proporcionada por el nodo, ¿cómo determina el mínimo del subárbol izquierdo, lo elimina y lo coloca en el nodo?

Creo que le está pidiendo demasiado a la FSA.

Answer 3

No conozco una languga de uso general que pueda hacer eso, pero me parece que usted está buscando algo como XPath.

Answer 4

Hay TXL para la reescritura de árboles basada en patrones.

árbol de reescritura con los patrones también se realiza con kits de herramientas del analizador como ANTLR

La generación de código de abajo hacia arriba con la reescritura de árbol, Google fresas o BURG.

Answer 5

This artículo da algunos consejos sabrosos sobre las expresiones regulares recursivas de Perl, pero sinceramente es raro ver una estructura de árbol abordada de esta manera.

Más típicamente, uno escribiría un analizador de estilo de máquina de estado, que podría usar expresiones regulares para analizar cada nodo en particular en el árbol.

Expat es probablemente un buen ejemplo a tener en cuenta.

Answer 6

Coincidencia de patrones, proporcionada por idiomas como Scala, F #, Erlang y Haskell (estoy seguro de que hay más) está diseñada para manipular estructuras de datos de forma sucinta, especialmente cuando se usa con recursividad.

here es una vista de muy alto nivel de lo que Pattren Match puede hacer en Scala. Los ejemplos mostrados realmente no hacen justicia de coincidencia de patrones.

Wikipedia tiene un par de referencias a la coincidencia de patrones, también. Here y here.

Answer 7

Estoy algo sorprendido de que XSLT no haya surgido como una respuesta. Por supuesto, no creo que sea un lenguaje particularmente elegante, y la mayoría de las soluciones existentes tienden a favorecer los enfoques de procedimiento en lugar de la coincidencia de patrones, y se ha logrado una mala reputación por ser aplicado ciegamente solo porque XML se aplica a XML, pero se ajusta a la ley. Lástima que su representación canónica es tan detallada, aunque ...