KockaAdmiralac: /* Rešenje */ Ispravka formatiranja

2023-08-13T13:01:40Z

Rešenje: Ispravka formatiranja

← Старија измена		Верзија на датум 13. август 2023. у 15:01
Ред 28:		Ред 28:
	\|-		\|-
	! ∇		! ∇
	\| <E><sub>x</sub> \|\| <T><sub>x1</sub> !! <P><sub>4</sub> \|\| slovo<sub>5</sub> \|\| epsilon<sub>6</sub> \|\| \|\| \|\|		\| <E><sub>x</sub> \|\| <T><sub>x1</sub> \|\| <P><sub>4</sub> \|\| slovo<sub>5</sub> \|\| epsilon<sub>6</sub> \|\| \|\| \|\|
	\|-		\|-
	! <T><sub>x1</sub>		! <T><sub>x1</sub>

WikiEditor: /* ispravka */

2023-06-28T11:37:50Z

ispravka

← Старија измена		Верзија на датум 28. јун 2023. у 13:37
Ред 207:		Ред 207:
	}		}
	Obj resultObj = null;		Obj resultObj = null;
	~~for (; s != null; s = s.getOuter()) {~~		if (scope.getLocals() != null) {
	if (s.getLocals() == null) {		resultObj = scope.getLocals().searchKey(name);
	~~continue;~~
	}
	resultObj = s.getLocals().searchKey(name);
	~~if (resultObj != null) {~~
	~~break;~~
	}
	}		}
	return (resultObj != null) ? resultObj : noObj;		return (resultObj != null) ? resultObj : noObj;

KockaAdmiralac: /* 5. zadatak */ Promenjeni offset-i u x86 kodu

2023-02-26T11:26:51Z

5. zadatak: Promenjeni offset-i u x86 kodu

← Старија измена		Верзија на датум 26. фебруар 2023. у 13:26
Ред 387:		Ред 387:
	<syntaxhighlight lang="asm">		<syntaxhighlight lang="asm">
	MOV DI, [BP+04]		MOV DI, [BP+04]
	MOV AX, [DI+02]		MOV AX, [DI+06]
	MOV DI, [DI]		MOV DI, [DI+04]
	MOV BX, [DI-06]		MOV BX, [DI-02]
	ADD AX, BX		ADD AX, BX
	MOV [DI-08], AX		MOV [DI-04], AX
	</syntaxhighlight>		</syntaxhighlight>

KockaAdmiralac: Slike sada rade

2023-01-18T18:46:19Z

Slike sada rade

← Старија измена		Верзија на датум 18. јануар 2023. у 20:46
Ред 17:		Ред 17:

	=== Rešenje ===		=== Rešenje ===
			[[Датотека:PPR januar 2020 zadatak 1 automat.svg\|thumb\|Automat iz prvog zadatka pod a.]]
	Relevantni FIRST i FOLLOW skupovi SLR(1) parsera su:		Relevantni FIRST i FOLLOW skupovi SLR(1) parsera su:
	* FOLLOW(<E>) = {\|, ─┤}		* FOLLOW(<E>) = {\|, ─┤}

KockaAdmiralac: /* 2. zadatak */ Ispravka sintakse

2023-01-18T18:41:05Z

2. zadatak: Ispravka sintakse

← Старија измена		Верзија на датум 18. јануар 2023. у 20:41
Ред 127:		Ред 127:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	# Promeniti Mikrojava gramatiku da se dodaju opisane mogućnosti (relevantan deo gramatike dat je u prilogu u EBNF notaciji). Jasno označiti šta je promenjeno.<pre>		<div class="abc-list">
			# Promeniti Mikrojava gramatiku da se dodaju opisane mogućnosti (relevantan deo gramatike dat je u prilogu u EBNF notaciji). Jasno označiti šta je promenjeno.
			# Dodati u mikrojava tabelu simbola metod <syntaxhighlight lang="java" inline>find_hidden(String name)</syntaxhighlight> koji se poziva za traženje imena pod dejstvom operatora <code>::</code>. Navesti kompletnu implementaciju ovog metoda. U prilogu je (na sledećoj strani) kao podsetnik dat deo postojeće implementacije klase <code>Tab</code>.
			# Gde u Mikrojava kompajleru treba ugraditi poziv metoda <code>find_hidden</code>?
			</div>
			Mikrojava gramatika:
			<pre>
	DesignatorStatement := Designator "=" Expr.		DesignatorStatement := Designator "=" Expr.
	DesignatorStatement := Designator "++".		DesignatorStatement := Designator "++".
Ред 142:		Ред 148:
	Mulop := "*" \| "/" \| "%".		Mulop := "*" \| "/" \| "%".
	</pre>		</pre>
	# Dodati u mikrojava tabelu simbola metod <syntaxhighlight lang="java" inline>find_hidden(String name)</syntaxhighlight> koji se poziva za traženje imena pod dejstvom operatora <code>::</code>. Navesti kompletnu implementaciju ovog metoda. U prilogu je (na sledećoj strani) kao podsetnik dat deo postojeće implementacije klase <code>Tab</code>.		Implementacija klase <code>Tab</code>:
	~~# Gde u Mikrojava kompajleru treba ugraditi poziv metoda <code>find_hidden</code>?~~
	<syntaxhighlight lang="java">		<syntaxhighlight lang="java">
	public class Tab {		public class Tab {

KockaAdmiralac: Moja rešenja januara 2020 (slike uskoro) // Edit via Wikitext Extension for VSCode

2023-01-18T18:37:31Z

Moja rešenja januara 2020 (slike uskoro) // Edit via Wikitext Extension for VSCode

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

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

== 1. zadatak ==
=== Postavka ===
Data gramatika opisuje regularne izraze sa operatorima konkatenacije ● i unije |.
# <E> → <E> | <T>
# <E> → <T>
# <T> → <T> ● 
# <T> → 
# → slovo
# → epsilon
<div class="abc-list">
# Konstruisati SLR(1) parser za datu gramatiku.
# Dopuniti datu gramatiku S-atributivnim pravilima tako da svaki neterminal date gramatike poseduje atribute koji predstavljaju vrednosti funkcija poništiv i prva_pozicija iz algoritma za konstrukciju determinističkog konačnog automata iz regularnog izraza. Terminal <code>slovo</code> poseduje atribut koji označava poziciju tog terminala u izrazu. Napomena: <code>epsilon</code> je terminal, a ne oznaka prazne sekvence. Takođe su | i ● terminalni simboli.
</div>

=== Rešenje ===
Relevantni FIRST i FOLLOW skupovi SLR(1) parsera su:
* FOLLOW(<E>) = {|, ─┤}
* FOLLOW(<T>) = {●} ∪ FOLLOW(<E>) = {●, |, ─┤}
* FOLLOW() = FOLLOW(<T>) = {●, |, ─┤}
{| class="wikitable"
|+ Potisna tabela SLR(1) parsera
! Stanje
! <E> !! <T> !! !! slovo !! epsilon !! ● !! | !! ─┤
|-
! ∇
| <E>x || <T>x1 !! 4 || slovo5 || epsilon6 || || ||
|-
! <T>x1
| || || || || || ●3 || ||
|-
! <E>x
| || || || || || || |1 || ─┤0
|-
! 4
| || || || || || || ||
|-
! slovo5
| || || || || || || ||
|-
! epsilon6
| || || || || || || ||
|-
! ●3
| || || 3 || slovo5 || epsilon6 || || ||
|-
! |1
| || <T>x2 || 4 || slovo5 || epsilon6 || || ||
|-
! ─┤0
| || || || || || || ||
|-
! 3
| || || || || || || ||
|-
! <T>x2
| || || || || || ●3 || ||
|}
{| class="wikitable"
|+ Kontrolna tabela SLR(1) parsera
! Stanje
! slovo !! epsilon !! ● !! | !! ─┤
|-
! ∇
| SHIFT || SHIFT || || ||
|-
! <T>x1
| || || SHIFT || REDUCE(2) || REDUCE(2)
|-
! <E>x
| || || || SHIFT || SHIFT
|-
! 4
| || || REDUCE(4) || REDUCE(4) || REDUCE(4)
|-
! slovo5
| || || REDUCE(5) || REDUCE(5) || REDUCE(5)
|-
! epsilon6
| || || REDUCE(6) || REDUCE(6) || REDUCE(6)
|-
! ●3
| SHIFT || SHIFT || || ||
|-
! |1
| SHIFT || SHIFT || || ||
|-
! ─┤0
| || || || || ACCEPT
|-
! 3
| || || REDUCE(3) || REDUCE(3) || REDUCE(3)
|-
! <T>x2
| || || SHIFT || REDUCE(1) || REDUCE(1)
|}
Dopunjena gramatika sa atributima izgleda:
# <E>pon,prva → <E>pon1,prva1 | <T>pon2,prva2
#: <math>pon \larr pon_1 or pon_2</math>
#: <math>prva \larr \{prva_1, prva_2\}</math>
# <E>pon,prva → <T>pon1,prva1
#: <math>pon \larr pon_1</math>
#: <math>prva \larr prva_1</math>
# <T>pon,prva → <T>pon1,prva1 ● pon2,prva2
#: <math>pon \larr pon_1 and pon_2</math>
#: <math>prva \larr pon_1 ? \{prva_1, prva_2\} : prva_1</math>
# <T>pon,prva → pon1,prva1
#: <math>pon \larr pon_1</math>
#: <math>prva \larr prva_1</math>
# pon,prva → slovopoz
#: <math>pon \larr 0</math>
#: <math>prva \larr poz</math>
# pon,prva → epsilon
#: <math>pon \larr 1</math>

== 2. zadatak ==
=== Postavka ===
U standardnoj Mikrojavi, lokalno definisana promenljiva sakriva globalnu promenljivu sa istim imenom. Želimo da uvedemo sledeću modifikaciju: Ako se želi pristupiti sakrivenoj globalnoj promenljivoj, mora se ispred imena navesti operator <code>::</code>.

Na primer:
<syntaxhighlight lang="java">
program P {
int X[];
void main() int X; { ::X = new int[5]; X = ::X[0];}
}
</syntaxhighlight>
# Promeniti Mikrojava gramatiku da se dodaju opisane mogućnosti (relevantan deo gramatike dat je u prilogu u EBNF notaciji). Jasno označiti šta je promenjeno.<pre>
DesignatorStatement := Designator "=" Expr.
DesignatorStatement := Designator "++".
DesignatorStatement := Designator "--".
Statement := DesignatorStatement ";".
Statement := "read" "(" Designator ")" ";".
Statement := "print" "(" Expr [“,” number] ")" ";".
Expr := ["‐"] Term {Addop Term}.
Term := Factor {Mulop Factor}.
Factor := numConst | charConst | "(" Expr ")" | boolConst | "new" Type [ "[" Expr "]" ].
Factor := Designator [ "(" ")" ].
Designator := ident ["[" Expr "]" ].
Addop := "+" | "‐" .
Mulop := "*" | "/" | "%".
</pre>
# Dodati u mikrojava tabelu simbola metod <syntaxhighlight lang="java" inline>find_hidden(String name)</syntaxhighlight> koji se poziva za traženje imena pod dejstvom operatora <code>::</code>. Navesti kompletnu implementaciju ovog metoda. U prilogu je (na sledećoj strani) kao podsetnik dat deo postojeće implementacije klase <code>Tab</code>.
# Gde u Mikrojava kompajleru treba ugraditi poziv metoda <code>find_hidden</code>?
<syntaxhighlight lang="java">
public class Tab {
public static final Struct
noType = new Struct(Struct.None),
intType = new Struct(Struct.Int),
charType = new Struct(Struct.Char),
nullType = new Struct(Struct.Class);
public static final Obj noObj = new Obj(Obj.Var, "noObj", noType);
public static Obj chrObj, ordObj, lenObj;
public static Scope currentScope; //tekuci opseg
private static int currentLevel; //nivo ugnezdavanja tekuceg opsega
public static void init() {
Scope universe = currentScope = new Scope(null);
. . . . .
currentLevel = -1;
}
public static void openScope() {
currentScope = new Scope(currentScope);
currentLevel++;
}
public static void closeScope() {
currentScope = currentScope.getOuter();
currentLevel--;
}
public static Obj insert(int kind, String name, Struct type) {
Obj newObj=new Obj(kind,name,type,0,((currentLevel!=0)?1:0));
. . . . .
}
public static Obj find(String name) {
Obj resultObj = null;
for (Scope s = currentScope; s != null; s = s.getOuter()) {
if (s.getLocals() != null) {
resultObj = s.getLocals().searchKey(name);
if (resultObj != null) break;
}
}
return (resultObj != null) ? resultObj : noObj;
}
public static Scope currentScope() {
return currentScope;
}
}
</syntaxhighlight>

=== Rešenje ===
U gramatici je potrebno izmeniti sledeću smenu:
<pre>
Designator := ["::"] ident ["[" Expr "]" ].
</pre>
Metoda <code>find_hidden</code> koja pronalazi promenljive iz globalnog dosega programa može da izgleda ovako:
<syntaxhighlight lang="java">
public static Obj find_hidden(String name) {
Scope scope = currentScope;
for (int level = currentLevel; level > 0; --level) {
scope = scope.getOuter();
}
Obj resultObj = null;
for (; s != null; s = s.getOuter()) {
if (s.getLocals() == null) {
continue;
}
resultObj = s.getLocals().searchKey(name);
if (resultObj != null) {
break;
}
}
return (resultObj != null) ? resultObj : noObj;
}
</syntaxhighlight>
U Mikrojava kompajleru poziv ove metode treba ugraditi tokom semantičke analize, kako bi se odgovarajućem čvoru u apstraktnom sintaksnom stablu dodelio simbol koji odgovara promenljivoj iz globalnog opsega.

== 3. zadatak ==
=== Postavka ===

=== Rešenje ===
{| class="wikitable"
|+ Nedeterministički konačni automat sa dešifrovanim stanjima.
! Stanje !! a !! b !! c !! Prihvata
|-
| → A || A || || C || 0
|-
| B || B, C || D || || 0
|-
| C || A || || D || 1
|-
| D || || B, C || || 0
|}
{| class="wikitable"
|+ Deterministički konačni automat sa dešifrovanim stanjima
! Stanje !! a !! b !! c !! Prihvata
|-
| → A, B || A, B, C || D || C || 0
|-
| A, B, C || A, B, C || D || C, D || 1
|-
| D || || B, C || || 0
|-
| C || A || || D || 1
|-
| C, D || A || B, C || D || 1
|-
| B, C || A, B, C || D || D || 1
|-
| A || A || || C || 0
|}

== 4. zadatak ==
=== Postavka ===
Data je gramatika:
# <S> → a <S> b
# <S> → b <S> c
# <S> → bc
# <S> → <S> a
<div class="abc-list">
# Transformisati gramatiku u LL(1) i odrediti SELECT skupove tako dobijene gramatike.
# Konstruisati parser na bazi rekurzivnog spusta za gramatiku dobijenu u tački a).
</div>

=== Rešenje ===
Transformisana gramatika može izgledati ovako:
# <S> → a <S> b <S'<nowiki />'>
#: SELECT(1) = {a}
# <S> → b <S'> c <S'<nowiki />'>
#: SELECT(2) = {b}
# <S'> → <S>
#: SELECT(3) = {a, b}
# <S'> → ε
#: SELECT(3) = {c}
# <S'<nowiki />'> → a <S'<nowiki />'>
#: SELECT(4) = {a}
# <S'<nowiki />'> → ε
#: SELECT(5) = {c, ─┤}
Parser na bazi rekurzivnog spusta na gornju gramatiku izgleda ovako:
<syntaxhighlight lang="java">
char input;

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

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

void S();

void S1() {
switch (input) {
case 'a':
case 'b':
S();
break;
case 'c':
break;
default:
reject();
}
}

void S() {
switch (input) {
case 'a':
terminal('a');
S();
terminal('b');
S2();
break;
case 'b':
terminal('b');
S1();
terminal('c');
S2();
break;
default:
reject();
}
}

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

== 5. zadatak ==
=== Postavka ===
Dat je sledeći deo program na jeziku sličnom Pascal-u:
<syntaxhighlight lang="pascal">
procedure proc0;
var x, y: integer;
procedure proc1(z: integer);
procedure proc2;
begin
y := x + z;
end;
begin
proc2;
end;
procedure proc3(z: integer);
var x: integer;
procedure proc4;
begin
proc1(x);
end;
begin
x := z + 1;
proc4;
end;
begin
x := 5;
proc3(x);
end;
</syntaxhighlight>
<div class="abc-list">
# Ako je statičko okruženje za nelokalne promenljive realizovano preko pristupnih veza, nacrtati izgled steka nakon izvršavanja naredbe <code>y := x + z;</code> iz procedure <code>proc2</code>.
# Napisati 80x86 asemblerski kod za naredbu <code>y := x + z;</code> iz procedure <code>proc2</code>.
</div>

=== Rešenje ===
[[Датотека:PPR januar 2020 zadatak 5 stek.svg|thumb|Stek iz petog zadatka pod a.]]
<syntaxhighlight lang="asm">
MOV DI, [BP+04]
MOV AX, [DI+02]
MOV DI, [DI]
MOV BX, [DI-06]
ADD AX, BX
MOV [DI-08], AX
</syntaxhighlight>

== 6. zadatak ==
=== Postavka ===
Za dati programski fragment:
<div class="abc-list">
# Napisati odgovarajući međukod i graf toka kontrole na nivou osnovnih blokova.
# Napisati međukod u SSA formi.
</div>
<syntaxhighlight lang="java">
x = 1;
y = 0;
z = 0;
for (x = 2; y > z; z = z + 1) {
if (x - 2 > y) {
x = y - 1;
} else if(x > y) {
x = z - 1;
} else break;
y = x * 2;
}
x = y + z;
</syntaxhighlight>

=== Rešenje ===
[[Датотека:PPR januar 2020 zadatak 6 graf.svg|thumb|Graf iz šestog zadatka pod a.]]
Međukod:
# x1 := 1
# y1 := 0
# z1 := 0
# x2 := 2
# t1 := Ф(y1, y2)
# if t1 <= z goto 22
# t2 := Ф(x2, x3, x4)
# t3 := t2 - 2
# if t3 <= t1 goto 13
# t4 := t1 - 1
# x3 := t4
# goto 18
# if t2 <= t1 goto 17
# t5 := z1 - 1
# x4 := t3
# goto 18
# goto 22
# t6 := Ф(x3, x4)
# t7 := t6 * 2
# y2 := t7
# goto 5
# t8 := t1 + z1
# x5 := t8

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

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

KockaAdmiralac: /* Rešenje */ Ispravka formatiranja

WikiEditor: /* ispravka */

KockaAdmiralac: /* 5. zadatak */ Promenjeni offset-i u x86 kodu

KockaAdmiralac: Slike sada rade

KockaAdmiralac: /* 2. zadatak */ Ispravka sintakse

KockaAdmiralac: Moja rešenja januara 2020 (slike uskoro) // Edit via Wikitext Extension for VSCode