Написание синтаксического анализатора — Часть III: Обработка синтаксических ошибок | by Supun Setunga

7 мин. чтения

·

10 сентября 2020 г.

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

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

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

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

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

• Следует ли удалить следующие маркеры?
• Должны ли быть вставлены некоторые токены? Если да, то какие жетоны должны быть вставлены?

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

Подход I:

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

Подход II:

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

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

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

Подход III (рекомендуемый):

При обнаружении неожиданного маркера

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

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

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

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

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

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

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

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

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

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

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

Ранний выход

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

 инт а = ; // синтаксическая ошибка 
 int b = 5; 

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

 expr := basic-literal | переменная-ссылка | функциональный вызов | binary-expr 

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

Запоминание

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

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

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

синтаксический анализ — использование синтаксического анализатора python ast для обработки многострочных строк

При использовании модуля синтаксического анализатора python AST в сочетании со сценариями, содержащими многострочные строки, эти многострочные строки всегда сокращаются до однострочных строк в кавычках. Пример:

 импорт аст
скрипт = "текст='''Строка1\nСтрока2'''"
code = ast. parse (скрипт, режим = 'exec')
распечатать (ast.unparse (код))
узел = код.тело[0].значение
печать (node.lineno, node.end_lineno)
 

Вывод:

 > текст = 'Строка1\nСтрока2'
> 1 2
 

Таким образом, несмотря на то, что перед синтаксическим анализом он представляет собой многострочную строку, при разборе текст сводится к одной строке в кавычках. Это затрудняет трансформацию скрипта, поскольку многострочные строки теряются при разборе преобразованного графа AST.

Есть ли способ правильно анализировать/разбирать скрипты с многострочными строками с помощью AST?

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

• python
• разбор
• абстрактное-синтаксическое дерево
• многострочный
• с указанием

2

Изучение исходного кода ast.unparse показывает, что модуль записи для метода visit_Constant , _write_constant , создаст строку repr , если специально не избегать процесса обратной косой черты:

 класс _Unparse:
   . ..
   def _write_constant (я, значение):
      if isinstance (значение, (с плавающей запятой, комплекс)):
          ...
      elif self._avoid_backslashes и isinstance (значение, строка):
          self._write_str_avoiding_backslashes(значение)
      еще:
          self.write (воспроизведение (значение))
 

---

По умолчанию для _avoid_backslashes установлено значение False , однако форматирование многострочных строк может быть правильно выполнено путем переопределения visit_Constant и специального вызова _write_str_avoiding_backslashes если строковый узел многострочный:

 import ast
класс Unparser (ast._Unparser):
 def visit_Constant (я, узел):
 если isinstance(node.value, str) и node.lineno < node.end_lineno:
 super()._write_str_avoiding_backslashes(node.value)
 возвращаться
 вернуть super().visit_Constant(узел)
защита _unparse (ast_node):
 u = депарсер ()
 вернуть u.visit (ast_node)
скрипт = "текст='''Строка1\nСтрока2'''"
print(_unparse(ast.