Програмски преводиоци 1/Јануар 2023

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу

Januarski ispit 2023. godine održan je 19. januara. Postavka roka je dostupna sa stranice predmeta.

1. zadatak

Postavka

Dat je sledeći program: 

int main() {
    int count;
    void procX() {
        void report() {
            writeln("count = " + count);
        }
        void proxY() {
            int count;
            count = 200;
            report();
        }
        count = 100;
        report();
        procY();
    }
    count = 300;
    procX();
}
  1. Ukoliko se koristi statičko razrešavanje dosega, šta će ispisati dati program?
  2. Ukoliko se koristi dinamičko razrešavanje dosega, šta će ispisati dati program?
  3. Ukoliko se za nelokalne promenljive koriste displeji, nacrtati poslednje stanje steka i displeja nakon što je report funkcija pozvana poslednji put.

Rešenje

a) Ispis:
count = 100
count = 100
Objasnjenje: Statičko razrešavanje znači da veza između imena promenljive i deklaracije se pravi u vreme prevođenja (kompajliranja). Dakle, kada se report kompajlira, kompajler već odluči: "ovo count u report se odnosi na count iz procX", jer je to najbliži leksički obuhvatajući opseg.
b) Ispis:
count = 100
count = 200
Objasnjenje: Kod dinamičkog razrešavanja, nelokalna promenljiva se traži preko lanca aktivacionih zapisa na steku, počev od najbližeg pozivaoca. c)

2. zadatak

Postavka

Dat je isečak koda klase Struct. Dopuniti metodu AssignableTo kodom koji fali. 

public class Struct {
    private int kind;
    private Struct elemType;
    public boolean Equals(Struct other) {
        return (this == other) || (kind == Kinds.Array && other.kind == Kinds.Array && elemType.Equals(other.ElemType));
    }
    public boolean IsRefType() {
        return kind == Kinds.Class || kind == Kinds.Array;
    }
    public boolean AssignableTo(Struct dest) {
        if (this.Equals(dest) || 
                || (kind == Kinds.Array && dest.kind == Kinds.Array && dest.elemType == Tab.noType)) {
            return true;
        }
        return false;
    }
}

Rešenje

Preuzeto iz udžbenika Programski prevodioci 1 (Dragan Bojić, Maja Vukasović) sa strane 209. 

class Struct {
    ...
    // checks, if this can be assigned to dest (explicit. assignment, parameters)
    public bool AssignableTo (Struct dest) {
        if ( this.Equals(dest) || this == Tab.nullType && dest.IsRefType() ||
            kind == Kinds.Arr && dest.kind == Kinds.Arr && // for len()
            dest.elemType == Tab.noType) return true;
        for (Struct s = elemType; s != null; s = s.elemType) {
            if (s.equals(dest)) return true;
        }
        return false;
    }
}

3. zadatak

Овај задатак није решен. Помозите SI Wiki тако што ћете га решити.

Postavka

Za dati blok koda napisati međukod a zatim nacrtati graf toka kontrole sa međukodom u SSA formi. 

int res = 10;
for (int i = 0; i < 10; i++) {
    int n = res;
    for (int j = i + 1; j < n; j++) {
        if ((i + j) % 2 == 0) {
           res++;
        }
    }
}

Rešenje

4. zadatak

Postavka

Za datu gramatiku konstruisati karakteristički LR(0) automat i kontrolnu tabelu, a zatim dodati LALR(1) predikcione skupove.

  1. <S> → <S> <A>
  2. <A> → <A> a <A> b
  3. <A> → <S> a
  4. <A> → c

Rešenje

Ova postavka zadatka je gotovo sigurno pogrešna, jer se u stanju praznog steka kod LR(0) parsera ne može preći ni u jedno drugo stanje, a ne može ni da se uradi Reduce. Takođe, nejasno je kakve ulazne sekvence prihvata/odbija ovakva gramatika jer se one ne mogu ni generisati zbog toga što jedina smena za startni neterminal < S > sadrži levu rekurziju, pa je tako jedina moguća sekvenca ona u kojoj se < S > neprestano dodaje na početak.

5. zadatak

Postavka

U datoj gramatici neterminalu <list> dodati sintetizovani atribut koji naizmenično sadrži cifre najvećih i najmanjih brojeva iz niza. Na primer, ukoliko je sekvenca koja se prepoznaje [1, 2, 3] [4, 5, 6] [7, 8, 9], taj atribut bi imao vrednost 349. Smatrati da terminal INT ima sintetizovani simbol sa svojom vrednošću.

  1. <list> → <list> <item>
  2. <list> → <item>
  3. <item> → [ <num_arr> ]
  4. <num_arr> → <num_arr>, INT
  5. <num_arr> → INT

Rešenje

Uvodimo sledeće sintetizovane atribute:

  • INTdigit - digit predstavlja cifru opisanu terminalom INT
  • <num_arr>minDigit, maxDigit - minDigit predstavlja minimalnu cifru sadržanu u nizu cifara <num_arr>, a maxDigit maksimalnu cifru sadržanu u nizu cifara <num_arr>
  • <item>minDigit, maxDigit - minDigit predstavlja minimalnu cifru sadržanu u nizu cifara koji se nalazi u neterminalu <item>, a maxDigit maksimalnu cifru sadržanu u nizu cifara koji se nalazi u neterminalu <item>
  • <list>value, takeMinDigit - value predstavlja vrednost koju treba izračunati po postavci zadatka, a takeMinDigit da li u sledećem koraku treba uzeti minimalnu ili maksimalnu cifru (ovo posmatramo kao neki flag kome u svakom koraku invertujemo vrednost, a čija je početna vrednost 1 jer u prvom koraku uzimamo maksimalnu, a u drugom minimalnu cifru)

Atributivno translaciona gramatika izgleda ovako (stvari koje su dodate u odnosu na gramatiku iz postavke su prikazane podebljanim slovima):

  1. <list>value, takeMinDigit -> <list>valueRHS, takeMinDigitRHS <item>minDigit, maxDigit { value = valueRHS * 10 + (takeMinDigitRHS == 1) ? minDigit : maxDigit; takeMinDigit = 1 - takeMinDigitRHS; }
  2. <list>value, takeMinDigit -> <item>minDigit, maxDigit { value = maxDigit; takeMinDigit = 1; }
  3. <item>minDigit, maxDigit -> [ <num_arr>minDigitRHS, maxDigitRHS ] { minDigit = minDigitRHS; maxDigit = maxDigitRHS; }
  4. <num_arr>minDigit, maxDigit -> <num_arr>minDigitRHS, maxDigitRHS , INTdigit { minDigit = min(minDigitRHS, digit); maxDigit = max(maxDigitRHS, digit); }
  5. <num_arr>minDigit, maxDigit -> INTdigit { minDigit = digit; maxDigit = digit; }

6. zadatak

Postavka

Napisati kompletan prevod funkcija f1, f2 i main na Mikrojava bajtkod. Smatrati da prevod f1 kreće od adrese 0. Sekciju označenu sa // ... nije potrebno prevoditi i smatrati da je njena dužina jedna instrukcija. 

program Januar2023
int b;
class A {
    int fun1(int p) {...}
}
class B {
    A[] arr;
}
B bObj;
int f1() {
    return 1;
}
int f2() {
    return 2;
}
void main() int x; {
    bObj = new B;
    // ...
    b = bObj.arr[1].fun1(3);
    if (b < x) {
        b = f1();
    }
    else b = f2();
}

Rešenje

00: enter 0 0
03: const_1
04: exit
05: return
06: enter 0 0
09: const_2
10: exit
11: return
12: enter 0 1
15: new 4
18: dup
19: const_2
20: putfield 0
23: putstatic 1
26: ...
27: getstatic 1
30: getfield 1
33: const_1
34: aload
35: const_3
36: getstatic 1
39: getfield 1
42: const_1
43: aload
44: getfield 0
47: invokevirtual 'f' 'u' 'n' '1' -1
68: putstatic 0
71: getstatic 0
74: load_0
75: jge 12
78: call -78
81: putstatic 0
84: jmp 9
87: call -81
90: putstatic 0
93: exit
94: return
95: ...
Преузето из „https://siwiki.rs/w/index.php?title=Програмски_преводиоци_1/Јануар_2023&oldid=8109”