Разбор кода с синтаксическими ошибками

Question

Методы синтаксического анализа хорошо описаны в литературе по CS.Но известные мне алгоритмы требуют, чтобы источник был синтаксически правильным.Если возникает синтаксическая ошибка, синтаксический анализ немедленно прерывается.

Но IDE (как Visual Studio) обычно способны обеспечить значимое завершение кода и другие подсказки при вводе , что означаетчасто не в действительном состоянии.Например, вы вводите открывающую скобку в вызове функции, и IDE предоставляет подсказки параметров для функции, даже если синтаксис недопустим до тех пор, пока не будет введена закрывающая скобка.отгадывания или устойчивый к ошибкам синтаксический анализатор.Кто-нибудь знает, какие методы или алгоритмы используются для этого?

Answer 1

Стандартный трюк - это исправление ошибок с помощью механизма синтаксического анализа, помогающего делать прогнозы.

Для синтаксических анализаторов на основе таблиц (таких как LALR или GLR), когда возникает синтаксическая ошибка, анализатор недавно находился в каком-то состоянии, в котором ошибка еще не произошла. Можно записать стек анализа, чтобы запомнить это перед каждой сменой (или, альтернативно, записать сокращения до ошибки). Учитывая, что возникла ошибка, можно проверить состояние анализа сохраненного стека, чтобы определить, какие токены могут быть следующими (это также как выполнить кодовое завершение с точки зрения синтаксических токенов). Более сложный метод может придумать наименьшую возможную последовательность токенов, которая допускает сдвиг на токен ошибки, или наименьшее возможное дерево, которое может заменить токен ошибки и разрешить переход на следующий.

Это не так просто с парсерами рекурсивного спуска, потому что там не так много информации, которая делает предикаты. Для исправления ошибок хитрый трюк - определить точки восстановления после ошибок (например, где может быть принята «stmt») и продолжить сканирование до «;» найден и принят и "ошибка stmt". Это не поможет, если вы хотите завершить код.

Answer 2

Packrat является многообещающим - он предоставляет информацию как об успешных, так и неудачных попытках синтаксического анализа в ключевых точках, которые можно восстановить и использовать для интеллектуальных отчетов об ошибках, завершения, подсказок и так далее.Например, если курсор находится в точке, где все попытки синтаксического анализа помечены в кеше как неудачные, список опробованных токенов можно указать для параметров завершения.