Назначение лексического анализатора

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

…

begin

for i:=1 to N do

fg := fg * 0.5;

...

Таблица 1

Лексемы программы

Поле “Значение” в табл. 1 подразумевает некое кодовое значение, которое бу­дет помещено в итоговую таблицу лексем в результате работы лексического ана­лизатора. Конечно, значения, которые записаны в примере, являются услов­ными. Конкретные коды определяются при реализации компилятора. Важно отметить также, что для идентификаторов устанавливается связка таблицы лек­сем с таблицей идентификаторов (в примере это отражено некоторым индексом, следующим после идентификатора за знаком :, а в реальном компиляторе все опять же определяется его реализацией).

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