2.4. Особенности построения интерпретаторов и их взаимодействие с компиляторами

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

Во-вторых, надо учитывать недостатки и преимущества интерпретаторов.

Недостатки интерпретаторов:

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

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

– при исполнении программы интерпретатор постоянно должен находиться в ОП, что снижает эффективное использование ОП.

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

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

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

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

Характерным примером интерпретирующего языка может служить HTML – язык описания гипертекстов. На его основе функционируют практически все структуры Интернета.

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

– сначала исходная программа компилируется в промежуточный код;

– результат компиляции интерпретируется с помощью интерпретатора промежуточного языка.

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

Лекция 8

3. Лексический анализ

3.1. Лексические анализаторы (сканеры)

3.1.1. Назначение сканера

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

В основном сканеры выполняют две функции:

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

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

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

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

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

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

Дескриптор – это пара вида:

(тип лексемы, указатель),

где тип лексемы – это, как правило, числовой код класса лексемы, который означает, что лексема принадлежит одному из конечного множества классов слов, выделенных в языке программирования;

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

Пример 3.1.

На вход лексического анализатора поступает цепочка символов:

PROGRAM PRIMER;

VAR X, Y, Z: REAL;

BEGIN

X: = 5;

Y: = 5;

Z: = X + Y;

END.

Определить выход лексического анализатора в виде таблиц и дескрипторного текста.

Прежде, чем определить дескрипторный образ каждой лексемы укажем коды типов лексем. В качестве кодов типов лексем используем следующие числа:

10 – ключевое слово;

20 – разделитель;

30 – идентификатор;

40 – константа.

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

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

Сканер для Примера 3.1 имеет следующие внутренние таблицы: таблица ключевых слов (табл. 2) и таблица разделителей (табл. 3).

Таблица 2

Таблица ключевых слов

№ п/п	Ключевое слово
1	PROGRAM
2	BEGIN
3	END
4	FOR
5	REAL
6	VAR
….	….

Таблица 3

Таблица разделителей

№ п/п	Разделитель
1	;
2	,
3	+
4	–
5	/
6	
7	:
8	=
9	.
….	….

Тогда на выходе сканера будут таблицы: таблица идентификаторов (табл. 4) и таблица констант (табл. 5).

Таблица 4

Таблица идентификаторов

№ п/п	Идентификатор
1	PRIMER
2	X
3	Y
4	Z

Таблица 5

Таблица констант

№ п/п	Значение константы
1	5

И дескрипторный текст:

(10,1) (30,1) (20,1)

(10,6) (30,2) (20,2) (30,3) (20,2) (30,4) (20,7) (10,5) (20,1)

(10,2)

(30,2) (20,7) (20,8) (40,1) (20,1)

(30,3) (20,7) (20,8) (40,1) (20,1)

(30,4) (20,7) (20,8) (30,2) (20,3) (30,3) (20,1)

(10,3) (20,9)

Вопросы слушателям. Почему в табл. 2 и 3 в последней строке указано многоточие? Каким образом получена пятая строка дескрипторного текста?