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

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

Јануарски рок 2021. године одржан је 22. јануара. Поставка рока је доступна са странице предмета.

1. задатак

Поставка

Дат је фрагмет[сиц] граматике једног програмског језика.

  1. <вар_децл> ::= <тyпе> : <ид_лист>
  2. <ид_лист> ::= <ид_лист> , Идент | Идент
  3. <тyпе> ::= инт | цхар
  1. Написати атрибутивну граматику којом се одређује тип за сваки идентификатор у листи (Идент). Јасно назначити који атрибути су синтетизовани, а који наслеђени.
  2. Да ли је добијена граматика С-атрибутивна или L-атрибутивна?
  3. Добијеној атрибутивној граматици (под а) додати неопходне акције које обезбеђују додавање симбола у табелу симбола и постављање њихових типова. За писање акција користити програмски језик Јава и следећи интерфејс табеле симбола.
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;
}

Решење

Атрибут t је у следећој граматици синтетизован, док су атрибути type и idtype наслеђени. Испод је приказана граматика са означеним атрибутима и додатим акцијама.

  1. <тyпе>т → инт
    т ← Струцт.Инт
  2. <тyпе>т → цхар
    т ← Струцт.Цхар
  3. <ид_лист>тyпе → <ид_лист>тyпе1, Идентидтyпе {: Таб.инсерт(неw Обј(Обј.Вар, идент, неw Струцт(тyпе))); :}
    идтyпе ← тyпе
    тyпе1 ← тyпе
  4. <ид_лист>тyпе → Идентидтyпе {: Таб.инсерт(неw Обј(Обј.Вар, идент, неw Струцт(тyпе))); :}
    идтyпе ← тyпе
  5. <вар_децл> → <тyпе>т : <ид_лист>тyпе
    тyпе ← т

Добијена граматика је L-атрибутивна, али није С-атрибутивна.

2. задатак

Поставка

За све секвенце облика ак(бц)па2п, к ≥ 0, п > 0

  1. Написати граматику која описује дате секвенце.
  2. Приказати потисни аутомат којим се препознаје искључиво дати скуп секвенци.

Решење

Граматика која описује дате секвенце би била:

  1. <С> → <А> <Б>
  2. <А> → ε
  3. <А> → <А> а
  4. <Б> → бц <Б> аа
  5. <Б> → бцаа
Стање С1 потисног аутомата за описивање секвенци из другог задатка.
Стање а б ц ─┤
∇ АДВАНЦЕ
  • ПУСХ(А)
  • АДВАНЦЕ
 РЕЈЕЦТ РЕЈЕЦТ
А РЕЈЕЦТ РЕЈЕЦТ
  • ПУСХ(Б)
  • АДВАНЦЕ
 РЕЈЕЦТ
Б СТАТЕ(С2) ПУСХ(А) РЕЈЕЦТ РЕЈЕЦТ
Стање С2 потисног аутомата за описивање секвенци из другог задатка.
Стање а б ц ─┤
∇ РЕЈЕЦТ РЕЈЕЦТ РЕЈЕЦТ АЦЦЕПТ
А
  • ПОП
  • АДВАНЦЕ
 РЕЈЕЦТ РЕЈЕЦТ РЕЈЕЦТ
Б
  • ПОП
  • АДВАНЦЕ
 РЕЈЕЦТ РЕЈЕЦТ РЕЈЕЦТ

3. задатак

Поставка

Формирати парсер на принципу рекурзивног спуста који препознаје скуп секвенци представљених следећим продукцијама.

  1. <С’> → <С> ─┤
  2. <С> → <А> а <Б>
  3. <А> → а б <Б> б
  4. <Б> → <C> а
  5. <Б> → <D> <C> а
  6. <Б> → ε
  7. <C> → ц <C>
  8. <C> → ε
  9. <D> → д

Решење

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. задатак

Поставка

  1. Дат је листинг програма написаног на програмском језику Микројава. Све методе унутрашњих класа су виртуелне. Глобалне методе се позивају статички. Написати комплетан Микројава бајткод превода датог програма. За сваку линију кода јасно назначити који део бајткода се односи на њу.
  2. Одредити део кода који се налази на месту коментара у датом програму, а коме одговара дати Микројава бајткод.
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

Решење

Преведени бајткод може да изгледа овако: 

enter 1 2       # void m(CL arg) int y; {
load_1          # if (
const_3
jge 8           # y >= K
load_1
const_0
jne 20          # y == 0)
getstatic 0     # global.p++;
getfield 1
const_1
add
getstatic 0
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

Линија кода која фали у програму је: 

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

5. задатак

Поставка

Дат је следећи фрагмент (базични блок) међукода:

  1. x = 2
  2. з = x + 3
  3. y = з – x
  4. x = y
  5. з = x + y
  6. x = з – y
  7. з = y – x
  1. За сваку инструкцију у коду одредити које су променљиве живе.
  2. Коришћењем алгоритма гетрег генерисати машински код за 80x86 архитектуру на основу датог међукода и информација из тачке а). Претпоставити да се користе двоадресне машинске инструкције где је први операнд одредиште операције (облика АДД дст, срц) и да се користе само два регистра АX и БX. Решење ЧИТКО уписати у дату табелу.

Решење

Табела са траженим информацијама из задатка.
Редни број Улаз Живот и следећа употреба Дескриптори гетрег Генерисани код
x y з АX БX
1. x = 2 ж2 м- м- x - АX МОВ АX, 2
2. з = x + 3 ж3 м- ж3 x з БX МОВ БX, АX; АДД БX, 2
3. y = з - x м- ж4 м- x y БX СУБ БX, АX
4. x = y ж5 ж5 м- x y АX МОВ АX, БX
5. з = x + y м- ж6 ж6 з y АX АДД АX, БX
6. x = з - y ж7 ж7 м- x y АX СУБ АX, БX
7. з = y - x ж- ж- ж- x з БX МОВ y, БX; СУБ БX, АX
МОВ x, АX; МОВ з, БX
Преузето из „https://siwiki.rs/w/index.php?title=Програмски_преводиоци_1/Јануар_2021&oldid=6365”