Введение

Пусть заданы некоторое конечное множество слов (лексем) в некотором языке и некоторое входное слово. Лексический анализ - это распознавание лексем в определенном входном потоке. Необходимо установить, какой элемент множества (если он существует) совпадает с данным входным словом. Обычно лексический анализ выполняется так называемым лексическим анализатором (ЛА). ЛА - это программа, LEX - генератор программ лексического анализа. Лексический анализ применяется во многих случаях, например, для построения редакторов или в качестве распознавателя директив в диалоговой программе и т.д. Однако наиболее важное применение ЛА - использование его в различного рода компиляторах, где он выполняет функцию программы ввода данных. ЛА выполняет первую стадию компиляции: читает строки компилируемой программы, выделяет лексемы и передает их на дальнейшие стадии компиляции (синтаксический анализ и генерацию кода). ЛА распознает тип каждой лексемы и соответствующим образом помечает ее. Например, при компиляции программы на языке Си могут быть выделены следующие типы лексем: число, идентификатор, оператор и др. Необходимо не только выделить лексему, но и выполнить некоторые преобразования. Например, если лексема - число, то его необходимо перевести во внутреннюю (двоичную) форму записи как число с плавающей или фиксированной точкой. Если лексема - идентификатор, то его необходимо разместить в таблице для того, чтобы в дальнейшем обращаться к нему не по имени, а по адресу в таблице. Хотя лексический анализ по идее достаточно прост, эта фаза работы компилятора часто занимает больше времени, чем любая другая. Частично это происходит из-за необходимости просматривать и анализировать исходный текст символ за символом. Происходит это потому, что часто бывает трудно определить, где проходят границы лексемы. Пусть имеются две лексемы:make и makefile. Пусть из входного потока поступает набор литеральных символов:...makefile....

При анализе входного потока может быть выделена лексема make, хотя правильно было бы выделить лексему makefile. Единственный способ преодолеть это затруднение - просмотр полученной цепочки вперед и назад. В примере при выделении лексемы make нужно просмотреть следующий поступающий литерал, и, если он будет символом f, то вполне возможно, что поступает лексема makefile. Процесс просмотра входного потока можно рассматривать как движение рамки влево и вправо над цепочкой символов. При этом анализируется только тот символ, который охвачен рамкой:

... . . source make.f.ile file compiler . . ... Анализ заключается в определении соответствия рассматриваемой последовательности некоторому, так называемому регулярному выражению. Например, регулярное выражение (\+?[0-9])+|(-?[0-9])+ позволяет выделить во входном потоке все лексемы типа целое, перед которыми либо стоит знак (+ или -), либо не стоит.

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

Для любого компилятора можно выделить три языка:

1. входной - язык, который анализируется компилятором.
2. рабочий - язык, на котором написан сам компилятор.
3. выходной - язык, который появляется в результате работы компилятора.

LEX частично или полностью автоматизирует процесс написания программы лексического анализа. Генерируемые с помощью LEX ЛА описываются на языке LEX. Последовательность использования LEX схематически показана на рис. 15:

Таким образом в этой последовательности можно выделить три этапа:

1. С помощью команды lex из файла (например, program.lex), описывающего ЛА некоторого языка и написанного на языке LEX (входной язык для lex), получается файл (например, lex.yy.c) с текстом ЛА на языке Си (выходной язык для lex).
2. С помощью команды cc из файла (lex.yy.c) на языке Си (входной язык для cc) получается исполняемый файл (например, a.out) с машинными кодами (выходной язык для cc), непосредственно реализующими ЛА.
3. После запуска исполняемого файла (a.out) осуществляется интерактивный лексический анализ вводимого с клавиатуры текста или лексический анализ файла, написанного на некотором языке (входной язык ЛА), и, возможно, вывод на экран или в файл информации, связанной с разбором (выходной язык ЛА). Гибкие возможности системы UNIX по управлению потоками позволяют использовать входной и выходной файлы и на этом этапе.