Програмски преводиоци 1/Јануар 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 |.

1. <E> → <E> | <T>
2. <E> → <T>
3. <T> → <T> ● <P>
4. <T> → <P>
5. <P> → slovo
6. <P> → epsilon

1. Konstruisati SLR(1) parser za datu gramatiku.
2. 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(<P>) = FOLLOW(<T>) = {●, |, ─┤}

Potisna tabela SLR(1) parsera

Stanje	<E>	<T>	<P>	slovo	epsilon	●	|	─┤
∇	<E>x	<T>x1 !! <P>4	slovo5	epsilon6
<T>x1						●3
<E>x							|1	─┤0
<P>4
slovo5
epsilon6
●3			<P>3	slovo5	epsilon6
|1		<T>x2	<P>4	slovo5	epsilon6
─┤0
<P>3
<T>x2						●3

Kontrolna tabela SLR(1) parsera

Stanje	slovo	epsilon	●	|	─┤
∇	SHIFT	SHIFT
<T>x1			SHIFT	REDUCE(2)	REDUCE(2)
<E>x				SHIFT	SHIFT
<P>4			REDUCE(4)	REDUCE(4)	REDUCE(4)
slovo5			REDUCE(5)	REDUCE(5)	REDUCE(5)
epsilon6			REDUCE(6)	REDUCE(6)	REDUCE(6)
●3	SHIFT	SHIFT
|1	SHIFT	SHIFT
─┤0					ACCEPT
<P>3			REDUCE(3)	REDUCE(3)	REDUCE(3)
<T>x2			SHIFT	REDUCE(1)	REDUCE(1)

Dopunjena gramatika sa atributima izgleda:

1. <E>_pon,prva → <E>_pon1,prva1 | <T>_pon2,prva2

   $pon \larr pon_1 or pon_2$

   $prva \larr \{prva_1, prva_2\}$

2. <E>_pon,prva → <T>_pon1,prva1

   $pon \larr pon_1$

   $prva \larr prva_1$

3. <T>_pon,prva → <T>_pon1,prva1 ● <P>_pon2,prva2

   $pon \larr pon_1 and pon_2$

   $prva \larr pon_1 ? \{prva_1, prva_2\} : prva_1$

4. <T>_pon,prva → <P>_pon1,prva1

   $pon \larr pon_1$

   $prva \larr prva_1$

5. <P>_pon,prva → slovo_poz

   $pon \larr 0$

   $prva \larr poz$

6. <P>_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];}
}

1. 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.
2. 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.
3. 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;
        for (; s != null; s = s.getOuter()) {
            if (s.getLocals() == null) {
                continue;
            }
            resultObj = s.getLocals().searchKey(name);
            if (resultObj != null) {
                break;
            }
        }
        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

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:

1. <S> → a <S> b
2. <S> → b <S> c
3. <S> → bc
4. <S> → <S> a

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

Rešenje

Transformisana gramatika može izgledati ovako:

1. <S> → a <S> b <S''>

   SELECT(1) = {a}

2. <S> → b <S'> c <S''>

   SELECT(2) = {b}

3. <S'> → <S>

   SELECT(3) = {a, b}

4. <S'> → ε

   SELECT(3) = {c}

5. <S''> → a <S''>

   SELECT(4) = {a}

6. <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;

1. 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.
2. 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+02]
MOV DI, [DI]
MOV BX, [DI-06]
ADD AX, BX
MOV [DI-08], AX

6. zadatak

Postavka

Za dati programski fragment:

1. Napisati odgovarajući međukod i graf toka kontrole na nivou osnovnih blokova.
2. 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:

1. x1 := 1
2. y1 := 0
3. z1 := 0
4. x2 := 2
5. t1 := Ф(y1, y2)
6. if t1 <= z goto 22
7. t2 := Ф(x2, x3, x4)
8. t3 := t2 - 2
9. if t3 <= t1 goto 13
10. t4 := t1 - 1
11. x3 := t4
12. goto 18
13. if t2 <= t1 goto 17
14. t5 := z1 - 1
15. x4 := t3
16. goto 18
17. goto 22
18. t6 := Ф(x3, x4)
19. t7 := t6 * 2
20. y2 := t7
21. goto 5
22. t8 := t1 + z1
23. x5 := t8