362.50K

Category:

programming

Інтерпретація. SPL-процесор. Виконання SPL-програми. Алгоритм створення SPL-програми

1.

Тема 7: ІНТЕРПРЕТАЦІЯ
1. SPL-процесор
2. Виконання SPL-програми
3. Алгоритм створення SPL-програми
4. Приклад проміжного коду для SPL
програми
5. Розробка компілятора SPL для
платформи . NET
1

SPL-процесор має:
1.
пам‘ять SPL-програми, що моделюється
глобальними даними:
масив TCD (таблиця команд);
adrnm- адреса головної програми, точка входу в
головну програму;
cpnm- кількість параметрів головної програми;
cgv- кількість глобальних змінних;
пам‘ять даних, що моделюється стеком st (масив),
де містяться значення всіх даних в процесі
інтерпретації.
Використовуються покажчики (індекси масивів):
2.
t-вершини стека st,
sp – початок області локальних
(запису активації),
p – поточної команди в TCD.
даних
3
функції

4.

Запис активації містить
значення фактичних параметрів р1, р2,..., рn;
кількість параметрів n;
адреса повернення в TCD (адреса команди
виклику);
адреса попереднього запису активації в стеку
(звідки відбувся виклик функції);
локальні
та
тимчасові
дані,
що
використовуються при обчисленні цього
виклику функції.
4

5.

Область глобальних даних
Стек ST
Значення фактичних параметрів
n (для main)
Нехай викликаються
функції main, р0, р1
Тоді стек st має вигляд:
-2
-1
Локальні та тимчасові дані
1) Область глобальних
даних, що вміщує сgv
елементів.
. . .
Значення фактичних параметрів
2) Три записи активації
для функцій main p0, р1
n (для p0)
Адреса повернення в TCD
Старе значення sp
p
1
(
x
,y
,z
)
Локальні та тимчасові дані для р0
begin
int
v
,w
,...
end
x
5
;y
4
;z
3
;
v
1
;w
2
.
С. 7
sp
t
. . .
-5
-4
-3
x
y
z
Значення фактичних параметрів
-2
n (для p1)
-1
Адреса повернення в TCD
0
Старе значення sp
5

6.

Звертанння до глобальних змінних: st[k], k=0,1,…,cgv-1;
Доступні також локальні дані, які знаходяться в верхньому
запису активації:
параметри, розташовані “нижче” sp, мають зміщення k<0;
локальні змінні, розташовані “вище” sp, мають зміщення
k>0;
Адресація до локальних змінних відбувається так: st[sp+k]
Зміщення для даних обчислюється при обробці описань в SPLпрограмі; зміщення можуть бути:
для n фактичних параметрів: -(n+2),…,-4,-3;
для локальних даних:
1,2,3,…
для глобальних змінних:
0,1,2,…
p
1
(
x
,y
,z
)
begin
int
v
,w
,...
en
С. 5
x
5
;y
4
;z
3
;
6
v
1
;w
2
.

7.

Файл protot.h має опис кодів команд
та структури команди SPL–
процесора:
enum {OPR=1,LIT,LDE, LDI, STE, STI,
CAL, INI, JMP, JMC};
typedef struct {
int code;
int opd;
} cmd;
cmd TCD[300];
7

8.

Коди операцій:
OPR — виконати операцію а над вершиною стеку;
LIT — завантажити в стек константу a;
LDE, LDI — записати в стек значення глобальної
(локальної) змінної зі зміщенням a;
STE, STI — запам'ятати значення вершини стека в
глобальній (локальній) змінній зі зміщенням а;
CAL — викликати функцію з точкою входу a;
INI — збільшити t на a (виділення пам'яті);
JMP — здійснити безумовний перехід на команду a;
JMC — виконати умовний перехід на команду a, якщо
верхній елемент стека менший чи рівний нулю (цей
елемент вилучається зі стека).
8

9.

У команді з кодом OPR
допустимі операції:
а = 1 – ввести в стек число з stdin;
а = 2 – вивести верхнє значення зі стека в
stdout;
а = 3,…,7 – виконати над двома верхніми
елементами стека операцію +, —, *, /, %;
а = 8 –змінити знак верхнього елемента стека;
а = 9 –повернутися в функції (результат
розміщується у верхньому елементі стека);
а = 10 – зупинити виконання SPL-програми.
9

10.

2. Виконання SPL-програми
Всі функції, що виконують
розміщуються у файлі inter.cpp:
SPL-програми,
interp() – починає та завершує
виконання SPL-програми, а також
здійснює загальне керування.
comman() – виконує поточну команду
TCD[p];
operat (а) — виконує операцію OPR a;
push (а) – заносить значення a в стек;
read () – вводить число з stdin у стек.
10

11.

// interp - початок: основний цикл //та
завершення iтерпретацiї
void interp(void)
extern cmd TCD[];
{
extern int adrnm, cpnm, cgv;
int i;
int st[500], sp, t, p;
t=-1;
puts("SPL: iнтерпретацiя");
for(i=0;i<cgv;i++) push(0);
if(cpnm) {
printf("%d>",cpnm);
for(i=0;i<cpnm;i++) push(read()); }
push(cpnm); push(-2); push(-1);
sp=t; p=adrnm;
do {
comman();
p++;
if(p==-1) printf("%d\n",st[t]);
}
} while(p>=0);
11

12.

// comman - виконання команди TCD[p]
void comman(void)
{ int a=TCD[p].opd;
switch(TCD[p].code)
{case OPR: operat(a); break;
case LIT: push(a); break;
case LDE: push(st[a]); break;
case LDI: push(st[sp+a]); break;
case STE: st[a]=st[t--]; break;
case STI: st[sp+a]=st[t--]; break;
case CAL: push(p); push(sp); sp=t; p=a-1; break;
case INI: for(int i=0; i<a; i++) push(0); break;
case JMP: p=a-1; break;
case JMC: if(st[t--]<=0) p=a-1; }
}
12

13.

// operat -виконання операцiї а
// над вершиною стека
void operat( int a)
{ int j=t-1;
switch(a)
{case 1: printf("1>"); push(read()); break;
case 2: printf("%d\n",st[t--]); break;
case 3: st[j]+=st[t--]; break;
case 4: st[j]-=st[t--]; break;
case 5: st[j]*=st[t--]; break;
case 6: if(st[t]==0) error1("/: дiльник = 0"); st[j]/=st[t--]; break;
case 7: if(st[t]<=0) error1("%%: дiльник = 0"); st[j]%=st[t--]; break;
case 8: st[t]=-st[t]; break;
case 9: j=st[sp-2]; st[sp-j-2]=st[t]; t=sp-j-2; p=st[sp-1]; sp=st[sp];break;
case 10: p=-3; }
}
13

14.

// push - занесення в стек значення a
void push(int a)
{
if(t>=499) error1("переповнення стеку st ");
st[++t]=a;
}
// read - введення наступного цiлого
//
значення iз stdin
int read(void)
{
int v,c;
do { c=getchar(); }
while(isspace(c));
if(!isdigit(c)) error1("помилка введення");
for(v=0;isdigit(c);c=getchar())
v=v*10+c-'0';
ungetc(c,stdin);
return v;
}
14

15.

3. Алгоритм створення SPL-програми
Оператори мови SPL переводяться в проміжний код за таким
принципом:
• f(p1, p2,…,pk) begin DC spop end — b: {ini l} <spop> {opr 10}
• константа або число v із значенням val — в {LIT val}
• глобальна змінна d із зміщенням а — в {LDE a}
• локальна змінна чи параметр d із зміщенням а — в {LDI a}
• виклик функції f(e1,e2,...,en) з точкою входу b —
в послідовність команд <e1><e2>...<en>{LIT n}{CAL b}
• вираз -е перекладається в
<e>{OPR 8},
• вираз e1 op e2 (де op — одна з операцій +, -, *, /, %) — в
послідовність <e1><e2>{OPR a}, де a = 3, 4, 5, 6, 7.
15

16.

Оператори мови SPL переводяться в
проміжний код за таким принципом:
Оператор присвоєння d=е, де d — змінна із зміщенням а,
перекладається в код
<e>{STE a} — для глобальної змінної d
<е>{SТІ а} — для локальної змінної
Оператор введення read d замінюється на
{OPR 1} {STE a} —для глобальної змінної
{OPR l}{STI a} —для локальної змінної
Оператор print е перекладається в — <e> {OPR 2}
Оператор return e
—
<e> {OPR 9}
Оператор if e then s end —
<e> {JMC l} <s> l:
Оператор while е do s end —
lb: <е> {JMC l} <s> {JMP lb} l:
16

17.

4. Приклад проміжного
Значення фактичних
параметрів main (немає)
коду для SPL програми
main ( )
begin
int x, у;
read x; read y; print exp(x, y)
end
exp (a, b)
begin int z;
z= 1;
while b do
if b % 2 then z = z * a end;
a = a * a; b = b/2
end;
return z
end
n =0
-2
sp
-1
1
x
2
y
. . .
-4
-3
Значення фактичних
параметрів exp
a
b
-2
n =2
-1
Адреса повернення 8
sp
Старе значення sp
1
Локальні та тимчасові
дані для exp
z 17
. . .

18.

main ( )
begin
int x, у;
read x; read y; print exp(x, y)
end
exp (a, b)
begin int z;
z= 1;
while b do
if b % 2 then z = z * a end;
a = a * a; b = b/2
end;
return z
end
read x;
read y;
Виклик
exp(x,y);
print e;
z=1;
while
b
номер
команди
код
команди і
операнд
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
INI 2
OPR 1
STI 1
OPR 1
STI 2
LDI 1
LDI 2
LIT 2
CAL 11
OPR 2
OPR 10
INI 1
LIT 1
STI 1
LDI –3
1833
JMC

19.

main ( )
begin
int x, у;
read x; read y; print exp(x, y)
end
exp (a, b)
begin int z;
z= 1;
while b do
if b % 2 then z = z * a end;
a = a * a; b = b/2
end;
return z
end
if
b%2
z=z*a
if
a=a*a
b=b/2
while
return z
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
LDI –3
LIT 2
OPR 7
JMC 24
LDI 1
LDI –4
OPR 5
STI 1
LDI –4
LDI –4
OPR 5
STI –4
LDI –3
LIT 2
OPR 6
STI –3
JMP 14
LDI 1
199
OPR
OPR 10

Інтерпретація. SPL-процесор. Виконання SPL-програми. Алгоритм створення SPL-програми

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.