Zadanie 1

W kompilatorze zachodzi często potrzeba wyszukiwania informacji związanej z identyfikatorami (np. jeśli w wyrażeniu występuje zmienna to potrzebujemy sprawdzić czy była ona wcześniej zadeklarowana). Odpowiednią strukturę danych nazywamy tablicą symboli. Abstrakcjnie wymaga to pamięci asocjacyjnej, np. kontenera 'map' z C++. Klasycznie w kompilatorach tablicę symboli realizowno przy pomocy tabel mieszających (choć obecnie jest tendencja do używania struktur danych wbudowanych w język w którym piszemy kompilator). Tabela mieszająca oparta jest na tzw. funkcji mieszającej, odwzorowującej zbiór kluczy (w przypadku tabeli symboli łańcuchy znaków) w przedział liczb całkowitych [0,N] dla pwenego N. Funkcji mieszająca powinna być tak dobrana by jej wartości zachowywały się podobnie jak liczby przypadkowe. Oczywiście, przy zadanym ciągu kluczy i ustalonej funkcji mieszającej otrzymany ciąg liczb całkowitych jest deterministyczny, ale chcemy dobrać funkcję tak by dla "regularnch" ciągów wejściowch wyjście nie było tak regularne. Dokładniej, przy teoretycznej analizie przyjmujemy że wartości funkcji mieszającej są losowe, zaś w praktyce staramy się unikać takich regularności na wyjściu które by unieważniły wynik analizy (daje się znaleźć w miarę dobre i łatwe do obliczenia funkcje mieszające). Mając zadaną funkcję mieszającą tablea mieszająca działa następująco:

Mamy tablicę t indeksową liczbami z [1,N] w której przechowujemy listy par (klucz, wartość). Listy te na początku są puste.
Mając słowo w najpierw obliczamy wartość funkcji mieszającej h = f(w)
Nastepnie wykonujemy wyszukiwanie na liście przechowywanej w t[h]. Jeśli nie znajdziemy w to dodajemy je do tej listy.

Uwaga: w praktyce tablica t zawiera zwykle wskaźnik na początek odpowiedniej listy. Są warianty gdzie elementy list przechowuje się w tabeli t, ale ich w tym zadaniu nie rozważamy

Oszacować średnią długość list po wstawieniu m elementów, zakładając że f(w) przyjmuje losowe wartości, niezależne i równo rozłożone w przedziale 1..N. Porównać oczekiwaną liczbę operacji i zajętość pamięci przy wyszukiwaniu w tabeli mieszającej i w drzewie binarnym.

Zadanie 2

Mamy następujące deklaracje struktur:

struct { char c; long l; short s; int i;} st1;

struct { long l; short s; char c;} st2;

Jak będzie wyglądało ich rozmieszczenie w pamięci zakładając że 2-bajtowe short i 4-bajtowe int i long oraz że short, int i long muszą być przechowywane pod adresami podzielnymi przez 2. Jak to się zmieni jeśli int i long muszą być przechowywane pod adresami podzielnymi przez 4. Jak to się zmieni jeśli long jest 8-bajtowy i musi być przechowywany pod adresami podzielnymi przez 8.

Zadanie 3

Klasy w C++ są zdefiniowane następująco:

class c1 {
   virtual void m1();
   virtual void m2();
   virtual void m3();
};

class c2:c1 {
   virtual void m4();
};

class c3:c2 {
   virtual void m5();
};

Zakładamy że klasa c1 definuje wszystkie swoje metody, klasa c2 definuje m2 i m4, zaś c3 defunuje m3, m4 i m5. Jak będą wyglądały table metod wirtualnych dla c1, c2 i c3. Zakładając że m1 wywołuje m2 i m3 które wersje metod będą wywoływane przez o.m1() dla o będącego odpowienio klasy c1, klasy c2 i klasy c3?

Zadanie 4

Rozważmy następującą deklarację w C:

struct {
    struct {
       int i1;
       char c1;
    } s1[3];
    int i2;
    struct {
       int i2;
       char * str1;
    } s2;
} s3[5];

Jak będzie ona rozmieszczona w pamięci, zakładając 4-bajtowe int, 8-bajtowe wskaźniki i wyrównywanie int do 4 zaś wskaźników do 8. Jak by się ona zmnieniła gdyby C miało semantykę referencyjną dla struktur i tablic (tzn. struktur i tablic jako elementy większych części byłby reprezentowane przez adresy, zaś faktyczne dane byłyby pamiętane oddzielnie). Jak by wyglądało rozmieszczenie w pamięci jeśli oprócz semantyki referencyjnej elementy struktur i tablic zajmowałyby pełne 8-bajtowe słowa (czyli in i char zastałyby powiększone do słowa), przy tym struktury dostały nagłówek z jednego słowa zaś tablice nagłówek z dwu słów (pierwsze identyfikowałoby typ tablicy a drugie dawałoby jej rozmiar). Zakładamy że maszyna posiada wystarczająco dużo dostępnych (wolnych) rejestrów r1, r2, r3, ... i instrukcje 'ldb', 'ldi', 'ldw' o składni 'ldw [ri], rj' które odczytują zawartość dane pod adresem z rejestru ri i umieszczają go w rejestrze rj. Przy tym 'ldw' odczytuje słowo, 'ldi' odczytuje 4-bajtową liczbę całkowitą zaś 'ldb' odczutuje znak (bajt). Dodatkowo maszyna ma instruję 'add stała, ri' która dodaje stałą do rejestru ri. Jak wyglądają sekwencje instrukcji umieszczające w rejestrze r2 wartość s3[2].s1[1].c1 dla poszczególnych wariantów (C, referencyjne C, referencyjne C z wartościami zajmującymi słowa i z nagłówkami). We wszystkich przypadkach zakładamy że w rejestrze r1 znajduje się adres początku struktury s3 i że można go nadpisać w trakcie obliczenia.