Програмски преводиоци 1/К2 2017 — разлика између измена
(Moja rešenja K2 2017) |
м (-nepotrebna dodela) |
||
(6 међуизмена истог корисника није приказано) | |||
Ред 21: | Ред 21: | ||
# <niz'> → , <broj> <niz'> | # <niz'> → , <broj> <niz'> | ||
#: SELECT(2) = {","} | #: SELECT(2) = {","} | ||
# <niz'> → | # <niz'> → ε | ||
#: SELECT(3) = {-|} | #: SELECT(3) = {-|} | ||
# <broj> → BIT <broj'> | # <broj> → BIT <broj'> | ||
#: SELECT(4) = {BIT} | #: SELECT(4) = {BIT} | ||
# <broj'> → | # <broj'> → <broj> | ||
#: SELECT(5) = {BIT} | #: SELECT(5) = {BIT} | ||
# <broj'> → | # <broj'> → ε | ||
#: SELECT(6) = {",", -|} | #: SELECT(6) = {",", -|} | ||
Neterminalu <niz> možemo dodati atribut koji broji koliko je neparnih brojeva bilo u njemu, dok neterminalu <broj> možemo dodati atribute koji kažu da li je taj broj paran (<math>p</math>, vrednost je 0 ako jeste a 1 ako nije) i da li se došlo do kraja sa parsiranjem broja (<math>e</math>). S tim u vidu, atributivno-translaciona gramatika može da izgleda ovako: | Neterminalu <niz> možemo dodati atribut koji broji koliko je neparnih brojeva bilo u njemu, dok neterminalu <broj> možemo dodati atribute koji kažu da li je taj broj paran (<math>p</math>, vrednost je 0 ako jeste a 1 ako nije) i da li se došlo do kraja sa parsiranjem broja (<math>e</math>). S tim u vidu, atributivno-translaciona gramatika može da izgleda ovako: | ||
Ред 34: | Ред 34: | ||
# <niz'><sub>n</sub> → , <broj><sub>p,e</sub> <niz'><sub>n<sub>1</sub></sub> | # <niz'><sub>n</sub> → , <broj><sub>p,e</sub> <niz'><sub>n<sub>1</sub></sub> | ||
#: <math>n \leftarrow n_1 + p</math> | #: <math>n \leftarrow n_1 + p</math> | ||
# <niz'>_n → | # <niz'>_n → ε | ||
#: <math>n \leftarrow 0</math> | #: <math>n \leftarrow 0</math> | ||
# <broj><sub>p,e</sub> → BIT<sub>v</sub> <broj'><sub>p<sub>1</sub>,e<sub>1</sub></sub> | # <broj><sub>p,e</sub> → BIT<sub>v</sub> <broj'><sub>p<sub>1</sub>,e<sub>1</sub></sub> | ||
#: <math>p \leftarrow e_1 \cdot v + (1 - e_1) \cdot p_1</math> | #: <math>p \leftarrow e_1 \cdot v + (1 - e_1) \cdot p_1</math> | ||
#: <math>e \leftarrow 0</math> | #: <math>e \leftarrow 0</math> | ||
# <broj'><sub>p,e</sub> → | # <broj'><sub>p,e</sub> → <broj><sub>p<sub>1</sub>,e<sub>1</sub></sub> | ||
#: <math>p \leftarrow | #: <math>p \leftarrow p_1</math> | ||
#: <math>e \leftarrow | #: <math>e \leftarrow e_1</math> | ||
# <broj'><sub>p,e</sub> → ε | # <broj'><sub>p,e</sub> → ε | ||
#: <math>p \leftarrow 0</math> | #: <math>p \leftarrow 0</math> | ||
Ред 118: | Ред 118: | ||
switch (input) { | switch (input) { | ||
case BIT: | case BIT: | ||
int p1; | int p1; | ||
int e1; | int e1; | ||
broj(p1, e1); | |||
p = p1; | p = p1; | ||
e = e1; | |||
break; | break; | ||
case ',': | case ',': | ||
Ред 185: | Ред 181: | ||
| a<sub>3</sub> || || || SHIFT || SHIFT || | | a<sub>3</sub> || || || SHIFT || SHIFT || | ||
|- | |- | ||
| c<sub>5</sub> || SHIFT || REDUCE(4) || || || | | c<sub>5</sub> || SHIFT || REDUCE(4) || || || REDUCE(4) | ||
|- | |- | ||
| <A><sub>5</sub> || || REDUCE(5) || || || | | <A><sub>5</sub> || || REDUCE(5) || || || REDUCE(5) | ||
|} | |} | ||
Na kraju parsiranja date sekvence na vrhu steka je stanje <A><sub>5</sub>, i sekvenca se odbija. | Na kraju parsiranja date sekvence na vrhu steka je stanje <A><sub>5</sub>, i sekvenca se odbija. | ||
Ред 204: | Ред 200: | ||
* FIRST(<A>) = {c} | * FIRST(<A>) = {c} | ||
* FIRST(<S>) = FIRST(<A>) = {c} | * FIRST(<S>) = FIRST(<A>) = {c} | ||
* FOLLOW(<A>) = FIRST(<S>) ∪ {b} = {b, c} | * FOLLOW(<A>) = FIRST(<S>) ∪ FOLLOW(<S>) ∪ {b} = {─┤, b, c} | ||
* FOLLOW(<S>) = FOLLOW(<A>) ∪ FIRST(<S>) ∪ {─┤} = {─┤, b, c} | * FOLLOW(<S>) = FOLLOW(<A>) ∪ FIRST(<S>) ∪ {─┤} = {─┤, b, c} | ||
{| class="wikitable" | {| class="wikitable" | ||
Ред 224: | Ред 220: | ||
|- | |- | ||
! <A><sub>x</sub> | ! <A><sub>x</sub> | ||
| <S><sub>1</sub> || | | <S><sub>1</sub> || <A><sub>x</sub> || b<sub>3</sub> || c<sub>4</sub> || | ||
|- | |- | ||
! b<sub>3</sub> | ! b<sub>3</sub> | ||
| <S><sub>3</sub> || | | <S><sub>3</sub> || <A><sub>x</sub> || || c<sub>4</sub> || | ||
|- | |- | ||
! <S><sub>3</sub> | ! <S><sub>3</sub> | ||
Ред 237: | Ред 233: | ||
{| class="wikitable" | {| class="wikitable" | ||
|+ Kontrolna tabela SLR(1) parsera | |+ Kontrolna tabela SLR(1) parsera | ||
! Stanje !! b | ! Stanje !! b !! c !! ─┤ | ||
|- | |- | ||
| ∇ || REDUCE(2) || '''S/R konflikt''' || REDUCE(2) | | ∇ || REDUCE(2) || '''S/R konflikt''' || REDUCE(2) | ||
|- | |- | ||
| <S><sub>0</sub> || | | <S><sub>0</sub> || || || SHIFT | ||
|- | |- | ||
| ─┤<sub>0</sub> || | | ─┤<sub>0</sub> || || || ACCEPT | ||
|- | |- | ||
| c<sub>4</sub> || REDUCE(4) || REDUCE(4) || | | c<sub>4</sub> || REDUCE(4) || REDUCE(4) || REDUCE(4) | ||
|- | |- | ||
| <A><sub>x</sub> || '''S/R konflikt''' || '''S/R konflikt''' || REDUCE(2) | | <A><sub>x</sub> || '''S/R konflikt''' || '''S/R konflikt''' || REDUCE(2) | ||
|- | |- | ||
| b<sub>3</sub> || REDUCE(2) || '''S/R konflikt''' || REDUCE(2) | | b<sub>3</sub> || REDUCE(2) || '''S/R konflikt''' || REDUCE(2) | ||
|- | |- | ||
| <S><sub>3</sub> || REDUCE(3) || REDUCE(3) || | | <S><sub>3</sub> || REDUCE(3) || REDUCE(3) || REDUCE(3) | ||
|- | |- | ||
| <S><sub>1</sub> || REDUCE(1) || REDUCE(1) || REDUCE(1) | | <S><sub>1</sub> || REDUCE(1) || REDUCE(1) || REDUCE(1) | ||
|} | |} | ||
[[Категорија:Рокови]] | [[Категорија:Рокови]] | ||
[[Категорија:Програмски преводиоци 1]] | [[Категорија:Програмски преводиоци 1]] |
Тренутна верзија на датум 4. децембар 2022. у 20:22
Drugi kolokvijum 2017. godine održan je 2. decembra i trajao je 90 minuta. Postavka roka dostupna je sa stranice predmeta (arhiva).
1. zadatak
Postavka
Data je gramatika koja opisuje niz brojeva u brojnom sistemu sa osnovom dva (niz binarnih vrednosti). Brojevi su razdvojeni zarezom. Broj se sastoji od jednog ili više bitova.
- <niz> → <niz> , <broj>
- <niz> → <broj>
- <broj> → BIT <broj>
- <broj> → BIT
- Gramatiku transformisati u LL(1) gramatiku.
- Gramatiku dobijenu pod a) dopuniti atributima tako da startni neterminal <niz> sadrži sintetizovani atribut koji predstavlja ukupan broj neparnih vrednosti u nizu. Terminal BIT ima sintetizovani atribut koji može biti 1 ili 0 u zavisnosti od vrednosti bita.
- Na osnovu gramatike dobijene pod b) formirati parser rekurzivnog spusta.
Rešenje
Gramatika transformisana u LL(1) zajedno sa SELECT skupovima glasi ovako:
- <niz> → <broj> <niz'>
- SELECT(1) = {BIT}
- <niz'> → , <broj> <niz'>
- SELECT(2) = {","}
- <niz'> → ε
- SELECT(3) = {-|}
- <broj> → BIT <broj'>
- SELECT(4) = {BIT}
- <broj'> → <broj>
- SELECT(5) = {BIT}
- <broj'> → ε
- SELECT(6) = {",", -|}
Neterminalu <niz> možemo dodati atribut koji broji koliko je neparnih brojeva bilo u njemu, dok neterminalu <broj> možemo dodati atribute koji kažu da li je taj broj paran (, vrednost je 0 ako jeste a 1 ako nije) i da li se došlo do kraja sa parsiranjem broja (). S tim u vidu, atributivno-translaciona gramatika može da izgleda ovako:
- <niz>n → <broj>p,e <niz'>n1
- <niz'>n → , <broj>p,e <niz'>n1
- <niz'>_n → ε
- <broj>p,e → BITv <broj'>p1,e1
- <broj'>p,e → <broj>p1,e1
- <broj'>p,e → ε
Parser rekurzivnog spusta za ovu gramatiku bi glasio:
char input;
int terminal(char t) {
if (input == t) {
input = advance();
// Za dobijanje vrednosti terminala BIT.
return getInputValue();
} else {
reject();
}
}
void parse() {
int n;
input = advance();
niz(n);
terminal(EOF);
}
void niz(int& n) {
switch (input) {
case BIT:
int p;
int e;
broj(p, e);
int n1;
niz1(n1);
n = n1 + p;
break;
default: reject();
}
}
void niz1(int& n) {
switch (input) {
case ',':
terminal(',');
int p;
int e;
broj(p, e);
int n1;
niz1(n1);
n = n1 + p;
break;
case EOF:
n = 0;
break;
default: reject();
}
}
void broj(int& p, int& e) {
switch (input) {
case BIT:
e = 0;
int v = terminal(BIT);
int p1;
int e1;
broj1(p1, e1);
p = p1;
if (e1) {
p = v;
}
break;
default: reject();
}
}
void broj1(int& p, int& e) {
switch (input) {
case BIT:
int p1;
int e1;
broj(p1, e1);
p = p1;
e = e1;
break;
case ',':
case EOF:
p = 0;
e = 1;
break;
default: reject();
}
}
2. zadatak
Postavka
Jedna bezbednosna agencija na osnovu zakona o obelodanjivanju informacija objavila je delove dosijea poznatog kompjuterskog stručnjaka sa sledećim LALR(1) karakterističnim automatom u kome su neka stanja namerno zasenčena:
- Navesti sadržaje svih zasenčenih stanja.
- Napisati originalnu gramatiku na osnovu koje je konstruisan dati automat.
- Napisati KONTROLNU tabelu LALR(1) parsera. Potisnu ne pisati (negativni poeni).
- Koje je finalno stanje na vrhu steka parsera i finalni rezultat parsiranja ulazne sekvence: cacbd─┤
Rešenje
Originalna gramatika glasi:
- <S> → a b <A>
- <S> → <A> <C>
- <A> → a <C> b
- <A> → ε
- <C> → c <A>
- <C> → d
Stanje | a | b | c | d | ─┤ |
---|---|---|---|---|---|
∇ | SHIFT | REDUCE(4) | REDUCE(4) | ||
<A>2 | SHIFT | SHIFT | |||
<S>0 | SHIFT | ||||
<C>2 | REDUCE(2) | ||||
ax | SHIFT | SHIFT | SHIFT | ||
d6 | REDUCE(6) | ||||
<C>3 | SHIFT | ||||
b3 | REDUCE(3) | REDUCE(3) | REDUCE(3) | ||
─┤0 | ACCEPT | ||||
b1 | SHIFT | REDUCE(4) | |||
<A>1 | REDUCE(1) | ||||
a3 | SHIFT | SHIFT | |||
c5 | SHIFT | REDUCE(4) | REDUCE(4) | ||
<A>5 | REDUCE(5) | REDUCE(5) |
Na kraju parsiranja date sekvence na vrhu steka je stanje <A>5, i sekvenca se odbija.
3. zadatak
Postavka
Na osnovu zadate beskontekstne gramatike, u kojoj se simbol ε koristi za opis praznih smena, konstruisati SLR(1) parser konfiguracionom metodom i odrediti FIRST i FOLLOW skupove.
- <S> → <A> <S>
- <S> → ε
- <A> → <A> b <S>
- <A> → c
Rešenje
FIRST i FOLLOW skupovi su sledeći:
- FIRST(<A>) = {c}
- FIRST(<S>) = FIRST(<A>) = {c}
- FOLLOW(<A>) = FIRST(<S>) ∪ FOLLOW(<S>) ∪ {b} = {─┤, b, c}
- FOLLOW(<S>) = FOLLOW(<A>) ∪ FIRST(<S>) ∪ {─┤} = {─┤, b, c}
Stanje | <S> | <A> | b | c | ─┤ |
---|---|---|---|---|---|
∇ | <S>0 | <A>x | c4 | ||
<S>0 | ─┤0 | ||||
─┤0 | |||||
c4 | |||||
<A>x | <S>1 | <A>x | b3 | c4 | |
b3 | <S>3 | <A>x | c4 | ||
<S>3 | |||||
<S>1 |
Stanje | b | c | ─┤ |
---|---|---|---|
∇ | REDUCE(2) | S/R konflikt | REDUCE(2) |
<S>0 | SHIFT | ||
─┤0 | ACCEPT | ||
c4 | REDUCE(4) | REDUCE(4) | REDUCE(4) |
<A>x | S/R konflikt | S/R konflikt | REDUCE(2) |
b3 | REDUCE(2) | S/R konflikt | REDUCE(2) |
<S>3 | REDUCE(3) | REDUCE(3) | REDUCE(3) |
<S>1 | REDUCE(1) | REDUCE(1) | REDUCE(1) |