Лексический анализ
Токен (лексема, token) — это последовательность символов и её тип.
Лексический анализ — это процесс разбора входной последовательности символов на распознанные группы с целью получения на выходе идентифицированных последовательностей.
Программа, выполняющая лексический анализ называется лексический анализатор.
Пример разбора строки на лексемы:
"2 + 33" => ["2", " ", "+", " ", "33"]
Лексер как правило работает в одном из двух режимов:
- выдача очередного токена парсеру
- проход с составлением списка токенов
НКА — недетерминированный конечный автомат
ДКА — детерминированный конечный автомат
Способы создания лексического анализатора на основе регулярных выражений:
- конвертировать регулярное выражение в НКА, моделировать НКА
- конвертировать регулярное выражение в НКА, затем НКА в ДКА
- конвертировать регулярное выражение напрямую в ДКА
Каждый из вариантов может быть применим в зависимости от требований к скорости работы или затрат по памяти. Для реальных примеров ДКА как правило получается очень большой, но моделирование НКА работает значительно медленнее.
Пример ДКА на основе регулярного выражения:
BlockComment : '/*' .*? '*/' ;
Процесс токенизации
Для интерпретации, помимо таблицы переходов ДКА и начального состояния, необходима дополнительная информация про каждое принимающее состояние. Каждое принимающее состояние должно соответствовать какому-либо типу токена. При конфликте как правило приоритет отдаётся правилу, которое в исходной грамматике было объявлено первым.
Лексический анализатор всегда пытается выделить лексему наибольшей длины. При интерпретации история состояний хранится в стеке. ДКА выполняется, пока он не перейдёт в состояние ошибки. После этого стек отматывается до тех пор, пока не встретится принимающее состояние. Длина лексемы будет равна текущему размеру стека.