SI Wiki - Кориснички доприноси [sr]

Програмски преводиоци 1/Фебруар 2021

2023-01-15T20:54:53Z

Brka: Ispravka 5. zadatak u 8. redu

{{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.drawio.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]]

Датотека:PPR februar 2021 zadatak 5 graf.svg

2023-01-15T20:53:20Z

Brka: Отпремљено кроз дијалог за отпремање датотека.

ОС1/Модификације јун 2021

2021-07-10T17:17:35Z

Brka: /* 20 поена */ Radio sam ovo ceo dan i pucao mi je program, pa sam zamenio naredbe da imaju vise smisla i potvrdio mi je kolega koji je radio ovu modifikaciju da je ipak ovaj pravi redosled

{{tocright}}
Следеће модификације су се појавиле на одбрани пројекта у јунском року 2021.

== 20 поена ==
* Следећа ставка иста је као 1. задатак са другог колоквијума у јунском року 2017. године: Школско језгро треба проширити концептом ''баријере'' ("ограда", "рампа", енгл. ''barrier'') чији је интерфејс дат доле. Семантика овог концепта и операција над њим је следећа:
** Баријера може бити у једном од два стања: ''отворена'' или ''затворена''. Баријера се иницијализује задатим стањем (аргумент конструктора). Нит у чијем контексту се креира баријера (тј. извршава конструктор) је њен ''власник''.
** <syntaxhighlight lang="cpp" inline>void Barrier::pass()</syntaxhighlight>: уколико позивајућа нит није власник ове баријере, ова операција нема ефекта - нит наставља своје извршавање; уколико је позивајућа нит власник баријере, а баријера затворена, нит се суспендује (блокира) све док се баријера не отвори; ако је баријера отворена, нит наставља извршавање без блокаде;
** <syntaxhighlight lang="cpp" inline>void Barrier::close()</syntaxhighlight>: затвара баријеру;
** <syntaxhighlight lang="cpp" inline>void Barrier::open()</syntaxhighlight>: отвара баријеру и евентуално деблокира нит која је на баријери блокирана.
* Написати јавни тест са две нити A и B. Нит B прави глобални семафор са вредношћу 0 и глобалну баријеру са вредношћу 1, а нит A упослено чека док се они не направе. Нит A треба циклично да позива <code>Barrier::open()</code>, <code>Barrier::pass()</code> и <code>Semaphore::wait(0)</code>, док нит B треба циклично да позива <code>Barrier::pass()</code>, <code>Barrier::close()</code> и <code>Semaphore::signal(0)</code> ''(редослед позива можда није тачан)''.
<syntaxhighlight lang="cpp">
class Barrier {
public:
Barrier (int open=1);
void open();
void close();
void pass();
};
</syntaxhighlight>

=== Решење ===
Оквирно решење може се наћи као решење поменутог колоквијума.

== 30 поена ==
* Направити да се након позива <code>fork()</code> као следећа нит за извршавање изабере дете (пре изласка из <code>fork()</code> у родитељској нити). Такође, форсирати да се прво бирају нити без деце.
* Написати тест пример који тестира задату функционалност. На пример, може да изгледа попут:
<syntaxhighlight lang="cpp">
int result = Thread::fork();
if (result != -1) {
if (result == 0) {
intLock
cout << "Child!" << endl;
intUnlock
Thread::exit();
} else {
intLock
cout << "Parent!" << endl;
intUnlock
Thread::waitForForkChildren();
}
}
</syntaxhighlight>

=== Решење ===
* Решење за бирање детета јесте да се у <code>PCB</code> дода показивач на дете које је изабрано који се поставља на новонаправљено дете у <code>fork()</code>, проверава да ли је <code>nullptr</code> у тајмеру, ако није онда се нит која је следећа за извршавање поставља на то дете и показивач се враћа на <code>nullptr</code>.
* Једно решење за форсирање нити које немају децу јесте да се, уколико се не дешава бирање детета, из <code>Scheduler</code> ваде нити док се не пронађе нит без деце (која се одмах постави као нит за извршавање) или док се не избаце све нити, ако су извађене нити са децом оне се убацују у другу листу и на крају се враћају назад у <code>Scheduler</code>. Уколико нит без деце није пронађена, између вађења и враћања нити проверава се да ли је извучена иједна нит без деце и вади се једна нит са децом уколико није.

[[Категорија:Лабораторијске вежбе]]
[[Категорија:ОС1]]