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

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

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

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

Иллюстрацией такого случая может служить пример оператора программы на языке Фортран, когда по части текста 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++ принято соглашение, что при возникновении проблем с определением границ лексемы всегда выбирается лексема максимально возможной длины.

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

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

Оглавление книги