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

Циљ и исход предмета

Упознавање студената са проблемима превођења са једног програмског језика на други, принципима рада програмских преводилаца, алатима за њихово прављење и начином њихове имплементације. Разумевање програмског преводиоца као једног од кључних алата у прављењу програма. Могућност укључивања у прављење програмског преводиоца.

Теоријска настава

Настанак виших програмских језика и програмских преводилаца. Класификација компајлера. Евалуација компајлера. Актуелни изазови пред развојем компајлера. Компајлерске инфраструктуре (GCC, LLVM). Теорија формалних језика (граматике, хијерархија Чомског). Лексичка анализа (основни алгоритам скенирања, основне дилеме, регуларни изрази, недетерминистички и детерминистички коначни аутомати, табеларна имплементација коначних аутомата, Lex). Семантичка анализа (контексно слободне граматике, вишесмисленост и превазилажење, приступи обради грешке у парсирању, апстрактно синтаксно стабло, рекурзивно силазно парсирање, лева рекурзија и превазилажење, предиктивно парсирање, LL1 табела, узлазно парсирање, Yacc). Семантичка анализа (опсег, табела симбола, окружење типа, тип методе, статичка и динамичка контрола типа). Генерисање кода (организација извршавања, активациони запис, алоцирање, поравнање, стек машина, архитектура MIPS). Основи оптимизације кода (правила евалуације, међукод, базични блок, граф контроле тока, локална и глобална оптимизација).

Практична настава

Парсирање стринга у језику C и у језику Python. Регуларни језици, вежба писања регуларних језика. Почетак писања једноставног интерпретера за језик C у језику Python. Лексичка анализа и препознавање токена. Имплементација коначног аутомата за конкретну контекстно независну граматику. Парсирање математичких израза употребом одговарајуће контекстно независне граматике. Генерисање апстрактног синтаксног стабла. Имплементација једноставних елемената језика C: функције, библиотеке, декларације, if, while, for. Имплементација семантичке анализе. Увод у окружење LLVM.