Програмски преводиоци 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

1. 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 onda val 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
2. Nacrtati atributivno stablo izvođenja za izraz 101.101.

Rešenje

Stablo izvođenja u prvom zadatku, stavci pod b.

1. <S>_val → <L>_v1,p1,c1 . <L>_v2,p2,c2

   $val \leftarrow v_1 + p_2$

2. <S>_val → <L>_v1,p1,c1

   $val \leftarrow v_1$

3. <L>_v,p,c → <L>_v1,p1,c1 <B>_v2

   $c \leftarrow c_1 + 1$

   $v \leftarrow 2v_1 + v_2$

   $p \leftarrow p_1 + \frac{v_2}{2^c}$

4. <L>_v,p,c → <B>_v1

   $c \leftarrow 1$

   $v \leftarrow v_1$

   $p \leftarrow \frac{v_1}{2}$

5. <B>_v → 0

   $v \leftarrow 0$

6. <B>_v → 1

   $v \leftarrow 1$

2. zadatak

Postavka

Data je gramatika:

• <S> → ( <L> ) | a
• <L> → <L> , <S> | <S>

1. 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.
2. Izračunati poništivost, FIRST, FOLLOW i SELECT skupove za gramatiku dobijenu u tački a).
3. 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.
4. 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:

1. <S> → ( <L> )

   SELECT(1) = {"("}

2. <S> → a

   SELECT(2) = {"a"}

3. <L> → <S> <L'>

   SELECT(3) = {"(", "a"}

4. <L'> → , <S> <L'>

   SELECT(4) = {","}

5. <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:

1. <S>_d → ( <L>_d1 )

   $d \leftarrow d_1 + 1$

2. <S>_d → a

   $d \leftarrow 0$

3. <L>_d → <S>_d1 <L'>_d2

   $d \leftarrow \max(d_1, d_2)$

4. <L'>_d → , <S>_d1 <L'>_d2

   $d \leftarrow \max(d_1, d_2)$

5. <L'>_d → ε

   $d \leftarrow 0$

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

Karakteristični automat u trećem zadatku.

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"}

Potisna tabela SLR(1) parsera

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

Kontrolna tabela SLR(1) parsera

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

Karakteristični automat u četvrtom zadatku.

Potisna tabela LALR(1) parsera

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

Kontrolna tabela LALR(1) parsera

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)