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

Јануарски рок 2021. године одржан је 22. јануара. Поставка рока је доступна са странице предмета.

1. задатак

Поставка

Дата граматика описује регуларне изразе са операторима конкатенације ● и уније |.

<Е> → <Е> | <Т>
<Е> → <Т>
<Т> → <Т> ● <П>
<Т> → <П>
<П> → слово
<П> → епсилон

Конструисати СЛР(1) парсер за дату граматику.
Допунити дату граматику С-атрибутивним правилима тако да сваки нетерминал дате граматике поседује атрибуте који представљају вредности функција поништив и прва_позиција из алгоритма за конструкцију детерминистичког коначног аутомата из регуларног израза. Терминал slovo поседује атрибут који означава позицију тог терминала у изразу. Напомена: epsilon је терминал, а не ознака празне секвенце. Такође су | и ● терминални симболи.

Решење

Аутомат из првог задатка под а.

Релевантни ФИРСТ и ФОЛЛОW скупови СЛР(1) парсера су:

ФОЛЛОW(<Е>) = {|, ─┤}
ФОЛЛОW(<Т>) = {●} ∪ ФОЛЛОW(<Е>) = {●, |, ─┤}
ФОЛЛОW(<П>) = ФОЛЛОW(<Т>) = {●, |, ─┤}

Потисна табела СЛР(1) парсера
Стање	<Е>	<Т>	<П>	слово	епсилон	●	\|	─┤
∇	<Е>_x	<Т>_x1	<П>₄	слово₅	епсилон₆
<Т>_x1						●₃
<Е>_x							\|₁	─┤₀
<П>₄
слово₅
епсилон₆
●₃			<П>₃	слово₅	епсилон₆
\|₁		<Т>_x2	<П>₄	слово₅	епсилон₆
─┤₀
<П>₃
<Т>_x2						●₃

Контролна табела СЛР(1) парсера
Стање	слово	епсилон	●	\|	─┤
∇	СХИФТ	СХИФТ
<Т>_x1			СХИФТ	РЕДУЦЕ(2)	РЕДУЦЕ(2)
<Е>_x				СХИФТ	СХИФТ
<П>₄			РЕДУЦЕ(4)	РЕДУЦЕ(4)	РЕДУЦЕ(4)
слово₅			РЕДУЦЕ(5)	РЕДУЦЕ(5)	РЕДУЦЕ(5)
епсилон₆			РЕДУЦЕ(6)	РЕДУЦЕ(6)	РЕДУЦЕ(6)
●₃	СХИФТ	СХИФТ
\|₁	СХИФТ	СХИФТ
─┤₀					АЦЦЕПТ
<П>₃			РЕДУЦЕ(3)	РЕДУЦЕ(3)	РЕДУЦЕ(3)
<Т>_x2			СХИФТ	РЕДУЦЕ(1)	РЕДУЦЕ(1)

Допуњена граматика са атрибутима изгледа:

<Е>_{пон,прва} → <Е>_{пон₁,прва₁} | <Т>_{пон₂,прва₂}
$pon \larr pon_1 or pon_2$

$prva \larr \{prva_1, prva_2\}$
<Е>_{пон,прва} → <Т>_{пон₁,прва₁}
$pon \larr pon_1$

$prva \larr prva_1$
<Т>_{пон,прва} → <Т>_{пон₁,прва₁} ● <П>_{пон₂,прва₂}
$pon \larr pon_1 and pon_2$

$prva \larr pon_1 ? \{prva_1, prva_2\} : prva_1$
<Т>_{пон,прва} → <П>_{пон₁,прва₁}
$pon \larr pon_1$

$prva \larr prva_1$
<П>_{пон,прва} → слово_поз
$pon \larr 0$

$prva \larr poz$
<П>_{пон,прва} → епсилон
$pon \larr 1$

2. задатак

Поставка

У стандардној Микројави, локално дефинисана променљива сакрива глобалну променљиву са истим именом. Желимо да уведемо следећу модификацију: Ако се жели приступити сакривеној глобалној променљивој, мора се испред имена навести оператор ::.

На пример:

program P {
    int X[];
    void main() int X; { ::X = new int[5]; X = ::X[0];}
}

Променити Микројава граматику да се додају описане могућности (релевантан део граматике дат је у прилогу у ЕБНФ нотацији). Јасно означити шта је промењено.
Додати у микројава табелу симбола метод финд_хидден(Стринг наме) који се позива за тражење имена под дејством оператора ::. Навести комплетну имплементацију овог метода. У прилогу је (на следећој страни) као подсетник дат део постојеће имплементације класе Tab.
Где у Микројава компајлеру треба уградити позив метода find_hidden?

Микројава граматика:

DesignatorStatement := Designator "=" Expr.
DesignatorStatement := Designator "++".
DesignatorStatement := Designator "--".
Statement := DesignatorStatement ";".
Statement := "read" "(" Designator ")" ";".
Statement := "print" "(" Expr [“,” number] ")" ";".
Expr := ["‐"] Term {Addop Term}.
Term := Factor {Mulop Factor}.
Factor := numConst | charConst | "(" Expr ")" | boolConst | "new" Type [ "[" Expr "]" ].
Factor := Designator [ "(" ")" ].
Designator := ident ["[" Expr "]" ].
Addop := "+" | "‐" .
Mulop := "*" | "/" | "%".

Имплементација класе Tab:

public class Tab {
    public static final Struct
        noType = new Struct(Struct.None),
        intType = new Struct(Struct.Int),
        charType = new Struct(Struct.Char),
        nullType = new Struct(Struct.Class);
    public static final Obj noObj = new Obj(Obj.Var, "noObj", noType);
    public static Obj chrObj, ordObj, lenObj;
    public static Scope currentScope; //tekuci opseg
    private static int currentLevel; //nivo ugnezdavanja tekuceg opsega
    public static void init() {
        Scope universe = currentScope = new Scope(null);
        . . . . .
        currentLevel = -1;
    }
    public static void openScope() {
        currentScope = new Scope(currentScope);
        currentLevel++;
    }
    public static void closeScope() {
        currentScope = currentScope.getOuter();
        currentLevel--;
    }
    public static Obj insert(int kind, String name, Struct type) {
        Obj newObj=new Obj(kind,name,type,0,((currentLevel!=0)?1:0));
        . . . . .
    }
    public static Obj find(String name) {
        Obj resultObj = null;
        for (Scope s = currentScope; s != null; s = s.getOuter()) {
            if (s.getLocals() != null) {
                resultObj = s.getLocals().searchKey(name);
                if (resultObj != null) break;
            }
        }
        return (resultObj != null) ? resultObj : noObj;
    }
    public static Scope currentScope() {
        return currentScope;
    }
}

Решење

У граматици је потребно изменити следећу смену:

Designator := ["::"] ident ["[" Expr "]" ].

Метода find_hidden која проналази променљиве из глобалног досега програма може да изгледа овако:

    public static Obj find_hidden(String name) {
        Scope scope = currentScope;
        for (int level = currentLevel; level > 0; --level) {
            scope = scope.getOuter();
        }
        Obj resultObj = null;
        if (scope.getLocals() != null) {
            resultObj = scope.getLocals().searchKey(name);
        }
        return (resultObj != null) ? resultObj : noObj;
    }

У Микројава компајлеру позив ове методе треба уградити током семантичке анализе, како би се одговарајућем чвору у апстрактном синтаксном стаблу доделио симбол који одговара променљивој из глобалног опсега.

3. задатак

Поставка

Решење

Недетерминистички коначни аутомат са дешифрованим стањима.
Стање	а	б	ц	Прихвата
→ А	А		C	0
Б	Б, C	D		0
C	А		D	1
D		Б, C		0

Детерминистички коначни аутомат са дешифрованим стањима
Стање	а	б	ц	Прихвата
→ А, Б	А, Б, C	D	C	0
А, Б, C	А, Б, C	D	C, D	1
D		Б, C		0
C	А		D	1
C, D	А	Б, C	D	1
Б, C	А, Б, C	D	D	1
А	А		C	0

4. задатак

Поставка

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

<С> → а <С> б
<С> → б <С> ц
<С> → бц
<С> → <С> а

Трансформисати граматику у ЛЛ(1) и одредити СЕЛЕЦТ скупове тако добијене граматике.
Конструисати парсер на бази рекурзивног спуста за граматику добијену у тачки а).

Решење

Трансформисана граматика може изгледати овако:

<С> → а <С> б <С''>
СЕЛЕЦТ(1) = {а}
<С> → б <С'> ц <С''>
СЕЛЕЦТ(2) = {б}
<С'> → <С>
СЕЛЕЦТ(3) = {а, б}
<С'> → ε
СЕЛЕЦТ(3) = {ц}
<С''> → а <С''>
СЕЛЕЦТ(4) = {а}
<С''> → ε
СЕЛЕЦТ(5) = {ц, ─┤}

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

char input;

void terminal(char c) {
    if (input == c) {
        input = advance();
    } else {
        reject();
    }
}

void S2() {
    switch (input) {
        case 'a':
            terminal('a');
            S2();
            break;
        case 'c':
        case EOF:
            break;
        default:
            reject();
    }
}

void S();

void S1() {
    switch (input) {
        case 'a':
        case 'b':
            S();
            break;
        case 'c':
            break;
        default:
            reject();
    }
}

void S() {
    switch (input) {
        case 'a':
            terminal('a');
            S();
            terminal('b');
            S2();
            break;
        case 'b':
            terminal('b');
            S1();
            terminal('c');
            S2();
            break;
        default:
            reject();
    }
}

void main() {
    input = advance();
    S();
    terminal(EOF);
}

5. задатак

Поставка

Дат је следећи део програм на језику сличном Пасцал-у:

procedure proc0;
    var x, y: integer;
    procedure proc1(z: integer);
        procedure proc2;
        begin
            y := x + z;
        end;
    begin
        proc2;
    end;
    procedure proc3(z: integer);
        var x: integer;
        procedure proc4;
        begin
            proc1(x);
        end;
    begin
        x := z + 1;
        proc4;
    end;
begin
    x := 5;
    proc3(x);
end;

Ако је статичко окружење за нелокалне променљиве реализовано преко приступних веза, нацртати изглед стека након извршавања наредбе y := x + z; из процедуре proc2.
Написати 80x86 асемблерски код за наредбу y := x + z; из процедуре proc2.

Решење

Стек из петог задатка под а.

MOV DI, [BP+04]
MOV AX, [DI+06]
MOV DI, [DI+04]
MOV BX, [DI-02]
ADD AX, BX
MOV [DI-04], AX

6. задатак

Поставка

За дати програмски фрагмент:

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

x = 1;
y = 0;
z = 0;
for (x = 2; y > z; z = z + 1) {
    if (x - 2 > y) {
        x = y - 1;
    } else if(x > y) {
        x = z - 1;
    } else break;
    y = x * 2;
}
x = y + z;

Решење

Граф из шестог задатка под а.

Међукод:

x1 := 1
y1 := 0
з1 := 0
x2 := 2
т1 := Ф(y1, y2)
иф т1 <= з гото 22
т2 := Ф(x2, x3, x4)
т3 := т2 - 2
иф т3 <= т1 гото 13
т4 := т1 - 1
x3 := т4
гото 18
иф т2 <= т1 гото 17
т5 := з1 - 1
x4 := т3
гото 18
гото 22
т6 := Ф(x3, x4)
т7 := т6 * 2
y2 := т7
гото 5
т8 := т1 + з1
x5 := т8

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

Садржај

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

5. задатак

Поставка

Решење

6. задатак

Поставка

Решење

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

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

1. задатак

Поставка

Решење

2. задатак

Поставка

Решење

3. задатак

Поставка

Решење

4. задатак

Поставка

Решење

5. задатак

Поставка

Решење

6. задатак

Поставка

Решење

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

Претрага