Nome do algoritmo - subárvores correspondentes em ASTs

Question

Eu tenho um conjunto S de árvores "pequenas" S[i] para os quais preciso encontrar suas posições dentro de um espaço maior que são usados ​​como padrões para encontrar subárvores correspondentes em uma escala maior árvore T.Eu sei S antes de começar a construir T (que é uma árvore de análise), então estou pensando em empregar um método do plano de corte para combinar os nós conforme eu vou (conforme o analisador gera o CST).

As árvores em S não são os mesmos ASTs que T - pense em XPath vs.XML- S contém a representação em árvore dos XPaths, enquanto T é o AST real do código-fonte - preciso de mapas entre i e um vetor de nós correspondentes de T.

No entanto, não tenho certeza sobre os nomes dos algoritmos que usaria.

Basicamente eu sei o que quero fazer, parece um "dividir e imperar para árvores" com uma pilha onde mantenho possíveis candidatos para correspondência, a cada mudança do analisador LALR duplico o topo da pilha e elimino os candidatos i de S[i] que não corresponde de qualquer maneira, e após uma redução eu saio da pilha.No início todos os membros do S são possíveis candidatos.

Observe:isso é só sobre o AST, o ASG é outra história...

Termo aditivo

Aqui está uma árvore de análise T.

A função de análise terá conhecimento de uma lista do que chamo de "treepaths", em forma canônica, também representada como árvores, armazenada em S.Mas eles não se parecerão com a árvore de análise, eles terão sua própria linguagem para serem representados, semelhante ao XPath.

Exemplo de treepath para obter todas as funções que possuem como valor de retorno uma variável:

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

1. Então, o que devo procurar na literatura existente?
2. Algum outro conselho?
3. Já existem linguagens que podem consultar árvores meta-anotadas como esta?Uma biblioteca C de código aberto (não C++) seria ideal.

Answer 1

1) Suas árvores S como XPath correspondem a algumas árvores T.Por que não construir as árvores T antecipadamente e depois combiná-las com padrões?

2) Se você deseja combinar um padrão com uma estrutura, você pode imaginar compilar o padrão para algum tipo de máquina de estados, que faz a transição quando determinadas partes da árvore estão sendo comparadas.Se a máquina de estado entrar em um estado de aceitação, você encontrou uma correspondência.Se você tiver mais de um padrão, cada um deles poderá ser tratado como uma máquina de estados e você poderá executá-los "em paralelo" (por simulação).Para tornar isso eficiente, calcule o produto vetorial de todas as máquinas de estado;agora há apenas uma, e apenas uma transição ocorre por entrada.Chamo essa ideia de "produtos padrão" e você vê algo parecido com uma variedade de combinadores eficientes.Um próximo do que você quer fazer é o Algoritmo Rete, que monitora quais "padrões" estão ativos à medida que os dados alimentados mudam.

Answer 2

Pode valer a pena dar uma olhada no JXPath: http://commons.apache.org/jxpath/Não tenho certeza de qual idioma você está almejando, mas pode valer a pena tentar.

De qualquer forma, meu primeiro impulso se eu tivesse que tentar implementar algo assim seria encontrar uma maneira de "serializar" ambas as árvores e reduzir o problema a uma simples correspondência de strings.