Програмски преводиоци 1/К2 2017 — разлика између измена
м (Ispravljen FOLLOW skup za A i dodate dve REDUCE smene u kontrolnu tabelu; ažurirana potisna tabela sa stanjima iz ispravljenog dijagrama) |
м (Izmena <broj'> da bude konzistentnije sa pravilima leve faktorizacije) |
||
Ред 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> |
Верзија на датум 2. децембар 2022. у 17:16
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:
e = 0;
int v = terminal(BIT);
int p1;
int e1;
broj1(p1, e1);
p = p1;
if (e1) {
p = v;
}
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) | |||
<A>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) |