Компилатор

Компилатор или програмски преводилац (енгл. Compiler) је рачунарски програм (или низ програма) који трансформише код једног програмског језика у други програмски језик. Код који се преводи обично се зове изворни код, а код добијен трансформацијом машински код.

Најчешћи разлог за превођење изворног кода јесте прављење извршног програма. Име компилатор се користи за програме који преводе изворни код са вишег програмског језика на језик нижег нивоа (нпр. асемблерски језик, машински језик). Програм који преводи са нижег на виши програмски језик је декомпилатор. Програм који преводи са једног вишег програмског језика на други се обично зове преводилац језика, преводилац извора у извор, или конвертор језика. Преиначилац језика је обично програм који преводи форму израза без промене језика.

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

Процес компилације се обично обично одвија кроз две главне етапе:

• анализу изворног кода и
• синтезу објектног кода.

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

Са своје стране, етапа анализе се дели у три фазе:

• лексичку анализу
• синтаксичку анализу
• семантичку анализу

За старије генерације рачунара, софтвер је годинама писан асемблерским језиком. Виши програмски језици нису пронађени све док предности могућности поновног коришћења софтвера на разним врстама процесора нису постале значајно веће од цене писања компилатора. Веома ограничен капацитет меморија старијих рачунара је такође стварао пуно техничких проблема при имплементацији компилатора.

Први виши програмски језик (Планкалкул) је предложен од стране Конрада Цузеа 1943. године. Крајем 50-их година прошлог века, предложени су машински независни програмски језици. Према том предлогу, развијено је неколико експерименталних компилатора. Грејс Хопер је 1952. написала први компилатор за А-0 програмски језик. Фортранов тим који је водио Џон Бакус из IBMа је генерално акредитован са представљањем првог комплетног компилатора 1957. године. Кобол је био рани језик који је компилиран на вишеструким архитектурама 1960. године.

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

Старији рачунари су писани асемблерским језиком. Први само-домаћи компилатор – способан да компилира сопствени код у виши програмски језик- креирали су Харт и Левин за Lisp на МИТу 1962. године. Још од 1970-их, имплементација компилатора у језику којег компилира је постала уобичајена пракса, иако су Паскал и C били популарни избори за имплементацију језика. Прављење само-домаћег компилатора је проблем бутстраповања – први такав компилатор за језик мора бити компилиран или компајлером писаним различитим језиком или (као у Харт и Левиновом компајлеру за Lisp) или покретањем компилатора у интерпретеру.

Конструкција компилатора и оптимизација компилатора се учи на универзитетима као део наставног плана рачунарске науке. Такви курсеви су обично допуњени имплементацијом компилатора за образовни програмски језик. Добро документован пример је ПЛ/0 компилатор Никлаус Вирта, који је Вирт користио да би подучавао конструкцију компилатора у 1970-им. Упркос својој једноставности, ПЛ/0 компилатор је имао неколико концепата:

1. Развој програма постепеним усавршавањем
2. Употреба рекурзивног десцентног парсера
3. Употреба ЕБНФа да би се описала синтакса језика
4. Генератор кода који производи портабилни П код
5. Употреба Т-дијаграмa у формалном описивању проблема бутстраповања

Један метод за класификацију компилатора је преко платформе на којој се извршава генерисани код који они производе. Позната је као циљна платформа.

Природни или домаћи компилатор је онај чији је излаз намењен да се директно покреће на истом типу рачунара и оперативног система на којима се покреће и компилатора. Излаз укрштеног компилатора је дизајниран да се покреће на другачијој платформи. Укрштени компилатори се често користе када се развија софтвер за укопане системе који нису планирани за подршку софтверског развојног окружења.

Излаз компилатора који производи код за виртуалну машину (ВМ) може или не може бити извршаван на истој платформи као компилатор који га је произвео. Зато такви компилатори често нису класификовани као природни или укрштени компилатори.

Виши програмски језици су, погодности ради, подељени на компилиране језике и интерпретиране језике. Ипак, ретко постоји нешто у вези језика што захтева да буде искључиво компилиран или искључиво интерпретиран. Категоризација често одражава најпопуларније или најраспрострањеније имплементације језика – нпр. БЕЈЗИК је интерпретиран језик и C је компилирани, упркос постојању БЕЈЗИК компилатора и C интерпретера.

Сви програмски језици могу да се посматрају као интерпретирани. Извршавање машинског кода био би само специјалан случај интерпретације коју изводи хардвер централне процесорске јединице. Модерни трендови као што су правовремена компилација и интерпретација бајткода такође нарушавају традиционалну категоризацију.

Постоје изузеци. Неке спецификације језика наговештавају да имплементације морају укључивати лаку компилацију, нпр. Common Lisp. Остали језици имају особину да се веома лако имплементирају у интерпретеру, али је писање компилатора знатно теже, нпр. АПЛ, СНОБОЛ4, и многи писани језици дозвољавају програмима да конструишу произвољан изворни код на почетку са операцијама регуларних стрингова, и онда да извршавају тај код додајући га специјалној функцији процене. Да би имплементирали ове особине у компилираним језицима, програми обично морају бити смештени у почетној библиотеци која укључује верзију самог компилатора.

Излази неких компајлера могу користити хардвер на веома ниском нивоу. Нпр. Низови пролаза програмибилних поља (НППП) или структрурално Апликативно специфично интегративно коло (АСИК). За такве компилаторе се каже да су компилатори хардвера или алати синтезе јер програми које они компилирају ефикасно контролишу финалну конфигурацију хардвера и начин њиховог деловања; излаз компилације нису инструкције које су извршене у секвенци – само веза транзистора или lookup табеле. На пример, XST је Xilinx Synthesis Tool који се користи за конфигурисање FGPA. Слични алати су доступни из Altera-e, Synplicity-ja, Synopsys-a и других продаваца.

Приступ за дизајнирање компилатора је узрокован комплексношћу потребног процесирања, искуством особе(а) које га дизајнирају и ресурсима који су на располагању (нпр. људи и алат).

Компилатор за релативно једноставан језик који је написала једна особа, може бити једно парче софтвера. Када је изворни језик велики и сложен и када је захтеван висококвалитетан излаз, дизајн може бити подељен у број релативно независних фаза или пролаза. Имати одвојене фазе значи да развој може бити подељен на мале делове и дат различитим људима. Тада је такође пуно лакше заменити једну фазу побољшаном или убацити нове фазе касније (нпр. додатне оптимизације).

Идеја о подели процеса компилације на фазе (или пролазе) је победила захваљујући Пројекту продукције квалитета компилатора на универзитету Карнеги Мелон. Овај пројекат је увео термине front end, middle end (данас ретко коришћен) и back end.

Сви осим најмањих компилатора имају више од две фазе. Ипак, ове фазе су обично посматране као део front end-а или back end-а. Тачка на којој се ова два краја сусрећу је увек дискутабилна. front end је генерално разматран да буде тамо где се обављају синтаксичко и семантичко процесирање заједно са померањем у нижи ниво репрезентације (него изворни код).

Middle end је обично дизајниран да изведе оптимизацију на форми различитој од изворног или машинског кода. Ова независност изворног (машинског) кода има за циљ да омогући да генеричке оптимизације буду подељене између верзија компилатора подржавајући разне језике и циљне процесоре.

Back end узима излаз из средине. Може да изводи више анализа, трансформација и оптимизација које су за неки посебан рачунар. Потом, генерише код за посебан процесор и ОС.

Овај front-end/middle/back-end приступ даје могућност комбиновања front end-ова за различите језике са back end-овима за различите централне процесорске јединице. Практични примери овог приступа су ГНУ компајлер колекција, ЛЛВМ и Амстердам компилатор алат који имају вишеструке front end-ове, подељене анализе и вишеструке back end-ове.

Класификација компилатора према броју пролаза има своју позадину у ограничењу хардверских ресурса рачунара. Компилација укључује пуно посла и старији рачунари нису имали довољно меморије да би садржали програм који би радио сав поменути посао. Зато су компилатори били подељени на мање програме од којих је сваки имао пролаз преко извора (или неке његове репрезентације) изводећи неке од захтеваних анализа и транслација.

Способност компилације у једном пролазу је често виђена као предност јер поједностављује посао писања компилатора и једнопролазни компилатори су генерално бржи од вишепролазних компилатора. Многи језици су дизајнирани тако да могу бити компилирани у једном пролазу (нпр. Паскал).

У неким случајевима дизајнирање особине језика може захтевати да компилатор изведе више од једног пролаза преко извора. Нпр. узимајући у обзир појављивање декларације у 20. линији извора што утиче на померање појављивања исказа у линији 10. У овом случају, први пролаз треба да сакупи информације о појављивањима декларација после исказа на које утичу са померањем догађаја за време следећег пролаза.

Недостатак компилације у једном пролазу је што она не може да омогући многе од добрих оптимизација потребних за генерисање високо – квалитетног кода. Може бити тешко да се преброји колико тачно фаза оптимизирајући компилатор прави. Нпр. различите фазе оптимизације могу анализирати један израз више пута али само једном неки други израз.

Подела компилатора на мање програме је техника коју користе истраживачи заинтересовани за стварање коректних компилатора. Доказивање коректности групе малих програма често захтева мање напора него доказивање коректности једног већег, еквивалентног програма.

Док типични вишепролазни компилатор избацује машински код из свог последњег пролаза, постоји неколико других типова:

• Извор – у – извор компилатор је тип компилатора који користи језик високог нивоа као улаз, а излаз је такође језик високог нивоа. Нпр. аутоматски паралелизујући компилатор ће учестало узимати програмски језик високог нивоа као улаз и онда трансформисати код и прибележити га са паралелним кодом (нпр. OpenMP) или конструкције језика (нпр. Фортранови DOALL искази).
• Фазни компилатор који компилира у асемблерски језик теоријске машине као неке Пролог имплементације
  • Ова Пролог машина је такође позната и као Воренова апстрактна машина (ВАМ). Бајткод компилатори за Јаву, Пајтон и многе друге су такође подтипови ових.
• Правовремени компилатор који користе Smalltalk и Јава системи, и такође Microsoft .Net - ов Обичан интермедијални језик (CIL)
  • Апликације се испоручију у бајткоду који је компилиран у природни машински код баш пре извршења.

Front end анализира изворни код да би направио унутрашњу репрезентацију програма која се зове интермедијална репрезентација или ИР. Он такође уређује табелу симбола, структуру података која мапира сваки симбол у изворном коду у повезане информације као што су локација, тип и циљ. Ово је урађено у неколико фаза у које се укључују неке од следећих:

1. Реконструкција линије. Језици који скупљају своје кључне речи или дозвољавају неограничен број белина унутар идентификатора захтевају фазу пре парсирања у којој се конвертује улазна секвенца карактера у канонску форму спремну за парсирање. анализа наниже, рекурзивни спуст парсери коришћени 1960-их су читали извор карактер по карактер и нису захтевали посебну фазу за токенизирање. Атлас аутокод и Имп (и неке имплементације Алголa и Корала 66) су примери скупљених језика чији би компилатори имали фазу реконструкција линије.
2. Лексичка анализа дели изворни код на мале делове који се зову токени. Сваки токен је атомична јединица језика, нпр. кључна реч, идентификатор или име симбола. Синтакса токена је типичан регуларни језик тако да би се коначни аутомат конструисан за дати регуларни израз могао користити за препознавање језика. Ова фаза се такође зове лексичка или скенирајућа, а софтвер који врши лексичку анализу зове се лексички анализатор или сканер.
3. Препроцесирање. Неки језици, нпр. C, захтевају фазу препроцесирања која подржава макро супституцију и условну компилацију. Фаза препроцесирања се одвија пре синтаксичке или семантичке анализе; нпр. у случају језика C, препроцесор пре управља лексичким токенима него синтаксичким формама. Ипак, неки језици као што је Шеме подржавају макро супституције засноване на синтаксичким формама.
4. Синтаксичка анализа обухвата парсирање секвенце токена да би идентификовао синтаксичку структуру програма. Задатак синтаксичке анализе је да се утврди да ли је програм у складу са граматичким правилима програмског језика у коме је писан. Ова фаза прави дрво парсирања које замењује линеарне секвенце токена дрволиком структуром насталом према правилима формалне граматике која дефинише синтаксу језика. Дрво парсирања је често анализирано, проширивано и транформисано у каснијим фазама у компилатору. Синтаксички анализатор или парсер ово дрво прослеђује семантичком анализатору.
5. Семантичка анализа ја фаза у којој компилатор додаје семантичке информације у дрво парсирања и гради табелу симбола. Ова фаза изводи семантичке провере као нпр. проверу типа (провера типа грешака) или повезивање објеката (повезивање референци на променљиве и функције са њиховим дефиницијама) или јасна додела, одбијање неисправних програма или избацивање упозорења. Семантичка анализа често захтева комплетно дрво парсирања што значи да ова фаза прати фазу парсирања и наилази на фазу генерисања кода иако је често могуће обухватити више фаза једним пролазом преко кода у имплементацији компилатора.

Израз back end се понекад меша са генератором кода због преклопљене функционалности генерисања асемблерског кода. Неке литературе користе middle end да би разликовале фазе генеричке анализе и оптимизације у back end-у од машински зависних генератора кода. Главне фазе back end-а укључују следеће:

1. Анализа: у овој фази се скупљају програмске информације из интермедијалне репрезентације изведене из улаза. Типичне анализе су анализе пролазних података за прављење употребно-дефинисаних ланаца, зависних анализа, алијас анализа, показних анализа, искејп анализа итд. Исправна анализа је основа за било коју компјутерску оптимизацију. Граф позивања и граф контроле тока се често праве за време фазе анализе.
2. Оптимизација: репрезентација интермедијалног језика је трансформисана у функционално еквивалентне али брже (или мање) форме. Популарне оптимизације су инлајн проширење, елиминација мртвог кода, множење константи, трансформација петље, алокација регистара или чак аутоматска паралелизација.
3. Генерисање кода: трансформисани интермедијални језик се преводи у излазни језик, обично у природни машински језик система. Ово укључује ресурсне и меморијске одлуке, као што су одлучивање које променљиве сместити у регистре и меморију као и бирање и временско планирање одговарајућих машинских инструкција заједно са њиховим повезаним адресним модовима (видети такође Сети-Улман алгоритам).

Компилаторска анализа је предуслов за било коју компилаторску оптимизацију и они су тесно повезани. Нпр. зависна анализа је кључна за трансформацију петље.

У додатку, циљ компилаторске анализе и оптимизације се пуно мења, од малог базног блока до процедуралног / функцијског нивоа или чак до читавог програма (интерпроцедурална оптимизација). Очигледно, компилатор би могао обављати бољи посао користећи шири поглед. Али тај шири поглед није бесплатан: велике циљне анализе и оптимизације су веома скупе у погледу времена компилације и меморијског простора; ово је нарочито тачно за интерпроцедуралне анализе и оптимизације.

Постојање интерпроцедуралних анализа и оптимизација је заједничко у модерним комерцијалним компилаторима из HPa, IBMa, SGIa, Intela, Microsofta и Sun Microsystemsa. Отворени извор GCC је критикован дуже времена због недостатка моћне интерпроцедуралне оптимизације, али све више добија на важности. Још један добар компилатор отвореног извора са пуном анализом и оптимизацијом инфраструктуре је Open64, који користе многе организације у истраживачке и комерцијалне сврхе.

Због захтева за додатним временом и простором за компилаторске анализе и оптимизације, неки компилатори их прескачу по default-у. Корисници морају користити опције компилације да би јасно саопштили компилатору које оптимизације треба омогућити.

Асемблерски језик је нижи програмски језик, програм који га компилира је познат као асемблер, чији се инверзни програм зове дисасемблер. Програм који преводи нижи програмски језик у виши је декомпилатор. Програм који преводи виши програмски језик у други, такође виши језик обично се назива преводилац језика, преводилац извора у извор, језички конвертор или преиначилац језика.

• Списак компилатора
• Оптимизација компилатора
• Апстрактна интерпретација
• Анализа навише
• Атрибутске граматике
• Семантичко енкодирање
• Нагомилавање грешака
• Метакомпилација
• Правовремена компилација
• Списак важних издања у рачунарској науци#Компилатори
• Интерпретатор
• Yacc
• Lex

• Компилаторске уџбеничке напомене Збирка напомена на главне уџбенике о компилаторској конструкцији
• Душко М. Витас: Преводиоци и интерпретатори (Увод у теорију и методе компилације програмских језика) - Математички факултет - Београд, 2006.
• Компилатори: Принципи, технике и алати, аутори Алфред Ахо, Рави Сети и Џефри Улман. ISBN 978-0-201-10088-4.) 0201100886, 00.html линк за издавача. Такође позната као ‘Змајева књига’.
• Напредни компилаторски дизајн и имплементација, аутор Стивен Мачник. ISBN 978-1-55860-320-2.
• Инжењеринг компилатора од Кејт Д. Купера и Линде Торцзон. Морган Кофман. 2004. ISBN 978-1-55860-699-9.
• Разумевање и писање компилатора: Будите свој водич. ISBN 978-0-333-21732-0., аутор Ричард Борнат , верзија књиге.
• Компилаторска конструкција, аутор Никлаус Вирт. ISBN 978-0-201-40353-4.), Едисон-Весли 1996, 176 страна
• Историја технологије језичког процесора у IBM од Ф. Е. Алена, IBM-ов часопис истраживања и развоја, септембар 1981.