Принципы построения лексических анализаторов

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

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

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

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

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

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

Как правило, сканеры действуют по следующему принципу: очередной символ из входного потока данных добавляется в лексему всегда, когда он может быть туда добавлен. Как только символ не может быть добавлен в лексему, то считается, что он является границей лексемы и началом следующей лексемы (если символ не является пустым разделителем – пробелом, символом табуляции или перево­да строки, знаком комментария). Такой принцип не всегда позволяет правильно определить границы лексем в том случае, когда они не разделены пустыми сим­волами. Например, приведенная выше строка языка С k=i+++++j; будет разбита на лексемы следующим образом: k=i+++++j;—и это разбиение неверное, ком­пилятор должен будет выдать пользователю сообщение об ошибке, хотя правильный вариант распознавания строки существует.

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

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

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

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

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

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