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

Ошибки синтаксиса

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

  • Ожидаемый токен в какой-то момент отсутствует.
  • Некоторые дополнительные токены (нежелательные токены) существуют до ожидаемого токена.

Это немного упрощает жизнь парсеру, так как ему нужно беспокоиться только о двух случаях. Но, тем не менее, синтаксическому анализатору необходимо восстановиться после таких синтаксических ошибок, чтобы продолжить синтаксический анализ остальной части документа / ввода. И это выздоровление не так просто, как может показаться.

Выздоровление

Обработчик ошибок отвечает за восстановление после таких синтаксических ошибок. Синтаксический анализатор запрашивает обработчик ошибок, чтобы попытаться исправить синтаксическую ошибку, а обработчик ошибок восстановится после ошибки и вернет восстановленный узел синтаксическому анализатору. В приведенном выше примере решение для восстановления в (2) состоит в том, чтобы вставить токен идентификатора (имя переменной), а решение для (3) состоит в том, чтобы удалить один из токенов идентификатора (предпочтительно «b»). Человеческому глазу это легко сказать, но как обработчик ошибок узнает, что нужно предпринять? С точки зрения обработчика ошибок при синтаксической ошибке

  • Следует ли удалить следующий токен (-ы)?
  • Следует ли вставить какие-то токены? Если да, то какой токен (ы) нужно вставить?

Чтобы ответить на эти вопросы, мы могли бы использовать стратегию исправления ошибок.

Подход I:

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

Подход II:

При обнаружении неожиданного токена проверьте, является ли этот токен «ожидаемым токеном» в рамках следующих k правил грамматики (например, k = 5).

  • Если да, то это означает, что ожидаемый токен в текущей позиции отсутствует. Следовательно, вставьте недостающий токен и продолжайте.
  • Если нет, значит, это посторонний токен. Следовательно, удалите токен.

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

Подход III (рекомендуется):

Когда достигается неожиданный токен,

  • Вставьте токен и посмотрите, как далеко может успешно продвинуться синтаксический анализатор. Текущий контекст синтаксического анализатора (то есть: какое правило грамматики в настоящее время анализируется) и формальная грамматика языка могут использоваться для определения типа вставляемого токена.
  • Удалите токен и посмотрите, как далеко может успешно продвинуться парсер.

Это можно сделать, поддерживая два потока токенов:

  • Ожидаемый набор токенов - может быть сформирован на основе грамматики.
  • Фактический набор токенов - это поток, возвращаемый лексером.

А затем сравнение двух потоков токенов может быть использовано для определения количества правильных совпадений и токенов, которые будут вставлены при неправильном совпадении. Рассмотрим приведенный выше пример (2), где имя переменной отсутствует в объявлении переменной. Если мы сравним два потока, то обнаружим несоответствие после 2-го токена (см. Ниже).

Как вы можете видеть на приведенной выше диаграмме, вставка токена идентификатора правильно выравнивает фактический поток токенов с ожидаемым потоком токенов. Однако это не так просто, как кажется. Например, вместо 'expr' могут быть разные типы разрешенных выражений, такие как int-literals, string-literals и т. Д. Таким образом, обработчик ошибок должен проверять все эти альтернативы. пути при сравнении потоков токенов. Кроме того, еще одна сложность, о которой следует подумать, заключается в том, что может быть более одной синтаксической ошибки рядом друг с другом - тогда это повлияет на проверку правильных совпадений. Таким образом, мы можем расширить вышеуказанное решение следующим образом, чтобы преодолеть эти проблемы.

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

  • Выберите решение с самой длинной совпадающей последовательностью.
  • Если есть ничья, найдите решение, которое требует наименьшего количества «исправлений».
  • Если есть ничья, отдайте приоритет «вставке», поскольку это не требует удаления введенных пользователем данных.
  • Если два или более альтернативных пути дают одинаковый результат, отдайте приоритет порядку появления.

Наконец, применяется лучшее решение, и анализ продолжается. Например, если лучшей комбинацией исправлений была [вставить, вставить, удалить, удалить], то примените только первое исправление и продолжайте.

  • Если исправление было «удалить» - тогда используйте поток токенов один раз и снова продолжите то же правило.
  • Если исправление было «вставкой» - затем вставьте отсутствующий узел и продолжите со следующего правила, не используя поток токенов.

Причина применения только первого исправления заключается в том, что после исправления ошибки и перемещения курсора вперед набор токенов, которые мы будем рассматривать для восстановления второй ошибки, может быть другим. Таким образом, существует вероятность получения другого решения, чем то, которое мы получили ранее (как второе исправление).

Оптимизация

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

Ранний выход

Предположим, есть синтаксическая ошибка в том месте, где грамматика поддерживает ветвление / альтернативные пути. Примером может быть синтаксическая ошибка в месте, где ожидается выражение. См. Приведенный ниже пример отсутствия выражения-значения в определении переменной.

int a = ;    // syntax error
int b = 5;

Грамматика на момент синтаксической ошибки:

expr := basic-literal | variable-ref | func-call | binary-expr

Теперь обработчик ошибок вставит / удалит токен и попробует все альтернативы (basic-literal, variable-ref, func-call, binary-expr), чтобы вычислить лучший матч. Но наиболее оптимальным решением здесь является вставка одного токена (числа или идентификатора). Тогда он будет соответствовать одному из вариантов basic-literal или variable-ref. Когда обработчик ошибок сначала пробует basic-literal в качестве первого варианта, он получит результат с всеми совпадениями, т.е. лучший результат, который может получить обработчик ошибок. Таким образом, нет смысла пробовать остальные альтернативы, поскольку у нас уже есть наилучшее возможное решение. Следовательно, обработчик ошибок может завершить обработку и вернуть этот результат.

Воспоминания

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

Безотказный

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

Однако в действительности полностью устранить его практически невозможно. Так что всегда хорошо иметь отказоустойчивый механизм для прекращения таких возможных бесконечных рекурсий. Один из подходов заключается в отслеживании индекса токена, и если синтаксический анализатор продолжает попытки синтаксического анализа одного и того же индекса снова и снова, можно решить, что синтаксический анализатор застрял в бесконечной рекурсии, и его можно выручить, явно потребляя жетон.