Програмски преводиоци 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 {
    class Kinds {
        public static final int None = 0, Int = 1, Char = 2,
                                Array = 3, Class = 4, Bool = 5;
    }
    private int kind;
    private Struct elemType; 
    private int numOfFields;
    public boolean IsRefType() {
        return kind == Kinds.Class || kind == Kinds.Array;
    }
    public boolean Equals(Struct other) {
        if (kind == Kinds.Array) return other.kind == Kinds.Array
                && elemType.Equals(other.elemType);
        if (kind == Kinds.Class) return other.kind == Kinds.Class
                && numOfFields == other.numOfFields
                && Obj.equalsCompleteHash(members, other.members);
        return this == other;
    }
    public boolean CompatibleWith(Struct other) {
        return this.Equals(other)
                || this == Tab.nullType && other.IsRefType()
                || other == Tab.nullType && this.IsRefType();
    }
    public boolean AssignableTo(Struct dest) {
        if (this.Equals(dest) || (this == Tab.nullType && dest.IsRefType())
                || (this.kind == Kinds.Array && dest.kind == Kinds.Array && dest.elemType == Tab.noType)) {
            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();
}