Програмски преводиоци 1/Фебруар 2021
Испит у фебруарском року 2021. године одржан је 12. фебруара. Поставка рока је доступна са странице предмета.
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. задатак
Поставка
За дату граматику
- <С> → <А> <С>
- <С> → ε
- <А> → <Б> б <Б> ц
- <А> → <C> ц <Б>
- <Б> → а <D>
- <C> → а <D>
- <D> → ε
- Нацртати стање ∇ карактеристичног ЛР(0) аутомата и врсту ∇ контролне табеле СЛР(1) парсера. Има ли конфликата?
- Нацртати стање ∇ карактеристичног ЛАЛР(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ики тако што ћете га решити.
Поставка
- <С> → а <А>
- <С> → <С> б
- <А> → ц <А>
- <А> → д
На улаз ЛР(0) парсера који је описан датом граматиком доведи се улазна секвенца accbcadb
. Претпоставка је да се за опоравак од грешака користи једноставан паниц моде алгоритам:
- са сигурним симболом ц.
- са сигурним симболом д.
За тачку а) и б) засебно приказати рад парсера и јасно назначити да ли је парсер успешно завршио парсирање.
Решење
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;
Решење
- x1 := 0
- y1 := 1
- з1 := 2
- т1 := Ф(x1, x2)
- т2 := т1 - 1
- x2 := т2
- т3 := Ф(з1, з2)
- иф т3 == 0 гото 17
- т4 := Ф(y1, y2)
- т5 := Ф(з1, з2)
- т6 := т4 + т5
- y2 := т6
- т7 := y2 + 1
- з2 := т7
- иф з2 <= 1 гото 17
- иф x2 == 0 гото 4
- т8 := Ф(y1, y2)
- т9 := Ф(з1, з2)
- т10 := т9 - т8
- x3 := т10