Laboratorium 7: tablica symboli

Tablica nazw

Zaprojektuj i zaimplementuj swoją tablicę nazw - strukturę danych dostarczającą operacji

• insert - wstawienie nazwy
• find - wyszukanie nazwy

W testowaniu moze pomóc poniższy kod:

void test() {
  NameTab nameTab;
  int identifiers = 0;
  while(yylex()) {
     identifiers ++;
     if(!nameTab.insert(yytext,yyleng)) 
       abort("FATAL: Pool memory exhausted");
  }   
  cout << "Identifier lexems: " << identifiers << endl;
  cout << "Repeats: " << nameTab.repeated << endl;

Lexer: https://gist.github.com/706400

[ben@students Nametab]$ find /usr/include -name \*.h | xargs cat | /usr/bin/time ./pooled
Identifier lexems: 3679282
Repeats: 3265862
2.94user 0.13system 0:03.11elapsed 98%CPU (0avgtext+0avgdata 67104maxresident)k
0inputs+0outputs (0major+4257minor)pagefaults 0swaps

Kalkulator ze zmiennymi

Rozszerz kalkulator o zmienne i przypisania, np

x = 2*2
y = x+1
y*y
25

Laboratorium 8: tablica symboli z zagnieżdzaniem

Rozszerzamy nasz kalkulator ze zmiennymi z poprzedniego laboratorium do prostego języka programowania ze strukturą blokową, na przykład

int a = 1;
int b = 2*a;
{
  int a = 3;
  b = a+b;
}
b-a;

alternatywnie

int a,b;
a = 1;
b = 2*a;
{
  int a ;
  a = 3;
  b = a+b;
}
b-a;

W tym celu należy zaimplementować tablicę symboli co najmniej z operacjami:

• wejście do zakresu
• dodanie definicji (identyfikator i jego wartość)
• odczytanie wartości identyfikatora
• modyfikacja identyfikatora
• opuszczenie zakresu

Mozna przyjąć, że deklaracja bez inicjalizatora nadaje wartość 0.

Laboratorium 9: kontrola typów

Rozszerzamy język z poprzedniego laboratorium o typ zmiennoprzecinkowy i kontrole typów, na przykład

int a,b;
double c;
a = 1;
b = 2*a;
{
  double a ;
  a = 3.14159;
  c = a+double(b);
}
int(c-a);

Laboratorium 10: kod czwórkowy

Kod czwórkowy

W PUBLIC/MRJP/Quadruples/ dostępny jest edukacyjny interpreter kodu czwórkowego iquadr}

Implementowany dialekt:

• program jest ciągiem otypowanych funkcji
• nieograniczona ilość rejestrów typu int i double, np. i0, d1
• zmienne lokalne i tymczasowe: t2 := a + t1 pisane jako $.i2 := a.i3 + $.i1 (identyfikator przed kropką ma charakter li tylko komentarza)
• brak zmiennych globalnych (tylko funkcje)
• konwersje między typami np. $.i1 := b.d0
• dodatkowa instrukcja print, np. print $.i0
• nie ma wbudowanego mechanizmu przekazywania parametrów
• dostęp do pamięci; adresowanie postaci {rejestr+stała}, np. {sp.i1-1} := 2,
  

  a.i3 := {bp.i2+1}

Przykłady

Liczby Fibonacciego

function main : int :
    $.d3 	:= 1.0
    lo.i0 	:= $.d3
    hi.i1 	:= lo.i0
    mx.i3 	:= 5000000
    mx.i2 	:= $.i3
    print lo.i0
L0:
    if hi.i1 >= mx.i2 goto L1
    print hi.i1
    $.i3 	:= lo.i0 + hi.i1
    hi.i1 	:= $.i3
    $.i3 	:= hi.i1 - lo.i0
    lo.i0 	:= $.i3
    goto L0
L1:
function end

Wywołanie funkcji z przekazywaniem argumentów w rejestrach:

function main : int :
  $.i0 := -40
  $.i0 := ~$.i0
  $.d0 := 3.14159
  call add
  print $.i0
function end
 
function add : int -> double -> int :
  $.i1 := b.d0
  result.i0 := a.i0 + $.i1
function end

Protokół wywołania funkcji przy użyciu stosu:

function main : int :
  sp.i1 := 512 
  bp.i2 := sp.i1
  {sp.i1-1} := 2
  {sp.i1-2} := 3
  sp.i1 := sp.i1 - 2
  call add
  print retval.i0
function end
 
function add : int -> int -> int :
  sp.i1 := sp.i1 - 1
  {sp.i1+0} := bp.i2
  bp.i2 := sp.i1
  a.i3 := {bp.i2+1}
  b.i4 := {bp.i2+2}
  retval.i0 := a.i3 + b.i4
function end

Zadania

1. Zakoduj i przetestuj prostą funkcję, np. silnię
2. Rozszerz kalkulator z poprzednich zajęć o funkcję generowania kodu czwórkowego
3. Dodaj instrukcje warunkowe, pętli,...