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

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

1. задатак

Поставка

1. Додати атрибуте и одговарајућа правила у дату граматику тако да стартни симбол добије атрибут val који представља децималну вредност бинарног броја описаног граматиком. На пример, ако је улазна секвенца 101.101 онда val треба да има вредност 5.625. Симбол | није терминални симбол, већ се користи да раздвоји смене истог нетерминала.
   • <С> → <L> . <L> | <L>
   • <L> → <L> <Б> | <Б>
   • <Б> → 0 | 1
2. Нацртати атрибутивно стабло извођења за израз 101.101.

Решење

Стабло извођења у првом задатку, ставци под б.

1. <С>_вал → <L>_в1,п1,ц1 . <L>_в2,п2,ц2

   $val \leftarrow v_1 + p_2$

2. <С>_вал → <L>_в1,п1,ц1

   $val \leftarrow v_1$

3. <L>_в,п,ц → <L>_в1,п1,ц1 <Б>_в2

   $c \leftarrow c_1 + 1$

   $v \leftarrow 2v_1 + v_2$

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

4. <L>_в,п,ц → <Б>_в1

   $c \leftarrow 1$

   $v \leftarrow v_1$

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

5. <Б>_в → 0

   $v \leftarrow 0$

6. <Б>_в → 1

   $v \leftarrow 1$

2. задатак

Поставка

Дата је граматика:

• <С> → ( <L> ) | а
• <L> → <L> , <С> | <С>

1. Да ли је граматика погодна за парсирање на бази рекурзивног спуста? Образложити одговор. Ако није погодна, извршити трансформацију граматике у еквивалентну која се може користити за рекурзивни спуст.
2. Израчунати поништивост, ФИРСТ, ФОЛЛОW и СЕЛЕЦТ скупове за граматику добијену у тачки а).
3. Додати у граматику аттрибуте, правила и акције да се израчуна и испише на излазу највећа дубина угнеждавања заграда у улазној секвенци. На пример, ако је у улазној секвенци ...(...(..)..)..(..).. онда је највећа дубина 2.
4. Направити парсер на бази рекурзивног спуста за граматику добијену у тачки ц). Напомена: ако прескочите тачку ц) онда за граматику добијену у тачки а).

Решење

Дата граматика није погодна за парсирање на бази рекурзивног спуста јер није ЛЛ(1) (садржи леву рекурзију). Трансформисањем добија се следећа граматика:

1. <С> → ( <L> )

   СЕЛЕЦТ(1) = {"("}

2. <С> → а

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

3. <L> → <С> <L'>

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

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

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

5. <L'> → Е

   СЕЛЕЦТ(5) = ФОЛЛОW(<L'>) = {")"}

ФИРСТ и ФОЛЛОW скупови у овој граматици гласе овако:

• ФИРСТ(<С>) = {"(", "а"}
• ФИРСТ(<L>) = ФИРСТ(<С>) = {"(", "а"}
• ФИРСТ(<L'>) = {","}
• ФОЛЛОW(<L>) = {")"}
• ФОЛЛОW(<L'>) = ФОЛЛОW(<L>) = {")"}
• ФОЛЛОW(<С>) = {─┤} ∪ ФИРСТ(<L'>) ∪ ФОЛЛОW(<L>) = {─┤, ",", ")"}

Атрибутивно-транслациона граматика из тачке ц би гласила овако:

1. <С>_д → ( <L>_д1 )

   $d \leftarrow d_1 + 1$

2. <С>_д → а

   $d \leftarrow 0$

3. <L>_д → <С>_д1 <L'>_д2

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

4. <L'>_д → , <С>_д1 <L'>_д2

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

5. <L'>_д → ε

   $d \leftarrow 0$

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

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

Поставка

На основу дате граматике конструисати ЛР(0) препознавач ручки, као и контролну и потисну табелу СЛР(1) парсера. Дати кратак коментар на добијени резултат.

• <С> → <А> <Б>
• <А> → а <Б>
• <Б> → <С> б
• <Б> → ε

Решење

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

ФИРСТ и ФОЛЛОW скупови у овој граматици су:

• ФИРСТ(<А>) = {"а"}
• ФИРСТ(<С>) = ФИРСТ(<А>) = {"а"}
• ФИРСТ(<Б>) = ФИРСТ(<С>) = {"а"}
• ФОЛЛОW(<С>) = {─┤, "б"}
• ФОЛЛОW(<А>) = ФИРСТ(<Б>) у ФОЛЛОW(<С>) = {─┤, "а", "б"}
• ФОЛЛОW(<Б>) = ФОЛЛОW(<А>) у ФОЛЛОW(<С>) = {─┤, "а", "б"}

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

Стање	<С>	<А>	<Б>	а	б	─┤
∇	<С>0	<А>1		а2
<С>0						─┤0
─┤0
а2	<С>3	<А>1	<Б>2	а2
<Б>2
<А>1	<С>3	<А>1	<Б>1	а2
<Б>1
<С>3					б3
б3

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

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

Можемо видети да, упркос коришћењу СЛР(1) аутомата уместо ЛР(0), нисмо успели да разрешимо С/Р конфликте.

4. задатак

Поставка

На основу дате граматике конструисати ЛР(0) аутомат, контролну и потисну табелу ЛАЛР(1) парсера.

• <С> → а <X>
• <X> → <X> б <X> ц
• <X> → ε

Решење

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

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

Стање	<С>	<X>	а	б	ц	─┤
∇	<С>0		а1
<С>0						─┤0
─┤0
а1		<X>x
<X>x				б2
б2		<X>x2
<X>x2				б2	ц2
ц2

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

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