Nom de l'algorithme - Sous-sous correspondance dans les AST

Question

J'ai un ensemble S de "petits" arbres S[i] dont j'ai besoin de trouver leurs positions pour un plus grand qui sont utilisés comme motifs pour trouver des sous-arbres assortis dans un plus grand arbre T. je sais S Avant de commencer à construire T (qui est un arbre d'analyse), donc je pense à l'utilisation d'un Méthode de référence Pour correspondre aux nœuds au fur et à mesure (comme l'analyseur génère le CST).

Les arbres dans S ne sont pas les mêmes asts que T - pensez à XPath vs XML - S tient la représentation des arbres des xpaths, tandis que T est l'AST réel du code source - j'ai besoin de cartes entre i et un vecteur de nœuds correspondants de T.

Cependant, je ne suis pas sûr des noms des algorithmes que j'utiliserais.

Fondamentalement, je sais ce que je veux faire, c'est comme un "diviser et impera Pour les arbres "avec une pile où je tiens les candidats possibles à correspondre, à chaque décalage de l'analyseur lalr, je reproduisant le haut de la pile et élimine les candidats i de S[i] Ce qui ne corresponde pas de toute façon, et après une réduction, je suis sorti de la pile. Au début, tous les membres de S sont des candidats possibles.

Veuillez noter: C'est à peu près l'AST, l'ASG est une autre histoire ...

Addenda

Voici un arbre d'analyse T.

La fonction d'analyse sera consciente d'une liste de ce que j'appelle "Treepaths", sous une forme canonique, également représentée comme des arbres, stockés dans S. Mais ils ne ressemblent pas à la Partidraire, ils ont leur propre langue à représenter, similaire à XPath.

Exemple de Treepath pour obtenir toutes les fonctions qui ont la valeur de retour une variable:

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

1. Alors, que dois-je rechercher dans la littérature existante?
2. D'autres conseils?
3. Y a-t-il déjà des langues qui peuvent interroger des arbres méta-annotés comme celui-ci? Une bibliothèque c (pas C ++) open source serait idéale.

Answer 1

1) Vos arbres comme XPATH correspondent à certains arbres. Pourquoi ne pas construire les arbres T à l'avance, puis les motifs les correspondent?

2) Si vous voulez faire correspondre un motif contre une structure, vous pouvez imaginer compiler le motif à une sorte de machine d'état, qui transitions lorsqu'on lui donne des morceaux de l'arbre contre. Si la machine d'État entre un état d'acceptation, vous avez trouvé un match. Si vous avez plus d'un modèle, chacun peut être traité comme une machine d'état et vous pouvez les exécuter "en parallèle" (par simulation). Pour rendre cela efficace, calculer le produit transversal de toutes les machines d'État; Maintenant, il n'y a qu'un seul, et une seule transition se produit par entrée. Cette idée que j'appelle des "produits de motif" et vous voyez quelque chose comme dans une variété de correspondants efficaces. Un proche de ce que vous voulez faire est le Algorithme de rete, qui garde une trace de quels "modèles" sont en direct à mesure que les données qui lui sont alimentées changent.

Answer 2

Cela pourrait valoir la peine d'être examiné sur Jxpath: http://commons.apache.org/jxpath/Je ne sais pas quelle langue vous ciblez, mais cela pourrait valoir la peine.

Quoi qu'il en soit, ma première impulsion si je devais essayer d'implémenter quelque chose comme celle-ci serait de trouver un moyen de "sérialiser" les deux arbres et de réduire le problème à une simple correspondance de cordes.