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

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

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

1. задатак

Поставка

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

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. Уколико се користи статичко разрешавање досега, шта ће исписати дати програм?
2. Уколико се користи динамичко разрешавање досега, шта ће исписати дати програм?
3. Уколико се за нелокалне променљиве користе дисплеји, нацртати последње стање стека и дисплеја након што је report функција позвана последњи пут.

2. задатак

Поставка

Дат је исечак кода класе Struct. Допунити методу AssignableTo кодом који фали.

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

Решење

Преузето из уџбеника Програмски преводиоци 1 (Драган Бојић, Маја Вукасовић) са стране 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. задатак

Поставка

За дати блок кода написати међукод а затим нацртати граф тока контроле са међукодом у ССА форми.

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

Поставка

За дату граматику конструисати карактеристички ЛР(0) аутомат и контролну табелу, а затим додати ЛАЛР(1) предикционе скупове.

1. <С> → <С> <А>
2. <А> → <А> а <А> б
3. <А> → <С> а
4. <А> → ц

5. задатак

Поставка

У датој граматици нетерминалу <list> додати синтетизовани атрибут који наизменично садржи цифре највећих и најмањих бројева из низа. На пример, уколико је секвенца која се препознаје [1, 2, 3] [4, 5, 6] [7, 8, 9], тај атрибут би имао вредност 349. Сматрати да терминал INT има синтетизовани симбол са својом вредношћу.

1. <лист> → <лист> <итем>
2. <лист> → <итем>
3. <итем> → [ <нум_арр> ]
4. <нум_арр> → <нум_арр>, ИНТ
5. <нум_арр> → ИНТ

Решење

Уводимо следеће синтетизоване атрибуте:

• ИНТ_дигит - дигит представља цифру описану терминалом ИНТ
• <нум_арр>_{минДигит, маxДигит} - минДигит представља минималну цифру садржану у низу цифара <нум_арр>, а маxДигит максималну цифру садржану у низу цифара <нум_арр>
• <итем>_{минДигит, маxДигит} - минДигит представља минималну цифру садржану у низу цифара који се налази у нетерминалу <итем>, а маxДигит максималну цифру садржану у низу цифара који се налази у нетерминалу <итем>
• <лист>_{валуе, такеМинДигит} - валуе представља вредност коју треба израчунати по поставци задатка, а такеМинДигит да ли у следећем кораку треба узети минималну или максималну цифру (ово посматрамо као неки флаг коме у сваком кораку инвертујемо вредност, а чија је почетна вредност 1 јер у првом кораку узимамо максималну, а у другом минималну цифру)

Атрибутивно транслациона граматика изгледа овако (ствари које су додате у односу на граматику из поставке су приказане подебљаним словима):

1. <лист>_{валуе, такеМинДигит} -> <лист>_{валуеРХС, такеМинДигитРХС} <итем>_{минДигит, маxДигит} { валуе = валуеРХС * 10 + (такеМинДигитРХС == 1) ? минДигит : маxДигит; такеМинДигит = 1 - такеМинДигитРХС; }
2. <лист>_{валуе, такеМинДигит} -> <итем>_{минДигит, маxДигит} { валуе = маxДигит; такеМинДигит = 1; }
3. <итем>_{минДигит, маxДигит} -> [ <нум_арр>_{минДигитРХС, маxДигитРХС} ] { минДигит = минДигитРХС; маxДигит = маxДигитРХС; }
4. <нум_арр>_{минДигит, маxДигит} -> <нум_арр>_{минДигитРХС, маxДигитРХС} , ИНТ_дигит { минДигит = мин(минДигитРХС, дигит); маxДигит = маx(маxДигитРХС, дигит); }
5. <нум_арр>_{минДигит, маxДигит} -> ИНТ_дигит { минДигит = дигит; маxДигит = дигит; }

6. задатак

Поставка

Написати комплетан превод функција f1, f2 и main на Микројава бајткод. Сматрати да превод f1 креће од адресе 0. Секцију означену са // ... није потребно преводити и сматрати да је њена дужина једна инструкција.

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

Решење

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: jgt 13
78: call -78
81: putstatic 0
84: jmp 9
87: call -81
90: putstatic 0
93: exit
94: return
95: ...