Andrija: dodat tag

2026-03-14T23:07:00Z

dodat tag

← Старија измена		Верзија на датум 15. март 2026. у 01:07
Ред 255:		Ред 255:

	== 5. zadatak ==		== 5. zadatak ==
			{{ознака\|5. zadatak\|Табела симбола}}
	=== Postavka ===		=== 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.		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.

Pop: /* Rešenje */

2025-08-19T16:14:42Z

Rešenje

← Старија измена		Верзија на датум 19. август 2025. у 18:14
Ред 21:		Ред 21:

	=== Rešenje ===		=== Rešenje ===
			Prvi korak je da dodamo eksplictno stanje greške i da ga dodamo u prazna polja. <br>
			Drugi korak je da izračunamo skup prethodnika za sva stanja (na grafu bi to bilo obrtanje strellica). <br>
			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} <br>
			δ(S0, a) = {B}∪{F} = S1 = {B,F} <br>
			δ(S0, a) = ∅ ∪ {D,F} = S2={D,F} <br>
			Analogno ćemo ovo uraditi za svako stanje. <br>
			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.


			<b>Traženi automat:</b>

			{\| class="wikitable"
			! 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 ==		== 2. zadatak ==

WikiEditor: /* z -> y */

2023-06-28T19:20:14Z

z -> y

← Старија измена		Верзија на датум 28. јун 2023. у 21:20
Ред 49:		Ред 49:
	a u drugoj smeni sledeće:		a u drugoj smeni sledeće:
	* <math>x1 = f(y_1, z_1, v_1, w_1, p_1)</math>		* <math>x1 = f(y_1, z_1, v_1, w_1, p_1)</math>
	* <math>z1 = f(~~z_1~~)</math>		* <math>z1 = f(y_1)</math>
	* <math>v1 = f(y_1, z_1)</math>		* <math>v1 = f(y_1, z_1)</math>
	Kod parsera sa adekvatno preimenovanim atributima dat je ispod:		Kod parsera sa adekvatno preimenovanim atributima dat je ispod:

KockaAdmiralac: a2 > 10 ispravljeno na a2 >= 10

2023-02-26T10:25:27Z

a2 > 10 ispravljeno na a2 >= 10

← Старија измена		Верзија на датум 26. фебруар 2023. у 12:25
Ред 263:		Ред 263:
	# t1 := Ф(b1, b2)		# t1 := Ф(b1, b2)
	# if t1 < c1 goto 8		# if t1 < c1 goto 8
	# if a2 > 10 goto 17		# if a2 >= 10 goto 17
	# t2 := t1 + c1		# t2 := t1 + c1
	# if a <= t2 goto 12		# if a <= t2 goto 12

KockaAdmiralac: Januarski rok 2022. godine, bez prvog zadatka

2023-01-11T20:12:16Z

Januarski rok 2022. godine, bez prvog zadatka

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

{{tocright}}
'''Ispit u januarskom roku 2022. 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 ==
{{delimično rešeno}}
=== 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.
{| class="wikitable"
! Stanje !! a !! b !! Prihvata
|-
| → A || B || || 0
|-
| B || C || D || 0
|-
| C || || || 1
|-
| D || || F || 0
|-
| F || F || F || 1
|}

=== Rešenje ===

== 2. zadatak ==
=== Postavka ===
<div class="abc-list">
# 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.
# 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.
</div>
# <S>x → ay <A>z,v,w <S>p {bq}
# <S>x1 → dy1 {cz1} <A>v1, w1, p1
# <A>x,y,z1 → aq {cv} <A>x1,z,u <A>u,t,y1
## <math>v \larr x - q</math>
## <math>x_1 \larr x</math>
## <math>y \larr y_1</math>
## <math>z_1 \larr z</math>
# <A>t,s,s1 → dq {bt1} as2
## <math>t_1 \larr t</math>
## <math>(s,s_1) \larr s_2</math>

=== Rešenje ===
Iz date gramatike možemo zaključiti sledeće o tipovima atributa:
* Akcije <code>b</code> i <code>c</code> sadrže nasleđene atribute.
* Neterminal <code><A></code> 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:
* <math>x = f(y, z, v, w, p, q)</math>
* <math>z = f(y)</math>
* <math>q = f(y, z, v, w, p)</math>
a u drugoj smeni sledeće:
* <math>x1 = f(y_1, z_1, v_1, w_1, p_1)</math>
* <math>z1 = f(z_1)</math>
* <math>v1 = f(y_1, z_1)</math>
Kod parsera sa adekvatno preimenovanim atributima dat je ispod:
<syntaxhighlight lang="cpp">
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;
}
}
</syntaxhighlight>

== 3. zadatak ==
=== Postavka ===
Zadata je gramatika
# <S> → <S> b <A>
# <S> → <A> a b
# <A> → c d
# <A> → ε
# → ε
<div class="abc-list">
# Konstruisati karaketristični[sic] automat LR(0) parsera kao i odgovarajuću kontrolnu tabelu. Da li ima konflikata?
# Konstruisati kontrolnu tabelu SLR(1) parsera. Da li ima konflikata?
</div>

=== Rešenje ===
[[Датотека:PPR januar 2022 zadatak 3 automat.svg|thumb|Karakteristični LR(0) automat u trećem zadatku.]]
{| class="wikitable"
|+ Kontrolna tabela LR(0) parsera
! Stanje !! Akcija
|-
| <S'>0 || '''R/R konflikt'''
|-
| <A>2 || SHIFT
|-
| 31 || SHIFT
|-
| <S>x || SHIFT
|-
| c3 || REDUCE(5)
|-
| 32 || SHIFT
|-
| d3 || REDUCE(3)
|-
| a2 || REDUCE(5)
|-
| 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, c, d}
* FOLLOW(<A>) = {a} ∪ FOLLOW(<S>) = {─┤, a, b}
{| class="wikitable"
|+ 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 || || || ||
|-
| 31 || || || SHIFT || ||
|-
| <S>x || || SHIFT || || || SHIFT
|-
| c3 || || REDUCE(5) || REDUCE(5) || REDUCE(5) ||
|-
| 32 || || || || SHIFT ||
|-
| d3 || REDUCE(3) || REDUCE(3) || || || REDUCE(3)
|-
| a2 || || REDUCE(5) || REDUCE(5) || REDUCE(5) ||
|-
| 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 <code>f</code> za dati program
<syntaxhighlight lang="java">
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));
}
}
</syntaxhighlight>

=== Rešenje ===
<pre>
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
</pre>

== 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 ===
<gallery widths="500" heights="500" class="transparent-svg">
PPR januar 2022 zadatak 5 T1.svg | Tabela simbola u stanju T1.
PPR januar 2022 zadatak 5 T2.svg | Tabela simbola u stanju T2.
</gallery>

== 6. 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="c">
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;
</syntaxhighlight>

=== Rešenje ===
[[Датотека:PPR januar 2022 zadatak 6 graf.svg|thumb|Karakteristični LR(0) automat u trećem zadatku.]]
# a1 := 1
# b1 := 2
# c1 := 3
# a2 := 4
# t1 := Ф(b1, b2)
# if t1 < c1 goto 8
# if a2 > 10 goto 17
# t2 := t1 + c1
# if a <= t2 goto 12
# c2 := c1 + 1
# goto 17
# t3 := t1 * c1
# if a <= t3 goto 16
# b2 := t1 - 1
# goto 5
# return a2
# t4 := Ф(b1, b2)
# t5 := Ф(c1, c2)
# t6 := t1 * t2
# a3 := t6
# return a3

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

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

Andrija: dodat tag

Pop: /* Rešenje */

WikiEditor: /* z -> y */

KockaAdmiralac: a2 > 10 ispravljeno na a2 >= 10

KockaAdmiralac: Januarski rok 2022. godine, bez prvog zadatka