Лексический анализ.

Parser Generator
Инструментарий для построения компиляторов.

Главная

О сайте

Документация

Download

Ссылки

Библиография

О нас

Лексический анализ.

Любой текст представляет собой набор символов, который необходимо проанализировать. Самая первая задача, которая встает перед компилятором- выделение из этого набора символов лексем- синтаксически значимых единиц. К лексемам относятся ключевые слова, знаки операций, числа, строки, разделители, идентификаторы. Таким образом, лексический анализ "укрупняет" единицы анализа. Можно, конечно, написать грамматику, на вход которой можно подавать простой поток символов, но это связано с большими трудностями и неэффективно. Лексические анализаторы еще называют сканерами.

Лексический анализ требует значительного времени, так как ему достается самая "черновая" работа. В его задачи входит: выделять из текста лексемы и определять, к какому классу они относятся (какой терминал представляют). В некоторых реализациях еще необходимо строить различные таблицы (например идентификаторов, в которые заносится информация о типах идентификаторов и их значениях).

Результат своей работы лексический анализатор передает синтаксическому анализатору в виде последовательности лексем. Существует две стратегии лексического анализа:

Анализ по шагам- при котором синтаксический анализатор по мере своей работы запрашивает у лексического анализатора очередную лексему. Сканер при таком запросе выполняет анализ необработанной части текста, выделяя очередную лексему и возвращая ее парсеру.

Анализ сразу всего текста. В этом случае сканер обрабатывает сразу весь текст, строя список лексем.

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

Интерфейс ITokenizer

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

ITokenizer
BOOL	hasMoreToken ( ) // Этот метод определяет есть ли еще во входном потоке лексемы. Возвращает TRUE, если поток еще содержит лексемы и FALSE в противном случае.
Token::ptr	nextToken ( ) // Возвращает следующую лексему, либо возбуждает исключение, если лексемы закончились.

Класс ITokenizer определят общий для всех сканеров интерфейс. С помощью этого интерфейса все классы-наследники будут использоваться сканерами.

Хочется также отметить, что второй вариант лексического анализатора также может использовать данный интерфейс. Например при первом своем запуске, он целиком сканирует входной поток, составляет список лексем, а затем по одной возвращает через метод nextToken.

Применение регулярных выражений для лексического анализа. Класс RETokenizer

Мощным инструментом для лексического анализа являются регулярные выражения. Регулярные выражения (РВ) успешно используются во многих приложениях. Фактически РВ- это краткий способ описания множества цепочек. Когда они только появились, они полностью соответствовали автоматным грамматикам и можно было сказать, что РВ- другой способ записи автоматной грамматики. Однако вскоре появились множество расширений, которые увеличили класс языков, определяемых РВ. Но даже классический вариант РВ позволяет эффективно описывать цепочки символов определенного вида.

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

Вот пример, описывающий лексемы практически любого языка программирования.

Целое число: [0-9]+

Вещ число: [0-9]*\.[0-9]+

Идентификатор: [A-Za-z_][A-Za-z_0-9]*

Ключевое слово if: if

Ключевое слово while: while

Знак операции + : \+

Знак операции ++ : \+\+

...

Как видно практически любой тип лексемы можно задать с помощью регулярного выражения. Однако возникает проблема: одна лексема может подходить под шаблоны нескольких регулярных выражений. Например, ключевое слово if может быть распознано и как идентификатор. Для избежания таких конфликтов, можно использовать приоритеты. Каждому РВ задается приоритет и в случае конфликта выбирается тот вариант, у которого приоритет выше. Таким образом, задав слову if приоритет более высокий, чем у идентификатора можно избавиться от этой проблемы.

Еще одна проблема заключается в том, что начало одно лексемы может совпадать с другой, например начало идентификатора переменной while1 совпадает с ключевым словом while. Эту проблему можно решить, рассматривая самые длинные цепочки.

Для лексического анализа на основе РВ используется класс RETokenizer. Этот класс осуществляет анализ входного текста поставляя лексемы через реализуемый интерфейс ITokenizer.

RETokenizer
void	addTermRE ( Term::ptr p_t , string p_re , int p_priority ) // Добавляет регулярное выражение для терма p_t. Если в тексте встретится цепочка, которая будет отнесена к данному РВ, то метод nextToken вернет токен, типа p_t.
BOOL	hasMoreToken ( ) // Этот метод определяет есть ли еще во входном потоке лексемы. Возвращает TRUE, если поток еще содержит лексемы и FALSE в противном случае.
Token::ptr	nextToken ( ) // Возвращает следующую лексему, либо возбуждает исключение, если лексемы закончились.

Класс RETokenizer реализует интерфейс ITokenizer.

Для того, чтобы сконфигурировать сканер нужно задать РВ и приоритет для каждого терминала.

ukman@yandex.ru