Лексический анализ – начальная стадия трансляции формальных языков, которая выполняется во многих практических случаях при обработке текстовых данных. В частности, лексический анализ необходим для обработки входного потока символьных данных в пакетном редакторе или для распознавания директив в диалоговой системе. Однако основной областью практического приложения лексического анализа является реализация начальной стадии обработки входного потока символьной информации в трансляторах универсальных языков программирования и специализированных входных языков различной проблемной ориентации.
В общем случае целью лексического анализа является разбиение входного потока символьной информации на структурные единицы, которые имеют определенное совокупное значение и называются лексемами. Например, типичными лексемами в исходных текстах программ, составленных на различных алгоритмических языках, являются операторы, служебные слова, числовые или символьные константы, идентификаторы переменных, директивы препроцессора системы программирования, обозначения типов данных и классов памяти. Выявленные при лексическом анализе входного потока лексемы могут быть обработаны и закодированы соответствующим образом для передачи на следующие стадии трансляции, в частности, на стадию синтаксического анализа.
Выполнение лексического анализа в трансляторах формальных языков обеспечивает специальная программная компонента, которая называется лексическим анализатором. Лексический анализатор может быть реализован в формате исполняемого файла или объектного модуля, который вызывается транслятором для выполнения этапа лексического анализа. В простых случаях разработка лексического анализатора может быть выполнена традиционными средствами, которые предоставляют системы программирования алгоритмических языков высокого уровня, например, C, C++ или Pascal. Однако в большинстве практически интересных случаев такой подход требует значительных трудозатрат и интеллектуальных усилий разработчиков системного программного обеспечения. По этой причине в настоящее время получили широкое распространение разнообразные систематические технологии и инструментальные средства, которые позволяют в значительной мере автоматизировать проектные процедуры практической разработки основных программных компонент трансляторов формальных языков в различных операционных средах.
В частности, для автоматизации проектирования лексических анализаторов операционная система OS UNIX предоставляет специальное инструментальное средство, которое было разработано К.С. Лекcом и называется генератор лексических анализаторов LEX (далее по тексту, генератор LEX). Его основными компонентами являются выполняемый модуль lex и библиотека объектных модулей стандартных функций libl.a (или разделяемый объект libl.so), которые обычно располагаются, соответственно, в каталогах /usr/bin и /usr/lib файловой системы OS UNIX. Исходными данными для генератора LEX является высокоуровневая проблемно-ориентированная спецификация лексем, которые должен распознавать проектируемый лексический анализатор во входном потоке символьных данных. Эта спецификация имеет формат текстового файла, который может быть подготовлен в текстовом редакторе и сохранен под произвольным именем, обычно с расширением .l, в любом доступном каталоге файловой системы OS UNIX.
Файл спецификации лексем должен иметь определенную внутреннюю структуру, в которой для описания лексем используются шаблоны регулярных выражений. В результате обработки файла спецификации лексем генератор LEX формирует исходный код проектируемого лексического анализатора на языке программирования C. Основная часть полученного исходного кода лексического анализатора реализует детерминированный конечный автомат, который генератор LEX автоматически строит по заданным шаблонам регулярных выражений. Полученный исходный код при необходимости может быть отредактирован и легко преобразуется в объектный модуль или выполняемый файл проектируемого лексического анализатора с помощью стандартных средств компилирующей системы языка программирования C.
Таким образом, практическое применение генератора LEX позволяет ограничить процедуру проектирования лексического анализатора составлением высокоуровневых спецификаций лексем, по которым автоматически порождается исходный код лексического анализатора на языке программирования C. Наиболее важным этапом рассмотренной технологии является формирование файла спецификации лексем. Основные интеллектуальные проблемы, которые при этом возникают, связаны с разработкой шаблонов регулярных выражений. Вопросы конструирования регулярных выражений и спецификации лексем подробно рассмотрены в следующих разделах предлагаемого учебного пособия.