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

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

1. задатак

Поставка

Дата граматика са скупом терминала {+ - Н * X ↑} описује полином (на пример -5*X↑2+3*X-1).

Трансформисати граматику у ЛЛ(1) граматику.
Додати ЛЛ(1) граматици аттрибуте да се израчуна вредност полинома за задату вредност X. При томе, задата вредност X се прослеђује као наслеђени атрибут x нетерминала <П>_x,y, а вредност полинома треба да се добије као синтетизовани атрибут y истог нетерминала. Додатно, терминал Н_к има атрибут k који представља целобројну вредност. Остали терминали немају атрибуте.
За ЛЛ(1) граматику са атрибутима добијену под б) приказати делове парсера на принципу рекурзивног спуста: процедуру маин и делове парсера који одговарају сменама за нетерминале <П> и <XнаН>. Остатак парсера не наводити. Користити функцију адванце(аттр) која враћа као резултат следећи токен са улаза и додатно враћа кроз параметер аттр вредност атрибута тог токена (0 ако токен нема атрибут).

<П> → <П> <Т>
<П> → <Т>
<Т> → + Н <XнаН>
<Т> → - Н <XнаН>
<XнаН> → * X
<XнаН> → * X ↑ Н
<XнаН> → ε

Решење

<П>_x,y → <Т>_x₁,y₁ <П'>_x₂,y₂
СЕЛЕЦТ(1) = {+, -}

$x_1 \larr x$

$x_2 \larr x$

$y \larr y_1 + y_2$
<П'>_x,y → <Т>_x₁,y₁ <П'>_x₂,y₂
СЕЛЕЦТ(2) = {+, -}

$x_1 \larr x$

$x_2 \larr x$

$y \larr y_1 + y_2$
<П'>_x,y → ε
СЕЛЕЦТ(3) = {─┤}

$y \larr 0$
<Т>_x,y → + Н_к <XнаН>_x₁,y₁
СЕЛЕЦТ(4) = {+}

$x_1 \larr x$

$y \larr k \cdot y_1$
<Т>_x,y → - Н_к <XнаН>_x₁,y₁
СЕЛЕЦТ(5) = {-}

$x_1 \larr x$

$y \larr -k \cdot y_1$
<XнаН>_x,y → * X <На>_x₁,y₁
СЕЛЕЦТ(6) = {*}

$x_1 \larr x$

$y \larr y_1$
<XнаН>_x,y → ε
СЕЛЕЦТ(7) = {+, -, ─┤}

$y \larr 1$
<На>_x,y → ↑ Н_к
СЕЛЕЦТ(8) = {↑}

$y \larr x^k$
<На>_x,y → ε
СЕЛЕЦТ(9) = {+, -, ─┤}

$y \larr 1$

2. задатак

Поставка

Представити меморијски распоред, у време извршавања програма, објеката ц1, ц2, д1 и д2 и одговарајућих виртуелних табела.

class A           { int a = 0; int f() {...} }
class B extends A { int g (){...} }
class C extends B { int g (){...} }
class D extends B { int b = 0; int f (){...} }
C c1 = new C(); C c2 = new C();
D d1 = new D(); D d2 = new D();

Нацртати изглед рун тиме стека програма и навести секвенцу кода за формирање приступне везе процедуре П4 (остатак позивне секвенце не наводити). Процедуре П3 и П4 су угнеждене у процедуру П2, која је угнеждена у процедуру П1. Из П1 се позива П2, из П2 се позива П3, из П3 се позива П4.

Решење

Стек у другом задатку.

Распоред статичког дела меморије у време извршавања.
Адреса	Вредност
0	Адреса ц1
1	Адреса ц2
2	Адреса д1
3	Адреса д2
4	"ф"
5	-1
6	Адреса А::ф
7	-2
8	"ф"
9	-1
10	Адреса А::ф
11	"г"
12	-1
13	Адреса Б::г
14	-2
15	"ф"
16	-1
17	Адреса А::ф
18	"г"
19	-1
20	Адреса C::г
21	-2
22	"ф"
23	-1
24	Адреса D::ф
25	"г"
26	-1
27	Адреса Б::г
28	-2

Код са процедурама о којима је реч би изгледао овако:

procedure P1
    procedure P2
        procedure P3
        begin
            P4();
        end
        procedure P4
        begin
            ...
        end
    begin
        P3();
    end
begin
    P2();
end

Пошто су П3 и П4 на истом лексичком нивоу, а П3 позива П4, формирање приступне везе постиже се са ПУСХ [БП+04].

3. задатак

Поставка

Нека је с₁ секвенца коју прихвата аутомат (1), с₂ секвенца коју прихвата аутомат (2), а с₃ секвенца коју прихвата аутомат (3).

Конструисати недетерминистички коначни аутомат који прихвата секвенце описане регуларним изразом с₁(с₂|с₃).
Добијени НКА из тачке а) конвертовати у детерминистички коначни аутомат.
За добијени ДКА у тачки б) проверити да ли је минималан и, уколико је потребно, спровести процес минимизације.

Аутомат (1).
Стање	0	1	Прихвата
→ А	А	C	1
Б	А	Б	0
C	Б	C	1

Аутомат (2).
Стање	0	1	2	Прихвата
→ D	D	D	Е	0
Е	D	Е	Е	1

Аутомат (3).
Стање	2	3	Прихвата
→ Ф	Ф	Г	1
Г	Г	Ф	0

Решење

Недетерминистички коначни аутомат
Стање	0	1	2	3	Прихвата
→ А, D, Ф	А, D, Ф	C, D, Ф	Е, Ф	Г	1
C, D, Ф	Б, D	C, D, Ф	Е, Ф	Г	1
Е, Ф	D	Е	Е, Ф	Г	1
Г			Г	Ф	0
Б, D	А, D, Ф	Б, D	Е		0
D	D	D	Е		0
Е	D	Е	Е		1
Ф			Ф	Г	1

Детерминистички коначни аутомат
Стање	0	1	2	3	Прихвата
→ С1	С1	С2	С3	С4	1
С2	С5	С2	С3	С4	1
С3	С6	С7	С3	С4	1
С4			С4	С8	0
С5	С1	С5	С7		0
С6	С6	С6	С7		0
С7	С6	С7	С7		1
С8			С8	С4	1

Наведени детерминистички коначни аутомат је већ минималан.

4. задатак

Поставка

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

void insertionSort(int arr[], int n)
{
    int i, key, j;
    i = 1;
    while (i < n)
    {
        key = arr[i];
        j = i-1;
        while (j >= 0 && arr[j] > key)
        {
            arr[j+1] = arr[j];
            j = j-1;
        }
        arr[j+1] = key;
        i++;
    }
}

Решење

Граф тока контроле у четвртом задатку.

5. задатак

Поставка

Дата је следећа граматика:

<С> → <С> , <А>
<С> → 1 <А>
<А> → ( <С> )
<А> → 0
<А> → ε

Конструисати карактеристични ЛР(0) аутомат за дату граматику и контролну табелу СЛР(1) парсера.
Приказати ЛАЛР(1) предикционе скупове конфигурација у почетном стању ЛР(0) аутомата и свим стањима у која се непосредно прелази из почетног стања.

Решење

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

ФОЛЛОW(<С>) = {─┤, ",", )}
ФОЛЛОW(<А>) = ФОЛЛОW(<С>) = {─┤, ",", )}

Контролна табела СЛР(1) парсера
Стање	,	0	1	(	)	─┤
∇			СХИФТ
1₂	РЕДУЦЕ(5)	СХИФТ		СХИФТ	РЕДУЦЕ(5)	РЕДУЦЕ(5)
<С>_x1	СХИФТ					СХИФТ
,₁	РЕДУЦЕ(5)	СХИФТ		СХИФТ	РЕДУЦЕ(5)	РЕДУЦЕ(5)
(₃			СХИФТ
0₄	РЕДУЦЕ(4)				РЕДУЦЕ(4)	РЕДУЦЕ(4)
<С>_x2	СХИФТ				СХИФТ
)₃	РЕДУЦЕ(3)				РЕДУЦЕ(3)	РЕДУЦЕ(3)
<А>₁	РЕДУЦЕ(1)				РЕДУЦЕ(1)	РЕДУЦЕ(1)
<А>₂	РЕДУЦЕ(2)				РЕДУЦЕ(2)	РЕДУЦЕ(2)
─┤₀						АЦЦЕПТ

6. задатак

Поставка

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

Уколико се врши синтаксно-управљано превођење, приказати изглед табеле симбола у тренутку /*T*/.
Написати комплетан Микројава бајткод превода функције main.

program Ispit
    const int K = 2;
    class C {
        int d;
    {
        int m(int c)
        { return c * d; }
    } }
    class DC extends C {
        int v;
    {
        int m(int q) /*T*/
        { return q + d; }
    } }
{
    void main()
        C c;
    {
        c = new DC;
        c.d = c.m(K);
    }
}

Решење

Табела симбола у шестом задатку.

Превод бајткода функције main може бити:

enter 0, 1
new 12
dup
const_4
putfield 0
store_0
load_0
load_0
const_2
load_0
getfield 0
invokevirtual 'm' -1
putfield 1
exit
return

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

Садржај

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

5. задатак

Поставка

Решење

6. задатак

Поставка

Решење

Мени за навигацију

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

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

5. задатак

Поставка

Решење

6. задатак

Поставка

Решење

Мени за навигацију

Претрага