Лексическое сканирование — это процесс анализа потока входных символов и разделения его на строки, называемые токенами, разделенные белым пространством. Большинство текстов компилятора начинаются здесь и посвящают несколько глав обсуждению различных способов создания сканеров.Spirit.Lex— это библиотека, созданная для решения сложных задач по созданию лексера для вашей грамматики (в этой документации мы будем использовать термины «лексический анализатор», «лексатор» и «сканер» взаимозаменяемо). Все, что нужно для создания лексера, это знать набор шаблонов, описывающих различные токены, которые вы хотите распознать во входе. Чтобы сделать это немного более формальным, вот некоторые определения:
- Токен — это последовательность последовательных символов, имеющих коллективное значение. Токены могут иметь атрибуты, характерные для типа токена, несущие дополнительную информацию о согласованной последовательности символов.
- Паттерн — это правило, выраженное как регулярное выражение и описывающее, как может быть сформирован конкретный токен. Например,<
[A-Za-z][A-Za-z_0-9]*>является шаблоном для правила, соответствующего идентификаторам C++.
- Персонажи между токенами называются белым пространством; они включают в себя пространства, вкладки, новые линии и формы. Многие люди также считают комментарии белым пространством, хотя, поскольку некоторые инструменты, такие как lint, не идеальны.
Как правило, лексическое сканирование выполняется в отдельном модуле от парсера, подавая парсер только потоком входных токенов. Теоретически это разделение не требуется, так как в конечном итоге существует только один набор синтаксических правил, определяющих язык, поэтому теоретически мы могли бы написать весь парсер в одном модуле. На самом деле,Spirit.Qiпозволяет писать парсеры без использования лексера, анализируя поток входных символов напрямую, и по большей части это способSpiritиспользовался с момента его изобретения.
Однако это разделение имеет как практическую, так и теоретическую основу и оказывается очень полезным в практическом применении. В 1956 году Ноам Хомский определил «Хомскую иерархию» грамматики:
- Тип 0: Неограниченные грамматики (например, естественные языки)
- Тип 1: контекстно-чувствительная грамматика
- Тип 2: бесконтекстная грамматика
- Тип 3: Регулярная грамматика
Сложность этих грамматик возрастает от обычных грамматик, являющихся самыми простыми, до неограниченных грамматик, являющихся самыми сложными. Точно так же сложность распознавания образов для этих грамматик возрастает. Хотя некоторые особенности некоторых языков программирования (таких как C++) относятся к типу 1, к счастью, по большей части языки программирования можно описать, используя только типы 2 и 3. Опрятная часть этих двух типов заключается в том, что они хорошо известны, и способы их разбора хорошо понятны. Было показано, что любую обычную грамматику можно разобрать с помощью машины состояния (конечного автомата). Аналогично, контекстно-свободные грамматики всегда можно разобрать с помощью автомата push-down (по сути, машины состояния, дополненной стеком).
В реальных языках программирования и практических грамматиках части, которые могут быть обработаны как регулярные выражения, как правило, являются частями более низкого уровня, такими как определение идентификатора или целого значения:
letter := [a-zA-Z]
digit := [0-9]
identifier := letter [ letter | digit ]*
integer := digit+
Части практичной грамматики более высокого уровня, как правило, более сложны и не могут быть реализованы с использованием простых регулярных выражений. Нам нужно хранить информацию о встроенном аппаратном стеке, повторяя иерархию грамматики, и это предпочтительный подход, используемый для анализа сверху вниз. Поскольку для разбора двух типов грамматики требуется другой тип абстрактной машины, оказалось эффективным разделить лексический сканер на отдельный модуль, построенный вокруг идеи государственной машины. Цель здесь состоит в том, чтобы использовать самую простую технику анализа, необходимую для работы.
Другой, более практичной, причиной отделения сканера от парсера является необходимость обратного сканирования во время парсеризации. Входные данные представляют собой поток символов, который, как часто полагают, обрабатывается слева направо без какого-либо обратного отсчета. К сожалению, на практике большую часть времени это невозможно. Почти каждый язык имеет определенные ключевые слова, такие как IF, FOR и WHILE. Решение о том, действительно ли определенная последовательность символов содержит ключевое слово или просто идентификатор, часто может быть принято только после просмотра первого делимитерапосле. Фактически, это делает процесс обратным, поскольку нам нужно хранить строку достаточно долго, чтобы принять решение. То же самое относится и к более грубым зернистым языковым особенностям, таким как вложенные утверждения IF/ELSE, где решение о том, к какому IF принадлежит последнее утверждение ELSE, может быть принято только после просмотра всей конструкции.
Таким образом, структура обычного компилятора часто включает в себя разделение функций более низкого уровня и более высокого уровня. Лексический сканер имеет дело с вещами на уровне символов, собирая символы в строки, преобразуя последовательность символов в различные представления в виде целых чисел и т. Д., И передавая их парсеру в качестве неделимых токенов. Также считается нормальным позволить сканеру выполнять дополнительные задания, такие как идентификация ключевых слов, хранение идентификаторов в таблицах и т. Д.
Сейчас,Духследует этой структуре, гдеДух.Лексможет использоваться для реализации распознавателей на основе государственных машин, в то время какSpirit.Qiможно использовать для создания распознавателей контекстной свободной грамматики. Поскольку оба модуля легко интегрируются друг с другом и с целевым языком C++, можно даже использовать предоставленную функциональность для создания более сложных распознавателей грамматики.
Преимуществом использованияSpirit.Lexдля создания лексического анализатора по сравнению с использованием более традиционных инструментов, таких какFlex, является тщательно продуманная интеграция с библиотекойSpiritи языком хоста C++. Вам не нужны никакие внешние инструменты для создания кода, ваш лексер будет идеально интегрирован с остальной частью вашей программы, что позволит свободно получать доступ к любой контекстной информации и структуре данных. Поскольку компилятор C++ видит весь код, он будет генерировать оптимальный код независимо от того, какие параметры конфигурации были выбраны пользователем.Spirit.Lexпредоставляет вам подавляющее большинство функций, которые вы могли бы получить из аналогичнойFlexпрограммы без необходимости оставлять C++ в качестве хоста:
- Определение токенов осуществляется с использованием регулярных выражений (паттернов)
- Определения токенов могут относиться к специальным строкам замены (макросхемам шаблонов), упрощающим определения шаблонов.
- Сгенерированный лексический сканер может иметь несколько начальных состояний
- Можно прикрепить код к любому из определений токена; этот код выполняется всякий раз, когда соответствующий шаблон токена был сопоставлен.
Даже если можно использоватьSpirit.Lexдля генерации кода C++, представляющего лексический анализатор (мы будем ссылаться на это как настатическуюмодель, более подробно описанную в разделеСтатическаяМодель) - модель, очень похожую на то, как работаетFlex- мы в основном сосредоточимся на противоположной,динамическоймодели. Вы можете напрямую интегрировать определения токенов в свою программу C++, динамически создавая лексический анализатор во время выполнения. Динамическая модель не поддерживаетсяFlexили другими генераторами лексических сканеров (такими какre2c,Ragelи т.д.). Эта динамическая гибкость позволяет ускорить разработку приложения.
На рисункениже показан обзор высокого уровня.В приложении может использоваться библиотека Spirit.Lex.Spirit.Lexпозволяет создавать лексические анализаторы на основе шаблонов. Эти шаблоны представляют собой правила, основанные на регулярном выражении, используемые для определения различных токенов, которые должны быть распознаны в последовательности ввода символа. Ожидается, что входная последовательность будет предоставлена лексическому анализатору в качестве произвольного стандартного переднего итератора. Сам лексический анализатор также предоставляет стандартный передний итератор. Разница здесь заключается в том, что открытый итератор обеспечивает доступ к последовательности токенов вместо последовательности символов. Токены в этой последовательности создаются на лету путем анализа базовой последовательности символов и сопоставления этого с шаблонами, определенными приложением.
