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

DjoleRkc: /* Rešenje */

2025-09-18T18:00:14Z

Rešenje

← Старија измена		Верзија на датум 18. септембар 2025. у 20:00
Ред 180:		Ред 180:
	\| < S ><sub>01</sub> \|\| b─┤ \|\| SHIFT		\| < S ><sub>01</sub> \|\| b─┤ \|\| SHIFT
	\|-		\|-
	\| < S ><sub>02</sub>b<sub>2</sub> \|\| ─┤ \|\| REDUCE(2)		\| < S ><sub>01</sub>b<sub>1</sub> \|\| ─┤ \|\| REDUCE(2)
	\|-		\|-
	\| < S ><sub>02</sub> \|\| ─┤ \|\| ACCEPT		\| < S ><sub>01</sub> \|\| ─┤ \|\| ACCEPT
	\|-		\|-
	\|}		\|}

DjoleRkc: /* Rešenje */

2025-09-18T17:58:59Z

Rešenje

← Старија измена		Верзија на датум 18. септембар 2025. у 19:58
Ред 180:		Ред 180:
	\| < S ><sub>01</sub> \|\| b─┤ \|\| SHIFT		\| < S ><sub>01</sub> \|\| b─┤ \|\| SHIFT
	\|-		\|-
	\| < S ><sub>01</sub>b<sub>1</sub> \|\| ─┤ \|\| REDUCE(2)		\| < S ><sub>02</sub>b<sub>2</sub> \|\| ─┤ \|\| REDUCE(2)
	\|-		\|-
	\| < S ><sub>01</sub> \|\| ─┤ \|\| ACCEPT		\| < S ><sub>02</sub> \|\| ─┤ \|\| ACCEPT
	\|-		\|-
	\|}		\|}

DjoleRkc: /* Rešenje */ Ispravka netacnog resenja

2025-08-21T10:17:06Z

Rešenje: Ispravka netacnog resenja

← Старија измена		Верзија на датум 21. август 2025. у 12:17
Ред 170:		Ред 170:
	\| ∇a<sub>1</sub>c<sub>3</sub>c<sub>3</sub> \|\| db─┤ \|\| PANIC: SHIFT		\| ∇a<sub>1</sub>c<sub>3</sub>c<sub>3</sub> \|\| db─┤ \|\| PANIC: SHIFT
	\|-		\|-
	\| ∇a<sub>1</sub>c<sub>3</sub>c<sub>3</sub>d<sub>4</sub> \|\| b─┤ \|\| ~~PANIC: ADVANCE 1~~		\| ∇a<sub>1</sub>c<sub>3</sub>c<sub>3</sub>d<sub>4</sub> \|\| b─┤ \|\| REDUCE(4)
	\|-		\|-
	\| ∇a<sub>1</sub>c<sub>3</sub>c<sub>3</sub>d<sub>4</sub> \|\| ─┤ \|\| ~~PANIC: POP 4~~		\| ∇a<sub>1</sub>c<sub>3</sub>c<sub>3</sub><A><sub>4</sub> \|\| b─┤ \|\| REDUCE(3)
	\|-		\|-
	\| ∇ \|\| ─┤ \|\| ~~REJECT~~		\| ∇a<sub>1</sub>c<sub>3</sub><A><sub>3</sub> \|\| b─┤ \|\| REDUCE(3)
			\|-
			\| ∇a<sub>1</sub><A><sub>3</sub> \|\| b─┤ \|\| REDUCE(1)
			\|-
			\| < S ><sub>01</sub> \|\| b─┤ \|\| SHIFT
			\|-
			\| < S ><sub>01</sub>b<sub>1</sub> \|\| ─┤ \|\| REDUCE(2)
			\|-
			\| < S ><sub>01</sub> \|\| ─┤ \|\| ACCEPT
	\|-		\|-
	\|}		\|}
	Parser ~~nije~~ uspešno završio parsiranje, tj. sekvence se ~~odbija~~.		Parser je uspešno završio parsiranje, tj. sekvence se prihvata.

	== 4. zadatak ==		== 4. zadatak ==

DjoleRkc: /* 3. zadatak */

2024-12-05T12:53:33Z

3. zadatak

@@ Ред 93: / Ред 93: @@
 == 3. zadatak ==
 === Postavka ===
 # &lt;S> → a &lt;A>
@@ Ред 108: / Ред 107: @@
 === Rešenje ===
 == 4. zadatak ==

KockaAdmiralac: /* 4. zadatak */ Napomena za sk

2023-02-26T11:29:13Z

4. zadatak: Napomena za sk

← Старија измена		Верзија на датум 26. фебруар 2023. у 13:29
Ред 185:		Ред 185:

	=== Rešenje ===		=== Rešenje ===
			Iz gorenavedene tabele simbola ne može se zaključiti da li je <code>sk</code> promenljiva tipa <code>SUPERKLASA</code> ili <code>POTKLASA</code>, pa se zaključuje na osnovu njenog imena.
	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">
	program PROBA		program PROBA

KockaAdmiralac: Ispravljeni linkovi

2023-02-09T11:44:16Z

Ispravljeni linkovi

← Старија измена		Верзија на датум 9. фебруар 2023. у 13:44
Ред 11:		Ред 11:

	=== Rešenje ===		=== Rešenje ===
	[[Датотека:PPR februar ~~2022~~ zadatak 1 stablo.svg\|thumb\|Sintaksno stablo u prvom zadatku.]]		[[Датотека:PPR februar 2021 zadatak 1 stablo.svg\|thumb\|Sintaksno stablo u prvom zadatku.]]
	Regularni izraz koji prepoznaje ovu sekvencu može biti <code>(mo(,mo)*\|)</code>, gde je <code>m</code> oznaka za malo slovo a <code>o</code> oznaka za mala slova, velika slova i donju crtu.		Regularni izraz koji prepoznaje ovu sekvencu može biti <code>(mo(,mo)*\|)</code>, gde je <code>m</code> oznaka za malo slovo a <code>o</code> oznaka za mala slova, velika slova i donju crtu.
	{\| class="wikitable"		{\| class="wikitable"
Ред 232:		Ред 232:

	=== Rešenje ===		=== Rešenje ===
	[[Датотека:PPR februar ~~2022~~ zadatak 5 graf.svg\|thumb\|Graf toka kontrole u petom zadatku.]]		[[Датотека:PPR februar 2021 zadatak 5 graf.svg\|thumb\|Graf toka kontrole u petom zadatku.]]
	# x1 := 0		# x1 := 0
	# y1 := 1		# y1 := 1

KockaAdmiralac: Vraćeno na staro ime

2023-01-15T20:56:01Z

Vraćeno na staro ime

← Старија измена		Верзија на датум 15. јануар 2023. у 22:56
Ред 232:		Ред 232:

	=== Rešenje ===		=== Rešenje ===
	[[Датотека:PPR februar 2022 zadatak 5~~.drawio~~.svg\|thumb\|Graf toka kontrole u petom zadatku.]]		[[Датотека:PPR februar 2022 zadatak 5 graf.svg\|thumb\|Graf toka kontrole u petom zadatku.]]
	# x1 := 0		# x1 := 0
	# y1 := 1		# y1 := 1

Brka: Ispravka 5. zadatak u 8. redu

2023-01-15T20:54:53Z

Ispravka 5. zadatak u 8. redu

← Старија измена		Верзија на датум 15. јануар 2023. у 22:54
Ред 232:		Ред 232:

	=== Rešenje ===		=== Rešenje ===
	[[Датотека:PPR februar 2022 zadatak 5 ~~graf~~.svg\|thumb\|Graf toka kontrole u petom zadatku.]]		[[Датотека:PPR februar 2022 zadatak 5.drawio.svg\|thumb\|Graf toka kontrole u petom zadatku.]]
	# x1 := 0		# x1 := 0
	# y1 := 1		# y1 := 1
Ред 240:		Ред 240:
	# x2 := t2		# x2 := t2
	# t3 := Ф(z1, z2)		# t3 := Ф(z1, z2)
	# if t3 != 0 goto 17		# if t3 == 0 goto 17
	# t4 := Ф(y1, y2)		# t4 := Ф(y1, y2)
	# t5 := Ф(z1, z2)		# t5 := Ф(z1, z2)

KockaAdmiralac: Februarski rok 2022. bez trećeg zadatka, prepisujem neki drugi put

2023-01-12T00:22:23Z

Februarski rok 2022. bez trećeg zadatka, prepisujem neki drugi put

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

{{tocright}}
'''Ispit u februarskom roku 2021. godine''' održan je 12. februara. Postavka roka je dostupna [http://ir4pp1.etf.rs/Rokovi/2020-2021/pp1-2021-februar-ispit.pdf sa stranice predmeta.]

== 1. zadatak ==
=== Postavka ===
Data je sekvenca od nula ili više promenljivih razdvojenih zarezima. Svaka promenljiva predstavlja niz od jednog ili više znakova, počinje obavezno malim slovom, nakon čega može doći prozvoljan broj znakova iz skupa koji čine mala slova, cifre i specijalni karakter "_".
<div class="abc-list">
# Napisati regularni izraz koji opisuje navedenu sekvencu.
# Na osnovu regularnog izraza pod a) formirati minimalni DKA korišćenjem metoda pozicije.
</div>

=== Rešenje ===
[[Датотека:PPR februar 2022 zadatak 1 stablo.svg|thumb|Sintaksno stablo u prvom zadatku.]]
Regularni izraz koji prepoznaje ovu sekvencu može biti <code>(mo*(,mo*)*|)</code>, gde je <code>m</code> oznaka za malo slovo a <code>o</code> oznaka za mala slova, velika slova i donju crtu.
{| class="wikitable"
|+ Tabela sledećih pozicija
! 1
| 2, 3, 6
|-
! 2
| 2, 3, 6
|-
! 3
| 4
|-
! 4
| 3, 5, 6
|-
! 5
| 3, 5, 6
|-
! 6
| -
|}
{| class="wikitable"
|+ Pretvaranje nedeterminističkog konačnog automata u deterministički
! !! m !! o !! , !! Prihvata
|-
| → 1, 6 || 2, 3, 6 || || || 1
|-
| 2, 3, 6 || || 2, 3, 6 || 4 || 1
|-
| 4 || 3, 5, 6 || || || 0
|-
| 3, 5, 6 || || 3, 5, 6 || 4 || 1
|}
{| class="wikitable"
|+ Deterministički konačni automat
! !! m !! o !! , !! Prihvata
|-
| → A || B || || || 1
|-
| B || || B || C || 1
|-
| C || D || || || 0
|-
| D || || D || C || 1
|}

== 2. zadatak ==
=== Postavka ===
Za datu gramatiku
# <S> → <A> <S>
# <S> → ε
# <A> → <B> b <B> c
# <A> → <C> c <B>
# <B> → a <D>
# <C> → a <D>
# <D> → ε
<div class="abc-list">
# Nacrtati stanje ∇ karakterističnog LR(0) automata i vrstu ∇ kontrolne tabele SLR(1) parsera. Ima li konflikata?
# Nacrtati stanje ∇ karakterističnog LALR(1) automata i vrstu ∇ kontrolne tabele LALR(1) parsera. Ima li konflikata?
</div>
Napomena: ne crtati ostatak karakterističnog automata, niti ostatak kontrolne tabele.

=== Rešenje ===
Stanje ∇ sadrži u sebi sledeće smene:
* <S'> → • <S> ─┤, {}
* <S> → • <A> <S>, {─┤}
* <S> → •, {─┤}
* <A> → • <B> b <B> c, {a, ─┤}
* <A> → • <C> c <B>, {a, ─┤}
* <B> → • a <D>, {b}
* <C> → • a <D>, {c}
Kako bismo odredili ∇ vrstu kontrolne tabele SLR(1) parsera, moramo odrediti i relevantne FIRST i FOLLOW skupove:
* FOLLOW(<C>) = {c}
* FOLLOW(<S>) = {─┤}
* FIRST(<S>) = FIRST(<A>) = FIRST(<B>) ∪ FIRST(<C>) = {a}
* FOLLOW(<A>) = FIRST(<S>) ∪ FOLLOW(<S>) = {a, ─┤}
* FOLLOW(<B>) = FOLLOW(<A>) ∪ {b, c} = {a, b, c, ─┤}
* FOLLOW(<D>) = FOLLOW(<C>) ∪ FOLLOW(<B>) = {a, b, c, ─┤}
Odavde možemo videti da se u <code>a</code> koloni nalazi SHIFT, a u ─┤ koloni REDUCE(2). Kontrolna tabela bi trebalo da je ista za oba parsera.

== 3. zadatak ==
{{delimično rešeno}}
=== Postavka ===
# <S> → a <A>
# <S> → <S> b
# <A> → c <A>
# <A> → d

Na ulaz LR(0) parsera koji je opisan datom gramatikom dovedi se ulazna sekvenca <code>accbcadb</code>. Pretpostavka je da se za oporavak od grešaka koristi jednostavan panic mode algoritam:
<div class="abc-list">
# sa sigurnim simbolom c.
# sa sigurnim simbolom d.
</div>
Za tačku a) i b) zasebno prikazati rad parsera i jasno naznačiti da li je parser uspešno završio parsiranje.

=== Rešenje ===

== 4. zadatak ==
=== Postavka ===
Kompajler za mikrojavu na izlazu daje sledeći ispis tabele simbola i listing bajtkoda. Kako izgleda izvorni mikrojava program koji odgovara ovim izlazima?
<pre>
==================SADRŽAJ TABELE SIMBOLA=======================
(Level -1)
Type int: int, 0, 0
Type char: char, 0, 0
Con eol: char, 10, 0
Con null: Class, 0, 0
Meth chr: char, 0, 1 [Var i: int, 0, 1 ]
Meth ord: int, 0, 1 [Var ch: char, 0, 1 ]
Meth len: int, 0, 1 [Var arr: Arr of notype, 0, 1 ]
Prog PROBA: notype, 0, 0
[Type SUPERKLASA: Class, 0, 0 [Fld s: int, 1, 1 ][Meth foo: int, 0, 1 [Var this: Class, 0, 2 ]]]
[Type POTKLASA: Class, 6, 0 [Fld s: int, 1, 1 ][Fld p: int, 2, 1 ][Meth foo: int, 9, 1 [Var this: Class, 0, 2 ]]]
[Var sk: Class, 12, 0 ]
[Meth main: notype, 19, 0 ]
</pre>
Mikrojava bajkod:<sup>[sic]</sup>
<pre>
0: enter 1 1
3: const_0
4: jmp 3 (=7)
7: exit
8: return
9: enter 1 1
12: const_1
13: neg
14: jmp 3 (=17)
17: exit
18: return
19: enter 0 0
22: const 102
27: putstatic 0
30: const 111
35: putstatic 1
38: const 111
43: putstatic 2
46: const_m1
47: putstatic 3
50: const 0
55: putstatic 4
58: const -2
63: putstatic 5
66: const 102
71: putstatic 6
74: const 111
79: putstatic 7
82: const 111
87: putstatic 8
90: const_m1
91: putstatic 9
94: const 9
99: putstatic 10
102: const -2
107: putstatic 11
110: new 12
113: dup
114: const 6
119: putfield 0
122: putstatic 12
125: getstatic 12
128: const_1
129: putfield 1
132: getstatic 12
135: dup
136: getfield 0
139: invokevirtual foo
156: const_0
157: print
158: exit
159: return
</pre>

=== Rešenje ===
<syntaxhighlight lang="java">
program PROBA
class SUPERKLASA {
int s;
{
int foo() {
return 0;
}
}
}
class POTKLASA extends SUPERKLASA {
int p;
{
int foo() {
return -1;
}
}
}
SUPERKLASA sk;
{
void main() {
sk = new POTKLASA();
sk.s = 1;
print(sk.foo(), 0);
}
}
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Za dati programski fragment napisati odgovarajući međukod u SSA formi i nacrtati graf toka kontrole na nivou osnovnih blokova.
<syntaxhighlight lang="java">
x = 0;
y = 1;
z = 2;
do {
x = x - 1;

if (z == 0) break;
else y = y + z;

z = y + 1;
} while (z > 1 && x == 0);
x = z - y;
</syntaxhighlight>

=== Rešenje ===
[[Датотека:PPR februar 2022 zadatak 5 graf.svg|thumb|Graf toka kontrole u petom zadatku.]]
# x1 := 0
# y1 := 1
# z1 := 2
# t1 := Ф(x1, x2)
# t2 := t1 - 1
# x2 := t2
# t3 := Ф(z1, z2)
# if t3 != 0 goto 17
# t4 := Ф(y1, y2)
# t5 := Ф(z1, z2)
# t6 := t4 + t5
# y2 := t6
# t7 := y2 + 1
# z2 := t7
# if z2 <= 1 goto 17
# if x2 == 0 goto 4
# t8 := Ф(y1, y2)
# t9 := Ф(z1, z2)
# t10 := t9 - t8
# x3 := t10

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