2.1. Лексемы

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

Лексема – это пара вида (<тип лексемы>, <указатель>),

где <тип лексемы> – код лексемы (код или номер таблицы, в которой хранится лексема);

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

Основными лексемами являются: ключевые слова, идентификаторы, константы различных типов, метки, однолитерные и двухлитерные разделители.

2.2. Польская инверсная запись

Польская инверсная запись (ПОЛИЗ) была предложена польским математиком Я. Лукашевичем для записи выражений математической логики и впоследствии была расширена для использования в качестве промежуточной формы программы после синтаксического анализа. ПОЛИЗ является постфиксной бесскобочной записью выражений, в которой операторы следуют непосредственно за своими операндами в той последовательности, в которой они должны выполняться. Например, выражение A + B × C в ПОЛИЗ записывается как A B C × +, (A + B) × C – как A B + C ×, а A + B × (C + D) – как A B C D + × +.

Синтаксис арифметических выражений для бинарных операций в ПОЛИЗ можно описать БНФ-формулами:

<операнд> ::= <идентификатор> <константа>

<операнд> <операнд> <операция>

<операция> ::= + – × /

Унарный минус можно представлять двумя способами: либо записывать его как бинарный оператор, т. е. –В представлять в виде 0 – В, либо для унарного минуса ввести новый символ операции, например @, и использовать еще одно правило:

<операнд> ::= @ <операнд>.

Широкое использование польской инверсной записи в качестве промежуточной формы объясняется тем, что интерпретация выражений или генерация объектного кода по ПОЛИЗ выполняется путем однократного просмотра выражения слева направо с использованием стека. Например, интерпретация ПОЛИЗ выполняется следующим образом:

1. Если текущий символ ПОЛИЗ – операнд (идентификатор или константа), его значение записывается в стек и осуществляется переход к следующему символу.

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

3. Если текущий символ – унарный оператор, он применяется к верхнему операнду стека, который затем заменяется результатом выполнения оператора и осуществляется переход к следующему символу.

Пример интерпретации выражения 11 4 + 3 / 5 + приведен на рисунке.

Расширение ПОЛИЗ для представления других конструкций языков программирования (переменных с индексами, обращений к функциям, оператора присваивания, безусловного и условного переходов) выполняется очень просто: нужно только придерживаться правила, что оператор должен следовать непосредственно за соответствующими ему операндами.

СОДЕРЖИМОЕ МАГАЗИНА ПОЛИЗ

# 11 4 + 3 / 5 +

# 11 4 + 3 / 5 +

# 11 4 + 3 / 5 +

# 15 3 / 5 +

# 15 3 / 5 +

# 5 5 +

# 5 5 +

# 10

Основные операторы ПОЛИЗ приведены в табл. 2.1.

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

Оператор SUBS используется для представления в ПОЛИЗ переменных с индексами. Операнды оператора располагаются в определенном порядке: имя массива, значения индексных выражений и константа k (целое без знака), определяющая число операндов (число операндов оператора SUBS зависит от размерности массива и определяется по формуле k = n + 1, где n – размерность массива). Интерпретация оператора: из верхушки стека читается константа k, после чего из стека выталкиваются k операндов и производится обращение к процедуре, которая по имени массива и значениям индексных выражений определяет адрес элемента массива и помещает его в стек.

Оператор вызова функции FUNC так же, как и оператор SUBS, имеет переменное число операндов, которое зависит от числа аргументов функции. Порядок расположения операндов следующий: имя функции, значения аргументов, константа, определяющая число аргументов. Интерпретация оператора: из верхушки стека читается константа k, после чего из стека выталкиваются k операндов и вызывается функция F, которая по значениям аргументов вычисляет значение функции и помещает его в стек.

Таблица 2.1

Представление основных операторов в ПОЛИЗ

Оператор	Код	Операнды	Семантика оператора
Начало блока	BLBEG		Отмечает начало блока
Конец блока	BLEND		Отмечает конец блока
Вычисление адреса элемента массива	SUBS	A, i1, …, in, k	Вычисление адреса элемента массива А; i1, …, in– индексные выражения, k = n + 1 – число операндов операции
Вызов функции	CALL	F, x1, …, xn, k	Вызов функции F с аргументами x1, …, xn; k = n + 1 – число операндов операции
Преобразование типа целыйвещественный вещественныйцелый	ITOA ATOI	E E	Преобразование типа
Оператор присваивания	:=	R, E	Оператор присваивания R := E
Определение метки	DEFL	m	Определение метки m
Переход по метке	BRL	m	Переход на метку m (m – идентификатор метки)
Безусловный переход	BR	m	Безусловный переход на m (m – номер элемента ПОЛИЗ)
Переход по условию = 0 > 0 < 0 0 0	BZ BP BM BPZ BMZ	m, E	Переход на m (m – метка или номер элемента ПОЛИЗ) при выполнении соответствующего условия для выражения Е

Оператор преобразования типа ITOA (ATOI) имеет один операнд – преобразуемое значение. Интерпретация оператора: из стека удаляется операнд, его значение преобразуется в соответствии с заданным типом преобразования, после чего новое значение записывается в стек.

При переводе в ПОЛИЗ оператора присваивания сначала записывается левая часть оператора (простая переменная или переменная с индексом), затем правая часть (выражение), за которой следует знак операции присваивания. Интерпретация оператора присваивания: из стека выталкиваются два операнда, вычисляется выражение, представляющее собой правую часть оператора (верхний элемент стека), которое пересылается по адресу, определяемому первым операндом. Оператор присваивания вида j := k := 0 в ПОЛИЗ записывается как j 0 := k 0 :=.

Оператор определения метки записывается в ПОЛИЗ как m DEFL, где m – имя метки (идентификатор) помеченного оператора. При выполнении этого оператора имя метки связывается с номером элемента ПОЛИЗ, соответствующего началу помечаемого оператора, после чего операнд (имя метки) выталкивается из стека.

Оператор перехода по метке записывается в ПОЛИЗ как m BRL, где m – имя метки оператора, которому передается управление. Оператор BRL не порождает результирующего значения, при его выполнении операнд (имя метки) исключается из стека.

Условный оператор вида if E = 0 then S₁ else S₂ , где Е – арифметическое выражение, а S₁ и S₂ – операторы, представление которых в ПОЛИЗ известно, записывается в ПОЛИЗ как m₁ E BZ S₂ m₂ BR S₁. Здесь m₁ – номер элемента ПОЛИЗ, соответствующего началу представления в ПОЛИЗ оператора S₁, m₂ – номер элемента ПОЛИЗ, следующего за условным оператором, BZ – оператор перехода по нулю, BR – оператор перехода к элементу ПОЛИЗ с номером m. Переход по нулю BZ имеет два операнда: значение арифметического выражения и номер элемента ПОЛИЗ, к которому осуществляется переход, если значение арифметического выражения равно нулю. Оператор BZ не создает результирующего значения, поэтому его выполнение завершается удалением из стека его операндов. Наряду с переходом по нулевому значению можно ввести и другие операторы перехода по условию (см. табл.2.1): BP – переход по положительному значению, BM – переход по отрицательному значению, BPZ – переход по нулю или положительному значению, BPN – переход по нулю или отрицательному значению. Для каждого нового оператора условного перехода необходимо составить процедуру для его интерпретации.

Если условие в условном операторе задается отношением вида

E1 = E2, то оно должно быть приведено к виду E1 – E2 = 0.