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

Јануарски испит 2024. године одржан је 18. јануара и трајао је 150 минута. Поставка рока није доступна са странице предмета.

1. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

Дат је следећи код на програмском језику 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;
}

• Дати испис програма;
• Дати изглед стека након последњег позива функције f2;
• Дати x86 код за функцију f2.

2. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

Дата је следећа граматика:

• <С> -> <С>а
• <С> -> <С><А>б
• <С> -> епс
• <А> -> а
• <А> -> б

1. Конструисати аутомат и контролну табелу СЛР(1) аутомата
2. Исправити граматику тако да се уклони конфликт али семантика остане иста.

3. задатак

Поставка

Дате су следеће граматике:

Граматика А:

1. <П> -> о <П> <П>
2. <П> -> в

Граматика Б:

1. <П> -> <П> о <П>
2. <П> -> в

Граматика C:

1. <П> -> <П> <П> о
2. <П> -> в

Граматика D:

1. <П> -> в <Q>
2. <Q> -> <П> о <Q>
3. <Q> -> епс

Граматика Е

1. <П> -> в <П> о
2. <П> -> в

• Које су две граматике исте?
• Доказати на примеру неке секвенце да се остале 3 граматике разликују.

Решење

а) Граматика А једина може почињати са О, па она сигурно није иста као нека друга. Граматика Б може прихватити секвенцу ВОВ, док граматика C не може, па ни оне нису исте. Граматика C мора почети са ВВ, што важи и за граматику Е, па су те две граматике исте.

б) Уколико узмемо секвенцу ОВВ, таква секвенца је валидна за граматику А, али није за граматике Б и D. У граматици Б видимо да уколико је улазна секвенца дужа од 1, после V мора да следи О, док у граматици D то није случај. На пример, за секвенцу ВВО се види да се Б и D разликују јер граматика D прихвата такву секвенцу док је граматика Б одбија.

4. задатак

Поставка

Написати функцију static Obj find(String name, boolean isGlobal) за микројаву, која се понаша као оператор :: ако је isGlobal=true. Тражену функцију писати од нуле.

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

Решење

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

Оператор :: прескаче све опсеге и тражи име директно у универсе опсегу. Пошто у фрагменту кода који је дат није наведено да постоји показивач на универсе опсег, онда се у иф грани иде на горе све док се не дође до њега и затим се у њему претражује. Елсе грана је стандардна имплементација која је дата у пројекту.

5. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

За дати регуларни израз (a | (bc)*)+ d (c | ε)+ конструисати ДКА.

6. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

За следећи код написати Микројава бајткод.

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