Програмски преводиоци 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).

Transformisati gramatiku u LL(1) gramatiku.
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 _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.
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 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).

→ <T>
→ <T>
<T> → + N <XnaN>
<T> → - N <XnaN>
<XnaN> → * X
<XnaN> → * X ↑ N
<XnaN> → ε

Rešenje

_x,y → <T>_x₁,y₁ <P'>_x₂,y₂
SELECT(1) = {+, -}

$x_1 \larr x$

$x_2 \larr x$

$y \larr y_1 + y_2$
<P'>_x,y → <T>_x₁,y₁ <P'>_x₂,y₂
SELECT(2) = {+, -}

$x_1 \larr x$

$x_2 \larr x$

$y \larr y_1 + y_2$
<P'>_x,y → ε
SELECT(3) = {─┤}

$y \larr 0$
<T>_x,y → + N_k <XnaN>_x₁,y₁
SELECT(4) = {+}

$x_1 \larr x$

$y \larr k \cdot y_1$
<T>_x,y → - N_k <XnaN>_x₁,y₁
SELECT(5) = {-}

$x_1 \larr x$

$y \larr -k \cdot y_1$
<XnaN>_x,y → * X <Na>_x₁,y₁
SELECT(6) = {*}

$x_1 \larr x$

$y \larr y_1$
<XnaN>_x,y → ε
SELECT(7) = {+, -, ─┤}

$y \larr 1$
<Na>_x,y → ↑ N_k
SELECT(8) = {↑}

$y \larr x^k$
<Na>_x,y → ε
SELECT(9) = {+, -, ─┤}

$y \larr 1$

2. zadatak

Postavka

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();

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).

Konstruisati nedeterministički konačni automat koji prihvata sekvence opisane regularnim izrazom s₁(s₂|s₃).
Dobijeni NKA iz tačke a) konvertovati u deterministički konačni automat.
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:

<S> → <S> , <A>
<S> → 1 <A>
<A> → ( <S> )
<A> → 0
<A> → ε

Konstruisati karakteristični LR(0) automat za datu gramatiku i kontrolnu tabelu SLR(1) parsera.
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
1₂	REDUCE(5)	SHIFT		SHIFT	REDUCE(5)	REDUCE(5)
<S>_x1	SHIFT					SHIFT
,₁	REDUCE(5)	SHIFT		SHIFT	REDUCE(5)	REDUCE(5)
(₃			SHIFT
0₄	REDUCE(4)				REDUCE(4)	REDUCE(4)
<S>_x2	SHIFT				SHIFT
)₃	REDUCE(3)				REDUCE(3)	REDUCE(3)
<A>₁	REDUCE(1)				REDUCE(1)	REDUCE(1)
<A>₂	REDUCE(2)				REDUCE(2)	REDUCE(2)
─┤₀						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.

Ukoliko se vrši sintaksno-upravljano prevođenje, prikazati izgled tabele simbola u trenutku /*T*/.
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

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

Садржај

1. zadatak

Postavka

Rešenje

2. zadatak

Postavka

Rešenje

3. zadatak

Postavka

Rešenje

4. zadatak

Postavka

Rešenje

5. zadatak

Postavka

Rešenje

6. zadatak

Postavka

Rešenje

Мени за навигацију

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

1. zadatak

Postavka

Rešenje

2. zadatak

Postavka

Rešenje

3. zadatak

Postavka

Rešenje

4. zadatak

Postavka

Rešenje

5. zadatak

Postavka

Rešenje

6. zadatak

Postavka

Rešenje

Мени за навигацију

Претрага