Програмски преводиоци 1/Јануар 2023
Јануарски испит 2023. године одржан је 19. јануара. Поставка рока је доступна са странице предмета.
1. задатак
Поставка
Дат је следећи програм:
int main() {
int count;
void procX() {
void report() {
writeln("count = " + count);
}
void proxY() {
int count;
count = 200;
report();
}
count = 100;
report();
procY();
}
count = 300;
procX();
}
- Уколико се користи статичко разрешавање досега, шта ће исписати дати програм?
- Уколико се користи динамичко разрешавање досега, шта ће исписати дати програм?
- Уколико се за нелокалне променљиве користе дисплеји, нацртати последње стање стека и дисплеја након што је
reportфункција позвана последњи пут.
Решење
а) Испис:
цоунт = 100
цоунт = 100
Објасњење: Статичко разрешавање значи да веза између имена променљиве и декларације се прави у време превођења (компајлирања).
Дакле, када се репорт компајлира, компајлер већ одлучи: "ово цоунт у репорт се односи на цоунт из процX", јер је то најближи лексички обухватајући опсег.
б) Испис:
цоунт = 100
цоунт = 200
Објасњење: Код динамичког разрешавања, нелокална променљива се тражи преко ланца активационих записа на стеку, почев од најближег позиваоца.
ц)
2. задатак
Поставка
Дат је исечак кода класе Struct. Допунити методу AssignableTo кодом који фали.
public class Struct {
private int kind;
private Struct elemType;
public boolean Equals(Struct other) {
return (this == other) || (kind == Kinds.Array && other.kind == Kinds.Array && elemType.Equals(other.ElemType));
}
public boolean IsRefType() {
return kind == Kinds.Class || kind == Kinds.Array;
}
public boolean AssignableTo(Struct dest) {
if (this.Equals(dest) ||
|| (kind == Kinds.Array && dest.kind == Kinds.Array && dest.elemType == Tab.noType)) {
return true;
}
return false;
}
}
Решење
Преузето из уџбеника Програмски преводиоци 1 (Драган Бојић, Маја Вукасовић) са стране 209.
class Struct {
...
// checks, if this can be assigned to dest (explicit. assignment, parameters)
public bool AssignableTo (Struct dest) {
if ( this.Equals(dest) || this == Tab.nullType && dest.IsRefType() ||
kind == Kinds.Arr && dest.kind == Kinds.Arr && // for len()
dest.elemType == Tab.noType) return true;
for (Struct s = elemType; s != null; s = s.elemType) {
if (s.equals(dest)) return true;
}
return false;
}
}
3. задатак
- Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.
Поставка
За дати блок кода написати међукод а затим нацртати граф тока контроле са међукодом у ССА форми.
int res = 10;
for (int i = 0; i < 10; i++) {
int n = res;
for (int j = i + 1; j < n; j++) {
if ((i + j) % 2 == 0) {
res++;
}
}
}
Решење
4. задатак
Поставка
За дату граматику конструисати карактеристички ЛР(0) аутомат и контролну табелу, а затим додати ЛАЛР(1) предикционе скупове.
- <С> → <С> <А>
- <А> → <А> а <А> б
- <А> → <С> а
- <А> → ц
Решење
Ова поставка задатка је готово сигурно погрешна, јер се у стању празног стека код ЛР(0) парсера не може прећи ни у једно друго стање, а не може ни да се уради Редуце. Такође, нејасно је какве улазне секвенце прихвата/одбија оваква граматика јер се оне не могу ни генерисати због тога што једина смена за стартни нетерминал < С > садржи леву рекурзију, па је тако једина могућа секвенца она у којој се < С > непрестано додаје на почетак.
5. задатак
Поставка
У датој граматици нетерминалу <list> додати синтетизовани атрибут који наизменично садржи цифре највећих и најмањих бројева из низа. На пример, уколико је секвенца која се препознаје [1, 2, 3] [4, 5, 6] [7, 8, 9], тај атрибут би имао вредност 349. Сматрати да терминал INT има синтетизовани симбол са својом вредношћу.
- <лист> → <лист> <итем>
- <лист> → <итем>
- <итем> → [ <нум_арр> ]
- <нум_арр> → <нум_арр>, ИНТ
- <нум_арр> → ИНТ
Решење
Уводимо следеће синтетизоване атрибуте:
- ИНТдигит - дигит представља цифру описану терминалом ИНТ
- <нум_арр>минДигит, маxДигит - минДигит представља минималну цифру садржану у низу цифара <нум_арр>, а маxДигит максималну цифру садржану у низу цифара <нум_арр>
- <итем>минДигит, маxДигит - минДигит представља минималну цифру садржану у низу цифара који се налази у нетерминалу <итем>, а маxДигит максималну цифру садржану у низу цифара који се налази у нетерминалу <итем>
- <лист>валуе, такеМинДигит - валуе представља вредност коју треба израчунати по поставци задатка, а такеМинДигит да ли у следећем кораку треба узети минималну или максималну цифру (ово посматрамо као неки флаг коме у сваком кораку инвертујемо вредност, а чија је почетна вредност 1 јер у првом кораку узимамо максималну, а у другом минималну цифру)
Атрибутивно транслациона граматика изгледа овако (ствари које су додате у односу на граматику из поставке су приказане подебљаним словима):
- <лист>валуе, такеМинДигит -> <лист>валуеРХС, такеМинДигитРХС <итем>минДигит, маxДигит { валуе = валуеРХС * 10 + (такеМинДигитРХС == 1) ? минДигит : маxДигит; такеМинДигит = 1 - такеМинДигитРХС; }
- <лист>валуе, такеМинДигит -> <итем>минДигит, маxДигит { валуе = маxДигит; такеМинДигит = 1; }
- <итем>минДигит, маxДигит -> [ <нум_арр>минДигитРХС, маxДигитРХС ] { минДигит = минДигитРХС; маxДигит = маxДигитРХС; }
- <нум_арр>минДигит, маxДигит -> <нум_арр>минДигитРХС, маxДигитРХС , ИНТдигит { минДигит = мин(минДигитРХС, дигит); маxДигит = маx(маxДигитРХС, дигит); }
- <нум_арр>минДигит, маxДигит -> ИНТдигит { минДигит = дигит; маxДигит = дигит; }
6. задатак
Поставка
Написати комплетан превод функција f1, f2 и main на Микројава бајткод. Сматрати да превод f1 креће од адресе 0. Секцију означену са // ... није потребно преводити и сматрати да је њена дужина једна инструкција.
program Januar2023
int b;
class A {
int fun1(int p) {...}
}
class B {
A[] arr;
}
B bObj;
int f1() {
return 1;
}
int f2() {
return 2;
}
void main() int x; {
bObj = new B;
// ...
b = bObj.arr[1].fun1(3);
if (b < x) {
b = f1();
}
else b = f2();
}
Решење
00: enter 0 0
03: const_1
04: exit
05: return
06: enter 0 0
09: const_2
10: exit
11: return
12: enter 0 1
15: new 4
18: dup
19: const_2
20: putfield 0
23: putstatic 1
26: ...
27: getstatic 1
30: getfield 1
33: const_1
34: aload
35: const_3
36: getstatic 1
39: getfield 1
42: const_1
43: aload
44: getfield 0
47: invokevirtual 'f' 'u' 'n' '1' -1
68: putstatic 0
71: getstatic 0
74: load_0
75: jge 12
78: call -78
81: putstatic 0
84: jmp 9
87: call -81
90: putstatic 0
93: exit
94: return
95: ...