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

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

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

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

Как правило, лексические анализаторы действуют по следующему принципу:

1) очередной символ из входного потока данных добавляется в лексему всегда, когда он может быть туда добавлен;

2) как только символ не может быть добавлен в лексему, то считается, что он является границей лексемы и началом следующей лексемы.

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

Основная задача лексического анализатора – обнаружение лексемы во входном потоке и ее распознавание, т.е. определение класса к которому она относится.

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-12-27