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

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

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

1. zadatak

Postavka

Dat je fragmet[sic] gramatike jednog programskog jezika.

  1. <var_decl> ::= <type> : <id_list>
  2. <id_list> ::= <id_list> , Ident | Ident
  3. <type> ::= int | char
  1. Napisati atributivnu gramatiku kojom se određuje tip za svaki identifikator u listi (Ident). Jasno naznačiti koji atributi su sintetizovani, a koji nasleđeni.
  2. Da li je dobijena gramatika S-atributivna ili L-atributivna?
  3. Dobijenoj atributivnoj gramatici (pod a) dodati neophodne akcije koje obezbeđuju dodavanje simbola u tabelu simbola i postavljanje njihovih tipova. Za pisanje akcija koristiti programski jezik Java i sledeći interfejs tabele simbola.
class Struct {
    static final int None = 0, Int = 1, Char = 2, Arr = 3, Class = 4;
    int kind; // None, Int, Char, Arr, Class
    boolean equals (Struct other);
}
class Tab {
    Obj insert (String name, Struct type) throws AlreadyDeclaredException;
    Obj findSymbol (String name) throws SymbolNotFoundException;
}
public class Obj {
    public static final int Con = 0, Var = 1, Type = 2, Prog = 5;
    public int kind; // Con, Var, Type, Meth, Fld, Prog
    public String name;
    public Struct type;
}

Rešenje

Atribut t je u sledećoj gramatici sintetizovan, dok su atributi type i idtype nasleđeni. Ispod je prikazana gramatika sa označenim atributima i dodatim akcijama.

  1. <type>t → int
    t ← Struct.Int
  2. <type>t → char
    t ← Struct.Char
  3. <id_list>type → <id_list>type1, Identidtype {: Tab.insert(new Obj(Obj.Var, ident, new Struct(type))); :}
    idtype ← type
    type1 ← type
  4. <id_list>type → Identidtype {: Tab.insert(new Obj(Obj.Var, ident, new Struct(type))); :}
    idtype ← type
  5. <var_decl> → <type>t : <id_list>type
    type ← t

Dobijena gramatika je L-atributivna, ali nije S-atributivna.

2. zadatak

Postavka

Za sve sekvence oblika ak(bc)pa2p, k ≥ 0, p > 0

  1. Napisati gramatiku koja opisuje date sekvence.
  2. Prikazati potisni automat kojim se prepoznaje isključivo dati skup sekvenci.

Rešenje

Gramatika koja opisuje date sekvence bi bila:

  1. <S> → <A> <B>
  2. <A> → ε
  3. <A> → <A> a
  4. <B> → bc <B> aa
  5. <B> → bcaa
Stanje S1 potisnog automata za opisivanje sekvenci iz drugog zadatka.
Stanje a b c ─┤
∇ ADVANCE
  • PUSH(A)
  • ADVANCE
 REJECT REJECT
A REJECT REJECT
  • PUSH(B)
  • ADVANCE
 REJECT
B STATE(S2)
  • PUSH(A)
  • ADVANCE
 REJECT REJECT
Stanje S2 potisnog automata za opisivanje sekvenci iz drugog zadatka.
Stanje a b c ─┤
∇ REJECT REJECT REJECT ACCEPT
A
  • POP
  • ADVANCE
 REJECT REJECT REJECT
B
  • POP
  • ADVANCE
 REJECT REJECT REJECT

3. zadatak

Postavka

Formirati parser na principu rekurzivnog spusta koji prepoznaje skup sekvenci predstavljenih sledećim produkcijama.

  1. <S’> → <S> ─┤
  2. <S> → <A> a <B>
  3. <A> → a b <B> b
  4. <B> → <C> a
  5. <B> → <D> <C> a
  6. <B> → ε
  7. <C> → c <C>
  8. <C> → ε
  9. <D> → d

Rešenje

char input;

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

void A() {
    terminal('a');
    terminal('b');
    B();
    terminal('b');
}

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

void D() {
    terminal('d');
}

void B() {
    switch (input) {
        case 'a':
        case 'c':
            C();
            terminal('a');
            break;
        case 'd':
            D();
            C();
            terminal('a');
            break;
        case 'b':
        case EOF:
            break;
        default:
            reject();
    }
}

void S() {
    A();
    terminal('a');
    B();
}

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

4. zadatak

Postavka

  1. Dat je listing programa napisanog na programskom jeziku Mikrojava. Sve metode unutrašnjih klasa su virtuelne. Globalne metode se pozivaju statički. Napisati kompletan Mikrojava bajtkod prevoda datog programa. Za svaku liniju koda jasno naznačiti koji deo bajtkoda se odnosi na nju.
  2. Odrediti deo koda koji se nalazi na mestu komentara u datom programu, a kome odgovara dati Mikrojava bajtkod.
program Januar2021
const int K = 3;
class CL { int p; }
CL global;
{
 void m(CL arg)
     int y;
 {
     if(y >= K || y == 0)
         global.p++;
     else arg.p = K;
 }
 void main()
     int x; int arr[];
 {
     global = new CL;
     arr = new int[3];
     arr[K-2] = -arr[x];
     m(global);
     /* ??? */
 }
}

getstatic 0
const_2
load_0
load_1
const_0
aload
mul
add
putfield 1

Rešenje

Prevedeni bajtkod može da izgleda ovako: 

enter 1 2       # void m(CL arg) int y; {
load_1          # if (
const_3
jge 8           # y >= K
load_1
const_0
jne 18          # y == 0)
getstatic 0     # global.p++;
dup
getfield 1
const_1
add
putfield 1
jmp 8           # else
load_0          # arg.p = K;
const_3
putfield 1
exit            # }
return
enter 0 2       # void main() int x; int arr[]; {
new 8           # global = new CL;
putstatic 0
const_3         # arr = new int[3];
newarray 1
store_1
load_1          # arr[K-2] = -arr[x];
const_3
const_2
sub
load_1
load_0
aload
neg
astore
getstatic 0     # m(global);
call ??? (=m)   # Verovatno nisu tražili tačan pomeraj?
exit            # }
return

Linija koda koja fali u programu je: 

global.p = 2 + x * arr[0];

5. zadatak

Postavka

Dat je sledeći fragment (bazični blok) međukoda:

  1. x = 2
  2. z = x + 3
  3. y = z – x
  4. x = y
  5. z = x + y
  6. x = z – y
  7. z = y – x
  1. Za svaku instrukciju u kodu odrediti koje su promenljive žive.
  2. Korišćenjem algoritma getreg generisati mašinski kod za 80x86 arhitekturu na osnovu datog međukoda i informacija iz tačke a). Pretpostaviti da se koriste dvoadresne mašinske instrukcije gde je prvi operand odredište operacije (oblika ADD dst, src) i da se koriste samo dva registra AX i BX. Rešenje ČITKO upisati u datu tabelu.

Rešenje

Tabela sa traženim informacijama iz zadatka.
Redni broj Ulaz Život i sledeća upotreba Deskriptori getreg Generisani kod
x y z AX BX
1. x = 2 ž2 m- m- x - AX MOV AX, 2
2. z = x + 3 ž3 m- ž3 x z BX MOV BX, AX; ADD BX, 3
3. y = z - x m- ž4 m- x y BX SUB BX, AX
4. x = y ž5 ž5 m- x y AX MOV AX, BX
5. z = x + y m- ž6 ž6 z y AX ADD AX, BX
6. x = z - y ž7 ž7 m- x y AX SUB AX, BX
7. z = y - x ž- ž- ž- x z BX MOV y, BX; SUB BX, AX
MOV x, AX; MOV z, BX
Преузето из „https://siwiki.rs/w/index.php?title=Програмски_преводиоци_1/Јануар_2021&oldid=6369”