Programski prevodioci 1/Januar 2024

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

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

1. zadatak

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

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.

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

Postavka

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

6. zadatak

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