Програмски преводиоци 1

Програмски преводиоци 1
Основне информације
Шифра	13С114ПП1, 13Е114ПП1
Семестар	7
Статус	обавезни
Страница	ir4pp1.etf.rs
ЕСПБ	6
Одсек	СИ, РТИ

Програмски преводиоци 1 је обавезни предмет у седмом семестру на СИ и РТИ.

Корисне везе

• ETF SI (модификације)
• ETF Materijali (Box) (решења старијих рокова)
• Студентски видео снимци решења задатака са вежби и рокова (обрађено градиво закључно са „парсирањем од врха ка дну“)
• Слике презентација Кристијана Жиже (снимљене вежбе 2020)
• Неки савети за израду пројекта (основа за водич за пројекат који је на викију)

Настава

Области се на следећи начин обрађују по блоковима:

• Први блок:
  • лексичка анализа (коначни аутомати, минимизација аутомата, конверзија из недетерминистичког у детерминистички, конверзија регуларног израза у ДКА, лексички процесори),
  • генератори лексичких анализатора (JFlex),
  • синтаксна анализа (увод у граматике и језике),
  • потисни аутомати
• Други блок:
  • парсирање од дна ка врху (LR(0) парсери, SLR(1) парсери, LALR(1) парсери, опоравак од грешака),
  • генератори парсера (CUP),
  • парсирање од врха ка дну (LL(1) граматике, трансформација у LL(1), конструкција парсера по принципу рекурзивног спуста),
  • атрибутивно-транслационе граматике (S-атрибутивне и L-атрибутивне граматике)
  • апстрактна синтаксна стабла (AST-CUP)
• Трећи блок:
  • табела симбола (конкретна реализација на пројекту, различите могуће организације, случај вишеструког наслеђивања),
  • Микројава виртуелна машина (меморијски сегменти, инструкције, превођење израза, превођење контролних структура, превођење позива метода, наслеђивање и виртуелни механизам),
  • генерисање међукода (четворке, тројке, граф тока контроле, SSA форма),
  • извршно окружење (контролне и приступне везе, дисплеји, стабла активације),
  • генерисање x86 кода (животни век променљивих, getreg алгоритам)

Градиво које се обрађује искључиво на предавањима укључује моделовање коначних аутомата у коду, S-атрибутивне и L-атрибутивне граматике, укључивање акција и атрибута у парсер конструисан по принципу рекурзивног спуста, апстрактна синтаксна стабла и вишеструко наслеђивање. Градиво из JFlex, CUP и апстрактних синтаксних стабала, иако теоретски може да дође на колоквијумима, се јако ретко појављује. Градиво S-атрибутивних и L-атрибутивних граматика се чешће појављује на испиту него на колоквијуму.

Сви материјали са вежби и предавања могу се пронаћи на страници предмета, у несрећној комбинацији различитих формата (ZIP, RAR, DOC, PDF и PPT). Презентације Кристијана Жиже, чије су снимљене вежбе из 2020. године, нису доступне (обрисао их је када је одлазио са предмета), али су доступне слике тих презентација из одељка са корисним везама. На вежбама и предавањима се такође могу помињати збирка или уџбеник, оне су доступне са странице предмета (додуше тешко видљиве) и из одељка са литературом.

Пројекат

Пројекат на предмету носи 40 бодова и обавезан је. Услов за излазак на испит је барем 20 бодова освојених на одбрани пројекта. Предаје се до дан или два пред одбрану, са мало ранијом иницијалном предајом ради формирања распореда (као на ОО1 и ОО2). Пројекат је подељен на 3 нивоа, где ниво А носи 20, ниво Б 30 и ниво Ц 40 бодова (могуће је освојити и број бодова између уколико пројекат испуњава део захтева за виши ниво, или уколико модификација на одбрани само делимично ради). Обично за сваки ниво буде по један захтев специфичан за ту школску годину, али се ниво Б генерално разликује од нивоа А по томе што захтева имплементацију функција, а ниво Ц од нивоа Б по томе што захтева имплементацију класа. На крају израде пројекта тражи се и документ са извештајем о пројекту.

Поставка пројекта се не мења много кроз године. У јануарском и фебруарском року важи једна поставка, у јулском се на ту поставку дода још захтева и у августовском и септембарском још више захтева. Пројекат је могуће бранити само једном по поставци! Ово значи да уколико паднете одбрану у јануару, немате право на одбрану у фебруару, и слично за августовки рок.

Од материјала за пројекат релевантне су вежбе из JFlex, CUP, табеле симбола и Микројава виртуелне машине. Поред тога, на страници предмета постоје снимци и изворни код једног студента који ради један мини-пројекат по фазама, који могу бити корисни као увод у алате за израду пројекта и примере имплементације одређених захтева. Већи део кода са тих снимака може се искористити ради имплементације захтева за ниво А на пројекту. На снимцима се као окружење за израду користи Eclipse, али било које окружење инсталирано у рачунарским лабораторијама на факултету је прихватљиво. Такође је доступан водич за израду пројекта.

Одбрана пројекта се организује неколико дана пре испита. На одбрани се прво раде модификације, затим асистенту или демонстратору покаже да модификација ради и потом брани основни пројекат. Одбрана основног пројекта обично није много детаљна, већ се покрену јавни тестови и види да ли раде (дају добар испис), евентуално откоментаришу неке линије које треба да изазову грешке. Том приликом се ретко тестира опоравак од синтаксних грешки и разне спецификације исписа прописане поставком. У извештај са пројекта се не улази. Структура пројекта која у поставци пише да је неопходна није заправо неопходна. Неке од модификација претходних година доступне су из одељка са корисним везама.

Стари пројекти доступни су са странице предмета (године 2021/2022 су доступни на http://ir4pp1.etf.rs/Domaci/2021-2022, претходне године на http://ir4pp1.etf.rs/Domaci/2020-2021 и тако даље, али не постоји лако доступна листа домаћих на једном месту).

Испитни рокови

Испитни рокови се понекад објављују на страници предмета, и понекад имају решења у виду сликаних вежбанки студената који су освојили максималан број бодова.

Рокови који су решени на викију су:

• Јануар 2018
• Јануар 2020
• Јануар 2021
• Јануар 2022
• Јануар 2023
• Јануар 2024
• К 2023
• К1 2012
• К1 2015
• К1 2017
• К1 2019
• К1 2022
• К2 2015
• К2 2017
• К2 2019
• К2 2020
• К2 2022
• Септембар 2023
• Фебруар 2021

Уколико желите да додате рок, посетите страницу за прављење рока.

Литература

Постоји једна збирка задатака и један уџбеник из предмета, доступни са странице предмета:

• "Збирка задатака из Програмских преводилаца 1", Д.Велашевић, Д.Бојић, 2000 издавач: Електротехнички факултет Универзитета у Београду
• "Програмски преводиоци 1", Д.Бојић, М.Вукасовић, 2022 (верзија 0.9)

На збирку се обично позива из материјала са вежби. Уџбеник опширно покрива градиво са предавања, али како још увек није дошао до стабилне верзије уме имати чудне језичке конструкте који га чине неоптималним за спремање испита.

Начин оцењивања

СИ

• $K_1$, $K_2$ — бодови са првог и другог колоквијума који се одржавају у првој и другој колоквијумској недељи и надокнађују се преко бодова са испита (0-20)
• $D$ — бодови са пројекта (0-40)
• $I$ — бодови са испита (0-60)
• Бодови са испита/колоквијума: $P_1 = max\left(\frac{1}{3} I + K_1 + K_2, \frac{2}{3} I + K_1, \frac{2}{3} I + K_2, I\right)$
• Бодови: $P = P_1 + D$
• Услов: $D \geq 20$, $P_1 \geq 31$

Бодови	$P \leq 51$	$50 < P \leq 61$	$60 < P \leq 71$	$70 < P \leq 81$	$80 < P \leq 91$	$91 < P$
Оцена	5	6	7	8	9	10

РТИ

Како на РТИ има само један колоквијум од 30 бодова, коначни бодови се рачунају по формули: $P = D + max\left(\frac{1}{2} I + K, I\right)$.

Потребна помоћ

• На овом предмету фале поставке рокова. Помозите викију памћењем/преписивањем рокова и постављањем на вики.
• На овом предмету фале решења рокова. Помозите викију решавањем рокова и постављањем њихових решења на вики.

  Рокови који су преписани а нису решени су:

  • Јануар 2023
  • Септембар 2023
  • К 2023
  • Јануар 2024

  Рокови којима недостаје понеко решење су:

  • К1 2012
  • К1 2022
  • К2 2022
  • Јануар 2022
  • Фебруар 2021