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

Други колоквијум 2020. године одржан је 22. јануара 2021. године, због неодржавања друге колоквијумске недеље у регуларном термину. Поставка овог рока је доступна са странице предмета (архива).

1. задатак

Поставка

Посматра се листа од једног или више идентификатора или целобројних константи, раздвојених зарезима, при чему се на крају користи ";". Улазни симболи су СЛОВО, ЦИФРА, "," и ";". Идентификатори почињу словом, а у наставку имају нула или више слова или цифара. Константе садрже само цифре, могу почињати нулом. Пример исправне листе: 1, а, тт20р, 120;

1. Написати граматику (у којој репетитивне конструкције треба да буду представљене лево рекурзивним сменама) за описане листе. Терминални симболи су СЛОВО, ЦИФРА, "," и ";". Граматика не сме бити двосмислена.
2. Трансформисати граматику иза тачке а) у ЛЛ(1) граматику, применом стандарних трансформација. Израчунати селекционе скупове и проверити да ли је добијена граматика ЛЛ(1).
3. Додати у граматику из тачке а) атрибуте којима се рачуна вредност сваке од константи које се појављују у улазној листи, а такође и збир вредности свих константи у листи. Напомена: акционе симболе не уводити, нису потребни.

Решење

Граматика тражена у ставци под а може да гласи овако:

1. <терминал> → СЛОВО
2. <терминал> → ЦИФРА
3. <ид> → <ид> <терминал>
4. <ид> → СЛОВО
5. <константа> → <константа> ЦИФРА
6. <константа> → ЦИФРА
7. <елемент> → <ид>
8. <елемент> → <константа>
9. <листа> → <листа>, <елемент>
10. <листа> → <елемент>
11. <С> → <листа>;

Трансформисана ЛЛ(1) граматика са селекционим скуповима може да изгледа овако:

1. <терминал> → СЛОВО

   СЕЛЕЦТ(1) = {СЛОВО}

2. <терминал> → ЦИФРА

   СЕЛЕЦТ(2) = {ЦИФРА}

3. <ид> → СЛОВО <ид'>

   СЕЛЕЦТ(3) = {СЛОВО}

4. <ид'> → <терминал> <ид'>

   СЕЛЕЦТ(4) = ФИРСТ(<терминал>) = {СЛОВО, ЦИФРА}

5. <ид'> → ε

   СЕЛЕЦТ(5) = ФОЛЛОW(<ид'>) = ФОЛЛОW(<ид>) = ФОЛЛОW(<елемент>) = ФИРСТ(<листа'>) ∪ ФОЛЛОW(<листа'>) = {","} ∪ ФОЛЛОW(<листа>) = {",", ";"}

6. <константа> → ЦИФРА <константа'>

   СЕЛЕЦТ(6) = {ЦИФРА}

7. <константа'> → ЦИФРА <константа'>

   СЕЛЕЦТ(7) = {ЦИФРА}

8. <константа'> → ε

   СЕЛЕЦТ(8) = ФОЛЛОW(<константа'>) = {",", ";"}

9. <елемент> → <ид>

   СЕЛЕЦТ(9) = {СЛОВО}

10. <елемент> → <константа>

    СЕЛЕЦТ(10) = {ЦИФРА}

11. <листа> → <елемент> <листа'>

    СЕЛЕЦТ(11) = ФИРСТ(<елемент>) = {СЛОВО, ЦИФРА}

12. <листа'> → , <елемент> <листа'>

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

13. <листа'> → ε

    СЕЛЕЦТ(13) = {";"}

14. <С> → <листа>;

    СЕЛЕЦТ(14) = ФИРСТ(<листа>) = ФИРСТ(<елемент>) = {СЛОВО, ЦИФРА}

Због тога што се ни за једну смену не преклапају СЕЛЕЦТ скупови, ово је ЛЛ(1) граматика.

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

1. <терминал> → СЛОВО
2. <терминал> → ЦИФРА
3. <ид> → <ид> <терминал>
4. <ид> → СЛОВО
5. <константа>_в → <константа>_в1 ЦИФРА_в2

   $v \leftarrow 10v_1 + v_2$

6. <константа>_в → ЦИФРА_в1

   $v \leftarrow v_1$

7. <елемент>_в → <ид>

   $v \leftarrow 0$

8. <елемент>_в → <константа>_в1

   $v \leftarrow v_1$

9. <листа>_в → <листа>_в1, <елемент>_в2

   $v \leftarrow v_1 + v_2$

10. <листа>_в → <елемент>_в1

    $v \leftarrow v_1$

11. <С>_в → <листа>_в1;

    $v \leftarrow v_1$

2. задатак

Поставка

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

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

1. Да ли се секвенца fcffcfcf може препознати описаном граматиком? Приказати поступак.
2. Нацртати карактеристични аутомат и контролну табелу ЛР(0) парсера (потисну не цртати).
3. Приказати контролну табелу СЛР(1) парсера. Да ли постоје конфликти?

Решење

• 

  Стабло израза у ставци под а.

• 

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

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

Стање	Операција
∇	СХИФТ
<С>0	СХИФТ
─┤0	АЦЦЕПТ
ф11	СХИФТ
<А>1	СХИФТ
ф12	РЕДУЦЕ(1)
ц2	С/Р конфликт
<Б>2	РЕДУЦЕ(2)
ф3	СХИФТ
<С>3	СХИФТ
ц3	РЕДУЦЕ(3)

ФОЛЛОW скупови ове граматике су:

• ФОЛЛОW(<С>) = {─┤, ц}
• ФОЛЛОW(<А>) = {ф}
• ФОЛЛОW(<Б>) = {ф}

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

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