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

Други колоквијум 2017. године одржан је 2. децембра и трајао је 90 минута. Поставка рока доступна је са странице предмета (архива).

1. задатак

Поставка

Дата је граматика која описује низ бројева у бројном систему са основом два (низ бинарних вредности). Бројеви су раздвојени зарезом. Број се састоји од једног или више битова.

1. <низ> → <низ> , <број>
2. <низ> → <број>
3. <број> → БИТ <број>
4. <број> → БИТ

1. Граматику трансформисати у ЛЛ(1) граматику.
2. Граматику добијену под а) допунити атрибутима тако да стартни нетерминал <низ> садржи синтетизовани атрибут који представља укупан број непарних вредности у низу. Терминал БИТ има синтетизовани атрибут који може бити 1 или 0 у зависности од вредности бита.
3. На основу граматике добијене под б) формирати парсер рекурзивног спуста.

Решење

Граматика трансформисана у ЛЛ(1) заједно са СЕЛЕЦТ скуповима гласи овако:

1. <низ> → <број> <низ'>

   СЕЛЕЦТ(1) = {БИТ}

2. <низ'> → , <број> <низ'>

   СЕЛЕЦТ(2) = {","}

3. <низ'> → Е

   СЕЛЕЦТ(3) = {-|}

4. <број> → БИТ <број'>

   СЕЛЕЦТ(4) = {БИТ}

5. <број'> → БИТ <број'>

   СЕЛЕЦТ(5) = {БИТ}

6. <број'> → Е

   СЕЛЕЦТ(6) = {",", -|}

Нетерминалу <низ> можемо додати атрибут који броји колико је непарних бројева било у њему, док нетерминалу <број> можемо додати атрибуте који кажу да ли је тај број паран ($p$, вредност је 0 ако јесте а 1 ако није) и да ли се дошло до краја са парсирањем броја ($e$). С тим у виду, атрибутивно-транслациона граматика може да изгледа овако:

1. <низ>_н → <број>_п,е <низ'>_н1

   $n \leftarrow n_1 + p$

2. <низ'>_н → , <број>_п,е <низ'>_н1

   $n \leftarrow n_1 + p$

3. <низ'>_н → Е

   $n \leftarrow 0$

4. <број>_п,е → БИТ_в <број'>_п1,е1

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

   $e \leftarrow 0$

5. <број'>_п,е → БИТ_в <број'>_п1,е1

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

   $e \leftarrow 0$

6. <број'>_п,е → ε

   $p \leftarrow 0$

   $e \leftarrow 1$

Парсер рекурзивног спуста за ову граматику би гласио:

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. задатак

Поставка

Једна безбедносна агенција на основу закона о обелодањивању информација објавила је делове досијеа познатог компјутерског стручњака са следећим ЛАЛР(1) карактеристичним аутоматом у коме су нека стања намерно засенчена:

1. Навести садржаје свих засенчених стања.
2. Написати оригиналну граматику на основу које је конструисан дати аутомат.
3. Написати КОНТРОЛНУ табелу ЛАЛР(1) парсера. Потисну не писати (негативни поени).
4. Које је финално стање на врху стека парсера и финални резултат парсирања улазне секвенце: цацбд─┤

Решење

Карактеристични аутомат из ставке под а другог задатка.

Оригинална граматика гласи:

1. <С> → а б <А>
2. <С> → <А> <C>
3. <А> → а <C> б
4. <А> → ε
5. <C> → ц <А>
6. <C> → д

Контролна табела ЛАЛР(1) парсера

Стање	а	б	ц	д	─┤
∇	СХИФТ		РЕДУЦЕ(4)	РЕДУЦЕ(4)
<А>2			СХИФТ	СХИФТ
<С>0					СХИФТ
<C>2					РЕДУЦЕ(2)
аx		СХИФТ	СХИФТ	СХИФТ
д6		РЕДУЦЕ(6)
<C>3		СХИФТ
б3			РЕДУЦЕ(3)	РЕДУЦЕ(3)	РЕДУЦЕ(3)
─┤0					АЦЦЕПТ
б1	СХИФТ				РЕДУЦЕ(4)
<А>1					РЕДУЦЕ(1)
а3			СХИФТ	СХИФТ
ц5	СХИФТ	РЕДУЦЕ(4)
<А>5		РЕДУЦЕ(5)

На крају парсирања дате секвенце на врху стека је стање <А>₅, и секвенца се одбија.

3. задатак

Поставка

На основу задате бесконтекстне граматике, у којој се симбол ε користи за опис празних смена, конструисати СЛР(1) парсер конфигурационом методом и одредити ФИРСТ и ФОЛЛОW скупове.

1. <С> → <А> <С>
2. <С> → ε
3. <А> → <А> б <С>
4. <А> → ц

Решење

Карактеристични аутомат из трећег задатка.

ФИРСТ и ФОЛЛОW скупови су следећи:

• ФИРСТ(<А>) = {ц}
• ФИРСТ(<С>) = ФИРСТ(<А>) = {ц}
• ФОЛЛОW(<А>) = ФИРСТ(<С>) ∪ {б} = {б, ц}
• ФОЛЛОW(<С>) = ФОЛЛОW(<А>) ∪ ФИРСТ(<С>) ∪ {─┤} = {─┤, б, ц}

Потисна табела СЛР(1) парсера

Стање	<С>	<А>	б	ц	─┤
∇	<С>0	<А>x		ц4
<С>0					─┤0
─┤0
ц4
<А>x	<С>1		б3
б3	<С>3
<С>3
<С>1

Контролна табела СЛР(1) парсера

Стање	б	ц	─┤
∇	РЕДУЦЕ(2)	С/Р конфликт	РЕДУЦЕ(2)
<С>0			СХИФТ
─┤0			АЦЦЕПТ
ц4	РЕДУЦЕ(4)	РЕДУЦЕ(4)
<А>x	С/Р конфликт	С/Р конфликт	РЕДУЦЕ(2)
б3	РЕДУЦЕ(2)	С/Р конфликт	РЕДУЦЕ(2)
<С>3	РЕДУЦЕ(3)	РЕДУЦЕ(3)
<С>1	РЕДУЦЕ(1)	РЕДУЦЕ(1)	РЕДУЦЕ(1)