DjoleRkc: /* Rešenje */

2024-12-04T12:11:06Z

Rešenje

@@ Ред 19: / Ред 19: @@
 === Rešenje ===
 # &lt;P><sub>x,y</sub> → &lt;T><sub>x<sub>1</sub>,y<sub>1</sub></sub> &lt;P'><sub>x<sub>2</sub>,y<sub>2</sub></sub>
 #: SELECT(1) = {+, -}
@@ Ред 53: / Ред 54: @@
 #: SELECT(9) = {+, -, ─┤}
 #: <math>y \larr 1</math>
 == 2. zadatak ==

Gase273: /* Rešenje */

2024-06-25T09:21:59Z

Rešenje

← Старија измена		Верзија на датум 25. јун 2024. у 11:21
Ред 128:		Ред 128:
	\| 26 \|\| -1		\| 26 \|\| -1
	\|-		\|-
	\| 27 \|\| Adresa C::g		\| 27 \|\| Adresa B::g
	\|-		\|-
	\| 28 \|\| -2		\| 28 \|\| -2

KockaAdmiralac: Moja rešenja januara 2018, slike dodajem uskoro // Edit via Wikitext Extension for VSCode

2023-01-19T14:01:35Z

Moja rešenja januara 2018, slike dodajem uskoro // Edit via Wikitext Extension for VSCode

Нова страница

{{tocright}}
'''Ispit u januarskom roku 2018. godine''' održan je 28. januara. Postavka roka je dostupna [http://ir4pp1.etf.rs/Rokovi/2021-2022/pp1-januar-2021-22.pdf sa stranice predmeta.]

== 1. zadatak ==
=== Postavka ===
Data gramatika sa skupom terminala {+ - N * X ↑} opisuje polinom (na primer -5*X↑2+3*X-1).
<div class="abc-list">
# 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 <code>x</code> neterminala x,y, a vrednost polinoma treba da se dobije kao sintetizovani atribut y istog neterminala. Dodatno, terminal Nk ima atribut <code>k</code> 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).
</div>
# → <T>
# → <T>
# <T> → + N <XnaN>
# <T> → - N <XnaN>
# <XnaN> → * X
# <XnaN> → * X ↑ N
# <XnaN> → ε

=== Rešenje ===
# x,y → <T>x1,y1 <P'>x2,y2
#: SELECT(1) = {+, -}
#: <math>x_1 \larr x</math>
#: <math>x_2 \larr x</math>
#: <math>y \larr y_1 + y_2</math>
# <P'>x,y → <T>x1,y1 <P'>x2,y2
#: SELECT(2) = {+, -}
#: <math>x_1 \larr x</math>
#: <math>x_2 \larr x</math>
#: <math>y \larr y_1 + y_2</math>
# <P'>x,y → ε
#: SELECT(3) = {─┤}
#: <math>y \larr 0</math>
# <T>x,y → + Nk <XnaN>x1,y1
#: SELECT(4) = {+}
#: <math>x_1 \larr x</math>
#: <math>y \larr k \cdot y_1</math>
# <T>x,y → - Nk <XnaN>x1,y1
#: SELECT(5) = {-}
#: <math>x_1 \larr x</math>
#: <math>y \larr -k \cdot y_1</math>
# <XnaN>x,y → * X <Na>x1,y1
#: SELECT(6) = {*}
#: <math>x_1 \larr x</math>
#: <math>y \larr y_1</math>
# <XnaN>x,y → ε
#: SELECT(7) = {+, -, ─┤}
#: <math>y \larr 1</math>
# <Na>x,y → ↑ Nk
#: SELECT(8) = {↑}
#: <math>y \larr x^k</math>
# <Na>x,y → ε
#: SELECT(9) = {+, -, ─┤}
#: <math>y \larr 1</math>

== 2. zadatak ==
=== Postavka ===
<div class="abc-list">
# Predstaviti memorijski raspored, u vreme izvršavanja programa, objekata c1, c2, d1 i d2 i odgovarajućih virtuelnih tabela.<syntaxhighlight lang="java">
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();
</syntaxhighlight>
# 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.
</div>

=== Rešenje ===
[[Датотека:PPR januar 2018 zadatak 2 stek.svg|thumb|Stek u drugom zadatku.]]
{| class="wikitable"
|+ 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 C::g
|-
| 28 || -2
|}
Kod sa procedurama o kojima je reč bi izgledao ovako:
<syntaxhighlight lang="pascal">
procedure P1
procedure P2
procedure P3
begin
P4();
end
procedure P4
begin
...
end
begin
P3();
end
begin
P2();
end
</syntaxhighlight>
Pošto su P3 i P4 na istom leksičkom nivou, a P3 poziva P4, formiranje pristupne veze postiže se sa <syntaxhighlight lang="asm" inline>PUSH [BP+04]</syntaxhighlight>.

== 3. zadatak ==
=== Postavka ===
Neka je s1 sekvenca koju prihvata automat (1), s2 sekvenca koju prihvata automat (2), a s3 sekvenca koju prihvata automat (3).
<div class="abc-list">
# Konstruisati nedeterministički konačni automat koji prihvata sekvence opisane regularnim izrazom s1(s2|s3).
# 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.
</div>
{| class="wikitable"
|+ Automat (1).
! Stanje !! 0 !! 1 !! Prihvata
|-
| → A || A || C || 1
|-
| B || A || B || 0
|-
| C || B || C || 1
|}
{| class="wikitable"
|+ Automat (2).
! Stanje !! 0 !! 1 !! 2 !! Prihvata
|-
| → D || D || D || E || 0
|-
| E || D || E || E || 1
|}
{| class="wikitable"
|+ Automat (3).
! Stanje !! 2 !! 3 !! Prihvata
|-
| → F || F || G || 1
|-
| G || G || F || 0
|}

=== Rešenje ===
{| class="wikitable"
|+ 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
|}
{| class="wikitable"
|+ 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.
<syntaxhighlight lang="java">
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++;
}
}
</syntaxhighlight>

=== Rešenje ===
[[Датотека:PPR januar 2018 zadatak 4 graf.svg|thumb|center|500px|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> → ε
<div class="abc-list">
# 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.
</div>

=== Rešenje ===
[[Датотека:PPR januar 2018 zadatak 5 automat.svg|thumb|Karakteristični LR(0) automat u petom zadatku.]]
* FOLLOW(<S>) = {─┤, ",", )}
* FOLLOW(<A>) = FOLLOW(<S>) = {─┤, ",", )}
{| class="wikitable"
|+ 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.
<div class="abc-list">
# Ukoliko se vrši sintaksno-upravljano prevođenje, prikazati izgled tabele simbola u trenutku <code>/*T*/</code>.
# Napisati kompletan Mikrojava bajtkod prevoda funkcije <code>main</code>.
</div>
<syntaxhighlight lang="java">
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);
}
}
</syntaxhighlight>

=== Rešenje ===
[[Датотека:PPR januar 2018 zadatak 6 tabela.svg|thumb|Tabela simbola u šestom zadatku.]]
Prevod bajtkoda funkcije <code>main</code> može biti:
<syntaxhighlight lang="asm">
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
</syntaxhighlight>

[[Категорија:Рокови]]
[[Категорија:Програмски преводиоци 1]]

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

DjoleRkc: /* Rešenje */

Gase273: /* Rešenje */

KockaAdmiralac: Moja rešenja januara 2018, slike dodajem uskoro // Edit via Wikitext Extension for VSCode