Програмски преводиоци 1/Фебруар 2021

Ispit u februarskom roku 2021. godine održan je 12. februara. Postavka roka je dostupna sa stranice predmeta.

1. zadatak

Postavka

Data je sekvenca od nula ili više promenljivih razdvojenih zarezima. Svaka promenljiva predstavlja niz od jednog ili više znakova, počinje obavezno malim slovom, nakon čega može doći prozvoljan broj znakova iz skupa koji čine mala slova, cifre i specijalni karakter "_".

1. Napisati regularni izraz koji opisuje navedenu sekvencu.
2. Na osnovu regularnog izraza pod a) formirati minimalni DKA korišćenjem metoda pozicije.

Rešenje

Sintaksno stablo u prvom zadatku.

Regularni izraz koji prepoznaje ovu sekvencu može biti (mo*(,mo*)*|), gde je m oznaka za malo slovo a o oznaka za mala slova, velika slova i donju crtu.

Tabela sledećih pozicija

1	2, 3, 6
2	2, 3, 6
3	4
4	3, 5, 6
5	3, 5, 6
6	-

Pretvaranje nedeterminističkog konačnog automata u deterministički

	m	o	,	Prihvata
→ 1, 6	2, 3, 6			1
2, 3, 6		2, 3, 6	4	1
4	3, 5, 6			0
3, 5, 6		3, 5, 6	4	1

Deterministički konačni automat

	m	o	,	Prihvata
→ A	B			1
B		B	C	1
C	D			0
D		D	C	1

2. zadatak

Postavka

Za datu gramatiku

1. <S> → <A> <S>
2. <S> → ε
3. <A> → <B> b <B> c
4. <A> → <C> c <B>
5. <B> → a <D>
6. <C> → a <D>
7. <D> → ε

1. Nacrtati stanje ∇ karakterističnog LR(0) automata i vrstu ∇ kontrolne tabele SLR(1) parsera. Ima li konflikata?
2. Nacrtati stanje ∇ karakterističnog LALR(1) automata i vrstu ∇ kontrolne tabele LALR(1) parsera. Ima li konflikata?

Napomena: ne crtati ostatak karakterističnog automata, niti ostatak kontrolne tabele.

Rešenje

Stanje ∇ sadrži u sebi sledeće smene:

• <S'> → • <S> ─┤, {}
• <S> → • <A> <S>, {─┤}
• <S> → •, {─┤}
• <A> → • <B> b <B> c, {a, ─┤}
• <A> → • <C> c <B>, {a, ─┤}
• <B> → • a <D>, {b}
• <C> → • a <D>, {c}

Kako bismo odredili ∇ vrstu kontrolne tabele SLR(1) parsera, moramo odrediti i relevantne FIRST i FOLLOW skupove:

• FOLLOW(<C>) = {c}
• FOLLOW(<S>) = {─┤}
• FIRST(<S>) = FIRST(<A>) = FIRST(<B>) ∪ FIRST(<C>) = {a}
• FOLLOW(<A>) = FIRST(<S>) ∪ FOLLOW(<S>) = {a, ─┤}
• FOLLOW(<B>) = FOLLOW(<A>) ∪ {b, c} = {a, b, c, ─┤}
• FOLLOW(<D>) = FOLLOW(<C>) ∪ FOLLOW(<B>) = {a, b, c, ─┤}

Odavde možemo videti da se u a koloni nalazi SHIFT, a u ─┤ koloni REDUCE(2). Kontrolna tabela bi trebalo da je ista za oba parsera.

3. zadatak

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

Postavka

1. <S> → a <A>
2. <S> → <S> b
3. <A> → c <A>
4. <A> → d

Na ulaz LR(0) parsera koji je opisan datom gramatikom dovedi se ulazna sekvenca accbcadb. Pretpostavka je da se za oporavak od grešaka koristi jednostavan panic mode algoritam:

1. sa sigurnim simbolom c.
2. sa sigurnim simbolom d.

Za tačku a) i b) zasebno prikazati rad parsera i jasno naznačiti da li je parser uspešno završio parsiranje.

4. zadatak

Postavka

Kompajler za mikrojavu na izlazu daje sledeći ispis tabele simbola i listing bajtkoda. Kako izgleda izvorni mikrojava program koji odgovara ovim izlazima?

==================SADRŽAJ TABELE SIMBOLA=======================
(Level -1)
Type int: int, 0, 0
Type char: char, 0, 0
Con eol: char, 10, 0
Con null: Class, 0, 0
Meth chr: char, 0, 1 [Var i: int, 0, 1 ]
Meth ord: int, 0, 1 [Var ch: char, 0, 1 ]
Meth len: int, 0, 1 [Var arr: Arr of notype, 0, 1 ]
Prog PROBA: notype, 0, 0
[Type SUPERKLASA: Class, 0, 0 [Fld s: int, 1, 1 ][Meth foo: int, 0, 1 [Var this: Class, 0, 2 ]]]
[Type POTKLASA: Class, 6, 0 [Fld s: int, 1, 1 ][Fld p: int, 2, 1 ][Meth foo: int, 9, 1 [Var this: Class, 0, 2 ]]]
[Var sk: Class, 12, 0 ]
[Meth main: notype, 19, 0 ]

Mikrojava bajkod:^[sic]

0: enter 1 1
3: const_0
4: jmp 3 (=7)
7: exit
8: return
9: enter 1 1
12: const_1
13: neg
14: jmp 3 (=17)
17: exit
18: return
19: enter 0 0
22: const 102
27: putstatic 0
30: const 111
35: putstatic 1
38: const 111
43: putstatic 2
46: const_m1
47: putstatic 3
50: const 0
55: putstatic 4
58: const -2
63: putstatic 5
66: const 102
71: putstatic 6
74: const 111
79: putstatic 7
82: const 111
87: putstatic 8
90: const_m1
91: putstatic 9
94: const 9
99: putstatic 10
102: const -2
107: putstatic 11
110: new 12
113: dup
114: const 6
119: putfield 0
122: putstatic 12
125: getstatic 12
128: const_1
129: putfield 1
132: getstatic 12
135: dup
136: getfield 0
139: invokevirtual foo
156: const_0
157: print
158: exit
159: return

Rešenje

Iz gorenavedene tabele simbola ne može se zaključiti da li je sk promenljiva tipa SUPERKLASA ili POTKLASA, pa se zaključuje na osnovu njenog imena.

program PROBA
    class SUPERKLASA {
        int s;
        {
            int foo() {
                return 0;
            }
        }
    }
    class POTKLASA extends SUPERKLASA {
        int p;
        {
            int foo() {
                return -1;
            }
        }
    }
    SUPERKLASA sk;
    {
        void main() {
            sk = new POTKLASA();
            sk.s = 1;
            print(sk.foo(), 0);
        }
    }

5. zadatak

Postavka

Za dati programski fragment napisati odgovarajući međukod u SSA formi i nacrtati graf toka kontrole na nivou osnovnih blokova.

x = 0;
y = 1;
z = 2;
do {
    x = x - 1;

    if (z == 0) break;
    else y = y + z;

    z = y + 1;
} while (z > 1 && x == 0);
x = z - y;

Rešenje

Graf toka kontrole u petom zadatku.

1. x1 := 0
2. y1 := 1
3. z1 := 2
4. t1 := Ф(x1, x2)
5. t2 := t1 - 1
6. x2 := t2
7. t3 := Ф(z1, z2)
8. if t3 == 0 goto 17
9. t4 := Ф(y1, y2)
10. t5 := Ф(z1, z2)
11. t6 := t4 + t5
12. y2 := t6
13. t7 := y2 + 1
14. z2 := t7
15. if z2 <= 1 goto 17
16. if x2 == 0 goto 4
17. t8 := Ф(y1, y2)
18. t9 := Ф(z1, z2)
19. t10 := t9 - t8
20. x3 := t10