Wydajny algorytm do aktualizowania drzewa analizy

Powiedzmy, że mam duży blok kodu, który już sprawdziłem i przeanalizowałem.
Załóżmy, że zmienia się tylko jedna postać; Chciałbym zaktualizować parsowanie, ale ponieważ modyfikacja jest bardzo niewielka w porównaniu do całości, chciałbym wiedzieć, czy nie można ponownie przeanalizować całości, ale czy istnieją algorytmy określające zakres do ponownej analizy i odpowiednio radzić sobie z przesuwaniem granic tokenów.

Z góry dziękuję!

Zgodnie z prośbą @Agos zmieniłem komentarz w odpowiedź.

Po pierwsze, muszę przyznać, że nie jestem tak naprawdę kompetentny w tej dziedzinie. Jednak sugeruję przeczytanie artykułów Budowanie przyjaznych parserów oraz wydajnego i elastycznego analizowania przyrostowego, aby zobaczyć, jakie algorytmy były używane do analizowania przyrostowego przed 2000 rokiem.

Aby uzyskać zaktualizowane metody leczenia, możesz zapoznać się z tymi dokumentami:

• Leniwa funkcjonalna analiza przyrostowa (2009)
• Praktyczne, przyrostowe, niekanoniczne parsowanie: metoda Celentano i algorytm parsowania uogólnionego fragmentarycznego LR (2006)
• Przyrostowa walidacja dokumentów XML (2004)
• Analiza przyrostowa w edytorach językowych: potrzeby użytkowników i sposoby ich zaspokojenia (2001)
• Analiza przyrostowa i preprocesor C (nigdzie nie można znaleźć pliku PDF. Pochodzi z pamięci podręcznej Google.)

Więcej informacji: Istnieją (przynajmniej) dwa podejścia do parsowania / kompilacji:

• The Partii podejście, w którym cały blok kodu jest analizowany / zestawiane.
• Przyrostowe podejście, w którym dokument jest najpierw analizowany / skompilowany w trybie wsadowym, a następnie zostaną wykryte zmiany i minimalne re-parsowania / re-kompilacji jest stosowana. Takie podejście nie tylko zwiększa szybkość analizy / kompilacji, ale także pomaga w ciekawych funkcjach IDE, takich jak kompilacja w tle , która jest powiązana z leniwą kompilacją . (Możesz także wyszukiwać funkcje komercyjne, takie jak IntelliSense ).

jeśli twój przyrostowy parser zapisuje stan na każdym końcu linii, ponownie analizujesz tylko od ostatniego poprawnego stanu analizatora (w najlepszym przypadku, np. po pełnej analizie jest to tylko początek linii, w której rozpoczyna się modyfikacja) i przestajesz analizować na końcu linii, w której kończy się modyfikacja (wewnętrzny parser może patrzeć w przyszłość poza modyfikację, aby poprawnie rozpoznać strukturę)