Схемы с процедурами Главная схема x=F (n) (y 1, y 2, …, y n ) Множество схем процедур. Главная схемаМножество схем процедур (старт(x), 1: z:=x, 2: u:=a, - презентация

1 Схемы с процедурами Главная схема x=F (n) (y 1, y 2, …, y n ) Множество схем процедур. Главная схемаМножество схем процедур (старт(x), 1: z:=x, 2: u:=a, 3: x:=F(x, z, u), 4: u:=b, 5: z:=F(z, x, u) 6: стоп(z)) F(y, v, w)=(старт, 1: если p(y) то 2 иначе 4, 2: y:=h(y), 3: v:=G(v, w), 4: если q(w) то 5 иначе 6, 5: y:=v, 6: стоп(y)) G(t, r)=(старт, 1: если q(r) то 2 иначе 3, 2: t:=r, 3: стоп(t))

2 Трансляция рекурсивных схем в схемы с процедурами (старт (y 1, y 2, …, y n ), 1: y:=t (y 1, y 2, …, y n ), 2: стоп (y)). F i (x 1, …, x n ) = если p(x i, …, x n ) то t i1 иначе t i0 F i (x 1, …, x n ) = (старт, 1: если p(x i1, …, x il ) то 2 иначе k, 2: S(v, t i1 ) на m, k: S(v, t i0 ), m: стоп (v)). S(v, t) : а) если t=х, то S(v, t) => v:=x; б) если t= (n) (t 1, …,t n ), то S(v, t) = 1, 2, …, n, v:= (n) (z 1, …, z n ), z i :=x, если t i – переменная х, i = S(z i, t i ) в противном случае.

3 Рекурсивная схема: S: F(x), F(x)=если p(x) то x иначе f(F(g(x)), F(h(x))) Схема с процедурами: S: (старт (x), 1: y:=F(x), 2: стоп(y)) F(x) = (старт, 1: если p(x) то 2 иначе 3, 2: v:=x на 8, 3: z:=g(x), 4: z:=F(z), 5: u:=h(x), 6: u:=F(u), 7: v:=f(z, u), 8: стоп(v)).

4 Трансляция схем с процедурами в рекурсивные S, P 1, …, P n независимо транслируются в рекурсивные схемы R S и R Pi (i=1, …, n). t 0 – главный терм схемы R S, t i (i=1, …, n) – главный терм схемы R Pi. F i (x 1, …, x n ) = t i.

5 Частичная трансляция схем с процедурами к: z:=F i (y 1, …, y n ) на l; стоп(v) => z:=v на l ; k: x 1 :=y 1, …, x n :=y n на m; Пример: S: (старт (x), 1: y:=F(x), 2: стоп(y)) F(x) = (старт, 1: если p(x) то 2 иначе 3, 2: v:=x на 5, 3: z:=g(x), 4: v:=F1(z), 5: стоп(v)). F1(y)=(старт, 1: если q(y) то 2 иначе 3, 2: v1:=a на 4, 3: v1:=b, 4: стоп(v1)) F(x)=(старт, 1: если p(x) то 2 иначе 3, 2: v:=x на 5, 3: z:=g(x), 4: z1:=z на 10, 5: стоп (v)) 10: если q(z1) то 11 иначе 12, 11: v1:=a на 13, 12: v1:=b, 13: v:=v1 на 5).

6 Обогащенные схемы класс счетчиковых схем; интерпретированные операторы: c:=c+1; c:=c-1; c=0; c1:=c2; F(x), F(x)= если р(х) то х иначе f(x, F(g(x)))

7 класс магазинных схем; интерпретированные операторы: M:=x; x:=M; M=Ø; класс схем с массивами; интерпретированные операторы: A[c]:=x; x:=A[c].

8 Трансляция обогащенных схем: Y стандартные схемы;Y(М) магазинные схемы; Y(R) рекурсивные схемы;Y(А) схемы с массивами; Y(с) счетчиковые схемы;Y(P) схемы с процедурами.

9 Трансляция счетчиковых схем в магазинные счетчик с заменяется магазином Мс; переменная х и константа а; х:=а; с:=с+1 => Мс:=х; с:=с-1 => х:= Мс; с=0 => Мс=. c=n =>

10 Трансляция схем с массивами в магазинные счетчики заменяются на магазины. Каждый массив А заменяется парой магазинов М А, М ! А и переменной u A.

11

12

13 Трансляция магазинных схем в схемы с массивами М =>А М и с М. l : x:=M на k, l : x:=A M [c M ], c M :=c M -1 на k; l : М:=х на k, l : c M :=c M +1, A M [c M ]:=х, на k; l : если М= то k иначе m l : если c=0 то k иначе m.

14 Магазинные и рекурсивные схемы Трансляция рекурсивной схемы в схему с процедурами; Трансляция схем с процедурами в класс схем с одним магазином и обогащенный метками Y(1M, L); Освобождение магазинной схемы от меток (т.е. переход к классу Y(1M)). Особенности схемы класса Y(1M, L): а) инструкции могут помечаться метками-символами; б) {L1, L2, …, Lm}; в) все переходы– метки-символы или выделенная переменная; г) w w:=L M:=w, w:=M.

15 Трансляция класса рекурсивных схем в класс Y(1M, L) Рекурсивная схема транслируется в схему с процедурами. Z={z1, z2, …, zl} k: z:=F i (n) (y1, …, yn) на m; k: M:=z1, …, M:=zl; w:=L; M:=w; x1:=y1, …, xn:=yn на L Fi ; L: z:=t на m. Fi(x1, …, xn) старт 1 => L Fi. стоп(v) t:=v; w:=M; zl:=M, …, z1:=M на w.

16 Пример: Рекурсивная схема S: F(x), F(x)=если p(x) то x иначе f(F(g(x)), F(h(x))) S: (старт (x), 1: y:=F(x), 2: стоп(y)) F(x) = (старт, 1: если p(x) то 2 иначе 3, 2: v:=x на 8, 3: z:=g(x), 4: z:=F(z), 5: u:=h(x), 6: u:=F(u), 7: v:=f(z, u), 8: стоп(v)). Сократим: M:=y 1, …, M:=y r =>M:=(y 1, …, y r ) y 1 :=M, …, y r :=M=>(y 1, …, y r ):=M x 1 :=y 1, …, x r :=y r =>(x 1, …, x r ):=(y 1, …, y r )