Програмски преводиоци 1/К2 2017

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.

1. <niz> → <niz> , <broj>
2. <niz> → <broj>
3. <broj> → BIT <broj>
4. <broj> → BIT

1. Gramatiku transformisati u LL(1) gramatiku.
2. 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.
3. Na osnovu gramatike dobijene pod b) formirati parser rekurzivnog spusta.

Rešenje

Gramatika transformisana u LL(1) zajedno sa SELECT skupovima glasi ovako:

1. <niz> → <broj> <niz'>

   SELECT(1) = {BIT}

2. <niz'> → , <broj> <niz'>

   SELECT(2) = {","}

3. <niz'> → ε

   SELECT(3) = {-|}

4. <broj> → BIT <broj'>

   SELECT(4) = {BIT}

5. <broj'> → <broj>

   SELECT(5) = {BIT}

6. <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 ($p$, vrednost je 0 ako jeste a 1 ako nije) i da li se došlo do kraja sa parsiranjem broja ($e$). S tim u vidu, atributivno-translaciona gramatika može da izgleda ovako:

1. <niz>_n → <broj>_p,e <niz'>_n1

   $n \leftarrow n_1 + p$

2. <niz'>_n → , <broj>_p,e <niz'>_n1

   $n \leftarrow n_1 + p$

3. <niz'>_n → ε

   $n \leftarrow 0$

4. <broj>_p,e → BIT_v <broj'>_p1,e1

   $p \leftarrow e_1 \cdot v + (1 - e_1) \cdot p_1$

   $e \leftarrow 0$

5. <broj'>_p,e → <broj>_p1,e1

   $p \leftarrow p_1$

   $e \leftarrow e_1$

6. <broj'>_p,e → ε

   $p \leftarrow 0$

   $e \leftarrow 1$

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:

1. Navesti sadržaje svih zasenčenih stanja.
2. Napisati originalnu gramatiku na osnovu koje je konstruisan dati automat.
3. Napisati KONTROLNU tabelu LALR(1) parsera. Potisnu ne pisati (negativni poeni).
4. Koje je finalno stanje na vrhu steka parsera i finalni rezultat parsiranja ulazne sekvence: cacbd─┤

Rešenje

Karakteristični automat iz stavkе pod a drugog zadatka.

Originalna gramatika glasi:

1. <S> → a b <A>
2. <S> → <A> <C>
3. <A> → a <C> b
4. <A> → ε
5. <C> → c <A>
6. <C> → d

Kontrolna tabela LALR(1) parsera

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>₅, 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.

1. <S> → <A> <S>
2. <S> → ε
3. <A> → <A> b <S>
4. <A> → c

Rešenje

Karakteristični automat iz trećeg zadatka.

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}

Potisna tabela SLR(1) parsera

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

Kontrolna tabela SLR(1) parsera

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)