Информационно-безопасные системы. Анализ проблемы: Учебное пособие, страница 30

Выделим следующие основные этапы решения задачи:

-  описание правил языка программирования;

-  выбор единой формы представления Ф_E программы и алгоритма;

-  описание метода перевода алгоритма из формы Ф_A в форму Ф_E;

-  построить транслятор для выбранного языка, который переводит программу, представленную в форме Ф_P, в форму Ф_E.

8.2. Описание языка программирования

В качестве языка программирования выберем подмножество алгоритмического языка Паскаль, содержащее операторы цикла с предусловием, присваивания и условно­го перехода. Все имена переменных состоят из одной заглавной буквы английского алфавита, все константы - целые, комментарии не допускаются. Определенное нами подмножество можно задать в виде синтаксических диаграмм (рис.8.2) [1].

Пусть исходный алгоритм представлен в виде схемы и, соответственно, может содержать операторы присваивания, циклы с предусловием и условные переходы (рис.8.3).

8.3. Промежуточные представления программы

8.3.1. Ориентированный граф

Ориентированный граф (ОТ) является наиболее наглядным представлением программы [2]. Например цепочке лексем а:=b^*-c+b^*-c будет соответствовать синтаксическое дерево рис.8.4а и соответствующий ориентированный граф рис.8.46.

8.3.2.Трехадресныйкод

Трехадресный код - это последовательность операторов вида х := у ор z, где х, у, z - имена, константы или сгенерированные компилятором временные объекты, ор -двухместная операция. Это линеаризованное представление синтаксического дерева или ориентированного графа, в котором явные имена соответствуют внутренним вершинам дерева или графа. Например,

х + у * z соответствует  tl:= у * z;   t2:= х + tl,

if A>B then SI else S2 соответствует t:= A - B; JGT t, S2.

Представлению синтаксического дерева (см. рис. 8.4а) соответствует tl:=-с;   t2:=b*tl; t3:=-с;   t4:=b * t3; t5:= t2 + t1;   a:= t5.

Существуют различные реализации трехадресного кода: четверки, тройки, косвен­ные тройки.

Четверка - это запись с четырьмя полями ( ор, arg1, arg2, result ). Обычно содер­жимое полей arg1, arg2 и result это указатели на входы таблицы символов для имен, представляемых этими полями. Временные имена вносятся в таблицу символов по мере их генерации. Чтобы избежать внесения новых имен в таблицу символов, на временное значение можно ссылаться, используя позиции вычисляющего его оператора.

Тройки - это запись с тремя полями (ор, arg1, arg2), где arg1 и arg2 либо указатели на таблицу символов, либо указатели на тройки.

Например, представление синтаксического дерева (см. рис.8.4а) четверками в сле­дующее (табл. 8.1).

Таблица 8.1.

	op	arg1	arg2	Result
(0) (1) (2) (3) (4) (5)	- + - * + :=	c b c b t2 t5	t1 t3 t4	t1 t2 t3 t4 t5 a

8.3.3. Линеаризованные представления

Линеаризованное представление - это запись дерева либо в порядке его обхода сни­зу-вверх (постфиксная запись, или обратная польская), либо сверху-вниз (префиксная запись, или прямая польская).

Постфиксная запись - это список вершин дерева, в котором каждая вершина следу­ет непосредственно за своими потомками:

a b c - * b c - * + := .

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

Префиксная запись - это список вершин дерева, в котором идет сначала операция, затем операнды:

:= а + * b – с * b - с.

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

Предположим, что перевод алгоритма осуществляется вручную по следующим пра­вилам.

1)  Для условного перехода польская запись имеет вид:

1.  Условие   УПнет(м1)   Посл-ть блоков м1: