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

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

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

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

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

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

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

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

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

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

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

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

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

Статьи к прочтению:

Cинтаксический анализ. Нисходящий синтаксический анализ

Похожие статьи: