Как создать анализатор AST, который допускает синтаксические ошибки?

Во-первых, что читать о разборе и построении AST?

Как создать синтаксический анализатор для языка (например, SQL), который будет создавать AST и допускать синтаксические ошибки?

Например, для "3+4*5":

  +
 / \
3   *
   / \
  4   5

А для "3+4*+" с синтаксической ошибкой парсер будет догадываться, что пользователь имел в виду:

  +
 / \
3   *
   / \
  4   +
     / \
    ?   ?

Когда начать?

SQL:

    SELECT_________________
   /           \           \
  .           FROM        JOIN
 / \           |         /    \
a city_name  people   address  ON
                                |
                                =______________
                               /               \
                              .____             .
                             /     \           / \
                            p  address_id     a  id
Источник

2 ответа

Решение

Стандартный ответ на вопрос о том, как создавать парсеры (которые создают AST), заключается в чтении стандартных текстов по компиляции. Книга компилятора "Дракон" Ахо и Уллмана довольно классическая. Если у вас нет терпения, чтобы получить лучшие справочные материалы, у вас будет больше проблем, потому что они предоставляют теорию и исследуют тонкости. Но вот мой ответ для спешащих людей, создающих парсеры рекурсивного спуска.

Можно создавать парсеры со встроенным восстановлением ошибок. Есть много статей на эту тему, горячая тема 1980-х годов. Проверьте Google Scholar, охота на "исправление синтаксической ошибки". Основная идея заключается в том, что синтаксический анализатор при обнаружении ошибки синтаксического анализа пропускает какой-либо известный маяк (";" разделитель операторов довольно популярен для языков, подобных С, поэтому в комментарии вас спрашивают, если ваш язык имеет терминаторы), или предлагает различные удаления или вставки входного потока, чтобы преодолеть точку синтаксической ошибки. Разнообразие таких схем удивительно. Основная идея, как правило, заключается в том, чтобы принимать во внимание как можно больше информации о точке ошибки. Одна из самых интригующих идей, которые я когда-либо видел, имела два анализатора, один из которых запускал N токенов впереди другого, ища мины с ошибками синтаксиса, а второй анализатор исправлял ошибки фида на основе доступных N токенов, прежде чем встретил синтаксис ошибка. Это позволяет второму синтаксическому анализатору решить действовать по-другому, прежде чем придет к синтаксической ошибке. Если у вас этого нет, большинство синтаксических анализаторов отбрасывают левый контекст и таким образом теряют способность к исправлению. (Я никогда не реализовывал такую ​​схему.)

Выбор вещей для вставки часто может быть получен из информации, используемой для построения синтаксического анализатора (часто наборы First и Follow). Это относительно легко сделать с анализаторами L(AL)R, потому что таблицы анализа содержат необходимую информацию и доступны синтаксическому анализатору в тот момент, когда он сталкивается с ошибкой. Если вы хотите понять, как это сделать, вам нужно понять теорию (упс, снова эта книга компиляторов) о том, как создаются парсеры. (Я реализовал эту схему несколько раз успешно).

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

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

Урок, который большинство людей, которые одержимы идеей создания парсера, не получают, заключается в том, что если они захотят сделать что-нибудь полезное с результатом или деревом разбора, им понадобится гораздо больше базовых механизмов, чем просто парсер. Проверьте мою биографию на "Жизнь после разбора".

Источник

Парсер может сделать две вещи:

  1. Сообщите об ошибке и попросите пользователя повторить попытку.
  2. Устраните ошибку и продолжайте.

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

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

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

Затем вам нужно выполнить повторную синхронизацию в какой-то момент после ошибки, чтобы продолжить синтаксический анализ. Как упомянула Ира Бакстер в своем ответе, вы можете искать токен, такой как ';', который разделяет утверждения. Правильный токен (ы) для поиска зависит от языка, который вы анализируете. Другая возможность - угадать, что имел в виду пользователь (например, вывести дополнительный токен или другой токен в том месте, где была обнаружена ошибка), а затем продолжить. Если вы столкнетесь с другой синтаксической ошибкой в ​​следующих нескольких токенах, вы можете вернуться назад, сделать другое предположение и повторить попытку.

Источник
Другие вопросы по тегам