Програмски преводиоци 1/Септембар 2023
Пређи на навигацију
Пређи на претрагу
- Овај рок није решен. Помозите СИ Wики тако што ћете га решити.
Испит у септембарском року 2023. године одржан је 16. Септембра.
1. задатак
Поставка
(10п) Дат је део имплементације класе Ноде у програмском језику Јава, која представља чвор у синтаксном стаблу изгенерисаном за конструкцију ДКА коришћењем метода позиције, где су објашњења поља и метода дата у коментарима изнад њих (сва поља су иницијализована конструктором):
public class Node {
private enum Type {
ASTERISK, // *
PLUS, // +
PERIOD, // .
OR, // |
SYMBOL, // s
EPSILON // ε
}
// left subtree of position node, null if leaf (symbol) node
private Node left;
// right subtree of position node, null if unary operation or leaf (symbol) node
private Node right;
// type of position node
private Type type;
// position of symbol in regex, only valid for leaf (symbol) nodes, otherwise set to -1
private int symbolPos;
// check whether the subsequence with the given node as root of the subtree can be empty
public boolean isNullable();
// find sert of leaf (symbol) node positions which could be at the beginning of
// subsequence with the given node as root of the subtree
public Set<Integer> firstPos();
// find set of leaf (symbol) node positions which could be at the end of
// subsequence with the given node as root of the subtree
public Set<Integer> lastPos();
// returns a union of the two parameters
public static Set<Integer> union(Set<Integer> first, Set<Integer> second);
}
Потребно је написати имплементацију метода firstPos() и lastPos()
1а. задатак
Идентичан овакав задатак (за исти број поена) се појавио у Августу 2023, само се тражила имплементација isNullable().
Решење
public Set<Integer> firstPos() {
Set<Integer> ret = new HashSet<Integer>();
switch (this.type) {
case 'SYMBOL':
ret.add(this.symbolPos);
break;
case 'ASTERISK':
return this.left.firstPos();
case 'OR':
for (Integer pos : this.left.firstPos()) {
ret.add(pos);
}
for (Integer pos : this.right.firstPos()) {
ret.add(pos);
}
break;
case 'PERIOD':
for (Integer pos : this.left.firstPos()) {
ret.add(pos);
}
if (this.left.isNullable()) {
for (Integer pos : this.right.firstPos()) {
ret.add(pos);
}
}
break;
default:
break;
}
return ret;
}
public Set<Integer> lastPos() {
Set<Integer> ret = new HashSet<Integer>();
switch (this.type) {
case 'SYMBOL':
ret.add(this.symbolPos);
break;
case 'ASTERISK':
return this.left.lastPos();
case 'OR':
for (Integer pos : this.left.lastPos()) {
ret.add(pos);
}
for (Integer pos : this.right.lastPos()) {
ret.add(pos);
}
break;
case 'PERIOD':
for (Integer pos : this.right.lastPos()) {
ret.add(pos);
}
if (this.right.isNullable()) {
for (Integer pos : this.left.lastPos()) {
ret.add(pos);
}
}
break;
default:
break;
}
return ret;
}
public boolean isNullable(){
switch(this.type){
case 'SYMBOL':
return false;
case 'EPSILON':
case 'ASTERISK':
return true;
case 'PERIOD':
return this.left.isNullable() && this.right.isNullable();
case 'OR':
return this.left.isNullable() || this.right.isNullable();
default: return false;
}
}
2. задатак
Поставка
(10п) За рекурзивни спуст који описује наведену граматику, који су описани испод:
- Допунити делове рекурзивног спуста обележених са лабелама ПН (Н означава лабелу која се може попунити и може представљати једну или више линија кода), уколико је познато да се секвенце аадддбб, дд и аб прихватају.
- Написати ЛЛ(1) граматику описану рекурзивним спустом.
Glavni program:
IN = NEXTCHAR();
call PROCS;
if (INP<> '˧')
then REJECT;
else ACCEPT;
end if;
end;
procedure PROCS:
case IN of
'a': goto P1;
'd', 'b', '˧': goto P2;
default: REJECT;
end case;
P1: /* ... */
P2: /* ... */
end procedure;
procedure PROCA:
case IN of
'b', '˧': goto P3;
'd': goto P4;
default: REJECT;
end case;
P3: /* ... */
P4: /* ... */
end procedure;
3. задатак
Поставка
(10п) За дати Микројава бајткод:
- Навести излаз програма.
- Реконструисати изворни Микројава код на основу датог бајткода.
0: enter 2 2 3: load_0 4: load_1 5: mul 6: jmp 3 (=9) 9: exit 10: return 11: enter 2 3 14: const_0 15: store_2 16: load_2 17: load_1 18: jge 21 (=39) 21: load_0 22: load_2 23: aload 24: const_0 25: print 26: const 32 31: const_0 32: bprint 33: inc 2,1 36: jmp -20 (=16) 39: const 10 44: const_0 45: bprint 46: exit 47: return 48: enter 0 5 51: const_0 52: store_0 53: const 10 58: newarray 1 60: store_1 61: const 10 66: newarray 1 68: store_2 69: load_0 70: const 10 75: jge 74 (=149) 78: load_1 79: load_0 80: load_0 81: const 10 86: mul 87: load_0 88: const_3 89: rem 90: add 91: astore 92: load_0 93: const_2 94: rem 95: const_1 96: jne 12 (=108) 99: load_1 100: load_0 101: const_1 102: neg 103: load_1 104: load_0 105: aload 106: mul 107: astore 108: load_1 109: load_0 110: aload 111: const_2 112: call -112 (=0) 115: store_3 116: load_1 117: load_0 118: aload 119: const_3 120: call -120 (=0) 123: store 4 125: load_3 126: load 4 128: jle 10 (=138) 131: load_2 132: load_0 133: load_3 134: astore 135: jmp 8 (=143) 138: load_2 139: load_0 140: load 4 142: astore 143: inc 0,1 146: jmp -77 (=69) 149: load_1 150: const 10 155: call -144 (=11) 158: load_2 159: const 10 164: call -153 (=11) 167: exit 168: return
4. задатак
Поставка
(10п) За дату граматику конструисати:
- ЛР(0) карактеристични аутомат
- ЛАЛР(1) карактеристични аутомат
- За оба случаја ЛР(0) и ЛАЛР(1) навести стања са по једним конфликтом и објаснити о ком се конфликту ради, у случају да конфликт постоји. Није потребно конструисати табеле парсера.
Оба аутомата приказати у виду графа прелаза, унутар стања написати конфигурације.
<S> → ( <X> )<S> → [ <X> ]<S> → ( <Y> ]<S> → [ <Y> )<X> → a<Y> → a
5. задатак
Поставка
(10п) Нацртати граф меморијске представе објеката ц, д1 и д2:
class A { int x; }
class B { int y; }
class C extends A, B { int z; }
class D extends B, C { int v; }
C c; D d1, d2;
- Ако је дозвољен неискоришћен простор на нивоу објеката.
- Ако неискоришћен простор може да постоји само на нивоу класе, а не и објеката
6. задатак
Поставка
(10п) Дат је следећи програм на језику сличном Пасцалу. Статичко окружење за нелокалне променљиве је реализовано помоћу приступних веза. Главни програм поседује сопствени акциони запис на стеку.
- Приказати јасно и прецизно изглед стека позива непосредно пре повратка из процедуре ц. Водити рачуна о формату активационих записа
- Написати комплетан 80x86 асемблерски код који би компајлер изгенерисао за процедуре ц и д (ентер и леаве инструкције не постоје)
program Sep23 (output);
var g, t: integer
procedure b(p: integer)
var m: integer;
procedure c ()
begin
g := m+t;
end; {c}
procedure d (p: integer)
t := p+2;
c();
end {d}
begin
m := p+1;
d(m);
end; {b}
begin
g := 1
b(g);
end. {Sep23}