Wydajny algorytm do aktualizowania drzewa analizy

14

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ę!

fl.formal-languages parsing

— Agos
źródło

1

Cześć i witam! Nie jestem ekspertem w tej dziedzinie, ale myślę, że słowem kluczowym, którego szukasz, jest przyrostowa analiza składniowa lub przyrostowa kompilacja .

— MS Dousti

@Sadeq dzięki za wskaźnik! Czy mógłbyś rozważyć dodanie odpowiedzi z pewnymi szczegółami? Byłoby to bardzo mile widziane!

— Agos

9

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 ).

— MS Dousti
źródło

1

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ę)