Програмски преводиоци 1/Јануар 2022

Испит у јануарском року 2022. године одржан је 28. јануара. Поставка рока је доступна са странице предмета.

1. задатак

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

Поставка

Одредити минимални коначни детерминистички аутомат који прихвата оне и само оне улазне секвенце које НЕ прихвата коначни аутомат са слике али када се читају са десна у лево. На пример, дати аутомат не прихвата секвенцу аб, то значи да тражени аутомат треба да прихвати секвенцу ба. Поступак изложити по корацима, на генералан начин који би се могао применити и на сваки други аутомат.

Стање	а	б	Прихвата
→ А	Б		0
Б	C	D	0
C			1
D		Ф	0
Ф	Ф	Ф	1

2. задатак

Поставка

1. За смене 1 и 2 дате граматике навести које атрибуте треба рачунати и од којих других атрибута они могу да зависе да би цела граматика била L-атрибутивна. Правила наводити у облику аа = ф(бб, цц, дд,..) где је аа атрибут који мора да се рачуна, док су бб, цц, дд, итд сви други атрибути од којих посматрани може да зависи. Нетерминал <С> има синтетизован атрибут.
2. Навести псеудокод за процедуру А у парсеру на бази рекурзивног спуста. Остале делове парсера не наводити. Преименовати променљиве да се минимизује број правила копирања вредности атрибута.

1. <С>_x → а_y <А>_з,в,w <С>_п {б_q}
2. <С>_x1 → д_y1 {ц_з1} <А>_{в1, w1, п1}
3. <А>_x,y,з1 → а_q {ц_в} <А>_x1,з,у <А>_у,т,y1
   1. $v \larr x - q$
   2. $x_1 \larr x$
   3. $y \larr y_1$
   4. $z_1 \larr z$
4. <А>_т,с,с1 → д_q {б_т1} а_с2
   1. $t_1 \larr t$
   2. $(s,s_1) \larr s_2$

Решење

Из дате граматике можемо закључити следеће о типовима атрибута:

• Акције b и c садрже наслеђене атрибуте.
• Нетерминал <A> садржи три атрибута, од којих је први наслеђен а друга два синтетизована.

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

• $x = f(y, z, v, w, p, q)$
• $z = f(y)$
• $q = f(y, z, v, w, p)$

а у другој смени следеће:

• $x1 = f(y_1, z_1, v_1, w_1, p_1)$
• $z1 = f(y_1)$
• $v1 = f(y_1, z_1)$

Код парсера са адекватно преименованим атрибутима дат је испод:

void A(int x, int& y, int& z) {
    switch (input) {
        case 'a':
            input = advance();
            int q = getInputValue();
            out('c', x - q);
            int u;
            A(x, z, u);
            int t;
            A(u, t, y);
            break;
        case 'd':
            input = advance();
            out('b', x);
            input = advance();
            y = z = getInputValue();
            break;
    }
}

3. задатак

Поставка

Задата је граматика

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

1. Конструисати каракетристични^[сиц] аутомат ЛР(0) парсера као и одговарајућу контролну табелу. Да ли има конфликата?
2. Конструисати контролну табелу СЛР(1) парсера. Да ли има конфликата?

Решење

Карактеристични ЛР(0) аутомат у трећем задатку.

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

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

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

• ФОЛЛОW(<С>) = {─┤, б}
• ФОЛЛОW(<Б>) = {б, ц, д}
• ФОЛЛОW(<А>) = {а} ∪ ФОЛЛОW(<С>) = {─┤, а, б}

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

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

4. задатак

Поставка

Дат је листинг програма Јануар2022, написан на програмском језику Микројава. Све методе унутрашњих класа су виртуелне. Глобалне методе се позивају статички. Написати комплетан Микројава бајткод превода функције f за дати програм

program Januar2022
	const int K = 2;
	int add;
	class A {
		int fld;
	{
		int m(int a)
		{ return fld * 2; }
		void met()
		{ fld = fld + 3; }
	} }
	class B extends A {
	{
		int m(int b)
		{ /*T1*/
			return fld + b;
		}
	}
	}
	A arr[];
{
	int f(int index){
		add = arr[index].m(K);
		arr[index].met();
		return add + K;
	}
	void main()
		B b;
		int ret;
	{
		/*T2*/
		arr = new A[2];
		arr[0] = new B;
		arr[1] = new A;
		ret = f(0) + f(1);
		print(arr[0].m(ret));
	}
}

Решење

enter 1, 1
getstatic 1
load_0
aload
const_2
getstatic 1
load_0
aload
getfield 0
invokevirtual 'm' -1
putstatic 0
getstatic 1
load_0
aload
dup
getfield 0
invokevirtual 'm' 'e' 't' -1
getstatic 0
const_2
add
exit
return

5. задатак

Поставка

Приказати изглед табеле симбола у тренуцима Т1 и Т2 на основу изворног кода из задатка 4 према формату чворова табеле симбола из прилога. Универсе опсег не треба цртати. За Т2 довољно је назначити измене у односу на претходно стање табеле.

Решење

• 

  Табела симбола у стању Т1.

• 

  Табела симбола у стању Т2.

6. задатак

Поставка

За дати програмски фрагмент написати одговарајући међукод у ССА форми и нацртати граф тока контроле на нивоу основних блокова.

a = 1;
b = 2;
c = 3;
for (a = 4; b < c || a < 10; a++) {
    if (a > b + c) {
        c++;
        break;
    } else if (a > b * c) {
        b--;
        continue;
    }
    else return a;
}
a = b * c;
return a;

Решење

Карактеристични ЛР(0) аутомат у трећем задатку.

1. а1 := 1
2. б1 := 2
3. ц1 := 3
4. а2 := 4
5. т1 := Ф(б1, б2)
6. иф т1 < ц1 гото 8
7. иф а2 >= 10 гото 17
8. т2 := т1 + ц1
9. иф а <= т2 гото 12
10. ц2 := ц1 + 1
11. гото 17
12. т3 := т1 * ц1
13. иф а <= т3 гото 16
14. б2 := т1 - 1
15. гото 5
16. ретурн а2
17. т4 := Ф(б1, б2)
18. т5 := Ф(ц1, ц2)
19. т6 := т1 * т2
20. а3 := т6
21. ретурн а3