Algoritmo eficiente para atualizar uma árvore de análise

14

Digamos que eu tenho um grande bloco de código que já lexei e analisei.
Suponha que apenas um caractere mude; Gostaria de atualizar minha análise, mas como a modificação é muito pequena em comparação com a coisa toda, gostaria de saber se é possível não analisar a coisa toda novamente, mas se existem algoritmos para determinar o intervalo a ser analisado novamente e para lidar adequadamente com os limites de token em movimento.

Desde já, obrigado!

Agos
fonte
1
Oi e bem vindo! Não sou especialista no assunto, mas acho que a palavra-chave que você procura é análise incremental ou compilação incremental .
MS Dousti
@Sadeq obrigado pelo ponteiro! Você consideraria adicionar uma resposta com alguns detalhes? Seria muito apreciado!
Agos

Respostas:

9

Conforme solicitação do @Agos, transformei o comentário em uma resposta.

Primeiro, devo admitir que não tenho muito conhecimento nesse campo. No entanto, sugiro que você leia os documentos Construindo analisadores amigáveis e Análise incremental eficiente e flexível para ter uma visão de quais algoritmos foram usados ​​para análise incremental antes de 2000.

Para tratamentos atualizados, você pode dar uma olhada nestes documentos:

Mais informações: Existem (pelo menos) duas abordagens para análise / compilação:

  • A abordagem em lote , na qual todo o bloco de código é analisado / compilado.
  • A abordagem incremental , na qual o documento é analisado / compilado primeiro no modo em lote, e então as alterações são detectadas e a re-análise / recompilação mínima é aplicada. Essa abordagem não apenas aumenta a velocidade de análise / compilação, mas também ajuda nos recursos interessantes do IDE, como a compilação em segundo plano , que está relacionada à compilação lenta . (Você também pode pesquisar sobre recursos comerciais, como o IntelliSense ).
MS Dousti
fonte
1

se o seu analisador incremental salva o estado em cada extremidade da linha, você analisa novamente apenas do último estado válido do analisador (na melhor das hipóteses, por exemplo, após uma análise completa, este é apenas o começo da linha em que a modificação começa) e para de analisar no final da linha em que a modificação termina (o analisador interno pode olhar além da modificação para reconhecer corretamente a estrutura)


fonte