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

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу

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 (, 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:

  1. <niz>n → <broj>p,e <niz'>n1
  2. <niz'>n → , <broj>p,e <niz'>n1
  3. <niz'>_n → ε
  4. <broj>p,e → BITv <broj'>p1,e1
  5. <broj'>p,e → <broj>p1,e1
  6. <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:

  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) 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.

  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)