a) Budując dwa różne drzewa lewostronnego wyprowadzenia dla słowa \(abab\), wykaż, że gramatyka ta jest niejednoznaczna
b) Zbuduj odpowiadające wyprowadzenia prawostronne dla \(abab\).
c) Jaki język jest generowany przez tę gramatykę?
Zad. 1
Przekształć poniższą gramatykę do postaci LL(1), oblicz zbiory SELECT
oraz wszystkie potrzebne zbiory First i Follow:
\(\begin{align*}
L &\to E , L \mid E\\
E &\to( L ) \mid \varepsilon
\end{align*}
\)
Zad. 2
Polecenie jak wyzej:
\(\begin{align*}
L &\to L ; S \mid S\\
S &\to\{ L \} \mid \varepsilon
\end{align*}
\)
Zad. 3
Przekształćdo postaci LL(1) poniższą gramatykę, oblicz zbiory SELECT,
zrealizuj analizator składniowy działający metoda zejść rekurencyjnych
i dopisz do niego instrukcje liczące wartość wyrazenia (w pierwszej
produkcji najpierw liczymy "*", później "+"):
\(\begin{align*}
E &\to E * E + F \mid F\\
F &\to( E ) \mid num
\end{align*}
\)
Zad. 4
Przeksztalc ponizsza gramatyke do postaci LL(1), oblicz zbiory SELECT
Narysuj i uprosc diagramy skladniowe. Wyjasnij, jak na ich podstawie
zbudowac analizator skladniowy metoda zejsc rekurencyjnych:
W -> W @ P | P
P -> id | liczba | id ( L ) | ( W ) | ( W ) P
L -> W | W , L
Zad. 5-7
Przeksztalc do postaci LL(1) i oblicz zbiory SELECT dla gramatyk:
E -> E F F | epsilon
F -> G ? F F | G
G -> ( E ) | id
I -> J = I I | J
J -> J ? | id | id + id | < L >
L -> L I | epsilon
E -> E F | E F G | F
F -> id E ?
G -> G ( E ) | ( E ) | =
Zad 8 (z kolokwium)
Poniżej znajduje się gramatyka języka K1Z2, którego słowa reprezentują
wyrażenia arytmetyczne. Obok każdej produkcji jest informacja o
znaczeniu opisywanej przez nią konstrukcji języka:
E → ε wyrażenie o wartości 0
E → F - E różnica wartości wyrażeń F i E
E → F wartość wyrażenia F
F → F F * iloczyn wartości dwóch wyrażeń F
F → F ! silnia wartości wyrażenia F
F → G wartość wyrażenia G
G → ( E ) wartość wyrażenia E
G → + G G suma wartości dwóch wyrażeń G
Tekstowy zapis słów języka K1Z2 jest ciągiem znaków "-", "*", "!",
"(", ")" i "+", z których każdy reprezentuje odpowiedni symbol
terminalny gramatyki. Żadnych innych znaków, oprócz wymienionych
powyżej, w tekstowym zapisie słow tego języka nie ma.
Napisz program, który wczyta z wejścia wyrażenie języka K1Z2 i wypisze
na wyjście jego wartość.
Analizator składniowy będący częścią programu zrealizuj za pomocą
metody zejść rekurencyjnych.
W przypadku wykrycia błędu składniowego program powinien wypisać na
wyjście słowo "BLAD".
Uwaga: przymujemy, że silnia liczby mniejszej niż 1 jest równa 1.
Zad 9 (*)
a. Wykaż, że gramatyka
S → aSb | ab
jest LL(2), ale nie LL(1)
b. Wykaż, że gramatyka
S → aAaa | bAba
A → b | ε
jest LL(2), ale nie jest silnie LL(2)
Jeśli nie zaznaczono inaczej, polecenie brzmi: stwórz najprostszy mozliwy automat LR (LR(0)<SLR(1)<LALR(1)<LR(1)) dla podanej gramatyki.
Standardowa konwencja: symbole terminalne złożone z małych liter i symboli (+,*,;,etc); symbole nieterminalne pisane wielkimi literami, pierwsza produkcja wyznacza symbol startowy)
0. Stwórz automat dla gramatyki z wykładu:
E -> E + T | T
T -> T * F | F
F -> n
dla pełnosci mozna też dodać produkcję
F -> (E)
1. (Ullman 4.35)
E -> E + T | T
T -> T F | F
F -> F * | a | b
2.
L -> ε | S L
S -> E | if E S | { L }
E -> id | id ( E )
3.
S -> ε | S E ; | S id = E ;
E -> id | num | ( E ) | - E
4. (Ullman 4.39)
S -> A a | b A c | d c | b d a
A -> d
5.(Ullman 4.40)
S -> A a | b A c | B c | b B a
A -> d
B -> d
6.
E -> A | A : A
A -> id | [ ] | [ L ]
L -> A | A , L
7. ( z kolokwium)
Dana jest gramatyka G:
A -> A x B | B
B -> B y C | C
C -> z A z | x
Czy można zbudować parser LR(0) dla gramatyki G ?
Czy można zbudować parser SLR dla gramatyki G ?
Czy można zbudować parser LR(1) dla gramatyki G ?
8. (z kolokwium)
Dana jest gramatyka języka K1Z3:
A → x C
A → B z
A → ε
B → ε
C → x B
C → x C y
Czy ta gramatyka jest LR(0) ? Czy jest SLR(1) ? Czy jest LALR(1) ? Czy
jest LR(1) ?
Odpowiedź na każde pytanie uzasadnij konstrując, za pomocą
odpowiedniej metody, tablicę sterującą analizatora składniowego lub
wskazując, dlaczego nie da się tego zrobić.
9. Do jakich klas LR/LL należy gramatyka
E → E E + | E E * | n
10. Wykaż, że gramatyka
S -> aF | bG
F -> Xc | Yd
G -> Xd | Yc
X -> ZA
Y -> ZB
Z → ε
A → ε
B → ε
jest LL(1), ale nie LALR(1)
11. (kolokwium 2010)
Dana gramatyka G (symbolem startowym jest A)
A →abb
A → B
B → bBa
B → ε
(a) Sprowadź G do postaci LL(1) i oblicz wszystkie zbiory SELECT.
(b) Do jakich klas spośród LR(0),SLR(1),LALR(1),LR(1) należy G? Odpowiedź uzasadnij.
12. (kolokwium 2011/12)
Dana jest gramatyka G o symbolu początkowym A:
A → ABs | C
B → CBw | C
C → t | uAs
(s,t,u,w są symbolami terminalnymi).
(a) Czy dla języka L(G) można zbudować analizator składniowy metoda zejść rekurencyjnych ? Jeśli tak, to posługując się nią napisz taki analizator. Jeśli nie jest to możliwe, wyjaśnij dlaczego.
(b) Zbuduj tablice sterującą analizatora składniowego LR dla gramatyki G lub udowodnij, że nie jest to możliwe.
Gramatyka G opisuje automat sterujący LR:
A -> P A | ε
P -> goto(n,n,n) | shift(n,n,n) | reduce(n,n,n) | accept(n,n)
gdzie n jest liczbą oznaczającą oznaczającą numer stanu, produkcji lub symbolu. Ciągi terminali n oddzielonych przecinkiem w produkcjach P oznaczają najpierw stan/stany, później ewentualnie produkcję, a na końcu symbol. Np. shift(1,2,6) oznacza operację shift w stanie 1 z przesunięciem symbolu 6 i przejściem do stanu 2.
Napisz na podstawie gramatyki G gramatykę atrybutywną, która ustawi atrybut sr dla A na true wtw gdy nie ma konfliktu shift/reduce. Załóż, że terminal n posiada atrybut v, reprezentujący jego wartość liczbową.
Rozważmy język programów opisany poniższą gramatyką, składających się z sekwencji deklaracji D poprzedzających pojedyncze wyrażenie W
P -> D;W
D -> D;D | id : T
T -> char | int | array [n] of T
W -> c | n | id | W mod W | W[W]
W gramatyce tej c oznacza stałą znakową, n - stałą liczbową.
1. Zapisz reguły sprawdzania typów dla tego języka (np. w postaci gramatyki atrybutywnej)
2. Rozszerz język o wskaźniki i reguły typowania dla nich
3. Używając zaprojektowanych wcześniej reguł wyznacz typy wyrażeń w następujących fragmentach programu:
a) c : char; i : int; c mod i mod 3
b) p : ^int; a: array[10] of int; a[p^]
4. Rozszerz język o typy postaci list of T (lista elementów typu T), wyrażenie konstruujące listę z głowy i ogona i wyrażenie nil reprezentujące listę pustą (która moze reprezentować listę pustą elementów dowolnego typu).
W pewnym języku programowania występuje typ real reprezentujący
liczby oraz mac(m,n) reprezentujący macierze wymiaru m * n o
wyrazach typu real. Napisz gramatykę atrybutywną dla produkcji mnożenia
(E -> E1 * E2) opisującą analizę typów (obliczone typy umieszczaj w
atrybucie E.typ).
Program w języku EZ2 składa się z ciągu definicji funkcji. Funkcje opisuje gramatyka
definicja-funkcji ::= identyfikator '(' wyrażenie ')' '=' wyrażenie
wyrażenie ::= wyrażenie operacja-arytmetyczna wyrażenie
| identyfikator
| stała-całkowita
| identyfikator '(' wyrażenie ')'
| 'let' identyfikator '=' wyrażenie 'in' wyrażeniePrzedostatnia produkcja oznacza wywołanie funkcji. Ostatnia oznacza deklarację i nadanie
wartości zmiennej lokalnej, która może przesłaniać zadeklarowane wcześniej zmienne, jak i
nazwy funkcji.
Zasięgiem deklaracji po 'let' jest wyrażenie po 'in'.
Funkcje mogą być rekurencyjne (także wzajemnie) i ich definicje mogą występować w dowolnej
kolejności (tzn. dowolna permutacja poprawnego ciągu definicji funkcji daje poprawny ciąg
definicji funkcji).
Programy w EZ2 operują wyłącznie na liczbach całkowitych.
Efektem działania programu w EZ2 jest wypisanie wyniku main(0)
a) Opisz zwięźle warunki poprawności kontekstowej programu EZ2, których spełnienie jest
niezbędne aby wykonanie programu było możliwe.
b) Opisz interfejs tablicy symboli dla EZ2
c) Uwzględniając powyższe, napisz fragment programu sprawdzający poprawność kontekstową
wyrażeń.
Dany jest język wyrażeń o gramatyce:
S → E E → * E E → & E E → E := E E → id
Identyfikatory występujące w wyrażeniach reprezentują zmienne typu prostego T.
Gwiazdka jest operatorem dereferencji (wyłuskania), który stosujemy do wskaźnika, by otrzymać wartość przezeń wskazywaną. Wyrazenie *E jest poprawne, jeśli E jest wskaźnikiem.
Ampersand (&) jest operatorem pobrania adresu, który daje wskaźnik do wartości wyrażenia, do którego ten operator stosujemy. Wyrażenie &E jest poprawne nawet, jesli E nie jest zmienną. W takiej sytuacji dostaniemy wskaźnik do zmiennej tymczasowej, przechowującej obliczoną wartość E.
Przypisanie E:=E jest poprawne, jeśli typy obu wyrażeń są równe, a lewa strona przypisania jest zmienną lub dereferencją wskaźnika.
Zbuduj, w oparciu o powyższą gramatykę bezkontekstową, gramatykę atrybutywną z regułami atrybutowania, ktore umieszczą na atrybucie S.ok wartość logiczną mowiącą, czy wyrażenie wyprowadzone z S jest poprawne.
W pewnym języku programowania występuje typ int reprezentujący liczby całkowite oraz typ list(t) reprezentujący listy o elementach typu t. Wszystkie elementy danej listy muszą być tego samego typu, aby lista była poprawna.
Do tworzenia list służy stała nil (pusta lista) i operator cons budujący listę, argumentami sa głowa i ogon listy. Operatory car i cdr daja odpowiedni głowę i ogon swojego argumentu.
Przykładowo: x = cons(1,cons(0,nil)) tworzy listę zawierającą dwa elementy: 1 i 0,car(x) = 1, cdr(x) = cons(0,nil).
Uzupełnij poniższą gramatykę o opis analizy typów (obliczone typy wyrażeń umieszczaj w atrybucie E.typ):
E → 0 | 1 | E+E | nil | cons(E,E) | car(E) | cdr(E)
.
Rozważmy język, którego składnię opisuje gramatyka w formie EBNF:
Program ::= {Funkcja}
Funkcja ::= id({id:Typ[,]})[:Typ] = Wyrażenie
Wyrażenie ::= num | id {Wyrażenie}
Typ ::= int | Typ -> TypPrzykład poprawnego programu:
main() = f 42 f(r:int):int = s p q r s (a:int->(int->int)->int, d:int->int->int, c:int):int = a c (d c) p(x:int, y:int->int) = x q(x:int, y:int) = x
Zaproponuj system typów dla tego języka.
Dana jest tablica symboli:
f : int -> double a : int g : (double, int) -> string print: string -> void
Narysuj drzewo składniowe dla fragmentu kodu źródłowego
print( g( f( 1), a ) );
Określ typ każdego węzła.
Dana jest tablica symboli:
f : int -> string f : int -> double g : double -> string g : string -> void h : string, double -> int
Narysuj drzewo składniowe dla fragmentu kodu źródłowego:
h ( g( f(5), f(8) ) )
Przeprowadź analizę typów.
Wskazówka: Zgodnie z metodą przedstawioną w wykładzie analiza typów w przypadku przeciążania zwracanej wartości funkcji zachodzi w dwóch fazach:
1. wstępującej - idąc od liści do korzenia w każdym węźle wylicz listę możliwe typy,
2. zstępującej - idąc od korzenia do liści w każdym węźle określ jednoznacznie możliwy typ.
Fragment tablicy symboli kompilatora to
f : int -> void
g : int -> int
t : referencja (wskaźnik) do tablicy intów
i : int
d : double
r : referencja do obiektu klasy K, zawierającej
a : int
h : int -> K (wynikiem jest referencja do K)Powiedz, które z poniższych wyrażeń są L-wartościami:
f g t i d f(1) g(1) t[1] t[g(1)] i + 5 t[t[g(1)] + 5] r r.a r.h(1) r.h(1).a
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.
Część zadań przygotował Tomasz Idziaszek.
Uwaga: jeśli nie zaznaczono inaczej, w ponizszych zadaniach kolejne argumenty funkcji przekazywane są w rejestrach EDI, ESI, EDX, ECX, zaś wynik zwracany w EAX. Funkcja musi zachowywać wartość rejestrów EBP i EBX.
Poniższe zadania nadają się również na laboratorium.
a. Napisz funkcję, która daje zawsze wynik 42 (uwaga na składnię!)
b. Napisz funkcję, która daje w wyniku swój argument.
Programista Tobiasz Niedbalski napisał powyższe funkcje następująco:
a.
.globl f f: mov 42, %eax ret
b.
f: mov %esi, %eax ret
Jakie mogły być tego efekty?
c. (lab) Napisz funkcję printInt(int n), która wypisuje swój argument
Zapisz w asemblerze x86 funkcję obliczającą silnię, w dwóch wersjach - rekurencyjnej oraz iteracyjnej (zanim zabierzemy się za silnię, można najpierw policzyć sumę [1..n]).
Zapisz w asemblerze kod dla prostego przypisania, np. x := (y + 17*x) / z.
Zakładamy, że adresy zmiennych są dostępne w tablicy symboli. Uwaga na dzielenie i różnice między l-wartościami i r-wartościami.
Przykładowe warianty adresów zmiennych:
Napisz w asemblerze szablony do generowania kodu dla wyrażeń warunkowych (if, if else) i pętli (for, while).
Napisz w asemblerze szablony do generowania kodu dla wyrażeń logicznych (dwoma metodami: przez sprowadzenie do wyrażeń arytmetycznych i przez skoki do etykiet).
Na laboratorium można dodatkowo napisać prosty program w C z nietrywialnym wyrażeniem logicznym i podglądnąć jak będzie wyglądał po skompilowaniu.
Zapisz w C prostą biblioteczką z predefiniowanymi funkcjami Latte i funkcją do konkatenacji napisów.
Napisz w asemblerze program demonstrujący użycie funkcji z powyższej biblioteczki.
Napisz funkcję obliczającą największy wspólny dzielnik dwóch liczb.
Napisz funkcję max(int[] a,int n) wyszukującą największy element w n-elementowej tablicy a.
Przetłumacz poniższy fragment programu na kod czwórkowy i sprowadź ten kod do postaci SSA. Wstaw funkcje \(\phi\) tylko tam, gdzie jest to konieczne. Pamiętaj o zmianie nazw (dodaniu indeksów) zmiennych.
while (a != 0) { if (a < 0) { b = 1; } else { b = -1; } a = a + b; }
Dana funkcja
int g(int a,b,c,d,e,f) { while(e) { a = b+c; d = d-c; e=a-f; if(e) f = a-d; else { b = d+f; e = a-c; } b = d+c; } return b; }
Maszyna docelowa: 3 rejestry ogólnego przeznaczenia, wskaźnik stosu i ramki, operacje
LOAD Ri, m -przesłanie z pamieci do rejestru
STORE Rj, m - przeslanie z rejestru do pamieci
SUB Ri, RJ - Ri := Ri - Rj
ADD analogicznie
a. Wygenerować kod czwórkowy, zidentyfikować bloki proste narysować graf przepływu i określić zmienne zywe na początku i końcu każdego bloku prostego.
b. Wygenerować kod maszynowy dla pierwszego bloku {a=b+c itd} metodą opisów rejestrów i wartości
Dana funkcja
unsigned f(unsigned a) { int b = a+1; { unsigned a = b+1; unsigned c = a/2; if(c>0) return f(c); else return 0; } }
Maszyna docelowa: 1 rejestr ogólnego przeznaczenia A, wskaźnik stosu i ramki, operacje
LOAD A, m ;przesłanie z pamieci do rejestru
STORE A, m ; przeslanie z rejestru do pamieci
SUB A, m ; A := A - M[m]
INC A ; A := A+1
SHL A ; A := 2*A
SHR A ; A := A/2
inne operacje analogicznie
a. Wygenerować kod czwórkowy, zidentyfikować bloki proste narysować graf przepływu i określić zmienne zywe na początku i końcu każdego bloku prostego.
b. Wygenerować kod dla opisanej maszyny
Podaj przykład programu w kodzie czwórkowym, który po wykonaniu podanego poniżej
ciągu optymalizacji uprości się do
return 42;
Optymalizacje powinny zostać wykonane w następującej kolejności:
1. Propagacja kopii
2. Eliminacja martwego kodu
3. Eliminacja wspólnych podwyrażeń
4. Propagacja stałej
5. Zwijanie stałej
6. Propagacja stałej
7. Zwijanie stałej
8. Propagacja stałej
9. Eliminacja martwego kodu
10. Zwijanie stałej
11. Propagacja stałej
12. Eliminacja martwego kodu
Uwaga: w każdym kroku daną optymalizację można w razie potrzeby zastosować więcej niż
raz. Tym niemniej obowiązuje kryterium długości kodu wyjściowego.
Dana jest maszyna z dwoma rejestrami R0, R1 i instrukcjami:
Ri:=Ri-Rj odejmowanie zawartości Rj od zawartości Ri
Ri:=Ri/Rj dzielenie zawartości Ri przez zawartosc Rj
Ri:=id
zaladowanie do Ri wartości zmiennej
id:=Ri
zapisanie na zmiennej zawartości rejestru Ri
Ri:=Rj
przepisanie do Ri zawartości Rj
gdzie "i", "j" to 0 lub 1 a "id" to identyfikator zmiennej.
Korzystając z metody tablicy opisów wartości i rejestrów wygeneruj możliwie dobry kod dla
ciągu instrukcji, po którym żywe są zmienne "a" i "b":
x:=a; a:=b/a; b:=a-x; a:=b/x
Dane są deklaracje:
var i,r:integer;
a,b:array [0..n] of integer;
Zakładając, że liczba całkowita zajmuje cztery adresowalne komórki pamięci, wygeneruj kod czwórkowy i narysuj graf przepływu sterowania dla fragmentu programu:
i:=1; while a[i]=b[i] do i:=i+1; r:=a[i]-b[i]
Przyjmując, ze na zakończenie tego fragmentu żyje tylko zmienna "r", zoptymalizuj wygenerowany wcześniej kod czworkowy, nazywając każdą z wykonanych optymalizacji.
Uwaga: Składnia Pascalowa, czyli "=" oznacza porównanie, a ":=" - przypisanie.
Dana funkcja:
int f(int n) { int u=0, v=1, i=2, t; while(i<n) { t=u+v; u=v; v=t; i=i+1; } return v; }
a. Wygeneruj kod czwórkowy w postaci SSA, podziel go na bloki proste;
narysuj graf przeplywu sterowania.
b. Zastosuj (i nazwij) znane optymalizacje w celu ulepszenia kodu
Rozważmy funkcję
void sort(int n) { int i,j,t; for (i = 0; i < n; i++) for (j = n-1; j > i; j--) if (A[j-1] > A[j]) { t = A[j-1]; A[j-1] = A[j]; A[j] = t; } }
a. Wygeneruj kod czwórkowy dla powyższej procedury (bez protokołu wejścia i powrotu). Zidentyfikuj bloki proste i narysuj graf przepływu sterowania. Uwaga: odwołanie do elementu tablicy wymaga podania offsetu tego elementu w bajtach, int zajmuje 4 bajty, tablice indeksowane od 0.
b. Wykonaj kilka kroków optymalizacji uzyskanego kodu czwórkowego (wystarczy zastosować dokładnie 5 różnych rodzajów optymalizacji i je odpowiednio opisać.)
Maszyna docelowa ma dwa rejestry ogólnego przeznaczenia R0,R1
oraz instrukcje (dla i,j=0,1, m oznacza komórkę pamięci):
Ri = Rj
Ri = m
m = Rj
Ri = Ri op Rj
"op" jest pewna operacją arytmetyczną; instrukcje operujące wyłącznie na rejestrach mają koszt 2, instrukcje z dostępem do pamięci mają koszt 7.
Rozważmy blok prosty, na końcu którego żywa jest (tylko) zmienna e:
c = b; a = a op c; d = b op a; e = d op e; e = a op e; a = c op b; e = a op e;
A. Wskaż zmienne żywe przed każdą z instrukcji.
B. Korzystając z metody opisu rejestrów i wartości, wygeneruj możliwie najlepszy (w sensie kosztu) kod dla tego bloku. Do komórek pamięci przechowujących zmienne można się odwoływać przez nazwę zmiennej (np. R0 = a).
Uwaga: na tym etapie należy generować kod maszynowy dokładnie dla podanego kodu czwórkowego, bez żadnych optymalizacji.
C. Jakie optymalizacje można zastosować do tego kodu czwórkowego? W jaki sposób wpłyną one na wynikowy kod maszynowy?