Програмски преводиоци 1/К1 2019 — разлика између измена
(Moja rešenja K1 2019) |
м (Često postavljeno pitanje) |
||
(2 међуизмене истог корисника нису приказане) | |||
Ред 92: | Ред 92: | ||
=== Rešenje === | === Rešenje === | ||
[[Datoteka:PPR K1 2019 zadatak 2 stablo.svg|thumb|center|Poziciono stablo u drugom zadatku.]] | [[Datoteka:PPR K1 2019 zadatak 2 stablo.svg|thumb|center|Poziciono stablo u drugom zadatku.]] | ||
U sintaksnom stablu je čvor + označen kao poništiv jer je njegov podizraz poništiv, pa samim tim može rezultovati praznom sekvencom (prazna sekvenca ponovljena jedan ili više puta je i dalje prazna sekvenca). | |||
{| class="wikitable" | {| class="wikitable" | ||
|+ Tabela sledećih pozicija | |+ Tabela sledećih pozicija | ||
Ред 179: | Ред 180: | ||
* <B> → c <B> a | * <B> → c <B> a | ||
Jedno rešenje stavke pod b, koje uključuje jedno stanje potisnog automata, izgleda ovako: | |||
{| class="wikitable" | {| class="wikitable" | ||
|+ Potisni automat za prepoznavanje sekvence zadate u zadatku | |+ Potisni automat za prepoznavanje sekvence zadate u zadatku | ||
Ред 230: | Ред 232: | ||
| REJECT | | REJECT | ||
| REJECT | | REJECT | ||
|} | |||
Alternativno rešenje sa više stanja izgleda ovako: | |||
{| class="wikitable" | |||
|+ Prvo stanje potisnog automata | |||
! | |||
! a | |||
! b | |||
! c | |||
! ─┤ | |||
|- | |||
! ∇ | |||
| | |||
* PUSH(A) | |||
* ADVANCE | |||
| REJECT | |||
| | |||
* RETAIN | |||
* STATE(S2) | |||
| REJECT | |||
|- | |||
! A | |||
| REJECT | |||
| | |||
* POP | |||
* ADVANCE | |||
| REJECT | |||
| REJECT | |||
|} | |||
{| class="wikitable" | |||
|+ Drugo stanje potisnog automata | |||
! | |||
! a | |||
! b | |||
! c | |||
! ─┤ | |||
|- | |||
! ∇ | |||
| REJECT | |||
| REJECT | |||
| | |||
* PUSH(A) | |||
* ADVANCE | |||
| REJECT | |||
|- | |||
! A | |||
| | |||
* RETAIN | |||
* STATE(S3) | |||
| REJECT | |||
| | |||
* PUSH(A) | |||
* ADVANCE | |||
| REJECT | |||
|} | |||
{| class="wikitable" | |||
|+ Treće stanje potisnog automata | |||
! | |||
! a | |||
! b | |||
! c | |||
! ─┤ | |||
|- | |||
! ∇ | |||
| REJECT | |||
| REJECT | |||
| REJECT | |||
| REJECT | |||
|- | |||
! A | |||
| | |||
* POP | |||
* ADVANCE | |||
| REJECT | |||
| REJECT | |||
| ACCEPT | |||
|} | |} | ||
[[Категорија:Рокови]] | [[Категорија:Рокови]] | ||
[[Категорија:Програмски преводиоци 1]] | [[Категорија:Програмски преводиоци 1]] |
Тренутна верзија на датум 31. октобар 2022. у 15:28
Prvi kolokvijum 2019. godine održan je 28. oktobra i trajao je 90 minuta. Postavka roka dostupna je sa stranice predmeta (arhiva).
1. zadatak
Postavka
Za dati konačni automat navesti:
- Klasni dijagram koji ilustruje projektni šablon (GoF design pattern) Stanje.
- Napisati programsku realizaciju datog automata na osnovu šablona iz tačke a).
a | b | c | Prihvata | |
---|---|---|---|---|
→ S1 | S2 | S1 | S2 | 0 |
S2 | S2 | S1 | 1 |
Rešenje
Rešenje dela pod a se može naći na slici, dok je pod b ispod:
class FSM {
interface State {
boolean accepting();
State handleInput(char input);
}
private StateS1 S1 = new StateS1();
private StateS2 S2 = new StateS2();
private StateError ERROR = new StateError();
class StateS1 implements State {
public boolean accepting() {
return false;
}
public State handleInput(char input) {
switch (input) {
case 'a':
case 'c':
return S2;
case 'b': return S1;
default: return ERROR;
}
}
}
class StateS2 implements State {
public boolean accepting() {
return true;
}
public State handleInput(char input) {
switch (input) {
case 'b': return S2;
case 'c': return S1;
default: return ERROR;
}
}
}
class StateError implements State {
public boolean accepting() {
return false;
}
public State handleInput(char input) {
return ERROR;
}
}
// ...
}
2. zadatak
Postavka
Metodom pozicija odrediti minimalni deterministički automat koji je opisan sledećim regularnim izrazrom:[sic]
b(a | (bc)*)+
Rešenje
U sintaksnom stablu je čvor + označen kao poništiv jer je njegov podizraz poništiv, pa samim tim može rezultovati praznom sekvencom (prazna sekvenca ponovljena jedan ili više puta je i dalje prazna sekvenca).
1 | 2, 3, 5 |
---|---|
2 | 2, 3, 5 |
3 | 4 |
4 | 2, 3, 5 |
5 | - |
a | b | c | Prihvata | |
---|---|---|---|---|
→ 1 | 2, 3, 5 | 0 | ||
2, 3, 5 | 2, 3, 5 | 4 | 1 | |
4 | 2, 3, 5 | 0 |
a | b | c | Prihvata | |
---|---|---|---|---|
→ A | B | 0 | ||
B | B | C | 1 | |
C | B | 0 |
3. zadatak
Postavka
Za sve sekvence oblika potrebno je:
- konstruisati gramatiku koja opisuje ovakve sekvence
- konstruisati potisni automat koji opisuje ovakve sekvence
Rešenje
Gramatika koja prepoznaje ovakve sekvence može da izgleda ovako:
- <S> → <A> <B>
- <A> → ab <A>
- <A> → ε
- <B> → cca
- <B> → c <B>
- <B> → c <B> a
Jedno rešenje stavke pod b, koje uključuje jedno stanje potisnog automata, izgleda ovako:
a | b | c | ─┤ | |
---|---|---|---|---|
∇ |
|
REJECT |
|
REJECT |
A | REJECT |
|
REJECT | REJECT |
B |
|
REJECT |
|
REJECT |
C |
|
REJECT | REJECT | ACCEPT |
D | REJECT | REJECT | REJECT | REJECT |
Alternativno rešenje sa više stanja izgleda ovako:
a | b | c | ─┤ | |
---|---|---|---|---|
∇ |
|
REJECT |
|
REJECT |
A | REJECT |
|
REJECT | REJECT |
a | b | c | ─┤ | |
---|---|---|---|---|
∇ | REJECT | REJECT |
|
REJECT |
A |
|
REJECT |
|
REJECT |
a | b | c | ─┤ | |
---|---|---|---|---|
∇ | REJECT | REJECT | REJECT | REJECT |
A |
|
REJECT | REJECT | ACCEPT |