WikiEditor: /* ispravka */

2023-06-28T10:14:12Z

ispravka

← Старија измена		Верзија на датум 28. јун 2023. у 12:14
Ред 87:		Ред 87:
	! B		! B
	\| STATE(S2)		\| STATE(S2)
	\| PUSH(A)		\|
			* PUSH(A)
			* ADVANCE
	\| REJECT		\| REJECT
	\| REJECT		\| REJECT

WikiEditor: /* ispravka */

2023-06-28T01:01:17Z

ispravka

← Старија измена		Верзија на датум 28. јун 2023. у 03:01
Ред 255:		Ред 255:
	load_1		load_1
	const_0		const_0
	jne 20 # y == 0)		jne 18 # y == 0)
	getstatic 0 # global.p++;		getstatic 0 # global.p++;
			dup
	getfield 1		getfield 1
	const_1		const_1
	add		add
	~~getstatic 0~~
	putfield 1		putfield 1
	jmp 8 # else		jmp 8 # else

WikiEditor: /* Postavka */

2023-06-28T00:18:27Z

Postavka

← Старија измена		Верзија на датум 28. јун 2023. у 02:18
Ред 210:		Ред 210:
	# Odrediti deo koda koji se nalazi na mestu komentara u datom programu, a kome odgovara dati Mikrojava bajtkod.		# Odrediti deo koda koji se nalazi na mestu komentara u datom programu, a kome odgovara dati Mikrojava bajtkod.
	</div>		</div>
	<syntaxhighlight>		<syntaxhighlight lang="java">
	program Januar2021		program Januar2021
	const int K = 3;		const int K = 3;

WikiEditor: /* 2 -> 3 */

2023-06-28T00:16:39Z

2 -> 3

← Старија измена		Верзија на датум 28. јун 2023. у 02:16
Ред 326:		Ред 326:
	\| 1. \|\| x = 2 \|\| ž2 \|\| m- \|\| m- \|\| x \|\| - \|\| AX \|\| MOV AX, 2		\| 1. \|\| x = 2 \|\| ž2 \|\| m- \|\| m- \|\| x \|\| - \|\| AX \|\| MOV AX, 2
	\|-		\|-
	\| 2. \|\| z = x + 3 \|\| ž3 \|\| m- \|\| ž3 \|\| x \|\| z \|\| BX \|\| MOV BX, AX; ADD BX, 2		\| 2. \|\| z = x + 3 \|\| ž3 \|\| m- \|\| ž3 \|\| x \|\| z \|\| BX \|\| MOV BX, AX; ADD BX, 3
	\|-		\|-
	\| 3. \|\| y = z - x \|\| m- \|\| ž4 \|\| m- \|\| x \|\| y \|\| BX \|\| SUB BX, AX		\| 3. \|\| y = z - x \|\| m- \|\| ž4 \|\| m- \|\| x \|\| y \|\| BX \|\| SUB BX, AX

WikiEditor: /* 4. zadatak - fali deo postavke*/

2023-06-28T00:16:15Z

4. zadatak - fali deo postavke

@@ Ред 210: / Ред 210: @@
 # Odrediti deo koda koji se nalazi na mestu komentara u datom programu, a kome odgovara dati Mikrojava bajtkod.
 </div>
 <syntaxhighlight lang="asm">
 getstatic 0

KockaAdmiralac: /* 4. zadatak */ Ispravljene lokacije skoka

2023-01-19T09:30:03Z

4. zadatak: Ispravljene lokacije skoka

← Старија измена		Верзија на датум 19. јануар 2023. у 11:30
Ред 228:		Ред 228:
	load_1 # if (		load_1 # if (
	const_3		const_3
	jge 5 # y >= K		jge 8 # y >= K
	load_1		load_1
	const_0		const_0
	jne 17 # y == 0)		jne 20 # y == 0)
	getstatic 0 # global.p++;		getstatic 0 # global.p++;
	getfield 1		getfield 1
Ред 238:		Ред 238:
	getstatic 0		getstatic 0
	putfield 1		putfield 1
	jmp 5 # else		jmp 8 # else
	load_0 # arg.p = K;		load_0 # arg.p = K;
	const_3		const_3

KockaAdmiralac: Moja rešenja januara 2021

2023-01-18T12:16:22Z

Moja rešenja januara 2021

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

{{tocright}}
'''Januarski rok 2021. godine''' održan je 22. januara. Postavka roka je dostupna [http://ir4pp1.etf.rs/Rokovi/2020-2021/pp1_jan2021_ispit.pdf sa stranice predmeta.]

== 1. zadatak ==
=== Postavka ===
Dat je fragmet<sup>[sic]</sup> gramatike jednog programskog jezika.
# <var_decl> ::= <type> : <id_list>
# <id_list> ::= <id_list> , Ident | Ident
# <type> ::= int | char
<div class="abc-list">
# Napisati atributivnu gramatiku kojom se određuje tip za svaki identifikator u listi (Ident). Jasno naznačiti koji atributi su sintetizovani, a koji nasleđeni.
# Da li je dobijena gramatika S-atributivna ili L-atributivna?
# Dobijenoj atributivnoj gramatici (pod a) dodati neophodne akcije koje obezbeđuju dodavanje simbola u tabelu simbola i postavljanje njihovih tipova. Za pisanje akcija koristiti programski jezik Java i sledeći interfejs tabele simbola.
</div>
<syntaxhighlight lang="java">
class Struct {
static final int None = 0, Int = 1, Char = 2, Arr = 3, Class = 4;
int kind; // None, Int, Char, Arr, Class
boolean equals (Struct other);
}
class Tab {
Obj insert (String name, Struct type) throws AlreadyDeclaredException;
Obj findSymbol (String name) throws SymbolNotFoundException;
}
public class Obj {
public static final int Con = 0, Var = 1, Type = 2, Prog = 5;
public int kind; // Con, Var, Type, Meth, Fld, Prog
public String name;
public Struct type;
}
</syntaxhighlight>

=== Rešenje ===
Atribut <code>t</code> je u sledećoj gramatici sintetizovan, dok su atributi <code>type</code> i <code>idtype</code> nasleđeni. Ispod je prikazana gramatika sa označenim atributima i dodatim akcijama.
# <type><sub>t</sub> → int
#: t ← Struct.Int
# <type><sub>t</sub> → char
#: t ← Struct.Char
# <id_list><sub>type</sub> → <id_list><sub>type<sub>1</sub></sub>, Ident<sub>idtype</sub> {: <syntaxhighlight lang="java" inline>Tab.insert(new Obj(Obj.Var, ident, new Struct(type)));</syntaxhighlight> :}
#: idtype ← type
#: type<sub>1</sub> ← type
# <id_list><sub>type</sub> → Ident<sub>idtype</sub> {: <syntaxhighlight lang="java" inline>Tab.insert(new Obj(Obj.Var, ident, new Struct(type)));</syntaxhighlight> :}
#: idtype ← type
# <var_decl> → <type><sub>t</sub> : <id_list><sub>type</sub>
#: type ← t
Dobijena gramatika je L-atributivna, ali nije S-atributivna.

== 2. zadatak ==
=== Postavka ===
Za sve sekvence oblika a<sup>k</sup>(bc)<sup>p</sup>a<sup>2p</sup>, k ≥ 0, p > 0
<div class="abc-list">
# Napisati gramatiku koja opisuje date sekvence.
# Prikazati potisni automat kojim se prepoznaje isključivo dati skup sekvenci.
</div>

=== Rešenje ===
Gramatika koja opisuje date sekvence bi bila:
# <S> → <A> <B>
# <A> → ε
# <A> → <A> a
# <B> → bc <B> aa
# <B> → bcaa
{| class="wikitable"
|+ Stanje S1 potisnog automata za opisivanje sekvenci iz drugog zadatka.
! Stanje
! a
! b
! c
! ─┤
|-
! ∇
| ADVANCE
|
* PUSH(A)
* ADVANCE
| REJECT
| REJECT
|-
! A
| REJECT
| REJECT
|
* PUSH(B)
* ADVANCE
| REJECT
|-
! B
| STATE(S2)
| PUSH(A)
| REJECT
| REJECT
|}
{| class="wikitable"
|+ Stanje S2 potisnog automata za opisivanje sekvenci iz drugog zadatka.
! Stanje
! a
! b
! c
! ─┤
|-
! ∇
| REJECT
| REJECT
| REJECT
| ACCEPT
|-
! A
|
* POP
* ADVANCE
| REJECT
| REJECT
| REJECT
|-
! B
|
* POP
* ADVANCE
| REJECT
| REJECT
| REJECT
|}

== 3. zadatak ==
=== Postavka ===
Formirati parser na principu rekurzivnog spusta koji prepoznaje skup sekvenci predstavljenih sledećim produkcijama.
# <S’> → <S> ─┤
# <S> → <A> a <B>
# <A> → a b <B> b
# <B> → <C> a
# <B> → <D> <C> a
# <B> → ε
# <C> → c <C>
# <C> → ε
# <D> → d

=== Rešenje ===
<syntaxhighlight lang="cpp">
char input;

void terminal(char t) {
if (input == t) {
input = advance();
} else {
reject();
}
}

void A() {
terminal('a');
terminal('b');
B();
terminal('b');
}

void C() {
switch (input) {
case 'c':
terminal('c');
C();
break;
case 'a':
break;
default:
reject();
}
}

void D() {
terminal('d');
}

void B() {
switch (input) {
case 'a':
case 'c':
C();
terminal('a');
break;
case 'd':
D();
C();
terminal('a');
break;
case 'b':
case EOF:
break;
default:
reject();
}
}

void S() {
A();
terminal('a');
B();
}

void main() {
input = advance();
S();
terminal(EOF);
}
</syntaxhighlight>

== 4. zadatak ==
=== Postavka ===
<div class="abc-list">
# Dat je listing programa napisanog na programskom jeziku Mikrojava. Sve metode unutrašnjih klasa su virtuelne. Globalne metode se pozivaju statički. Napisati kompletan Mikrojava bajtkod prevoda datog programa. Za svaku liniju koda jasno naznačiti koji deo bajtkoda se odnosi na nju.
# Odrediti deo koda koji se nalazi na mestu komentara u datom programu, a kome odgovara dati Mikrojava bajtkod.
</div>
<syntaxhighlight lang="asm">
getstatic 0
const_2
load_0
load_1
const_0
aload
mul
add
putfield 1
</syntaxhighlight>

=== Rešenje ===
Prevedeni bajtkod može da izgleda ovako:
<syntaxhighlight lang="asm">
enter 1 2 # void m(CL arg) int y; {
load_1 # if (
const_3
jge 5 # y >= K
load_1
const_0
jne 17 # y == 0)
getstatic 0 # global.p++;
getfield 1
const_1
add
getstatic 0
putfield 1
jmp 5 # else
load_0 # arg.p = K;
const_3
putfield 1
exit # }
return
enter 0 2 # void main() int x; int arr[]; {
new 8 # global = new CL;
putstatic 0
const_3 # arr = new int[3];
newarray 1
store_1
load_1 # arr[K-2] = -arr[x];
const_3
const_2
sub
load_1
load_0
aload
neg
astore
getstatic 0 # m(global);
call ??? (=m) # Verovatno nisu tražili tačan pomeraj?
exit # }
return
</syntaxhighlight>
Linija koda koja fali u programu je:
<syntaxhighlight lang="java">
global.p = 2 + x * arr[0];
</syntaxhighlight>

== 5. zadatak ==
=== Postavka ===
Dat je sledeći fragment (bazični blok) međukoda:
# x = 2
# z = x + 3
# y = z – x
# x = y
# z = x + y
# x = z – y
# z = y – x
<div class="abc-list">
# Za svaku instrukciju u kodu odrediti koje su promenljive žive.
# Korišćenjem algoritma getreg generisati mašinski kod za 80x86 arhitekturu na osnovu datog međukoda i informacija iz tačke a). Pretpostaviti da se koriste dvoadresne mašinske instrukcije gde je prvi operand odredište operacije (oblika ADD dst, src) i da se koriste samo dva registra AX i BX. Rešenje ČITKO upisati u datu tabelu.
</div>

=== Rešenje ===
{| class="wikitable"
|+ Tabela sa traženim informacijama iz zadatka.
! rowspan="2" | Redni broj
! rowspan="2" | Ulaz
! colspan="3" | Život i sledeća upotreba
! colspan="2" | Deskriptori
! rowspan="2" | ''getreg''
! rowspan="2" | Generisani kod
|-
! x
! y
! z
! AX
! BX
|-
| 1. || x = 2 || ž2 || m- || m- || x || - || AX || MOV AX, 2
|-
| 2. || z = x + 3 || ž3 || m- || ž3 || x || z || BX || MOV BX, AX; ADD BX, 2
|-
| 3. || y = z - x || m- || ž4 || m- || x || y || BX || SUB BX, AX
|-
| 4. || x = y || ž5 || ž5 || m- || x || y || AX || MOV AX, BX
|-
| 5. || z = x + y || m- || ž6 || ž6 || z || y || AX || ADD AX, BX
|-
| 6. || x = z - y || ž7 || ž7 || m- || x || y || AX || SUB AX, BX
|-
| 7. || z = y - x || ž- || ž- || ž- || x || z || BX || MOV y, BX; SUB BX, AX
|-
| colspan="8" |
| MOV x, AX; MOV z, BX
|}

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

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

WikiEditor: /* ispravka */

WikiEditor: /* ispravka */

WikiEditor: /* Postavka */

WikiEditor: /* 2 -> 3 */

WikiEditor: /* 4. zadatak - fali deo postavke*/

KockaAdmiralac: /* 4. zadatak */ Ispravljene lokacije skoka

KockaAdmiralac: Moja rešenja januara 2021