Jezyk - C + przekazywanie parametrów przez referencję
Dany program
int f(int w, int& x); void printInt(n); int g(int y, int& z) { int a=z, b; z = f(a+2,y); printInt(z); b = y; return b; }
Zaplanuj rekord aktywacji dla funkcji g i przetłumacz ją
Język: oddzielnie kompilowane, rekurencyjne funkcje bez struktury blokowej, zmienne lokalne i wynik funkcji typu integer, dwa rodzaje parametrow: przez wartość (integer) oraz referencję (również do zmiennej typu integer). Składnia zbliżona do C++ (parametry przekazywane przez referencję są oznaczane jako typu int&).
Komputer: cztery rejestry uniwersalne R0,...,R3 i instrukcje
Ri:=Ri op Rj (op to +-*/)
Ri:=Rj
Ri:=n
INC Ri,n
LOAD Ri,n
LOAD Ri, [Rj]
STORE Ri,[Rj]
GOTO n
GOTO [Ri]
CALL Ri (adres skoku w rejestrze, ślad tamże)
plus potrzebne skoki warunkowe.
Notacja [Ri] oznacza komórkę pamięci o adresie w Ri
Zaprojektuj protokół wywołania i powrotu z funkcji i przetłumacz
extern int g(int& a); int f(int a, int& b) { int c; c = 21 + g(a) + g(b); return c; }
rozwiązanie powinno obejmować opis rekordu aktywacji funkcji f i istotny fragment rekordu aktywacji funkcji g.
Rozważmy język D♭ ze strukturą blokową, dopuszczający zagnieżdżanie funkcji oraz przekazywanie ich jako parametrów (poza tym podobny do C), oraz fragment programu w nim:
int h(int a, int b, function int k(int)) { return k(a) + k(b) ; } int g(int a) { int b; int f(int c) { return (b=a+c); } f(a); return h(a,b,f); }
a. Zaprojektuj protokół wywołania i powrotu z funkcji dla tego języka.
b. Opisz rekordy aktywacji dla funkcji f,g,h
c. Wygeneruj kod dla podanego fragmentu programu.
Można przyjąć, że w języku D♭ nie występują wskaźniki do funkcji (ani w ogóle konstrukcje nie występujące w przytoczonym fragmencie programu).
Rozważmy język ze strukturą blokową, dopuszczający zagnieżdzanie procedur oraz trzy rodzaje parametrów:
* wejściowe (przekazywane przez wartość), oznaczane na liście parametrów formalnych słowem kluczowym in
* wyjściowe - kopiowane po powrocie z funkcji na zmienną będącą parametrem faktycznym, oznaczane out
* wejściowo-wyjściowe - przekazujące wartość do funkcji przy wywołaniu i z funkcji przy powrocie (inout)
Dalej, rozważmy fragment programu w tym języku:
program Foo;
procedure P(in int a,out int b);
var int c;
procedure Q(inout int b, out int c);
begin
c := b / a;
b := b - c
end; (* Q *)
procedure R(inout int d) begin Q(d,c) end (* R *);
begin (* P *)
c := a + 1;
R(c)
Q(c,b);
end; (* P *)a. Zaprojektuj protokół wywołania i powrotu z procedur dla tego języka.
b. Opisz rekordy aktywacji dla procedur P,Q,R
c. Wygeneruj kod na maszynę stosową dla podanego fragmentu programu.
Jezyk: oddzielnie kompilowane, rekurencyjne funkcje bez struktury
blokowej, zmienne lokalne i wynik funkcji typu integer, dwa rodzaje
parametrow: przez wartosc (integer) oraz etykieta, skoki tylko nielokalne,
do etykiet przekazanych jako parametr.
Komputer: cztery rejestry uniwersalne R0,...,R3 i instrukcje
Ri:=Ri op Rj (op to +-*/)
Ri:=Rj
Ri:=n
INC Ri,n
LOAD Ri,arg
STORE Ri,arg
GOTO arg
CALL Ri (adres skoku w rejestrze, slad tez tam)
plus potrzebne skoki warunkowe.
Zaprojektowac protokol wywolania funkcji dla tego jezyka i przetlumaczyc:
function F(a,b,c);
var d,e,f,g;
begin
g:=10;
if a>0 then c:=a+b;
repeat
f:=a+b; e:=b; d:=a;
f:=FUNKCJA((d+e)*f,(b+d)-(c*g),ETYKIETA);
if f>0 then e:=(a+b)*(c*d) else e:=c*d;
ETYKIETA:
e:=e-(c*d);
a:=a+1
until a=b;
return e;
end;(Oczywiscie interesuja nas tylko ciekawsze fragmenty)
W jezyku L-- istnieja rekurencyjne funkcje (z parametrami przekazywanymi
przez wartosc). Funkcje moga byc zagniezdzane, ale wewnatrz funkcji
widoczne sa jedynie zmienne i funkcje zadeklarowane w niej samej lub w
funkcji bezposrednio ja otaczajacej. Wszystkie zmienne lokalne, parametry
i funkcje sa typu integer. Przyklad programu:
function p();
var p1; function q(a); begin ...end;
function F(a,b); var c; function R(); begin ...end;
begin {F}
c:=1; if a<b then c:=F(Q(F(a+p1,b-1)),R()); return 5;
end;
begin ... end;Komputer ma rejestr adresowy A oraz wbudowany stos (o ograniczonej,
niewielkiej pojemnosci) sluzacy do obliczen arytmetycznych. Istnieja
miedzy innymi instrukcje:
PUSH A
PUSH n
PUSH (A+n)
PUSH * adres na czubku stosu zastepuje wartoscia spod tego adresu
POP A
POP (A+n)
POP * na czubku wartosc i adres, wykonujemy przypisanie
ADD, SUB ...
GOTO n
GOTO * adres skoku na czubku stosu
IFZERO n
IFNOTNEG n
CALL n slad zostaje na czubku stosu
Ponadto istniej funkcja ALLOC przydzielajaca obszar pamieci o rozmiarze na czubku stosu i zastepujaca rozmiar adresem obszaru. Jest tez procedura FREE zwalniajaca obszar o adresie na czubku stosu.
Zaprojektowac rekord aktywacji i protokol wywolania funkcji. (Rekordy aktywacji tworzymy i usuwamy przez ALLOC i FREE).
Napisac tlumaczenie funkcji F z przykladu powyzej.
Dany jest język programowania, w którym:
Maszyna docelowa ma pamięć składającą się ze słów, długość adresu jest równa długości słowa. Maszyna ma dwa
rejestry ogólnego przeznaczenia, R0 i R1, wskaźnik wierzchołka stosu SP i rejestr BP. Stos rośnie w kierunku
malejących adresów. Adresy można podawać bezpośrednio bądź w sposób indeksowany (np. [adres+10]).
Dostępne są następujące instrukcje:
MOV Rx, Ry – kopiuje zawartość Rx do Ry,
MOV adres, Ry – kopiuje zawartość pamięci spod adresu adres do Ry,
MOV Rx, adres – kopiuje zawartość rejestru Ry do pamięci pod adres adres,
ADD Rx, Ry, SUB Rx, Ry, MUL Rx, Ry – operacje arytmetyczne, ich wynik jest umieszczany w Rx,
PUSH num – odkłada na stos liczbę num,
PUSH Rx – odkłada na stos zawartość rejestru Rx,
POP Rx – zdejmuje ze stosu liczbę i umieszcza ją w Rx,
CALL adres – odkłada na stos adres kolejnej instrukcji i skacze pod adres adres,
RET – zdejmuje ze stosu liczbę, którą traktuje jako adres pod który skacze,
oraz inne, nieistotne dla treści zadania.
Zaprojektuj protokół wywołania i powrotu z funkcji tak, by możliwe było zaimplementowanie powyżej
przedstawionych cech języka programowania. Opisz jak wygląda prolog i epilog funkcji oraz jej wywołanie i do czego
są używane poszczególne rejestry.
Przedstaw na rysunku zawartość stosu (zaznaczając strzałkami SL-e i DL-e oraz pomijając zmienne tymczasowe) przed
wykonaniem linijki zaznaczonej przez (*) z poniższego programu, zakładając, że pierwszy wykonywany był wiersz
oznaczony (**):
int f1(int a, int b, int c) {
int f2(int &a) {
int f3(int b, ...) {
int c = f4(a)+_argv[0]+b;
return c;
};
a = 17;
return f3(c, 2)+b;
}
int f4(int c) {
(*)
return a+c;
}
return f2(b);
}
...
(**) f1(1,2,3);
...Adresy funkcji przedstaw jako #nazwa, a adresy zmiennych przez ich nazwę w nawiasach kwadratowych.
Podaj wartość zwracaną przez wywołanie f1.
Przesledzic wykonanie programu (wczesniej trzeba rozplanowac rekord
aktywacji i omowic sposob przekazywania parametrow):
program A; var aa:integer; function B(function bf:integer; var bv:integer):integer; function C(cc:integer):integer; begin c:=aa+bv+cc; aa:=E(cc) end; begin bv:=bv+1; if bv=2 then B:=B(C,bv) else B:=(aa+bv)*D(bf) end; function D(function dd:integer):integer; begin D:=(2*aa)-dd(aa) end; function E(ee:integer):integer; begin E:=ee+2 end; begin aa:=1; writeln(B(D,aa)) end.