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

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, Ident_idtype {: Tab.insert(new Obj(Obj.Var, ident, new Struct(type))); :}

   idtype ← type

   type₁ ← type

4. <id_list>_type → Ident_idtype {: 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 a^k(bc)^pa^2p, 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