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

Januarski ispit 2024. godine održan je 18. januara i trajao je 150 minuta. Postavka roka nije dostupna sa stranice predmeta.

1. zadatak

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

Postavka

Dat je sledeći kod na programskom jeziku C.

int f1(int a) {
    int b = a;
    b = b + 1;
    return b;
}

int f2(int a) {
    int b = a;
    b = b + f1(1);
    return b;
}

int m(int a, int n, int (*m1)(int), int(*m2)(int)) {
    int tmp1, int tmp2;
    tmp1 = f1(a);
    tmp2 = f2(a);
    
    if (n == 0) {
        return 1;
    } else {
        return tmp2 * m(tmp1, n - 1, m1, m2);
    }
}

int main() {
    printf("%d", m(1, 3, &f1, &f2));
    return 0;
}

• Dati ispis programa;
• Dati izgled steka nakon poslednjeg poziva funkcije f2;
• Dati x86 kod za funkciju f2.

2. zadatak

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

Postavka

Data je sledeća gramatika:

• <S> -> <S>a
• <S> -> <S><A>b
• <S> -> eps
• <A> -> a
• <A> -> b

1. Konstruisati automat i kontrolnu tabelu SLR(1) automata
2. Ispraviti gramatiku tako da se ukloni konflikt ali semantika ostane ista.

3. zadatak

Postavka

Date su sledeće gramatike:

Gramatika A:

1. <P> -> o <P> <P>
2. <P> -> v

Gramatika B:

1. <P> -> <P> o <P>
2. <P> -> v

Gramatika C:

1. <P> -> <P> <P> o
2. <P> -> v

Gramatika D:

1. <P> -> v <Q>
2. <Q> -> <P> o <Q>
3. <Q> -> eps

Gramatika E

1. <P> -> v <P> o
2. <P> -> v

• Koje su dve gramatike iste?
• Dokazati na primeru neke sekvence da se ostale 3 gramatike razlikuju.

Rešenje

a) Gramatika A jedina može počinjati sa O, pa ona sigurno nije ista kao neka druga. Gramatika B može prihvatiti sekvencu VOV, dok gramatika C ne može, pa ni one nisu iste. Gramatika C mora početi sa VV, što važi i za gramatiku E, pa su te dve gramatike iste.

b) Ukoliko uzmemo sekvencu OVV, takva sekvenca je validna za gramatiku A, ali nije za gramatike B i D. U gramatici B vidimo da ukoliko je ulazna sekvenca duža od 1, posle V mora da sledi O, dok u gramatici D to nije slučaj. Na primer, za sekvencu VVO se vidi da se B i D razlikuju jer gramatika D prihvata takvu sekvencu dok je gramatika B odbija.

4. zadatak

Postavka

Napisati funkciju static Obj find(String name, boolean isGlobal) za mikrojavu, koja se ponaša kao operator :: ako je isGlobal=true. Traženu funkciju pisati od nule.

public class Tab {
    public static final Struct
        noType = new Struct(Struct.None),
        intType = new Struct(Struct.Int),
        charType = new Struct(Struct.Char),
        nullType = new Struct(Struct.Class);
    public static final Obj noObj = new Obj(Obj.Var, "noObj", noType);
    public static Obj chrObj, ordObj, lenObj;
    public static Scope currentScope; 
    private static int currentLevel; //universe == -1

    public static Obj find(String name, boolean isGlobal);
}

Rešenje

public static Obj find(String name, boolean isGlobal) {
    Obj result = null;

    if (isGlobal == true) {
        Scope s = currentScope;

        while (s.getOuter() != null) {
            s = s.getOuter();
        }

        if (s.getLocals() != null) {
            result = s.getLocals().searchKey(name);
        }

    } else {
        for (Scope s = currentScope; s != null; s = s.getOuter()) {
            if (s.getLocals() != null) {
                result = s.getLocals().searchKey(name);
                if (result != null) break;
            }
        }
    }

    return (result != null) ? result : noObj;
}

Operator :: preskače sve opsege i traži ime direktno u universe opsegu. Pošto u fragmentu koda koji je dat nije navedeno da postoji pokazivač na universe opseg, onda se u if grani ide na gore sve dok se ne dođe do njega i zatim se u njemu pretražuje. Else grana je standardna implementacija koja je data u projektu.

5. zadatak

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

Postavka

Za dati regularni izraz (a | (bc)*)+ d (c | ε)+ konstruisati DKA.

6. zadatak

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

Postavka

Za sledeći kod napisati Mikrojava bajtkod.

int b;
const int one = 1;

class A {
    int[] niz;
    int calc(int a) {
        ...nebitno
    }
}

class B extends A {
    int calc(int a) {
        ...isto nebitno
    }
}

int f(int c) 
{
    if (c > 10) return c;
    else return c + 1;
}

void main() 
    int x, y; A c;
{
    read(b);
    b = f(b);
    c = new B;
    x = 0;

    do {
        if (x % 2 == 0) y = c.calc(b);
        else y = y + (b + one);
        
        x++;
    } while (x < 5);
}