Материал: LabWork2

Теоретические сведения

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

Лексический анализатор (сканер) читает поток символов,

составляющих исходную программу, и группирует эти символы в значащие последовательности, называющиеся лексемами.

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

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

‹имя_токена, значение_атрибута›

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

Предположим, например, что исходная программа содержит инструкцию присваивания a = b + c * d

Символы в этом присваивании могут быть сгруппированы в следующие лексемы и отображены в следующие токены:

1)a представляет собой лексему, которая может отображаться в токен ‹id, 1›, где id – абстрактный символ, обозначающий идентификатор, а 1 указывает запись в таблице идентификаторов для a, в которой хранится такая информация как имя и тип идентификатора;

2)cимвол присваивания = представляет собой лексему, которая отображается в токен ‹=›. Поскольку этот токен не требует значения атрибута, второй компонент данного токена

1

опущен. В качестве имени токена может быть использован любой абстрактный символ, например, такой, как «assign», но для удобства записи в качестве имени абстрактного символа можно использовать саму лексему;

3)b представляет собой лексему, которая отображается в токен ‹id, 2›, где 2 указывает на запись в таблице идентификаторов для b;

4)+ является лексемой, отображаемой в токен ‹+›;

5)c – лексема, отображаемая в токен ‹id, 3›, где 3 указывает на запись в таблице идентификаторов для c;

6)* – лексема, отображаемая в токен ‹*›;

7)d – лексема, отображаемая в токен ‹id, 4›, где 4 указывает на запись в таблице идентификаторов для d.

Пробелы, разделяющие лексемы, лексическим анализатором пропускаются.

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

‹id, 1›‹=›‹id, 2›‹+›‹*›‹id, 3›‹id, 4›.

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

Чтобы увидеть использование этих концепций на практике, рассмотрим инструкцию на языке программирования Си

printf("Total = %d\n", score);

в которой printf и score представляют собой лексемы, соответствующие токену id, a "Total = %d\n" является лексемой, соответствующей токену literal.

Таблица 1. Примеры токенов

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

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

2

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

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

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

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

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

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

Работу синтаксического и лексического анализаторов можно изобразить в виде схемы, приведённой на рисунке 1.

Таблица

идентификаторов

Рисунок 1. Взаимодействие лексического анализатора с синтаксическим

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

Иллюстрацией такого случая может служить пример оператора присваивания из языка программирования Си

k = i+++++j;

который имеет только одну верную интерпретацию (если операции разделить пробелами):

3

k = i++ + ++j;

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

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

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

k = i++ ++ +j;

что неверно. Компилятор gcc в этом случае выдаст сообщение об ошибке: lvalue required as increment operand – в качестве операнда оператора инкремента требуется l-значение. Любые неоднозначности при анализе данного оператора присваивания могут быть исключены только в случае правильной расстановки пробелов в исходной программе.

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

– указатель на информацию о лексеме, может быть включён и третий столбец – тип лексем. Не

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

Вот пример фрагмента текста программы на языке Паскаль и соответствующей ему таблицы лексем:

...

begin

for i:=1 to N do fg := fg * 0.5

...

4

Таблица 2. Таблица лексем программы

В таблице 2 поле «значение» подразумевает некое кодовое значение, которое будет помещено в итоговую таблицу лексем. Значения, приведённые в примере, являются условными. Конкретные коды выбираются разработчиками при реализации компилятора. Связь между таблицей лексем и таблицей идентификаторов отражена в примере некоторым индексом, следующим после идентификатора за знаком «:». В реальном компиляторе эта связь определяется его реализацией.

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

В качестве примера возьмем входной язык, содержащий операторы цикла for (…; …; …) do …, разделённые символом ; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, десятичные числа с плавающей точкой (в обычной и экспоненциальной форме), знак присваивания (:=).

Описанный выше входной язык может быть задан с помощью КС-грамматики G ({for, do,

‘:=’, ‘<’, ‘>’, ‘=’, ‘-’, ‘+’, ‘(‘, ‘)’, ‘;’, ‘.’, ‘_’, ‘a’, ‘b’, ‘c’, ..., ‘x’, ‘y’, ‘z’, ‘A’, ‘B’, ‘C’, ..., ‘X’, ‘Y’, ‘Z’, ‘0’, ‘1’, ‘2’, ’3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’}, {S, A, B, C, I, L, N, Z}, P, S) с правилами Р (правила представлены в расширенной форме Бэкуса-Наура):

S for (A; A; A;) do A; | for (A; A; A;) do S; | for (A; A; A;) do A; S

A I := B

B C > C | C < C | C = C

C I | N

I (_ | L) {_ | L | Z | 0}

N [- | +] ({0 | Z} . {0 | Z} | {0 | Z}. | {0 | Z}) [(e | E) [- | +]{0 | Z}][f | l | F | L]

L a | b | c | … | x | y | z | A | B | C | … | X | Y | Z

Z 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Целевым символом грамматики является символ S. Лексемы входного языка разделим на несколько классов:

ключевые слова языка (for, do) – класс 1;

разделители и знаки операций (‘(‘, ‘)’, ‘;’, '<', ‘>’, ‘=’) – класс 2;

знак операции присваивания (‘:=’) – класс 3;

идентификаторы – класс 4;

5