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

Лексема (лексическая единица языка) — это структурная единица языка, кото­рая состоит из элементарных символов языка и не содержит в своем составе дру­гих структурных единиц языка.

Лексемами языков естественного общения являются слова. Лексемами языков программирования являются идентификаторы, константы, ключевые слова язы­ка, знаки операции и т. п. Состав возможных лексем каждого конкретного языка программирования определяется синтаксисом этого языка. Лексический анализатор (или сканер) — это часть компилятора, которая читает исходную программу и выделяет в ее тексте лексемы входного языка. На вход лексического анализатора поступает текст исходной программы, а выходная ин­формация передается для дальнейшей обработки компилятором на этапе син­таксического анализа и разбора.

Результатом работы лексического анализатора является перечень всех найденных в тексте исходной программы лексем с учетом характеристик каждой лексемы. Этот перечень лексем можно представить в виде таблицы, называемой таблицей лексем. Каждой лексеме в таблице лексем соответствует некий уникальный ус­ловный код, зависящий от типа лексемы, и дополнительная служебная информа­ция. Кроме того, информация о некоторых типах лексем, найденных в исходной программе, должна помещаться в таблицу идентификаторов (или в одну из таб­лиц идентификаторов, если компилятор предусматривает различные таблицы идентификаторов для различных типов лексем).

Лексический анализатор имеет дело с такими объектами, как Различного рода константы и идентификаторы (к последним относятся и ключевые слова). Язык констант и идентификаторов является регулярным — то есть может быть описан с помощью регулярных грамматик. Распознавателями для регулярных языков являются конечные автоматы. Следовательно, основой для реализации лексиче­ских анализаторов служат регулярные грамматики и конечные автоматы.

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

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

· определить границы лексем, которые в тексте исходной программы явно не указаны;

· выполнить действия для сохранения информации об обнаруженной лексеме (или выдать сообщение об ошибке, если лексема неверна).

Эти действия связаны с определенными проблемами. Далее рассмотрено, как эти проблемы решаются в лексических анализаторах.

Определение границ лексем

Выделение границ лексем является нетривиальной задачей. Ведь в тексте исход­ной программы лексемы не ограничены никакими специальными символами. Если говорить в терминах лексического анализатора, то определение границ лек­сем — это выделение тех строк в общем потоке входных символов, для которых надо выполнять распознавание.

В большинстве компиляторов лексический и синтаксический анализа­торы — это взаимосвязанные части. Возможны два принципиально различных метода организации взаимосвязи лексического и синтаксического анализа:

· последовательный;

· параллельный.

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

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

Выполнение действий, связанных с лексемами

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

В конечном автомате, лежащем в основе лексического анализатора, эти действия можно отобразить довольно просто — достаточно иметь возможность с каждым переходом на графе автомата (или в функции переходов автомата) связать вы­полнение некоторой произвольной функции f(q, a), где q — текущее состояние автомата, a — текущий входной символ. Функция f(q, a) может выполнять любые действия, доступные лексическому анализатору:

· помещать новую лексему в таблицу лексем;

· проверять наличие найденной лексемы в таблице идентификаторов;

· добавлять новую лексему в таблицу идентификаторов;

· выдавать сообщения пользователю о найденных ошибках и предупреждения об обнаруженных неточностях в программе;

· прерывать процесс компиляции.

Возможны и другие действия, предусмотренные реализацией компилятора. Такую функцию f(q, a), если она есть, обычно записывают на графе переходов конечного автомата под дугами, соединяющими состояния автомата. Функция f(q, a) может быть пустой (не выполнять никаких действий), тогда соответствующая запись отсутствует.