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

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

Prvi korak je da dodamo eksplictno stanje greške i da ga dodamo u prazna polja.
Drugi korak je da izračunamo skup prethodnika za sva stanja (na grafu bi to bilo obrtanje strellica).
Treći korak je konstruišemo DKA sa ovim novim funkcijama prelaza, gde će nam početno stanje biti stanja prihvatanja originalnog automata, a stanje prihvatanja početno stanje originalnog automata.

S0 = {B, F}
δ(S0, a) = {B}∪{F} = S1 = {B,F}
δ(S0, a) = ∅ ∪ {D,F} = S2={D,F}
Analogno ćemo ovo uraditi za svako stanje.
Svako stanje koje u sebi sadrži u sebi početno stanje originalnog automata je stanje prihvatanja. I na kraju da bi dobili odgovarajući automat radimo komplement tj. obrnemo stanja prihvatanja.

Traženi automat:

Stanje	a	b	Prihvata
→ S0={C,F}	S1	S2	1
S1={B,F}	S5	S2	1
S2={D,F}	S3	S4	1
S3={F}	S3	S2	1
S4={B,D,F}	S5	S4	1
S5={A,F}	S3	S2	0

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 → a_y <A>_z,v,w <S>_p {b_q}
2. <S>_x1 → d_y1 {c_z1} <A>_{v1, w1, p1}
3. <A>_x,y,z1 → a_q {c_v} <A>_x1,z,u <A>_u,t,y1
   1. $v \larr x - q$
   2. $x_1 \larr x$
   3. $y \larr y_1$
   4. $z_1 \larr z$
4. <A>_t,s,s1 → d_q {b_t1} a_s2
   1. $t_1 \larr t$
   2. $(s,s_1) \larr s_2$

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:

• $x = f(y, z, v, w, p, q)$
• $z = f(y)$
• $q = f(y, z, v, w, p)$

a u drugoj smeni sledeće:

• $x1 = f(y_1, z_1, v_1, w_1, p_1)$
• $z1 = f(y_1)$
• $v1 = f(y_1, z_1)$

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

• 

  Tabela simbola u stanju T1.

• 

  Tabela simbola u stanju T2.

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