Трансляция класса рекурсивных схем в класс Y(1M, L) Рекурсивная схема транслируется в схему с процедурами. Z={z1, z2, …, zl} k: z:=F i (n) (y1, …, yn) - презентация

1 Трансляция класса рекурсивных схем в класс 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.

2 Пример: Рекурсивная схема 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 )

3 L F : если p(x) то L1 иначе L2, 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, x, z, u, v), w:= L0, M:=w, x:=x на LF, L0: y:=t, M:=(y, x, z, u, v), w:=L3, M:=w, x:=z на LF, L3: z:=t, M:=(y, x, z, u, v), w:=L4, M:=w; x:=u на LF, L4: u:=t, L5: t:=v, w:=M, (v, u, z, x, y):=M на w). L1: L2: L5

4 Структурированные схемы (о 0, о 1, …, о n ) Специальные символы: если, то, иначе, пока, цикл, конец. Три типа схемных операторов: -простой оператор; -условный оператор: если то 1 иначе 0 конец. -оператор цикла: пока цикл конец до цикл конец.

5 Стандартная схема программы Структурированная схема программы старт(х), 1: y := f(x), 2: если p(y) то 7 иначе 3, 3: y := f(y), 4: если p(y) то 5 иначе 7, 5: если p(x) то 6 иначе 7, 6: x := h(x) на 5, 7: стоп(х, y). старт(х), y := f(x), если p(y) то иначе y := f(y), если p(y) то пока p(x) цикл x := h(x) конец иначе конец конец, стоп(х, y).

6 Трансляция структурированных схем в стандартные Все схемные операторы помечаются метками-числами k: если то k+1: 1 иначе l : 0 конец, k: если то k+1 иначе l, k+1: 1 на m, l : 0, k: пока цикл k+1: конец k: если то k+1 иначе m, k+1: на k, k: до цикл k+1: конец k: если то m иначе k+1, k+1: на k, k: если то k иначе m, k: если то m иначе k.

7 Семантическая теория программ Семантика Что делает данная программа? 1.Формальные грамматики. 2.Семантика языка. 3.Верификация программы. Синтаксис Как должна выглядеть программа?

8 Описание синтаксиса языков ::= | ::= if then else | if then

9

10 Описание семантики задается указанием: Используемых в языке типов (множеств) простых значений. Способов построения составных значений из нескольких простых. Операций над простыми, а иногда и над составными значениями. Способов задания сложных действий.

11 Семантика языка Грамматические модели Атрибутивные грамматики. Императивные (операционные) модели VDL. Аппликативные модели. Аксиоматические модели Аксиоматическая семантика Хоара. Модели спецификаций pop(push(S,x))=S.

12 Атрибутивные грамматики ET | E+T TP | T×P PI | (E) ПравилоАтрибут EE+T значение(Е)=значение(Е)+значение(Т) ETET значение(Е)=значение(Т) TT×P значение(Т)=значение(Т)×значение(Р) TPTP значение(Т)=значение(Р) PIPI значение(Р)=значение числа I P(E) значение(Р)=значение(Е)

13 2+4*(1+2)

14 Операционная семантика Оператор языка СОперационная семантика for (exp1; exp2; ехрЗ){exp1... loop: if exp2 = 0 goto out } … ехрЗ; goto loop; out; PL/1Vienna Definition Language

15 Денотационная семантика 0 |1|1 | 0 | 1 Mb:Mb: М b ('0') = 0, М b ('1')=1 М b ( '0') = =2 * М b ( ) М b ( 1) = =2 * М b ( ) + 1

16 0|1|2|3|4|5|6|7|8|9 | (0|1|2|3|4|5|6|7|8|9) Синтаксические правила: M d (0) = 0, M d ('1') = 1,,..., M d ('9') = 9 М d ( '0') = =10 * М d ( ) М d ( 1) = = 10 * М d ( ) + 1 … М d ( '9') = = 10 * М d ( ) + 9