Лексический анализ в компиляторах¶

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

¶Задачи и принципы работы

Основная задача лексера — упростить работу синтаксического анализатора, избавив его от необходимости работать с отдельными символами и учитывать такие детали, как пробелы и переносы строк. Лексер читает входной поток символов и группирует их в токены согласно правилам, заданным лексической грамматикой языка программирования.

Каждый токен обычно описывается парой: тип токена (например, IDENTIFIER, INTEGER_LITERAL, KEYWORD_IF) и его атрибут (например, имя идентификатора или числовое значение). Тип токена определяется классом лексемы, а атрибут хранит конкретную информацию, необходимую для последующих этапов компиляции.

¶Токенизация и распознавание

Распознавание лексем чаще всего выполняется с использованием конечных автоматов (КА), которые строятся на основе регулярных выражений. Каждому типу лексемы (идентификатор, число, оператор) соответствует своё регулярное выражение. Лексер последовательно просматривает символы, переходя между состояниями автомата, пока не будет найдено максимально длинное совпадение с одним из регулярных выражений (принцип «максимального съедания»). Если ни одно правило не подходит, генерируется ошибка лексического анализа.

¶Таблица символов

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

¶Классификация лексем

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

• Ключевые слова — зарезервированные слова языка (if, while, return), которые не могут использоваться как идентификаторы.
• Идентификаторы — имена переменных, функций, типов и других объектов.
• Литералы — константы: целые числа, числа с плавающей точкой, строки, символы, булевы значения.
• Операторы и разделители — символы или их последовательности (+, ==, ;, {, }), задающие операции и структуру кода.
• Специальные лексемы — например, маркеры конца файла (EOF).

¶Инструменты генерации лексеров

Ручное написание лексеров — трудоёмкая задача, поэтому часто используются генераторы лексических анализаторов. Наиболее известный из них — Lex (и его свободный аналог Flex). Генератор принимает на вход файл с описанием регулярных выражений и действий, а на выходе выдаёт код на C (или другом языке), реализующий конечный автомат. Аналогичные инструменты существуют для других языков, например, JFlex для Java и RE2C, который генерирует быстрые лексеры на C/C++.

¶Связь с синтаксическим анализом

Лексический и синтаксический анализ тесно связаны, но разделены концептуально. Лексический анализ работает на уровне символов и лексем, а синтаксический — на уровне грамматических конструкций (выражений, операторов, объявлений). Разделение упрощает разработку компилятора: грамматика языка становится проще, а лексические детали (например, допустимые символы в идентификаторе) изолируются в одном модуле. В некоторых случаях (например, при обработке макросов в C/C++) границы между фазами размываются, и лексер может взаимодействовать с препроцессором.

¶Ошибки лексического анализа

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

¶Применение вне компиляторов

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

¶Литература

• Ахо А., Лам М., Сети Р., Ульман Д. «Компиляторы: принципы, технологии и инструменты» (Книга дракона).
• Вирт Н. «Построение компиляторов».
• Левин Дж. «Lex & Yacc».