Лексические анализаторы

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

Язык естественного общения

идентификаторы,
константы,
ключевые слова языка,
знаки операций и т. п.

слова

Язык программирования

Состав возможных лексем
каждого конкретного языка программирования
определяется синтаксисом этого языка.

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

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

применение ЛА упрощает работу с текстом исходной программы на этапе синтаксического разбора и сокращает объем обрабатываемой информации;

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

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

ЛА структурирует поступающий на вход
исходный текст программы и выкидывает
всю незначащую информацию

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

комментарии, незначащие пробелы, символы табуляции, перевода строки;

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

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

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

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

Организация взаимосвязи лексического и синтаксического анализа

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

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

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

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

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

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

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

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

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

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

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