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

Испит у фебруарском року 2021. године одржан је 12. фебруара. Поставка рока је доступна са странице предмета.

1. задатак

Поставка

Дата је секвенца од нула или више променљивих раздвојених зарезима. Свака променљива представља низ од једног или више знакова, почиње обавезно малим словом, након чега може доћи прозвољан број знакова из скупа који чине мала слова, цифре и специјални карактер "_".

1. Написати регуларни израз који описује наведену секвенцу.
2. На основу регуларног израза под а) формирати минимални ДКА коришћењем метода позиције.

Решење

Датотека:ППР фебруар 2022 задатак 1 стабло.свг

Синтаксно стабло у првом задатку.

Регуларни израз који препознаје ову секвенцу може бити (mo*(,mo*)*|), где је m ознака за мало слово а o ознака за мала слова, велика слова и доњу црту.

Табела следећих позиција

1	2, 3, 6
2	2, 3, 6
3	4
4	3, 5, 6
5	3, 5, 6
6	-

Претварање недетерминистичког коначног аутомата у детерминистички

	м	о	,	Прихвата
→ 1, 6	2, 3, 6			1
2, 3, 6		2, 3, 6	4	1
4	3, 5, 6			0
3, 5, 6		3, 5, 6	4	1

Детерминистички коначни аутомат

	м	о	,	Прихвата
→ А	Б			1
Б		Б	C	1
C	D			0
D		D	C	1

2. задатак

Поставка

За дату граматику

1. <С> → <А> <С>
2. <С> → ε
3. <А> → <Б> б <Б> ц
4. <А> → <C> ц <Б>
5. <Б> → а <D>
6. <C> → а <D>
7. <D> → ε

1. Нацртати стање ∇ карактеристичног ЛР(0) аутомата и врсту ∇ контролне табеле СЛР(1) парсера. Има ли конфликата?
2. Нацртати стање ∇ карактеристичног ЛАЛР(1) аутомата и врсту ∇ контролне табеле ЛАЛР(1) парсера. Има ли конфликата?

Напомена: не цртати остатак карактеристичног аутомата, нити остатак контролне табеле.

Решење

Стање ∇ садржи у себи следеће смене:

• <С'> → • <С> ─┤, {}
• <С> → • <А> <С>, {─┤}
• <С> → •, {─┤}
• <А> → • <Б> б <Б> ц, {а, ─┤}
• <А> → • <C> ц <Б>, {а, ─┤}
• <Б> → • а <D>, {б}
• <C> → • а <D>, {ц}

Како бисмо одредили ∇ врсту контролне табеле СЛР(1) парсера, морамо одредити и релевантне ФИРСТ и ФОЛЛОW скупове:

• ФОЛЛОW(<C>) = {ц}
• ФОЛЛОW(<С>) = {─┤}
• ФИРСТ(<С>) = ФИРСТ(<А>) = ФИРСТ(<Б>) ∪ ФИРСТ(<C>) = {а}
• ФОЛЛОW(<А>) = ФИРСТ(<С>) ∪ ФОЛЛОW(<С>) = {а, ─┤}
• ФОЛЛОW(<Б>) = ФОЛЛОW(<А>) ∪ {б, ц} = {а, б, ц, ─┤}
• ФОЛЛОW(<D>) = ФОЛЛОW(<C>) ∪ ФОЛЛОW(<Б>) = {а, б, ц, ─┤}

Одавде можемо видети да се у a колони налази СХИФТ, а у ─┤ колони РЕДУЦЕ(2). Контролна табела би требало да је иста за оба парсера.

3. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

1. <С> → а <А>
2. <С> → <С> б
3. <А> → ц <А>
4. <А> → д

На улаз ЛР(0) парсера који је описан датом граматиком доведи се улазна секвенца accbcadb. Претпоставка је да се за опоравак од грешака користи једноставан паниц моде алгоритам:

1. са сигурним симболом ц.
2. са сигурним симболом д.

За тачку а) и б) засебно приказати рад парсера и јасно назначити да ли је парсер успешно завршио парсирање.

4. задатак

Поставка

Компајлер за микројаву на излазу даје следећи испис табеле симбола и листинг бајткода. Како изгледа изворни микројава програм који одговара овим излазима?

==================SADRŽAJ TABELE SIMBOLA=======================
(Level -1)
Type int: int, 0, 0
Type char: char, 0, 0
Con eol: char, 10, 0
Con null: Class, 0, 0
Meth chr: char, 0, 1 [Var i: int, 0, 1 ]
Meth ord: int, 0, 1 [Var ch: char, 0, 1 ]
Meth len: int, 0, 1 [Var arr: Arr of notype, 0, 1 ]
Prog PROBA: notype, 0, 0
[Type SUPERKLASA: Class, 0, 0 [Fld s: int, 1, 1 ][Meth foo: int, 0, 1 [Var this: Class, 0, 2 ]]]
[Type POTKLASA: Class, 6, 0 [Fld s: int, 1, 1 ][Fld p: int, 2, 1 ][Meth foo: int, 9, 1 [Var this: Class, 0, 2 ]]]
[Var sk: Class, 12, 0 ]
[Meth main: notype, 19, 0 ]

Микројава бајкод:^[сиц]

0: enter 1 1
3: const_0
4: jmp 3 (=7)
7: exit
8: return
9: enter 1 1
12: const_1
13: neg
14: jmp 3 (=17)
17: exit
18: return
19: enter 0 0
22: const 102
27: putstatic 0
30: const 111
35: putstatic 1
38: const 111
43: putstatic 2
46: const_m1
47: putstatic 3
50: const 0
55: putstatic 4
58: const -2
63: putstatic 5
66: const 102
71: putstatic 6
74: const 111
79: putstatic 7
82: const 111
87: putstatic 8
90: const_m1
91: putstatic 9
94: const 9
99: putstatic 10
102: const -2
107: putstatic 11
110: new 12
113: dup
114: const 6
119: putfield 0
122: putstatic 12
125: getstatic 12
128: const_1
129: putfield 1
132: getstatic 12
135: dup
136: getfield 0
139: invokevirtual foo
156: const_0
157: print
158: exit
159: return

Решење

program PROBA
    class SUPERKLASA {
        int s;
        {
            int foo() {
                return 0;
            }
        }
    }
    class POTKLASA extends SUPERKLASA {
        int p;
        {
            int foo() {
                return -1;
            }
        }
    }
    SUPERKLASA sk;
    {
        void main() {
            sk = new POTKLASA();
            sk.s = 1;
            print(sk.foo(), 0);
        }
    }

5. задатак

Поставка

За дати програмски фрагмент написати одговарајући међукод у ССА форми и нацртати граф тока контроле на нивоу основних блокова.

x = 0;
y = 1;
z = 2;
do {
    x = x - 1;

    if (z == 0) break;
    else y = y + z;

    z = y + 1;
} while (z > 1 && x == 0);
x = z - y;

Решење

Датотека:ППР фебруар 2022 задатак 5 граф.свг

Граф тока контроле у петом задатку.

1. x1 := 0
2. y1 := 1
3. з1 := 2
4. т1 := Ф(x1, x2)
5. т2 := т1 - 1
6. x2 := т2
7. т3 := Ф(з1, з2)
8. иф т3 == 0 гото 17
9. т4 := Ф(y1, y2)
10. т5 := Ф(з1, з2)
11. т6 := т4 + т5
12. y2 := т6
13. т7 := y2 + 1
14. з2 := т7
15. иф з2 <= 1 гото 17
16. иф x2 == 0 гото 4
17. т8 := Ф(y1, y2)
18. т9 := Ф(з1, з2)
19. т10 := т9 - т8
20. x3 := т10