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

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

Januarski ispit 2023. godine održan je 19. januara. Postavka roka nije 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.

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

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++;
        }
    }
}

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

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:

• INT_digit - 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} , INT_digit { minDigit = min(minDigitRHS, digit); maxDigit = max(maxDigitRHS, digit); }
5. <num_arr>_{minDigit, maxDigit} -> INT_digit { 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.

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_0
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: ...