Програмски преводиоци 1/Септембар 2023

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

Ispit u septembarskom roku 2023. godine održan je 16. Septembra.

1. zadatak

Postavka

(10p) Dat je deo implementacije klase Node u programskom jeziku Java, koja predstavlja čvor u sintaksnom stablu izgenerisanom za konstrukciju DKA korišćenjem metoda pozicije, gde su objašnjenja polja i metoda data u komentarima iznad njih (sva polja su inicijalizovana konstruktorom):

    public class Node {
        private enum Type {
            ASTERISK,   // *
            PLUS,       // +
            PERIOD,     // .
            OR,         // |
            SYMBOL,     // s
            EPSILON     // ε
        }
        // left subtree of position node, null if leaf (symbol) node
        private Node left;

        // right subtree of position node, null if unary operation or leaf (symbol) node
        private Node right;

        // type of position node
        private Type type;

        // position of symbol in regex, only valid for leaf (symbol) nodes, otherwise set to -1
        private int symbolPos;

        // check whether the subsequence with the given node as root of the subtree can be empty
        public boolean isNullable();

        // find sert of leaf (symbol) node positions which could be at the beginning of
        // subsequence with the given node as root of the subtree
        public Set<Integer> firstPos();

        // find set of leaf (symbol) node positions which could be at the end of
        // subsequence with the given node as root of the subtree
        public Set<Integer> lastPos();

        // returns a union of the two parameters
        public static Set<Integer> union(Set<Integer> first, Set<Integer> second);
    }

Potrebno je napisati implementaciju metoda firstPos() i lastPos()

1a. zadatak

Identičan ovakav zadatak (za isti broj poena) se pojavio u Avgustu 2023, samo se tražila implementacija isNullable().

2. zadatak

Postavka

(10p) Za rekurzivni spust koji opisuje navedenu gramatiku, koji su opisani ispod:

1. Dopuniti delove rekurzivnog spusta obeleženih sa labelama PN (N označava labelu koja se može popuniti i može predstavljati jednu ili više linija koda), ukoliko je poznato da se sekvence aadddbb, dd i ab prihvataju.
2. Napisati LL(1) gramatiku opisanu rekurzivnim spustom.

Glavni program:
IN = NEXTCHAR();
call PROCS;
if (INP<> '˧')
    then REJECT;
    else ACCEPT;
end if;
end;

procedure PROCS:
    case IN of
        'a': goto P1;
        'd', 'b', '˧': goto P2;
        default: REJECT;
    end case;
P1: /* ... */
P2: /* ... */
end procedure;

procedure PROCA:
    case IN of
        'b', '˧': goto P3;
        'd': goto P4;
        default: REJECT;
    end case;
P3: /* ... */
P4: /* ... */
end procedure;

3. zadatak

Postavka

(10p) Za dati Mikrojava bajtkod:

1. Navesti izlaz programa.
2. Rekonstruisati izvorni Mikrojava kod na osnovu datog bajtkoda.

0:      enter 2 2
3:      load_0
4:      load_1
5:      mul
6:      jmp 3 (=9)
9:      exit
10:     return
11:     enter 2 3
14:     const_0
15:     store_2
16:     load_2
17:     load_1
18:     jge 21 (=39)
21:     load_0
22:     load_2
23:     aload
24:     const_0
25:     print
26:     const 32
31:     const_0
32:     bprint
33:     inc 2,1
36:     jmp -20 (=16)
39:     const 10
44:     const_0
45:     bprint
46:     exit
47:     return
48:     enter 0 5
51:     const_0
52:     store_0
53:     const 10
58:     newarray 1
60:     store_1
61:     const 10
66:     newarray 1
68:     store_2
69:     load_0
70:     const 10
75:     jge 74 (=149)
78:     load_1
79:     load_0
80:     load_0
81:     const 10
86:     mul
87:     load_0
88:     const_3
89:     rem
90:     add
91:     astore
92:     load_0
93:     const_2
94:     rem
95:     const_1
96:     jne 12 (=108)
99:     load_1
100:    load_0
101:    const_1
102:    neg
103:    load_1
104:    load_0
105:    aload
106:    mul
107:    astore
108:    load_1
109:    load_0
110:    aload
111:    const_2
112:    call -112 (=0)
115:    store_3
116:    load_1
117:    load_0
118:    aload
119:    const_3
120:    call -120 (=0)
123:    store 4
125:    load_3
126:    load 4
128:    jle 10 (=138)
131:    load_2
132:    load_0
133:    load_3
134:    astore
135:    jmp 8 (=143)
138:    load_2
139:    load_0
140:    load 4
142:    astore
143:    inc 0,1
146:    jmp -77 (=69)
149:    load_1
150:    const 10
155:    call -144 (=11)
158:    load_2
159:    const 10
164:    call -153 (=11)
167:    exit
168:    return

4. zadatak

Postavka

(10p) Za datu gramatiku konstruisati:

1. LR(0) karakteristični automat
2. LALR(1) karakteristični automat
3. Za oba slučaja LR(0) i LALR(1) navesti stanja sa po jednim konfliktom i objasniti o kom se konfliktu radi, u slučaju da konflikt postoji. Nije potrebno konstruisati tabele parsera.

Oba automata prikazati u vidu grafa prelaza, unutar stanja napisati konfiguracije.

1. <S> → ( <X> )
2. <S> → [ <X> ]
3. <S> → ( <Y> ]
4. <S> → [ <Y> )
5. <X> → a
6. <Y> → a

5. zadatak

Postavka

(10p) Nacrtati graf memorijske predstave objekata c, d1 i d2:

class A { int x; }
class B { int y; }
class C extends A, B { int z; }
class D extends B, C { int v; }
C c; D d1, d2;

1. Ako je dozvoljen neiskorišćen prostor na nivou objekata.
2. Ako neiskorišćen prostor može da postoji samo na nivou klase, a ne i objekata

6. zadatak

Postavka

(10p) Dat je sledeći program na jeziku sličnom Pascalu. Statičko okruženje za nelokalne promenljive je realizovano pomoću pristupnih veza. Glavni program poseduje sopstveni akcioni zapis na steku.

1. Prikazati jasno i precizno izgled steka poziva neposredno pre povratka iz procedure c. Voditi računa o formatu aktivacionih zapisa
2. Napisati kompletan 80x86 asemblerski kod koji bi kompajler izgenerisao za procedure c i d (enter i leave instrukcije ne postoje)

program Sep23 (output);
    var g, t: integer

    procedure b(p: integer)
        var m: integer;

        procedure c ()
        begin
            g := m+t;
        end; {c}
        procedure d (p: integer)
            t := p+2;
            c();
        end {d}
    begin
        m := p+1;
        d(m);
    end; {b}

begin
    g := 1
    b(g);
end. {Sep23}