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

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

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

1. задатак

Поставка

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

Поставка

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

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

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. задатак

Поставка

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

6. задатак

Поставка

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

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