Перевод описаний переменных и процедурных блоков в ОПЗ
В компиляторах обработка описаний переменных необходима для:
- выявления типов данных;
- подготовки информации для распределения памяти;
- выделения в объектной программе места для размещения данных.
Очевидно, что распределение памяти в объектной программе всегда должно предшествовать ее генерации. Поскольку исходная программа может содержать вложенные процедуры, то область действия идентификаторов, описанных во вложенных процедурах, является локализованной в пределах процедуры. Компилятор должен учитывать это обстоятельство и располагать информацией о начале и конце процедуры.
Приведем пример обработки описаний данных на базе описанного выше подмножества языка PL/1.
В этом языке программирования имеется несколько типов данных:
DEC FLOAT - десятичное число с плавающей точкой;
DEC FIXED - десятичное число с фиксированной точкой;
BIN FIXED FIXED - двоичное число с фиксированной точкой;
CHAR – символьная строка.
Сопоставим этим конструкциям языка в ОПЗ операцию типа, формат которой имеет вид:
Список переменных k ТИП,
где k – количество описываемых переменных;
Поясним операцию типа, для чего предположим, что в программе описано несколько переменных
DCL (A,B,C) DEC FLOAT
С учетом операции типа построенная ОПЗ этого описания примет следующий вид:
A B C 3 DFT
Рассмотрим далее следующие операции описания процедур:
- начало процедуры - имеет два операнда: номер процедуры, уровень процедуры
<номер><уровень> НП
- конец процедуры - не имеет операндов
КП
- конец описания - имеет два операнда: номер процедуры, уровень процедуры
<номер><уровень>КО
Операторы начала и конца процедуры и описания данных в исходной программе являются неисполняемыми. Им можно присвоить самый низкий приоритет в таблица приоритетов, после чего она примет следующий вид (табл. 2.7).
Таблица 2.7
| Входной элемент | Приоритет |
| IF ( [ АЭМ Ф | |
| , ; ) ] THEN ELSE | |
| := GOTO | |
| V | |
| & | |
| Отношения | |
| + - | |
| * / | |
| возведение в степень | |
| : PROC END DCL |
Сам алгоритм Дейкстры с учетом обработки описательных операторов модифицируется следующим образом:
- символ PROC из входной строки заносится в стек, при этом в стек с ним также заносятся номер и уровень процедуры;
- символа DCL из входной строки заносится в стек с номером и уровнем процедуры и начальным значением счетчика операндов, равным 1;
- символ описания типа помещается в вершину стека;
- символ ',' из входной строки в зависимости от верхнего элемента стека выполняет различные функции:
o если в вершине стека находится оператор DCL, значение счетчика операндов наращивается на 1 (запятая между операндами);
o если в вершине стека находится символ описания типа, он выталкивает его из стека, помещает в выходную строку операцию ТИП со значением счетчика из оператора DCL и счетчик операндов принимает начальное значение 1 (запятая между символами описания типа);
- символ END из входной строки всегда заносится в стек;
- символ ';' из входной строки в зависимости от верхнего элемента стека выполняет различные функции:
o если в вершине стека находится оператор PROC, то рассматриваемый символ выталкивает его из стека, занося в выходную строку операцию начала процедуры с ее номером и уровнем;
o если в вершине стека находится оператор DCL, точка с запятой выталкивает его из стека, записывая в выходную строку операцию конца описания с номером и уровнем процедуры;
o если в вершине стека находится символ описания типа, то рассматриваемый символ обрабатывает его аналогично запятой, а затем применяется к следующему в стеке оператору DCL;
o если в вершине стека находится оператор END, точка с запятой выталкивает его из стека, записывая в выходную строку операцию конца процедуры;
- символ '.' выталкивает из стека оператор END, записывая в выходную строку операцию конца процедуры.
Например, алгоритм перевода программы
PROC F1;
DCL (A,B) DEC FIXED,
D DEC FLOAT;
PROC F2;
DCL (C,D) BIN FIXED;
END;
END.
выглядит следующим образом:
| Выходная строка | F1 | 1 1 НП | A | B | |||||
| С Т Е К | PROC 1,1 | DCL 1,1,1 | ( | ( | DCL 1,1,2 | ||||
| DCL 1,1,1 | DCL 1,1,2 | ||||||||
| Входная строка | PROC | F1 | ; | DCL | ( | A | , | B | ) |
| Выходная строка | 2 DFD | D | DFT | 1 1 КО | F2 | 2 2 НП | |||
| С Т Е К | DFD | DCL 1,1,1 | DFT | DCL 1,1,1 | PROC 2,2 | ||||
| DCL 1,1,2 | DCL 1,1,1 | ||||||||
| Входная строка | DEC FIXED | , | D | DEC FLOAT | ; | PROC | F2 | ; |
| Выходная строка | C | D | 2 BFD | 2 2 КО | |||||
| С Т Е К | DCL 2,2,1 | ( | ( | DCL 2,2,2 | BFD | DCL 2,2,1 | |||
| DCL 2,2,1 | DCL 2,2,2 | DCL 2,2,2 | |||||||
| Входная строка | DCL | ( | C | , | D | ) | BIN FIXED | ; |
| Выходная строка | КП | КП | ||
| СТЕК | END | END | ||
| Входная строка | END | ; | END | . |
Таким образом, ОПЗ рассмотренной программы имеет следующий вид:
F1 1 1 НП A B 2 DFD D DFT 1 1 КО F2 2 2 НП C D 2 BFD 2 2 КО КП КП
2.10 Комплексный пример перевода исходной программы в ОПЗ
Рассмотрим комплексный пример перевода исходной программы на языке, описанном в лабораторной работе № 1, в обратную польскую запись.
PROC MAIN;
DCL (A1, A2) DEC FIXED;
A1=378;
A2=.73;
PROC CALC;
DCL (SUM, MULT) DEC FIXED;
IF A1+A2<>3.2 THEN GOTO P;
SUM=(A1+A2)*A2;
P: MULT=A1*A2;
END;
END.
Прежде всего, составим таблицу приоритетов, включив в нее все операции и операторы, имеющиеся во входном языке (табл. 2.8). Для этого воспользуемся обозначениями операторов и операций, которые были введены в лабораторной работе № 1.
Таблица 2.8
| Приоритет | Входной элемент | Обозначение |
| IF | W6 | |
| ( | R4 | |
| THEN | W8 | |
| . | R6 | |
| , | R2 | |
| ; | R3 | |
| ) | R5 | |
| GOTO | W5 | |
| = | O5 | |
| < | O3 | |
| > | O4 | |
| + | O1 | |
| * | O2 | |
| PROC | W7 | |
| END | W3 | |
| DCL | W2 | |
| : | O6 |
Привычное представление процесса перевода исходной программы в ОПЗ на основе алгоритма Дейкстры имеет следующий вид:
| Выходная строка | MAIN | 1 1 НП | A1 | A2 | |||||
| С Т Е К | PROC 1,1 | DCL 1,1,1 | ( | ( | DCL 1,1,2 | ||||
| DCL 1,1,1 | DCL 1,1,2 | ||||||||
| Входная строка | PROC | MAIN | ; | DCL | ( | A1 | , | A2 | ) |
| Выходная строка | 2 DFD | 1 1 КО | A1 | := | A2 | .73 | := | CALC | |||||
| С Т Е К | DFD | DCL 1,1,1 | := | := | PROC 2,2 | ||||||||
| DCL 1,1,2 | |||||||||||||
| Входная строка | DEC FIXED | ; | A1 | := | ; | A2 | := | .73 | ; | PROC | CALC |
| Выходная строка | 2 2 НП | SUM | MULT | 2 BFD | 2 2 КО | |||||
| С Т Е К | DCL 2,2,1 | ( | ( | DCL 2,2,2 | BFD | DCL 2,2,1 | ||||
| DCL 2,2,1 | DCL 2,2,2 | DCL 2,2,2 | ||||||||
| Входная строка | ; | DCL | ( | SUM | , | MULT | ) | BIN FIXED | ; |
| Выходная строка | A1 | A2 | + | 3.2 | > | M1 УПЛ | P | БП | М1: | SUM | A2 | A1 | + | := | |||||
| С Т Е К | IF | + | > | IF | IF M1 | GOTO | IF M1 | := | + | := | |||||||||
| IF | IF | IF M1 | := | ||||||||||||||||
| Входная строка | IF | A1 | + | A2 | > | 3.2 | THEN | GOTO | P | ; | SUM | := | A2 | + | A1 | ; |
| Выходная строка | P | : | MULT | A1 | A2 | SUM | + | * | := | КП | КП | ||||||
| С Т Е К | := | * | ( | + | * | := | END | END | |||||||||
| := | * | ( | := | ||||||||||||||
| := | * | ||||||||||||||||
| := | |||||||||||||||||
| Входная строка | P | : | MULT | = | A1 | * | ( | A2 | + | SUM | ) | ; | END | ; | END | . |
Полученная в результате перевода ОПЗ программы имеет вид:
MAIN 1 1 НП A1 A2 2 DFD 1 1 КО A1 378 := A2 .73 := CALC2 2 НП
SUM MULT 2 BFD 2 2 КО A1 A2 + 3.2 > M1 УПЛ P БП М1: SUM A2 A1 + :=
P : MULT A1 A2 SUM + * := КП КП
Для наглядности в рассмотренном примере текст программы представлен на исходном языке, но в реальном трансляторе входной текст является результатом работы лексического анализатора. В нем уже выделены и классифицированы лексемы, но в остальном работа протекает в соответствии с описанным выше примером.