DIPLOM (663709), страница 6

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

Текст из файла (страница 6)

ПолИЗ: abc*+dab+/-

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

Результат выполнения операции фиксируется в виде рабочей переменной вида r_j . После очередной операции рабочая переменная r₁ или r₂ вычеркивается, освободившуюся рабочую переменную можно использовать вновь для записи результата операции. Использование каждый раз свободной рабочей переменной с минимальным номером экономит количество занятых рабочих переменных. Такой пример экономии рабочих ячеек приведен в таблице № 2. Это же правило используют в трансляторах.

Аналогичным способом можно записывать и вычислять булевские выражения.

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

Таблица № 2

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

В рассмотренном примере встречались двухместные операции. Каждая такая операция, как правило, заменяется одной или двумя машинными командами (в зависимости от адресации машины). В общем случае операция R может иметь k операндов (k1). На ЭВМ такая операция должна заменяться группой машинных команд. Будем считать, что к моменту генерирования машинных команд проведено распределение памяти, и каждый операнд представлен соответствующей ссылкой на таблицу имен, содержащую адрес операнда. Аналогично, для каждой рабочей переменной известен ее адрес.

Для трансляции выражений из обратной польской записи в машинные команды используется стек операндов (СО) с указателем i. В исходном состоянии стек операндов пуст, а указатель i=1. Будем также считать, что в исходном состоянии номер первой свободной рабочей переменной j=1.

Алгоритм трансляции состоит в следующем.

1. Взять очередной символ S из обратной польской записи выражения.

2. Если S – операнд, то занести S в СО[i] , выполнить i=i+1 и перейти к пункту 1, иначе к пункту 3.

3. Если S – не знак операции, то перейти к пункту 4, иначе, если S – знак операции R, выполнить следующее

1. Среди элементов стека СО[i-k], где k – число операндов операции R, найти рабочую переменную с минимальным номером l. Если в рассматриваемых элементах стека нет рабочих переменных, то положить l=j.

2. Записать машинные команды, реализующие оператор присваивания r_l=R(СО[i-k],…,СО[i-1]). Здесь R(x₁, … , x_k) – результат выполнения операции R над операндами x₁, … , x_k.

3. Занести символ r_l в СО[i-k].

4. Выполнить: i=i-k+1 и j=l+1. Перейти к пункту 1.

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

Вход

Рис.4. Блок-схема перевода обратной польской записи в машинные команды.

Для реализации пункта 3.2. приведенного алгоритма используются заранее подготовленные заготовки групп машинных команд, в которые требуется лишь подставить адреса операндов, взятые из стека операндов. Эту подстановку выполняет подпрограмма, соответствующая рассматриваемой операции R.

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

Блок-схема алгоритма перевода обратной польской записи в машинные команды приведена рисунке 4.

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

4.3.5. Общая схема работы интерпретатора

Рассмотрим, что же представляет собой программа, написанная на языке блок - схем с точки зрения интерпретатора. Это список структур следующего вида:

struct Blocks

{

int type; // тип блока

int x; // координаты блока на планшете по оси X

int y; // координаты блока на планшете по оси Y

int true_x; // координаты блока на планшете для перехода

int true_y; // по ИСТИНЕ (TRUE)

int false_x; // координаты блока на планшете для перехода

int false_y; // по ЛЖИ (FALSE)

char* text; // указатель на текст блока

struct Blocks far *next; // указатель на следующий блок в списке блоков

};

Минимальной единицей интерпретации в языке блок-схем является блок. Работой всего интерпретатора управляет функция, которая перемещает фокус интерпретации по блок-схеме, распознает тип блока, на который указывает фокус и запускает функцию обработки (интерпретации) соответствующего блока. После того как функция обработки блока отработает, она передает управление функции управляющей работой интерпретатора. Каждый тип блока имеет свою функцию обработки. Рассмотрим каждый блок по порядку.

НАЧАЛО – блок «НАЧАЛО» отвечает за описание переменных. Строка символов, принадлежащая этому блоку, переводится в список указателей (см. параграф «Структуры данных»). Затем происходит формирование таблицы переменных одновременно с лексической и семантической проверкой. Если функция блок отработала без ошибок, то процесс интерпретации продолжается, иначе нет.

КОНЕЦ – Функция блока ничего не делает. После того, как она передаст управление функции управления интерпретацией, интерпретатор заканчивает свою работу.

АВТОМАТИЧЕСКИЕ ДЕЙСТВИЯ – Строка символов переводится в массив указателей. Затем этот массив переводится в обратную польскую запись (ПолИЗ) и выполняется. Предварительно производится лексический и синтаксический анализ. Если ошибок нет, то управление передается функции управления интерпретацией.

ПОДПРОГРАММА – Предварительно производится лексический и синтаксический анализ. Потом текст переводится в список дескрипторов ПолИЗа, и если ошибок нет, то управление передается функции управления интерпретацией.

ВЕТВЛЕНИЕ ПО УСЛОВИЮ – Сначала производится синтаксический и лексический анализ. Затем строка символов переводится в массив указателей, потом этот массив переводится в ПолИЗ и выполняется. После выполнения ПолИЗа осуществляется семантический анализ. Если ошибок не было, то в зависимости от результата анализа функции управления будет передана информация, как выполнять ветвление.

ВВОД\ВЫВОД – В этих блоках происходит семантический и лексический анализ. По результатам анализов происходит либо выдача сообщений в окно, либо вывод (ввод) значений переменных. Особенность возникает при обработке массивов, так как в этом случае необходимо вычислять адрес элемента массива. Для этого, выражение стоящие внутри квадратных скобок ( [ , ] ) переводится в обратную польскую запись и после обработки ПолИЗа, происходит либо ввод, либо вывод определенного элемента массива. По окончании работы функции обработки блоков, они передают управление функции управления интерпретацией.

МЕТКА – Обработка этого блока происходит в функции блока БЕЗУСЛОВНЫЙ ПЕРЕХОД НА МЕТКУ.

Характеристики

Список файлов реферата