Системное программное обеспечение. Лабораторный практикум

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

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

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

В большинстве компиляторов лексический и синтаксический анализаторы – это взаимосвязанные части. Где провести границу между лексическим и синтаксическим анализом, какие конструкции анализировать сканером, а какие – синтаксическим распознавателем, решает разработчик компилятора. Как правило, любой анализ стремятся выполнить на этапе лексического разбора входной программы, если он может быть там выполнен. Возможности лексического анализатора ограничены по сравнению с синтаксическим анализатором, так как в его основе лежат более простые механизмы. Более подробно о роли лексического анализатора в компиляторе и о его взаимодействии с синтаксическим анализатором можно узнать в [1–4, 7].

Проблема определения границ лексем

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

Иллюстрацией такого случая может служить пример оператора программы на языке Фортран, когда по части текста DO 10 I=1… невозможно определить тип оператора (а соответственно, и границы лексем). В случае DO 10 I=1.15 это будет присвоение вещественной переменной DO10I значения константы 1.15 (пробелы в Фортране игнорируются), а в случае DO 10 I=1,15 это цикл с перечислением от 1 до 15 по целочисленной переменной I до метки 10.

Другая иллюстрация из более современного языка программирования C++ – оператор присваивания k=i+++++j;, который имеет только одну верную интерпретацию (если операции разделить пробелами): k = i++ + ++j;.

Если невозможно определить границы лексем, то лексический анализ исходного текста должен выполняться поэтапно. Тогда лексический и синтаксический анализаторы должны функционировать параллельно, поочередно обращаясь друг к другу. Лексический анализатор, найдя очередную лексему, передает ее синтаксическому анализатору, тот пытается выполнить анализ считанной части исходной программы и может либо запросить у лексического анализатора следующую лексему, либо потребовать от него вернуться на несколько шагов назад и попробовать выделить лексемы с другими границами. При этом он может сообщить информацию о том, какую лексему следует ожидать. Более подробно такая схема взаимодействия лексического и синтаксического анализаторов описана в [3, 7].

Параллельная работа лексического и синтаксического анализаторов, очевидно, более сложна в реализации, чем их последовательное выполнение. Кроме того, такой подход требует больше вычислительных ресурсов и в общем случае большего времени на анализ исходной программы, так как допускает возврат назад и повторный анализ уже прочитанной части исходного кода. Тем не менее сложность синтаксиса некоторых языков программирования требует именно такого подхода – рассмотренный ранее пример программы на языке Фортран не может быть проанализирован иначе.

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