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

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу

Ispit u januarskom roku 2022. godine održan je 28. januara. Postavka roka je dostupna sa stranice predmeta.

1. zadatak

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

Postavka

Odrediti minimalni konačni deterministički automat koji prihvata one i samo one ulazne sekvence koje NE prihvata konačni automat sa slike ali kada se čitaju sa desna u levo. Na primer, dati automat ne prihvata sekvencu ab, to znači da traženi automat treba da prihvati sekvencu ba. Postupak izložiti po koracima, na generalan način koji bi se mogao primeniti i na svaki drugi automat.

Stanje a b Prihvata
→ A B 0
B C D 0
C 1
D F 0
F F F 1

Rešenje

2. zadatak

Postavka

  1. Za smene 1 i 2 date gramatike navesti koje atribute treba računati i od kojih drugih atributa oni mogu da zavise da bi cela gramatika bila L-atributivna. Pravila navoditi u obliku aa = f(bb, cc, dd,..) gde je aa atribut koji mora da se računa, dok su bb, cc, dd, itd svi drugi atributi od kojih posmatrani može da zavisi. Neterminal <S> ima sintetizovan atribut.
  2. Navesti pseudokod za proceduru A u parseru na bazi rekurzivnog spusta. Ostale delove parsera ne navoditi. Preimenovati promenljive da se minimizuje broj pravila kopiranja vrednosti atributa.
  1. <S>x → ay <A>z,v,w <S>p {bq}
  2. <S>x1 → dy1 {cz1} <A>v1, w1, p1
  3. <A>x,y,z1 → aq {cv} <A>x1,z,u <A>u,t,y1
  4. <A>t,s,s1 → dq {bt1} as2

Rešenje

Iz date gramatike možemo zaključiti sledeće o tipovima atributa:

  • Akcije b i c sadrže nasleđene atribute.
  • Neterminal <A> sadrži tri atributa, od kojih je prvi nasleđen a druga dva sintetizovana.

Na osnovu toga, u prvoj smeni vidimo da atributi mogu imati sledeće vrednosti:

a u drugoj smeni sledeće:

Kod parsera sa adekvatno preimenovanim atributima dat je ispod:

void A(int x, int& y, int& z) {
    switch (input) {
        case 'a':
            input = advance();
            int q = getInputValue();
            out('c', x - q);
            int u;
            A(x, z, u);
            int t;
            A(u, t, y);
            break;
        case 'd':
            input = advance();
            out('b', x);
            input = advance();
            y = z = getInputValue();
            break;
    }
}

3. zadatak

Postavka

Zadata je gramatika

  1. <S> → <S> b <A>
  2. <S> → <A> a <B> b
  3. <A> → <B> c <B> d
  4. <A> → ε
  5. <B> → ε
  1. Konstruisati karaketristični[sic] automat LR(0) parsera kao i odgovarajuću kontrolnu tabelu. Da li ima konflikata?
  2. Konstruisati kontrolnu tabelu SLR(1) parsera. Da li ima konflikata?

Rešenje

Karakteristični LR(0) automat u trećem zadatku.
Kontrolna tabela LR(0) parsera
Stanje Akcija
<S'>0 R/R konflikt
<A>2 SHIFT
<B>31 SHIFT
<S>x SHIFT
c3 REDUCE(5)
<B>32 SHIFT
d3 REDUCE(3)
a2 REDUCE(5)
<B>2 SHIFT
b2 REDUCE(2)
─┤0 ACCEPT
b1 R/R konflikt
<A>1 REDUCE(1)

FOLLOW skupovi su sledeći:

  • FOLLOW(<S>) = {─┤, b}
  • FOLLOW(<B>) = {b, c, d}
  • FOLLOW(<A>) = {a} ∪ FOLLOW(<S>) = {─┤, a, b}
Kontrolna tabela SLR(0) parsera
Stanje a b c d ─┤
<S'>0 REDUCE(4) R/R konflikt REDUCE(5) REDUCE(5) REDUCE(4)
<A>2 SHIFT
<B>31 SHIFT
<S>x SHIFT SHIFT
c3 REDUCE(5) REDUCE(5) REDUCE(5)
<B>32 SHIFT
d3 REDUCE(3) REDUCE(3) REDUCE(3)
a2 REDUCE(5) REDUCE(5) REDUCE(5)
<B>2 SHIFT
b2 REDUCE(2) REDUCE(2)
─┤0 ACCEPT
b1 REDUCE(4) R/R konflikt REDUCE(5) REDUCE(5) REDUCE(4)
<A>1 REDUCE(1) REDUCE(1)

4. zadatak

Postavka

Dat je listing programa Januar2022, napisan na programskom jeziku Mikrojava. Sve metode unutrašnjih klasa su virtuelne. Globalne metode se pozivaju statički. Napisati kompletan Mikrojava bajtkod prevoda funkcije f za dati program

program Januar2022
	const int K = 2;
	int add;
	class A {
		int fld;
	{
		int m(int a)
		{ return fld * 2; }
		void met()
		{ fld = fld + 3; }
	} }
	class B extends A {
	{
		int m(int b)
		{ /*T1*/
			return fld + b;
		}
	}
	}
	A arr[];
{
	int f(int index){
		add = arr[index].m(K);
		arr[index].met();
		return add + K;
	}
	void main()
		B b;
		int ret;
	{
		/*T2*/
		arr = new A[2];
		arr[0] = new B;
		arr[1] = new A;
		ret = f(0) + f(1);
		print(arr[0].m(ret));
	}
}

Rešenje

enter 1, 1
getstatic 1
load_0
aload
const_2
getstatic 1
load_0
aload
getfield 0
invokevirtual 'm' -1
putstatic 0
getstatic 1
load_0
aload
dup
getfield 0
invokevirtual 'm' 'e' 't' -1
getstatic 0
const_2
add
exit
return

5. zadatak

Postavka

Prikazati izgled tabele simbola u trenucima T1 i T2 na osnovu izvornog koda iz zadatka 4 prema formatu čvorova tabele simbola iz priloga. Universe opseg ne treba crtati. Za T2 dovoljno je naznačiti izmene u odnosu na prethodno stanje tabele.

Rešenje

6. zadatak

Postavka

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

a = 1;
b = 2;
c = 3;
for (a = 4; b < c || a < 10; a++) {
    if (a > b + c) {
        c++;
        break;
    } else if (a > b * c) {
        b--;
        continue;
    }
    else return a;
}
a = b * c;
return a;

Rešenje

Karakteristični LR(0) automat u trećem zadatku.
  1. a1 := 1
  2. b1 := 2
  3. c1 := 3
  4. a2 := 4
  5. t1 := Ф(b1, b2)
  6. if t1 < c1 goto 8
  7. if a2 >= 10 goto 17
  8. t2 := t1 + c1
  9. if a <= t2 goto 12
  10. c2 := c1 + 1
  11. goto 17
  12. t3 := t1 * c1
  13. if a <= t3 goto 16
  14. b2 := t1 - 1
  15. goto 5
  16. return a2
  17. t4 := Ф(b1, b2)
  18. t5 := Ф(c1, c2)
  19. t6 := t1 * t2
  20. a3 := t6
  21. return a3