The OpenNET Project / Index page

[ новости /+++ | форум | теги | ]

Каталог документации / Раздел "Программирование в Linux" / Оглавление документа
next up previous contents
Next: Команда lex Up: LEX - лексический анализатор Previous: LEX - лексический анализатор   Contents

Введение

Пусть заданы некоторое конечное множество слов (лексем) в некотором языке и некоторое входное слово. Лексический анализ - это распознавание лексем в определенном входном потоке. Необходимо установить, какой элемент множества (если он существует) совпадает с данным входным словом. Обычно лексический анализ выполняется так называемым лексическим анализатором (ЛА). ЛА - это программа, 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:

\includegraphics[ scale=0.45]{lex_ris.eps}

Рис. 15. Схема использования LEX

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

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



2004-06-22



Партнёры:
PostgresPro
Inferno Solutions
Hosting by Hoster.ru
Хостинг:

Закладки на сайте
Проследить за страницей
Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру