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

Први колоквијум 2012. године одржан је 26. октобра и трајао је 1.5 сат. Поставка рока доступна је са странице предмета.

1. задатак

Поставка

Робот се креће по правоугаоној решетки. Може да иде напред (ф), скрене лево (л), или скрене десно (р).

1. Конструисати коначни аутомат који описује оне и само оне секвенце покрета које робота доводе у исти правац и смер кретања као и на почетку.
2. Конструисати безконтекстну граматику која описује исти скуп секвенци као и под а).

Решење

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

	ф	л	р	Прихвата
Н	Н	W	Е	1
W	W	С	Н	0
Е	Е	Н	С	0
С	С	Е	W	0

Безконтекстна граматика је:

• <Н> → ε
• <Н> → ф <Н>
• <Н> → л <W>
• <Н> → р <Е>
• <W> → ф <W>
• <W> → л <С>
• <W> → р <Н>
• <Е> → ф <Е>
• <Е> → л <Н>
• <Е> → р <С>
• <С> → ф <С>
• <С> → л <Е>
• <С> → р <W>

2. задатак

Поставка

Написати регуларни израз којим се описују све секвенце које:

• почињу једним или више малих слова енглеске абецеде, након којих се појављује
  • или нула или више знакова из скупа цифара од 5 до 9 и великих слова енглеске абецеде (поређаних у произвољном редоследу, тј. мешају се слова и цифре).
  • или се појављује један или више бројева из опсега од 0 до 4.

Решење

[a-z]+([5-9A-Z]*|[0-4]+)

3. задатак

Поставка

Написати граматику којом се дефинишу правила формирања израза у хипотетичком програмском језику. Постоје два бинарна оператора: оператор "$" и оператор "#". Оператор "$" је лево асоцијативан и има већи приоритет од оператора "#", који је десно асоцијативан. Изрази се састоје од идентификатора (ИДЕНТ) и константи (ЦОНСТ) између којих се наводе дати оператори. Бинарни оператор се пише између своја два операнда. ИДЕНТ и ЦОНСТ су терминални симболи. Граматика не сме бити вишезначна.

Пример израза: а$2$3 # б$3 # ц

Решење

• <еxпр> → <доллар_еxпр> # <еxпр>
• <еxпр> → <доллар_еxпр>
• <доллар_еxпр> → <доллар_еxпр> $ <терм>
• <доллар_еxпр> → <терм>
• <терм> → <ИДЕНТ>
• <терм> → <ЦОНСТ>

4. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

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

• <С> → (<А>)
• <А> → <С>, б
• <А> → а

Приказати рад парсера када се на улаз доведе следећа улазна секвенца: ((а),б)

Решење

Потисна табела

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

Контролна табела

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