Nome dell'algoritmo: sottoalberi corrispondenti negli AST

Question

Ho un set S di "piccoli" alberi S[i] di cui ho bisogno per trovare le loro posizioni all'interno di un più grande che sono usati come modelli per trovare sottoalberi corrispondenti in un albero T. Conosco S prima di iniziare a costruire T (che è un albero di analisi), quindi sto pensando di utilizzare un metodo del piano di taglio per abbinare i nodi mentre procedo (poiché il parser genera il CST).

Gli alberi in S non sono gli stessi AST di T - pensa a XPath e XML - S contiene la rappresentazione ad albero degli XPath, mentre T è l'AST effettivo del codice sorgente - Ho bisogno di mappe tra i e un vettore di nodi corrispondenti di T.

Tuttavia non sono sicuro dei nomi degli algoritmi che userei.

Fondamentalmente so cosa voglio fare, sembra un " divide et impera per gli alberi" con uno stack in cui tengo i possibili candidati da abbinare, ad ogni turno del parser LALR che duplico la parte superiore della pila ed elimina i candidati i da S[i] che non corrisponderà comunque, e dopo una riduzione esco dallo stack. All'inizio sono possibili candidati tutti i membri di S.

Nota : questo riguarda solo l'AST, l'ASG è un'altra storia ...

<”Addendum

Ecco un albero di analisi T.

La funzione di parsing sarà a conoscenza di un elenco di quelli che chiamo "treepaths", in forma canonica, rappresentati anche come alberi, memorizzati in S. Ma non assomigliano all'albero parset, hanno la loro lingua in cui essere rappresentati, simile a XPath.

Esempio di un percorso albero per ottenere tutte le funzioni che hanno come valore di ritorno una variabile:

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

1. Quindi cosa dovrei cercare nella letteratura esistente?
2. Qualche altro consiglio?
3. Esistono già linguaggi che possono interrogare alberi meta-annotati come questo? Una libreria C (non C ++) open source sarebbe l'ideale.

Answer 1

1) I tuoi alberi S come XPath corrispondono ad alcuni alberi T.Perché non costruire gli alberi T in anticipo e poi combinarli con il pattern?

2) Se si desidera confrontare un pattern con una struttura, si può immaginare di compilare il pattern in una sorta di macchina a stati, che transizioni quando vengono confrontati i pezzi dell'albero.Se la macchina a stati entra in uno stato di accettazione, hai trovato una corrispondenza.Se hai più di un pattern, ognuno può essere trattato come una macchina a stati e puoi eseguirli "in parallelo" (tramite simulazione).Per renderlo efficiente, calcola il prodotto incrociato di tutte le macchine a stati;ora ce n'è solo una e si verifica una sola transizione per input.Questa idea la chiamo "prodotti modello" e si vede qualcosa di simile in una varietà di abbinatori efficienti.Uno vicino a quello che vuoi fare è l ' Rete Algorithm , che tiene traccia di quali "schemi"sono attivi man mano che i dati ad esso inviati cambiano.

Answer 2

Potrebbe valere la pena esaminare JXPath: http://commons.apache.org/jxpath/ Non sono sicuro della lingua scelta come target, ma potrebbe valerne la pena.

Ad ogni modo, il mio primo impulso se dovessi provare a implementare qualcosa del genere sarebbe trovare un modo per "serializzare" entrambi gli alberi e ridurre il problema a una semplice corrispondenza di stringhe.