Задача
Задача анализа текста с помощью лексических анализаторов встаёт перед разработчиками достаточно часто. Это может понадобится при разработке парсеров DSL, языков запросов или при парсинге специфичных текстовых протоколов.
Существующие подходы
При создании лексичского анализатора можно использовать несколько подходов:
- Написать парсер ad hoc — для конкретной лексической структуры.
- Воспользоваться генератором лексеров — например LEX.
- Воспользоваться библиотекой с готовым парсером.
Как это всегда и бывает, каждый из этих подходов имеет преимущества и недостатки, рассмотрим их вкратце.
Ad hoc лексер может быть реализован двумя основными способами: как конечный автомат или как парсер с рекурсивным спуском. Оба этих способа приведут к очень запутанному и императивному коду, в который тяжело будет вносить изменения, когда это неизбежно поттребуется, однако получившийся лексер будет невероятно гибким, а в случае с рекурсивным спуском может без особых усилий превратиться в парсер необходимой грамматики.
Следующие два способа объединяет то, что они рассчитывают на использование стороннего софта, что можно считать положительной стороной: библиотеки и генераторы лексеров поддерживаются и тестируются опытными разработчиками, так что вероятность ошибки или непредсказуемого поведения очень мала. Однако генераторы лексеров тяжело бывает встроить в пайплайн сборки, а библиотеки оказываются недостаточно гибки. Всё же для практических целей это, вероятно, самые удачные способы.
Альтернативный подход
Но при отсутствии возможности пользоваться сторонним софтом, можно использовать иной метод: написать обобщённый лексер, а затем декларативно объявить правила.
Может показаться, что написание лексера — очень сложная задача, однако это не так. Ниже мы рассмотрим простой, однако не самый оптимальный, способ напиания обобщённых лексеров.
Каждая лексема задаётся регулярным выражением. Так "\p{L}+" — задаёт идентификатор. "[0-9]+" — целое число.
Какие-то токены могут быть не регулярным выражением, а конкретной строкой, с которой он должен совпадать. Например "if" — не является идентификатором, хотя и подходит под его регулярное выражение. Такие типы токенов задаются отдельно.
Токены могут быть помечены, как пробельные символы, тогда лексер не будет добавлять их к возвращаемому значению.
Пусть у нас есть список регулярных выражений, которым поставлены в соответствие типы токенов, а так же список уникальных токенов с их типами и список пробельных токенов.
Например regex_tokens: {"\p{L}+": ident, "[0-9]+": number, "\s+": space}, reserved_tokens: {"if": if}, space_tokens: [space].
По такому набору токенов мы сформируем регулярное выражение "(?<ident>\p{L}+)|(?<number>[0-9]+)|(?<space>\s+)".
Алгоритм парсинга выглядит следующим образом:
- Получим все непересекающеся совпадения с регулярным выражением в строке, для каждого из них:
- Проверим, что индекс начала этого вхождения совпадает с концом предыдущего вхождения. Если это не так — возвращаем ошибку "неожиданный символ по индексу" с индексом конца предыдущего вхождения и прервыаем парсинг.
- Проверяем, не является ли вхождения одним из зарезервированных токенов. Если является — добавляем его в результат (если он не находится в множестве пробельных) и переходим к обработке следующего символа.
- Проверяем к какой группе относится вхождение, добавляем к результату соответствующий токен (если он не находится в множестве пробельных). Переходим к обработке следующего символа.
Выводы
Таким образом мы получим простой и исчерпывающий лексический анализатор, который требует для своей работы только регулярные выражения, которые поставляются почти с каждым современным языком. При необходимости в него легко добавить любые требуемые возможности, что тяжело сделать с библитечными парсерами.