lex (Метода по лексу)

Московский Государственный Технический Университетим. Н.Э. БауманаТ.М. Волосатова, С.В. РодионовАВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯЛЕКСИЧЕСКИХ АНАЛИЗАТОРОВУчебное пособиедля практических занятий по курсуЛингвистическое Обеспечение САПРМоскваИздательство МГТУ им. Н.Э. Баумана2005ВВЕДЕНИЕЛексический анализ – начальная стадия трансляции формальных языков, которая выполняетсяво многих практических случаях при обработке текстовых данных. В частности, лексическийанализ необходим для обработки входного потока символьных данных в пакетном редактореили для распознавания директив в диалоговой системе.

Однако основной областьюпрактического приложения лексического анализа является реализация начальной стадииобработки входного потока символьной информации в трансляторах универсальных языковпрограммирования и специализированных входных языков различной проблемной ориентации.В общем случае целью лексического анализа является разбиение входного потока символьнойинформации на структурные единицы, которые имеют определенное совокупное значение иназываются лексемами. Например, типичными лексемами в исходных текстах программ,составленных на различных алгоритмических языках, являются операторы, служебные слова,числовые или символьные константы, идентификаторы переменных, директивы препроцессорасистемы программирования, обозначения типов данных и классов памяти. Выявленные прилексическом анализе входного потока лексемы могут быть обработаны и закодированысоответствующим образом для передачи на следующие стадии трансляции, в частности, настадию синтаксического анализа.Выполнение лексического анализа в трансляторах формальных языков обеспечиваетспециальная программная компонента, которая называется лексическим анализатором.Лексический анализатор может быть реализован в формате исполняемого файла илиобъектного модуля, который вызывается транслятором для выполнения этапа лексическогоанализа.

В простых случаях разработка лексического анализатора может быть выполненатрадиционнымисредствами,которыепредоставляютсистемыпрограммированияалгоритмических языков высокого уровня, например, C, C++ или Pascal. Однако вбольшинстве практически интересных случаев такой подход требует значительных трудозатрати интеллектуальных усилий разработчиков системного программного обеспечения.

По этойпричиневнастоящеевремяполучилиширокоераспространениеразнообразныесистематические технологии и инструментальные средства, которые позволяют в значительноймере автоматизировать проектные процедуры практической разработки основных программныхкомпонент трансляторов формальных языков в различных операционных средах.В частности, для автоматизации проектирования лексических анализаторов операционнаясистема OS UNIX предоставляет специальное инструментальное средство, которое былоразработано К.С.

Леском и называется генератор лексических анализаторов LEX (далее потексту, генератор LEX). Его основными компонентами являются выполняемый модуль lex ибиблиотека объектных модулей стандартных функций libl.a (или разделяемый объектlibl.so), которые обычно располагаются, соответственно, в каталогах /usr/bin и/usr/lib файловой системы OS UNIX. Исходными данными для генератора LEX являетсявысокоуровневаяпроблемно-ориентированнаяспецификациялексем,которыедолженраспознавать проектируемый лексический анализатор во входном потоке символьных данных.Эта спецификация имеет формат текстового файла, который может быть подготовлен втекстовом редакторе и сохранен под произвольным именем, обычно с расширением .l, в любомдоступном каталоге файловой системы OS UNIX.Файл спецификации лексем должен иметь определенную внутреннюю структуру, в которой дляописания лексем используются шаблоны регулярных выражений.

В результате обработки файласпецификации лексем генератор LEX формирует исходный код проектируемого лексическогоанализатора на языке программирования C. Основная часть полученного исходного кодалексического анализатора реализует детерминированный конечный автомат, которыйгенератор LEX автоматически строит по заданным шаблонам регулярных выражений.Полученный исходный код при необходимости может быть отредактирован и легкопреобразуется в объектный модуль или выполняемый файл проектируемого лексическогоанализатораспомощьюстандартныхсредствкомпилирующейсистемыязыкапрограммирования C.Таким образом, практическое применение генератора LEX позволяет ограничить процедурупроектирования лексического анализатора составлением высокоуровневых спецификацийлексем, по которым автоматически порождается исходный код лексического анализатора наязыке программирования C.

Наиболее важным этапом рассмотренной технологии являетсяформирование файла спецификации лексем. Основные интеллектуальные проблемы, которыепри этом возникают, связаны с разработкой шаблонов регулярных выражений. Вопросыконструирования регулярных выражений и спецификации лексем подробно рассмотрены вследующих разделах предлагаемого учебного пособия.РЕГУЛЯРНЫЕ ВЫРАЖЕНИЯОБЩАЯ ХАРАКТЕРИСТИКА РЕГУЛЯРНЫХ ВЫРАЖЕНИЙВ теории формальных языков под регулярным выражением понимается алгебраическая записьмножества символьных слов, которая имеет вид формулы, где символы конечного алфавитачередуются со знаками регулярных операций.

Теоретически обосновано, что любое регулярноемножество слов, составленных из символов конечного алфавита, замкнуто относительнорегулярных операций объединения, конкатенации и итерации. Они образуют базовыйоперационный набор для конструирования регулярных выражений. Операция объединенияпредоставляет возможность выбора слов по любой из двух альтернатив. Конкатенацияиспользуется для слияния слов, когда одно слово приписывается к другому справа. Итерацияобеспечивает повторение слова произвольное число или ноль раз.Первоначально регулярные выражения были введены С. Клини для удобства формальногоописания множества регулярных событий в нейронных сетях средствами теории конечныхавтоматов.

В практическом программировании регулярные выражения были впервыеиспользованы К. Томпсоном в текстовом редакторе qed, на основе которого был разработанпопулярный в прошлом текстовый редактор ed для OS UNIX. Регулярные выражения edуступали по возможностям регулярным выражениям qed, но именно они получили широкоераспространение за пределами теоретических кругов. Одна из служебных команд edобеспечивала вывод на консоль строк редактируемого текстового файла, в которых найденосовпадение фрагментов текста с заданным регулярным выражением.

Эта функция оказаласьнастолько полезной, что была преобразована в отдельную утилиту grep (Global RegularExpression Print), которая в настоящее время широко используется в различных операционныхсредах для поиска информации в текстовых файлах на основе заданного регулярноговыражения. В настоящее время различные диалекты регулярных выражений активноприменяются в разнообразных инструментальных средствах, которые ориентированы наобработку текстовой информации. В частности, регулярные выражения применяются всценарных языках Perl, Tcl и Pyton, в текстовых редакторах, например, Emacs и vi, в языкахкомандных процессоров sh, csh, ksh, bash для OS UNIX, в генераторе отчетов awk, впотоковом редакторе sed и в других специализированных утилитах, ориентированных наобработку текстовых данных.ЭЛЕМЕНТЫ РЕГУЛЯРНЫХ ВЫРАЖЕНИЙГенератор LEX использует регулярные выражения для описания символьных конструкцийформального языка, обозначающих лексемы.

Регулярные выражения, которые обрабатываетгенератор LEX, строятся из обычных текстовых символов (литералов) и управляющихсимволов (метасимволов), которые обозначают знаки регулярных операций и выполняютслужебные функции. Генератор LEX использует расширенный набор регулярных операций,для обозначения которых применяются следующие метасимволы:" \ ^ $ / <> | [] . ? * + {} ()Перечисленные метасимволы имеют специальный смысл и выполняют определенныеслужебные функции в регулярных выражениях. Остальные отображаемые символы, например,буквы или цифры, считаются обычными символами и интерпретируются в регулярномвыражении в соответствии с их кодами ASCII.

Исключение составляет только символытабуляции, процента % и пробел, которые не могут быть непосредственно использованы врегулярных выражениях. Особый смысл этих символов связан с особенностями форматаспецификации лексем генератора LEX, где они применяются для конструирования служебныхразделителей.КОНКАТЕНАЦИЯ ЛИТЕРАЛОВВ простейшем случае регулярное выражение может состоять только из обычных текстовыхсимволов и интерпретируется как последовательность литералов. Например, регулярноевыражение:INTEGERсоставлено только из обычных символов и во входном потоке ему соответствует идентичнаяпоследовательность букв, которая образует слово INTEGER. Хотя в этом регулярномвыражении отсутствуют знаки операций, его следует формально интерпретировать какрезультат применения регулярной операции конкатенации, которая обеспечивает слияниезаданных букв в одно слово.ЭКРАНИРОВАНИЕ МЕТАСИМВОЛОВВ практике лексического анализа часто встречается ситуация, когда в регулярном выражениикакие-либо из метасимволов должны использоваться как литералы.

В этом случае их нужноэкранировать либо индивидуально с помощью символа обратной дробной черты (\), либо ввиде последовательности, заключенной в кавычки (").В частности, кавычки указывают, что заключенная в них последовательность должнарассматриваться как обычные текстовые символы. Например, следующее регулярноевыражение:ALPHA"++"удовлетворяет входной последовательности ALPHA++, где метасимволы, обозначенные знакомплюс, теряют свой специальный смысл, потому что их экранируют кавычки. Здесь, следуетобратить внимание, на то, что экранироваться может как вся строка, так и часть строки.