Програмски преводиоци 1/К2 2015
Drugi kolokvijum 2015. godine održan je 29. novembra i trajao je 90 minuta. Postavka roka dostupna je sa stranice predmeta (arhiva).
1. zadatak
Postavka
- Dodati atribute i odgovarajuća pravila u datu gramatiku tako da startni simbol dobije atribut
val
koji predstavlja decimalnu vrednost binarnog broja opisanog gramatikom. Na primer, ako je ulazna sekvenca 101.101 ondaval
treba da ima vrednost 5.625. Simbol | nije terminalni simbol, već se koristi da razdvoji smene istog neterminala.- <S> → <L> . <L> | <L>
- <L> → <L> <B> | <B>
- <B> → 0 | 1
- Nacrtati atributivno stablo izvođenja za izraz 101.101.
Rešenje
- <S>val → <L>v1,p1,c1 . <L>v2,p2,c2
- <S>val → <L>v1,p1,c1
- <L>v,p,c → <L>v1,p1,c1 <B>v2
- <L>v,p,c → <B>v1
- <B>v → 0
- <B>v → 1
2. zadatak
Postavka
Data je gramatika:
- <S> → ( <L> ) | a
- <L> → <L> , <S> | <S>
- Da li je gramatika pogodna za parsiranje na bazi rekurzivnog spusta? Obrazložiti odgovor. Ako nije pogodna, izvršiti transformaciju gramatike u ekvivalentnu koja se može koristiti za rekurzivni spust.
- Izračunati poništivost, FIRST, FOLLOW i SELECT skupove za gramatiku dobijenu u tački a).
- Dodati u gramatiku attribute, pravila i akcije da se izračuna i ispiše na izlazu najveća dubina ugneždavanja zagrada u ulaznoj sekvenci. Na primer, ako je u ulaznoj sekvenci ...(...(..)..)..(..).. onda je najveća dubina 2.
- Napraviti parser na bazi rekurzivnog spusta za gramatiku dobijenu u tački c). Napomena: ako preskočite tačku c) onda za gramatiku dobijenu u tački a).
Rešenje
Data gramatika nije pogodna za parsiranje na bazi rekurzivnog spusta jer nije LL(1) (sadrži levu rekurziju). Transformisanjem dobija se sledeća gramatika:
- <S> → ( <L> )
- SELECT(1) = {"("}
- <S> → a
- SELECT(2) = {"a"}
- <L> → <S> <L'>
- SELECT(3) = {"(", "a"}
- <L'> → , <S> <L'>
- SELECT(4) = {","}
- <L'> → E
- SELECT(5) = FOLLOW(<L'>) = {")"}
FIRST i FOLLOW skupovi u ovoj gramatici glase ovako:
- FIRST(<S>) = {"(", "a"}
- FIRST(<L>) = FIRST(<S>) = {"(", "a"}
- FIRST(<L'>) = {","}
- FOLLOW(<L>) = {")"}
- FOLLOW(<L'>) = FOLLOW(<L>) = {")"}
- FOLLOW(<S>) = {─┤} ∪ FIRST(<L'>) ∪ FOLLOW(<L>) = {─┤, ",", ")"}
Atributivno-translaciona gramatika iz tačke c bi glasila ovako:
- <S>d → ( <L>d1 )
- <S>d → a
- <L>d → <S>d1 <L'>d2
- <L'>d → , <S>d1 <L'>d2
- <L'>d → ε
Na osnovu toga, parser ove gramatike bi mogao da izgleda ovako:
char input;
void terminal(char t) {
if (input == t) {
input = advance();
} else {
reject();
}
}
void parse() {
input = advance();
int depth;
S(depth);
}
void S(int& depth) {
switch (input) {
case 'a':
terminal('a');
depth = 0;
break;
case '(':
terminal('(');
int d1;
L(d1);
depth = d1;
terminal(')');
default: reject();
}
}
void L(int& depth) {
switch (input) {
case '(':
case 'a':
int d1;
int d2;
S(d1);
L1(d2);
depth = max(d1, d2);
break;
default: reject();
}
}
void L1(int& depth) {
switch (input) {
case ',':
terminal(',');
int d1;
int d2;
S(d1);
L1(d2);
depth = max(d1, d2);
break;
case ')':
depth = 0;
break;
default: reject();
}
}
3. zadatak
Postavka
Na osnovu date gramatike konstruisati LR(0) prepoznavač ručki, kao i kontrolnu i potisnu tabelu SLR(1) parsera. Dati kratak komentar na dobijeni rezultat.
- <S> → <A> <B>
- <A> → a <B>
- <B> → <S> b
- <B> → ε
Rešenje
FIRST i FOLLOW skupovi u ovoj gramatici su:
- FIRST(<A>) = {"a"}
- FIRST(<S>) = FIRST(<A>) = {"a"}
- FIRST(<B>) = FIRST(<S>) = {"a"}
- FOLLOW(<S>) = {─┤, "b"}
- FOLLOW(<A>) = FIRST(<B>) u FOLLOW(<S>) = {─┤, "a", "b"}
- FOLLOW(<B>) = FOLLOW(<A>) u FOLLOW(<S>) = {─┤, "a", "b"}
Stanje | <S> | <A> | <B> | a | b | ─┤ |
---|---|---|---|---|---|---|
∇ | <S>0 | <A>1 | a2 | |||
<S>0 | ─┤0 | |||||
─┤0 | ||||||
a2 | <S>3 | <A>1 | <B>2 | a2 | ||
<B>2 | ||||||
<A>1 | <S>3 | <A>1 | <B>1 | a2 | ||
<B>1 | ||||||
<S>3 | b3 | |||||
b3 |
Stanje | a | b | ─┤ |
---|---|---|---|
∇ | SHIFT | ||
<S>0 | SHIFT | ||
─┤0 | ACCEPT | ||
a2 | S/R konflikt | REDUCE(4) | REDUCE(4) |
<B>2 | REDUCE(2) | REDUCE(2) | REDUCE(2) |
<A>1 | S/R konflikt | REDUCE(4) | REDUCE(4) |
<B>1 | REDUCE(1) | REDUCE(1) | |
<S>3 | SHIFT | ||
b3 | REDUCE(3) | REDUCE(3) | REDUCE(3) |
Možemo videti da, uprkos korišćenju SLR(1) automata umesto LR(0), nismo uspeli da razrešimo S/R konflikte.
4. zadatak
Postavka
Na osnovu date gramatike konstruisati LR(0) automat, kontrolnu i potisnu tabelu LALR(1) parsera.
- <S> → a <X>
- <X> → <X> b <X> c
- <X> → ε
Rešenje
Stanje | <S> | <X> | a | b | c | ─┤ |
---|---|---|---|---|---|---|
∇ | <S>0 | a1 | ||||
<S>0 | ─┤0 | |||||
─┤0 | ||||||
a1 | <X>x | |||||
<X>x | b2 | |||||
b2 | <X>x2 | |||||
<X>x2 | b2 | c2 | ||||
c2 |
Stanje | a | b | c | ─┤ |
---|---|---|---|---|
∇ | SHIFT | |||
<S>0 | SHIFT | |||
─┤0 | ACCEPT | |||
a1 | REDUCE(3) | REDUCE(3) | ||
<X>x | SHIFT | REDUCE(1) | ||
b2 | REDUCE(3) | REDUCE(3) | ||
<X>x2 | SHIFT | SHIFT | ||
c2 | REDUCE(2) | REDUCE(2) | REDUCE(2) |