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

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу

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
  2. <E>pon,prva → <T>pon1,prva1
  3. <T>pon,prva → <T>pon1,prva1 ● <P>pon2,prva2
  4. <T>pon,prva → <P>pon1,prva1
  5. <P>pon,prva → slovopoz
  6. <P>pon,prva → epsilon

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

  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+06]
MOV DI, [DI+04]
MOV BX, [DI-02]
ADD AX, BX
MOV [DI-04], 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