курсовая 2. 1 Постановка задачи 4 2 Формальная модель задачи 5

• Название: 1 Постановка задачи 4 2 Формальная модель задачи 5
• Дата: 27.11.2021
• Размер: 0.89 Mb.
• Имя файла: курсовая 2.doc
• Тип: Реферат; #283891
• страница: 2 из 4

Перевод в ПОЛИЗ операторов. Каждый оператор языка программирования может быть представлен как n-местная операция с семантикой, соответствующей семантике оператора.

Оператор присваивания I ass B в ПОЛИЗе записывается:

IB ass,

где «ass» - двуместная операция,

I, B – операнды операции присваивания;

I – означает, что операндом операции «ass» является адрес переменной I, а не ее значение.

Пример 2: Оператор x ass x+9 в ПОЛИЗе имеет вид: x x 9 + ass.

Оператор перехода в терминах ПОЛИЗа означает, что процесс интерпретации необходимо продолжить с того элемента ПОЛИЗа, который указан как операнд операции перехода. Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, что все они пронумерованы, начиная с единицы (например, последовательные элементы одномерного массива). Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p, тогда оператору безусловного перехода goto L в ПОЛИЗе будет соответствовать:

p!, где ! – операция выбора элемента ПОЛИЗа, номер которого равен p.

Условный оператор. Введем вспомогательную операцию – условный переход «по лжи» с семантикой if not E goto L. Это двуместная операция с операндами E и L. Обозначим ее !F, тогда в ПОЛИЗе она будет записываться:

E p !F, где p – номер элемента, с которого начинается ПОЛИЗ оператора, помеченного меткой L.

С использованием введенной операции условный оператор if E then S else S₄ в ПОЛИЗе будет записываться:

E p₁ !F S p₂ ! S₄, где p₁ – номер элемента, с которого начинается ПОЛИЗ оператора S₄, а p₁ – оператора, следующего за условным оператором.
Пример 3: ПОЛИЗ оператора if x>0 x ass x-5 else x ass x*2 представлен в таблице 2.3.
Таблица 3 – ПОЛИЗ оператора if

лексема	x	0	>	13	!F	x	x	5	-	ass	18	!	x	x	2	*	ass	…
Номер	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18

Оператор цикла while. С учетом введенных операций оператор цикла while E do S в ПОЛИЗе будет записываться:

E p₁ !F S p_o !, где p_o – номер элемента, с которого начинается ПОЛИЗ выражения B, а p₁ – оператора, следующего за данным оператором цикла.

Оператор цикла for. С учетом введенных операций оператор цикла for G to E do S в ПОЛИЗе будет записываться:

G E I <= p₁ !F S I I 1 +ass p_o !, где p_o – номер элемента, с которого начинается операция сравнения , а p₁ – оператора, следующего за данным оператором цикла.

Операторы ввода и вывода языка М одноместные. Пусть R – обозначение операции ввода, а W – обозначение операции вывода, тогда оператор read (I) в ПОЛИЗе запишется как I R, а оператор write (E) – E W.

Составной оператор begin S1; S2;...; Sn end в ПОЛИЗе записывается как S1 S2... Sn.

Пример 4: ПОЛИЗ оператора while n<9 do t ass n*n-1: n ass n-1;

Таблица 4 – ПОЛИЗ оператора while



Синтаксически управляемый перевод.

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

Пример 5: Составим процедуры перевода в ПОЛИЗ программы на языке М.

ПОЛИЗ представляет собой массив, каждый элемент которого является парой вида (n, k), где n – номер таблицы лексем, k – номер лексемы в таблице. Расширяем набор лексем:

1) в таблицу ограничителей добавляем новые операции ! (22), !F (19), R (21), W (20);

2) для ссылок на номера элементов ПОЛИЗа введем нулевую таблицу лексем, т.е. пара (0, p) - это лексема, обозначающая p-ый элемент в ПОЛИЗе;

3) чтобы различать операнды-переменные и операнды-адреса переменных, обозначим переменные как 4 таблицу лексем, а адреса – 5.

3.5 Интерпретация ПОЛИЗа программы

Ход интерпретации программы с помощью таблицы

Интерпретируем следующую программу:

program

var integer a,b;

begin

b ass 1;

for a ass 1 to 2 do

b ass b+1

write(b)

end.

ПОЛИЗ данной программы будет иметь вид:

Таблица 5 – ПОЛИЗ исходной программы

Лексема	b	1	ass	a	1	ass	a	2	<=	26	!F
Номер	1	2	3	4	5	6	7	8	9	10	11

Лексема	b	b	1	+	ass	b	W	a	a	1	+
Номер	12	13	14	15	16	17	18	19	20	21	22

Лексема	ass	7	!	.
Номер	23	24	25	26

Процесс интерпретации программы на модельном языке М, записанной в форме ПОЛИЗа, показан в таблице 6.
Таблица 6 – Ход интерпретации ПОЛИЗа программы

Стек	Текущий элемент ПОЛИЗа	Операция	Таблицы переменных
			адреса	значения
пуст	1	адрес - в стек	1) a 2) b	1) - 2) -
2	2	число в стек	1) a 2) b	1) - 2) -
2;1	3	присвоить второму элементу таблицы значений число 1	1) a 2) b	1) - 2) 1
пуст	4	адрес - в стек	1) a 2) b	1) - 2) 1
1	5	число в стек	1) a 2) b	1) - 2) 1
1;1	6	присвоить первому элементу таблицы значений число 1	1) a 2) b	1) 1 2) 1
пуст	7	значение - в стек	1) a 2) b	1) 1 2) 1
1	8	число в стек	1) a 2) b	1) 1 2) 1
1;2	9	в стек – true, т.к. 1<=2	1) a 2) b	1) 1 2) 1
1	10	метка - в стек	1) a 2) b	1) 1 2) 1
1;22	11	переход, к следующему элементу ПОЛИЗа, т.к. условие истинно	1) a 2) b	1) 1 2) 1
пуст	12	адрес - в стек	1) a 2) b	1) 1 2) 1
2	13	значение - в стек	1) a 2) b	1) 1 2) 1
2;1	14	число в стек	1) a 2) b	1) 1 2) 1
2;1;1	15	извлечь из стека 1 и 1 и поместить в стек их сумму	1) a 2) b	1) 1 2) 1
2;2	16	присвоить второму элементу таблицы значений число 2	1) a 2) b	1) 1 2) 2
пуст	17	значение - в стек	1) a 2) b	1) 1 2) 2
2	18	значение из стека на экран	1) a 2) b	1) 1 2) 2
пуст	19	адрес - в стек	1) a 2) b	1) 1 2) 2
1	20	значение - в стек	1) a 2) b	1) 1 2) 2
1,1	21	число в стек	1) a 2) b	1) 1 2) 2
1,1,1	22	2 из стека + и результат в стек	1) a 2) b	1) 1 2) 2
1,2	23	присваиваем 2 по адресу 1	1) a 2) b	1) 2 2) 2
пуст	24	адрес в стек	1) a 2) b	1) 2 2) 2
7	25	переход к элементу ПОЛИЗа, с номером, извлекаемым из вершины стека	1) a 2) b	1) 2 2) 2
пуст	7	значение - в стек	1) a 2) b	1) 2 2) 1
2	8	число в стек	1) a 2) b	1) 2 2) 1
2;1	9	в стек – true, т.к. 2<=2	1) a 2) b	1) 2 2) 1
1	10	метка - в стек	1) a 2) b	1) 2 2) 1
1;22	11	переход, к следующему элементу ПОЛИЗа, т.к. условие истинно	1) a 2) b	1) 2 2) 1
пуст	12	адрес - в стек	1) a 2) b	1) 2 2) 1
2	13	значение - в стек	1) a 2) b	1) 2 2) 1
2;2	14	число в стек	1) a 2) b	1) 2 2) 1
2;2;1	15	извлечь из стека 2 и 1 и поместить в стек их сумму	1) a 2) b	1) 2 2) 1
2;3	16	присвоить второму элементу таблицы значений число 3	1) a 2) b	1) 2 2) 2
пуст	17	значение - в стек	1) a 2) b	1) 2 2) 3
3	18	значение из стека на экран	1) a 2) b	1) 2 2) 3
пуст	19	адрес - в стек	1) a 2) b	1) 2 2) 3
1	20	значение - в стек	1) a 2) b	1) 2 2) 3
1,2	21	число в стек	1) a 2) b	1) 2 2) 3
1,2,1	22	2 из стека + и результат в стек	1) a 2) b	1) 2 2) 3
1,3	23	присваиваем 3 по адресу 1	1) a 2) b	1) 2 2) 3
пуст	24	адрес в стек	1) a 2) b	1) 3 2) 3
7	25	переход к элементу ПОЛИЗа, с номером, извлекаемым из вершины стека	1) a 2) b	1) 3 2) 3
пуст	7	значение - в стек	1) a 2) b	1) 3 2) 3
3	8	число в стек	1) a 2) b	1) 3 2) 3
3,2	9	2 из стека и сравниваем, т.к. 3<=2 то в стек false	1) a 2) b	1) 3 2) 3
0	10	адрес в стек	1) a 2) b	1) 3 2) 3
0,26	11	Т.к false то переход на 26	1) a 2) b	1) 3 2) 3
пуст	26	интерпретация завершена	1) a 2) b	1) 3 2) 3