Эффективный алгоритм обновления дерева разбора

14

Допустим, у меня есть большой блок кода, который я уже проанализировал и проанализировал.
Предположим, что меняется только один символ; Я хотел бы обновить мой синтаксический анализ, но поскольку модификация очень мала по сравнению со всем этим, я хотел бы знать, возможно ли не анализировать все заново, но есть ли алгоритмы для определения диапазона для повторного анализа и правильно справляться с перемещением границ токенов.

Заранее спасибо!

Акос
источник
1
Привет и добро пожаловать! Я не специалист по этому вопросу, но я думаю, что ключевое слово, которое вы ищете, - это инкрементальный анализ или инкрементная компиляция .
MS Dousti
@Sadeq спасибо за указатель! Не могли бы вы добавить ответ с некоторыми подробностями? Это будет с благодарностью!
Agos

Ответы:

9

По запросу @Agos я превратил комментарий в ответ.

Во-первых, я должен признать, что я не очень осведомлен в этой области. Тем не менее, я предлагаю вам прочитать статьи Создание дружественных парсеров и Эффективный и гибкий пошаговый анализ, чтобы узнать, какие алгоритмы использовались для пошагового разбора до 2000 года.

Для обновленных методов лечения вы можете взглянуть на эти документы:

Больше информации: Есть (по крайней мере) два подхода к синтаксическому анализу / компиляции:

  • партия подход, при котором весь блок кода анализируется / сост.
  • Инкрементный подход, при котором документ сначала анализируется / скомпилированы в пакетном режиме, а затем изменения будут обнаружены и минимальное повторное синтаксический / повторное составление применяется. Такой подход не только увеличивает скорость разбора / компиляции, но также помогает в изящных функциях IDE, таких как фоновая компиляция , которая связана с отложенной компиляцией . (Вы также можете искать о коммерческих функциях, таких как IntelliSense ).
М.С. Дусти
источник
1

если ваш инкрементный синтаксический анализатор сохраняет состояние на каждом конце строки, вы выполняете повторный анализ только из последнего действительного состояния синтаксического анализатора (в лучшем случае, например, после полного анализа это только начало строки, где начинается модификация) и прекращаете анализ в конце строки, где заканчивается модификация (внутренний синтаксический анализатор может смотреть вперед за пределы модификации, чтобы правильно распознать структуру)


источник