Programski prevodioci 1/Januar 2020

Januarski rok 2021. godine održan je 22. januara. Postavka roka je dostupna sa stranice predmeta.

1. zadatak

Postavka

Data gramatika opisuje regularne izraze sa operatorima konkatenacije ● i unije |.

<E> → <E> | <T>
<E> → <T>
<T> → <T> ●
<T> →
→ slovo
→ epsilon

Konstruisati SLR(1) parser za datu gramatiku.
Dopuniti datu gramatiku S-atributivnim pravilima tako da svaki neterminal date gramatike poseduje atribute koji predstavljaju vrednosti funkcija poništiv i prva_pozicija iz algoritma za konstrukciju determinističkog konačnog automata iz regularnog izraza. Terminal slovo poseduje atribut koji označava poziciju tog terminala u izrazu. Napomena: epsilon je terminal, a ne oznaka prazne sekvence. Takođe su | i ● terminalni simboli.

Rešenje

Automat iz prvog zadatka pod a.

Relevantni FIRST i FOLLOW skupovi SLR(1) parsera su:

FOLLOW(<E>) = {|, ─┤}
FOLLOW(<T>) = {●} ∪ FOLLOW(<E>) = {●, |, ─┤}
FOLLOW() = FOLLOW(<T>) = {●, |, ─┤}

Potisna tabela SLR(1) parsera
Stanje	<E>	<T>	<P>	slovo	epsilon	●	\|	─┤
∇	<E>_x	<T>_x1	<P>₄	slovo₅	epsilon₆
<T>_x1						●₃
<E>_x							\|₁	─┤₀
<P>₄
slovo₅
epsilon₆
●₃			<P>₃	slovo₅	epsilon₆
\|₁		<T>_x2	<P>₄	slovo₅	epsilon₆
─┤₀
<P>₃
<T>_x2						●₃

Kontrolna tabela SLR(1) parsera
Stanje	slovo	epsilon	●	\|	─┤
∇	SHIFT	SHIFT
<T>_x1			SHIFT	REDUCE(2)	REDUCE(2)
<E>_x				SHIFT	SHIFT
<P>₄			REDUCE(4)	REDUCE(4)	REDUCE(4)
slovo₅			REDUCE(5)	REDUCE(5)	REDUCE(5)
epsilon₆			REDUCE(6)	REDUCE(6)	REDUCE(6)
●₃	SHIFT	SHIFT
\|₁	SHIFT	SHIFT
─┤₀					ACCEPT
<P>₃			REDUCE(3)	REDUCE(3)	REDUCE(3)
<T>_x2			SHIFT	REDUCE(1)	REDUCE(1)

Dopunjena gramatika sa atributima izgleda:

<E>_pon,prva → <E>_{pon₁,prva₁} | <T>_{pon₂,prva₂}
$pon \larr pon_1 or pon_2$

$prva \larr \{prva_1, prva_2\}$
<E>_pon,prva → <T>_{pon₁,prva₁}
$pon \larr pon_1$

$prva \larr prva_1$
<T>_pon,prva → <T>_{pon₁,prva₁} ● _{pon₂,prva₂}
$pon \larr pon_1 and pon_2$

$prva \larr pon_1 ? \{prva_1, prva_2\} : prva_1$
<T>_pon,prva → _{pon₁,prva₁}
$pon \larr pon_1$

$prva \larr prva_1$
_pon,prva → slovo_poz
$pon \larr 0$

$prva \larr poz$
_pon,prva → epsilon
$pon \larr 1$

2. zadatak

Postavka

U standardnoj Mikrojavi, lokalno definisana promenljiva sakriva globalnu promenljivu sa istim imenom. Želimo da uvedemo sledeću modifikaciju: Ako se želi pristupiti sakrivenoj globalnoj promenljivoj, mora se ispred imena navesti operator ::.

Na primer:

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

Promeniti Mikrojava gramatiku da se dodaju opisane mogućnosti (relevantan deo gramatike dat je u prilogu u EBNF notaciji). Jasno označiti šta je promenjeno.
Dodati u mikrojava tabelu simbola metod find_hidden(String name) koji se poziva za traženje imena pod dejstvom operatora ::. Navesti kompletnu implementaciju ovog metoda. U prilogu je (na sledećoj strani) kao podsetnik dat deo postojeće implementacije klase Tab.
Gde u Mikrojava kompajleru treba ugraditi poziv metoda find_hidden?

Mikrojava gramatika:

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 := "*" | "/" | "%".

Implementacija klase 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;
    }
}

Rešenje

U gramatici je potrebno izmeniti sledeću smenu:

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

Metoda find_hidden koja pronalazi promenljive iz globalnog dosega programa može da izgleda ovako:

    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;
    }

U Mikrojava kompajleru poziv ove metode treba ugraditi tokom semantičke analize, kako bi se odgovarajućem čvoru u apstraktnom sintaksnom stablu dodelio simbol koji odgovara promenljivoj iz globalnog opsega.

3. zadatak

Postavka

Rešenje

Nedeterministički konačni automat sa dešifrovanim stanjima.
Stanje	a	b	c	Prihvata
→ A	A		C	0
B	B, C	D		0
C	A		D	1
D		B, C		0

Deterministički konačni automat sa dešifrovanim stanjima
Stanje	a	b	c	Prihvata
→ A, B	A, B, C	D	C	0
A, B, C	A, B, C	D	C, D	1
D		B, C		0
C	A		D	1
C, D	A	B, C	D	1
B, C	A, B, C	D	D	1
A	A		C	0

4. zadatak

Postavka

Data je gramatika:

<S> → a <S> b
<S> → b <S> c
<S> → bc
<S> → <S> a

Transformisati gramatiku u LL(1) i odrediti SELECT skupove tako dobijene gramatike.
Konstruisati parser na bazi rekurzivnog spusta za gramatiku dobijenu u tački a).

Rešenje

Transformisana gramatika može izgledati ovako:

<S> → a <S> b <S''>
SELECT(1) = {a}
<S> → b <S'> c <S''>
SELECT(2) = {b}
<S'> → <S>
SELECT(3) = {a, b}
<S'> → ε
SELECT(3) = {c}
<S''> → a <S''>
SELECT(4) = {a}
<S''> → ε
SELECT(5) = {c, ─┤}

Parser na bazi rekurzivnog spusta na gornju gramatiku izgleda ovako:

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. zadatak

Postavka

Dat je sledeći deo program na jeziku sličnom Pascal-u:

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;

Ako je statičko okruženje za nelokalne promenljive realizovano preko pristupnih veza, nacrtati izgled steka nakon izvršavanja naredbe y := x + z; iz procedure proc2.
Napisati 80x86 asemblerski kod za naredbu y := x + z; iz procedure proc2.

Rešenje

Stek iz petog zadatka pod a.

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

6. zadatak

Postavka

Za dati programski fragment:

Napisati odgovarajući međukod i graf toka kontrole na nivou osnovnih blokova.
Napisati međukod u SSA formi.

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;

Rešenje

Graf iz šestog zadatka pod a.

Međukod:

x1 := 1
y1 := 0
z1 := 0
x2 := 2
t1 := Ф(y1, y2)
if t1 <= z goto 22
t2 := Ф(x2, x3, x4)
t3 := t2 - 2
if t3 <= t1 goto 13
t4 := t1 - 1
x3 := t4
goto 18
if t2 <= t1 goto 17
t5 := z1 - 1
x4 := t3
goto 18
goto 22
t6 := Ф(x3, x4)
t7 := t6 * 2
y2 := t7
goto 5
t8 := t1 + z1
x5 := t8

Programski prevodioci 1/Januar 2020

Sadržaj

1. zadatak

Postavka

Rešenje

2. zadatak

Postavka

Rešenje

3. zadatak

Postavka

Rešenje

4. zadatak

Postavka

Rešenje

5. zadatak

Postavka

Rešenje

6. zadatak

Postavka

Rešenje

Meni za navigaciju

Programski prevodioci 1/Januar 2020

1. zadatak

Postavka

Rešenje

2. zadatak

Postavka

Rešenje

3. zadatak

Postavka

Rešenje

4. zadatak

Postavka

Rešenje

5. zadatak

Postavka

Rešenje

6. zadatak

Postavka

Rešenje

Meni za navigaciju

Pretraga