Nombre del algoritmo: subárboles coincidentes en AST

Question

tengo un conjunto S de árboles "pequeños" S[i] que necesito para encontrar sus posiciones dentro de un más grande que se utilizan como patrones para encontrar subárboles coincidentes en un mayor árbol T.Sé S antes de empezar a construir T (que es un árbol de análisis), así que estoy pensando en emplear un método del plano de corte para hacer coincidir los nodos a medida que avanzo (mientras el analizador genera el CST).

los arboles en S no son los mismos AST que T - piense en XPath vs.XML - S contiene la representación de árbol de los XPath, mientras que T es el AST real del código fuente; necesito mapas entre i y un vector de nodos coincidentes de T.

Sin embargo, no estoy seguro de los nombres de los algoritmos que usaría.

Básicamente sé lo que quiero hacer, se siente como un "divide y vencerás para árboles" con una pila donde tengo posibles candidatos para coincidir, en cada cambio del analizador LALR duplico la parte superior de la pila y elimino candidatos i de S[i] que no coincidirá de todos modos, y después de una reducción salgo de la pila.Al principio todos los miembros de S son posibles candidatos.

tenga en cuenta:Esto es sólo sobre el AST, el ASG es otra historia...

Apéndice

Aquí hay un árbol de análisis. T.

La función de análisis tendrá en cuenta una lista de lo que yo llamo "treepaths", en forma canónica, también representados como árboles, almacenados en S.Pero no se verán como el árbol de análisis, tienen su propio lenguaje para ser representados, similar a XPath.

Ejemplo de un treepath para obtener todas las funciones que tienen como valor de retorno una variable:

function[body[return[expr[@type="variable"]]]]]

1. Entonces, ¿qué debo buscar en la literatura existente?
2. ¿Algún otro consejo?
3. ¿Existen ya lenguajes que puedan consultar árboles metaanotados como este?Una biblioteca C (no C++) de código abierto sería ideal.

Answer 1

1) Sus árboles S como XPath corresponden a algunos árboles T.¿Por qué no construir los árboles T de antemano y luego combinarlos con el patrón?

2) Si desea hacer coincidir un patrón con una estructura, puede imaginarse compilar el patrón en algún tipo de máquina de estados, que realiza la transición cuando se comparan determinadas partes del árbol.Si la máquina de estado alguna vez ingresa a un estado de aceptación, habrá encontrado una coincidencia.Si tiene más de un patrón, cada uno puede tratarse como una máquina de estados y puede ejecutarlos "en paralelo" (mediante simulación).Para que esto sea eficiente, calcule el producto cruzado de todas las máquinas de estados;ahora solo hay una y solo ocurre una transición por entrada.A esta idea la llamo "productos patrón" y se ve algo así como en una variedad de comparadores eficientes.Uno cercano a lo que quieres hacer es el Algoritmo de red, que realiza un seguimiento de qué "patrones" están activos a medida que cambian los datos que se le envían.

Answer 2

Podría valer la pena investigar JXPath: http://commons.apache.org/jxpath/No estoy seguro de a qué idioma te diriges, pero podría valer la pena intentarlo.

De todos modos, mi primer impulso si tuviera que intentar implementar algo como esto sería encontrar una manera de "serializar" ambos árboles y reducir el problema a uno de simple coincidencia de cadenas.