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

Введение

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

Что такое парсинг

По сути, синтаксический анализ означает преобразование исходного кода в представление объекта в виде дерева, которое называется «деревом синтаксического анализа» (также иногда называемым «синтаксическим деревом»). Часто абстрактное синтаксическое дерево (AST) путают с синтаксическим деревом. Дерево синтаксического анализа - это конкретное представление исходного кода. Он сохраняет всю информацию исходного кода, включая тривиальную информацию, такую ​​как разделители, пробелы, комментарии и т. Д. Принимая во внимание, что AST является абстрактным представлением исходного кода и может не содержать некоторую информацию, которая есть в исходном коде. .

В синтаксическом дереве каждый элемент называется «узлом». Конечные узлы или конечные узлы рассматриваются как особый вид узлов, который называется «токеном». Нетерминальные узлы обычно называются просто «узлами».

Почему рукописный парсер?

Если вы посмотрите вокруг, вы увидите, что существует довольно много генераторов парсеров, таких как ANTLR, Bison, Yacc и т. Д. С помощью этих генераторов парсеров мы можем просто определить грамматику и автоматически сгенерировать парсер в соответствии с эта грамматика. Звучит довольно просто! Если да, то зачем писать парсер с нуля?

Распространенная ошибка при создании компилятора - думать, что нам нужно написать синтаксический анализатор с нуля, или думать, что нам не нужен собственный синтаксический анализатор. Что ж, звучит противоречиво! Загвоздка в том, что у обоих подходов есть свои плюсы и минусы. Поэтому важно знать, когда писать парсер вручную или использовать генератор парсера:

Сгенерированный синтаксический анализатор:

  • Легко реализовать - определите грамматику в необходимом формате и сгенерируйте парсер. например: для ANTLR все, что нам нужно, это определить грамматику в .g4format. Затем сгенерировать синтаксический анализатор так же просто, как запустить одну команду.
  • Простота обслуживания. Все, что вам нужно сделать, - это обновить правила грамматики и восстановить синтаксический анализатор.
  • Может быть компактным по размеру.
  • Однако у него нет преимуществ рукописного синтаксического анализатора (см. Ниже).

Рукописный синтаксический анализатор:

  • Написать парсер вручную - задача в меру сложная. Сложность может возрасти, если грамматика языка сложна. Однако у него есть следующие преимущества.
  • Могут иметь более качественные и содержательные сообщения об ошибках. Автоматически сгенерированные парсеры могут иногда приводить к совершенно бесполезным ошибкам.
  • Может поддерживать устойчивый синтаксический анализ. Другими словами, он может создать действительное дерево синтаксического анализа даже при синтаксической ошибке. Это также означает, что рукописный синтаксический анализатор может одновременно обнаруживать и обрабатывать несколько синтаксических ошибок. В сгенерированных синтаксических анализаторах это может быть достигнуто в определенной степени с помощью обширных настроек, но может быть не в состоянии полностью поддерживать устойчивый синтаксический анализ.
  • Может поддерживать инкрементный синтаксический анализ - анализируйте только часть кода при обновлении источника.
  • Обычно лучше с точки зрения производительности.
  • Легко настроить. Вы владеете кодом и имеете полный контроль над ним - например: в ANTLR4, если вы хотите настроить логику синтаксического анализа, вам придется либо расширить и немного взломать сгенерированный синтаксический анализатор, либо написать некоторую настраиваемую логику в сам файл грамматики на другом языке. Иногда это может быть беспорядочно, и уровень настройки, которую можно выполнить, очень ограничен.
  • Может легко обрабатывать контекстно-зависимые грамматики. Не все языки на 100% контекстно-свободны. Могут быть ситуации, когда вы хотите токенизировать ввод или построить дерево синтаксического анализа по-разному в зависимости от контекста. Когда дело касается сгенерированных синтаксических анализаторов, это очень сложная или практически невыполнимая задача.

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

Грамматика

Независимо от того, реализовывать ли рукописный синтаксический анализатор или использовать сгенерированный синтаксический анализатор, всегда будет нужна одна вещь: четко определенная грамматика (формальная грамматика) для языка, который мы собираемся реализовать. Грамматика определяет лексическую и синтаксическую структуру программы на этом языке. Очень популярным и простым форматом определения контекстно-свободной грамматики является Форма Бэкуса-Наура (BNF) или один из ее вариантов, например, Расширенная форма Бэкуса-Наура (EBNF).

Компоненты парсера:

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

Считыватель символов / считыватель ввода

Считыватель символов, также называемый считывателем ввода, считывает исходный код и предоставляет символы / кодовые точки лексеру по запросу. Исходным кодом может быть множество вещей: файл, входной поток или даже строка.

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

Средство чтения ввода состоит из трех наборов важных методов:

  • peek () / peek (k) - получить следующий символ / следующий k-й символ из ввода. Это используется для просмотра символов вперед, не потребляя / не удаляя их из входного потока. Вызов метода peek() более одного раза вернет один и тот же символ.
  • Потреблять () / потреблять (k) - получить следующий символ / следующий k-й токен из ввода и удалить его из ввода. Это означает, что многократный вызов метода consume() будет возвращать новый символ при каждом вызове. Иногда этот consume() метод также называют read() или next().
  • isEOF () - проверяет, дошел ли читатель до конца ввода.

Лексер

Лексер считывает символы из устройства чтения / ввода символов и производит токены. Другими словами, он преобразует поток символов в поток токенов. Следовательно, его иногда также называют токенизатором. Эти токены производятся в соответствии с определенной грамматикой. Обычно реализация лексера немного сложнее, чем программа чтения символов, но намного проще, чем синтаксический анализатор.

Важным аспектом лексического анализатора является обработка пробелов и комментариев. В большинстве языков семантика языка не зависит от пробелов. Пробелы необходимы только для обозначения конца токена, поэтому их также называют «мелочами» или «мелочами», поскольку они не имеют большого значения для AST. Однако это не относится к каждому языку, потому что пробелы могут иметь семантическое значение в некоторых языках, таких как python. Разные лексеры по-разному обрабатывают эти пробелы и комментарии:

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

Подобно программе чтения символов, лексер состоит из двух методов:

  • peek () / peek (k) - получить следующий токен / следующий k-й токен. Это используется для просмотра токенов вперед, не потребляя / не удаляя их из входного потока. Вызов метода peek() более одного раза вернет один и тот же токен.
  • Потреблять () / потреблять (k) - получить следующий токен / следующий k-й токен и удалить его из потока токенов. Это означает, что многократный вызов метода consume() будет возвращать новый токен при каждом вызове. Иногда этот consume() метод также называют read() или next().

Как только лексер достигает конца ввода от считывателя символов, он выдает специальный токен, называемый «EOFToken» (токен конца файла). Парсер использует этот EOFToken для завершения анализа.

Парсер

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

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

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

Обработчик ошибок

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

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

  • Попытка восстановить каждое место приведет к множеству повторяющихся задач и дублированию кодов.
  • Логика парсера будет загромождена логикой обработки ошибок, что в конечном итоге сделает кодовую базу трудной для чтения и понимания.
  • Имея отдельный обработчик ошибок, можно также подключать разные обработчики ошибок для разных сценариев использования. Например, можно использовать один подход к обработке ошибок для инструментов CLI и другой подход к обработке ошибок для интерактивных IDE. Поскольку IDE могут захотеть облегчить завершение кода и т. Д., И, следовательно, шаблон восстановления будет более близок к шаблону написания пользователя.

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