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

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

1. zadatak

Postavka

Data gramatika sa skupom terminala {+ - N * X ↑} opisuje polinom (na primer -5*X↑2+3*X-1).

1. Transformisati gramatiku u LL(1) gramatiku.
2. Dodati LL(1) gramatici attribute da se izračuna vrednost polinoma za zadatu vrednost X. Pri tome, zadata vrednost X se prosleđuje kao nasleđeni atribut x neterminala <P>_x,y, a vrednost polinoma treba da se dobije kao sintetizovani atribut y istog neterminala. Dodatno, terminal N_k ima atribut k koji predstavlja celobrojnu vrednost. Ostali terminali nemaju atribute.
3. Za LL(1) gramatiku sa atributima dobijenu pod b) prikazati delove parsera na principu rekurzivnog spusta: proceduru main i delove parsera koji odgovaraju smenama za neterminale <P> i <XnaN>. Ostatak parsera ne navoditi. Koristiti funkciju advance(attr) koja vraća kao rezultat sledeći token sa ulaza i dodatno vraća kroz parameter attr vrednost atributa tog tokena (0 ako token nema atribut).

1. <P> → <P> <T>
2. <P> → <T>
3. <T> → + N <XnaN>
4. <T> → - N <XnaN>
5. <XnaN> → * X
6. <XnaN> → * X ↑ N
7. <XnaN> → ε

Rešenje

1. <P>_x,y → <T>_x1,y1 <P'>_x2,y2

   SELECT(1) = {+, -}

   $x_1 \larr x$

   $x_2 \larr x$

   $y \larr y_1 + y_2$

2. <P'>_x,y → <T>_x1,y1 <P'>_x2,y2

   SELECT(2) = {+, -}

   $x_1 \larr x$

   $x_2 \larr x$

   $y \larr y_1 + y_2$

3. <P'>_x,y → ε

   SELECT(3) = {─┤}

   $y \larr 0$

4. <T>_x,y → + N_k <XnaN>_x1,y1

   SELECT(4) = {+}

   $x_1 \larr x$

   $y \larr k \cdot y_1$

5. <T>_x,y → - N_k <XnaN>_x1,y1

   SELECT(5) = {-}

   $x_1 \larr x$

   $y \larr -k \cdot y_1$

6. <XnaN>_x,y → * X <Na>_x1,y1

   SELECT(6) = {*}

   $x_1 \larr x$

   $y \larr y_1$

7. <XnaN>_x,y → ε

   SELECT(7) = {+, -, ─┤}

   $y \larr 1$

8. <Na>_x,y → ↑ N_k

   SELECT(8) = {↑}

   $y \larr x^k$

9. <Na>_x,y → ε

   SELECT(9) = {+, -, ─┤}

   $y \larr 1$

2. zadatak

Postavka

1. Predstaviti memorijski raspored, u vreme izvršavanja programa, objekata c1, c2, d1 i d2 i odgovarajućih virtuelnih tabela.

   class A           { int a = 0; int f() {...} }
   class B extends A { int g (){...} }
   class C extends B { int g (){...} }
   class D extends B { int b = 0; int f (){...} }
   C c1 = new C(); C c2 = new C();
   D d1 = new D(); D d2 = new D();
   

2. Nacrtati izgled run time steka programa i navesti sekvencu koda za formiranje pristupne veze procedure P4 (ostatak pozivne sekvence ne navoditi). Procedure P3 i P4 su ugneždene u proceduru P2, koja je ugneždena u proceduru P1. Iz P1 se poziva P2, iz P2 se poziva P3, iz P3 se poziva P4.

Rešenje

Stek u drugom zadatku.

Raspored statičkog dela memorije u vreme izvršavanja.

Adresa	Vrednost
0	Adresa c1
1	Adresa c2
2	Adresa d1
3	Adresa d2
4	"f"
5	-1
6	Adresa A::f
7	-2
8	"f"
9	-1
10	Adresa A::f
11	"g"
12	-1
13	Adresa B::g
14	-2
15	"f"
16	-1
17	Adresa A::f
18	"g"
19	-1
20	Adresa C::g
21	-2
22	"f"
23	-1
24	Adresa D::f
25	"g"
26	-1
27	Adresa B::g
28	-2

Kod sa procedurama o kojima je reč bi izgledao ovako:

procedure P1
    procedure P2
        procedure P3
        begin
            P4();
        end
        procedure P4
        begin
            ...
        end
    begin
        P3();
    end
begin
    P2();
end

Pošto su P3 i P4 na istom leksičkom nivou, a P3 poziva P4, formiranje pristupne veze postiže se sa PUSH [BP+04].

3. zadatak

Postavka

Neka je s₁ sekvenca koju prihvata automat (1), s₂ sekvenca koju prihvata automat (2), a s₃ sekvenca koju prihvata automat (3).

1. Konstruisati nedeterministički konačni automat koji prihvata sekvence opisane regularnim izrazom s₁(s₂|s₃).
2. Dobijeni NKA iz tačke a) konvertovati u deterministički konačni automat.
3. Za dobijeni DKA u tački b) proveriti da li je minimalan i, ukoliko je potrebno, sprovesti proces minimizacije.

Automat (1).

Stanje	0	1	Prihvata
→ A	A	C	1
B	A	B	0
C	B	C	1

Automat (2).

Stanje	0	1	2	Prihvata
→ D	D	D	E	0
E	D	E	E	1

Automat (3).

Stanje	2	3	Prihvata
→ F	F	G	1
G	G	F	0

Rešenje

Nedeterministički konačni automat

Stanje	0	1	2	3	Prihvata
→ A, D, F	A, D, F	C, D, F	E, F	G	1
C, D, F	B, D	C, D, F	E, F	G	1
E, F	D	E	E, F	G	1
G			G	F	0
B, D	A, D, F	B, D	E		0
D	D	D	E		0
E	D	E	E		1
F			F	G	1

Deterministički konačni automat

Stanje	0	1	2	3	Prihvata
→ S1	S1	S2	S3	S4	1
S2	S5	S2	S3	S4	1
S3	S6	S7	S3	S4	1
S4			S4	S8	0
S5	S1	S5	S7		0
S6	S6	S6	S7		0
S7	S6	S7	S7		1
S8			S8	S4	1

Navedeni deterministički konačni automat je već minimalan.

4. zadatak

Postavka

Za programski fragment napisati odgovarajući troadresni međukod u SSA formi i dati graf toka kontrole na nivou bazičnih blokova.

void insertionSort(int arr[], int n)
{
    int i, key, j;
    i = 1;
    while (i < n)
    {
        key = arr[i];
        j = i-1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = key;
        i++;
    }
}

Rešenje

Graf toka kontrole u četvrtom zadatku.

5. zadatak

Postavka

Data je sledeća gramatika:

1. <S> → <S> , <A>
2. <S> → 1 <A>
3. <A> → ( <S> )
4. <A> → 0
5. <A> → ε

1. Konstruisati karakteristični LR(0) automat za datu gramatiku i kontrolnu tabelu SLR(1) parsera.
2. Prikazati LALR(1) predikcione skupove konfiguracija u početnom stanju LR(0) automata i svim stanjima u koja se neposredno prelazi iz početnog stanja.

Rešenje

Karakteristični LR(0) automat u petom zadatku.

• FOLLOW(<S>) = {─┤, ",", )}
• FOLLOW(<A>) = FOLLOW(<S>) = {─┤, ",", )}

Kontrolna tabela SLR(1) parsera

Stanje	,	0	1	(	)	─┤
∇			SHIFT
12	REDUCE(5)	SHIFT		SHIFT	REDUCE(5)	REDUCE(5)
<S>x1	SHIFT					SHIFT
,1	REDUCE(5)	SHIFT		SHIFT	REDUCE(5)	REDUCE(5)
(3			SHIFT
04	REDUCE(4)				REDUCE(4)	REDUCE(4)
<S>x2	SHIFT				SHIFT
)3	REDUCE(3)				REDUCE(3)	REDUCE(3)
<A>1	REDUCE(1)				REDUCE(1)	REDUCE(1)
<A>2	REDUCE(2)				REDUCE(2)	REDUCE(2)
─┤0						ACCEPT

6. zadatak

Postavka

Dat je listing programa napisanog na programskom jeziku Mikrojava. Sve metode unutrašnjih klasa su virtuelne. Globalne metode se pozivaju statički.

1. Ukoliko se vrši sintaksno-upravljano prevođenje, prikazati izgled tabele simbola u trenutku /*T*/.
2. Napisati kompletan Mikrojava bajtkod prevoda funkcije main.

program Ispit
    const int K = 2;
    class C {
        int d;
    {
        int m(int c)
        { return c * d; }
    } }
    class DC extends C {
        int v;
    {
        int m(int q) /*T*/
        { return q + d; }
    } }
{
    void main()
        C c;
    {
        c = new DC;
        c.d = c.m(K);
    }
}

Rešenje

Tabela simbola u šestom zadatku.

Prevod bajtkoda funkcije main može biti:

enter 0, 1
new 12
dup
const_4
putfield 0
store_0
load_0
load_0
const_2
load_0
getfield 0
invokevirtual 'm' -1
putfield 1
exit
return