Компајлер

Од Википедија, слободна енциклопедија

Дијаграм на операциите на типичен мултијазичен, мултитаргет компјалер.
Дијаграм на операциите на типичен мултијазичен, мултитаргет компјалер.

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

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

Обично компајлерот ги изведува следниве активности: Лексичка анализа, Предпроцесирање, Парсирање, Семантичка анализа, Оптимизација на кодот, Генерирање на код.

Содржина

[уреди] Историја

Софтверот за првите компјутери се пишувал во асемблерски јазик многу години. Вишите програмски јазици не беа измислени се додека не се доби поволноста тие да се користат на различни видови CPU (Централна Процесирачка Единица). Многу ограничената меморија на раните компјутери исто така правела многу техничкипрограми за имплементацијата на компајлерот.

На крајот на 50тите години, први беа предложени машински-независните јазици. Тогаш се направени неколку експериментални компајлери. Првиот компајлер е напишан од Грејс Хопер, во 1952, за А-0 програмскиот јазик. FORTRAN тимот предводен од Џон Бакус (John Backus) во IBM е најголемиот виновник за претставувањето на првиот комплетен компајлер , во 1957 год.

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

Раните компајлери беа пишувани во асембли јазик. Првиот само-одржувачки компајлер- спосебен да искомпајлира сопствен изворен код од виш програмски јазик- беше креиран од Lisp од Харт и Левин во MIT во 1962 год. Од 70тите години вообичаена практика беше да се имплементира компајлер во јазикот кој го компајлира , иако и Pascal и C беа популарни избори за имплементација на јазикот.


[уреди] Што извршува кодот?

Еден метод кој се користи за разликување на компајлерите е платформата на која се генерира кодот кој ја создава извршната програма.

Хостиран компајлер е оној компајлер чиј излез е наменет да работи на истиот тип на компјутер и оперативен систем на кој што работи самиот тој. Додека пак излезот на вкрстениот компајлер (cross compiler) е дизајниран да работи на различни платформи. Вкрстените компајлери често се употребуваат за градење на софтвер за вгнездени системи кои што не се наменети за поддржување на околина за развивање на софтвер.

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


[уреди] Компајлер наспроти интерпретер

Многу луѓе прават поделба меѓу вишите програмски јазици на компајлички јазици и интерпретирачки јазици. Компајлерите и интерпретерите се имплементации на јазици, но не и јазици самите тие. Категоризирањето обично се рефлектира на најпознатите и најрачирените имплементации на јазикот, на пример за BASIC се мисли дека е интерпретирачки јазик, додека за С компајлирачки, и покрај постоењето на BASIC компајлери и С интерпретери.

Но постојат и исклучоци, некои спецификации на јазици кажуваат дека во имплементацијата мора да се вклучи функционалноста на компајлерот (Common Lisp) додека други јазици имаат делови кои можат многу лесно да се приспособат на интерпретер, но прават пишувањето на компајлер да биде многу тешко, за пример, SNOBOL4.


[уреди] Хардвер компајлирање

Излезот на компајлирањето мора да влијае на хардверот на многу ниско ниво, на пример Field Programmable Gate Array (FPGA). Тие компајлери се наречени хардвер компајлери бидејќи програмите коишто тие ги компајлираат ефективно ја контролираат финалната конфигурација на хардверот и како истата работи.

[уреди] Дизајн на компајлерот

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

Компајлер за релативно едноставе јазик напишан од некое лице може да биде многу едноставен софтвер. Но кога изворниот код е голем и комплексен и е потребен квалитетен излез тогаш дизајнот на компајлерот може да се подели во неколку фази или поминувања. Да се раздели работата во фази се мисли дека развојот може подели на мали делови и да се додели на различни лица да ги изработат. Исто така многу е полесно да се замени само еден дел со некоја негова подобрена верзија.

Поделбата на компајлирањето како процес беше предложено од Production Quality Compiler-Compiler Project на Carneige Mellon Универзитетот. Овој проект ги внесе термините “преден крај”,” среден крај”(кој ретко се користи) и “заден крај”.

Скоро сите помали компајлери имаат најмалку две фази. Но, овие фази обично се разгледуваат какодел од ” предниот” или “задниот крај”. Местото каде овие “краеви” се сретнуваат секогаш било отворено за дебата. “Предниот крај” генерално работи за синтаксичка и семантичка анализа, заедно со преведувањето во понизок јазик од изворниот код.

“Средниот крај” обично е наменет за оптимизација на друг вид на код различен од изворниот или машинскиот. “Задниот крај” го зема излезот на средниот крај, и потоа може да направи уште анализи, трансформации и оптимизации кои ќе ги направи за соодветниот компјутер. Пото генерира код за соодветниот процесор и оперативен систем.

Пристапот со разделување на компајлирањето во фази преден/среден/заден крај прави возможно комбинирањето на фазата на предниот крај за различни јазици со фазата-заден крај за различни CPU. Практичен пример за тоа GNU Compiler Collection и Amsterdam Compiler Kit.


[уреди] Преден крај

Во фазата Преден крај се анализира изворниот код за да сеизгради интерна репрезентација на програмата, наречена Интермедиална Репрезрнтација или ИР . Исто така се работи со табелата на симболи којашто е податочна структура која секој симбол од изворниот код му ја придава информацијата како локација и тип. Тоа се прави во неколку фази, меѓу кои ги вклучува и следниве:

  • Реконструкција на редовите - јазиците кои ги категоризираат нивните клучни зборови и дозволуваат празни места меѓу идентификаторите имаат потреба од фаза пред парсирањето, којашто ги конвертира влезните знаци во канонична форма подготвена за парсерот. Top-down рекурзивниот парсер кој користи табела користен во 60тите години чита од изворниот код знак по знак и не му е потребна позебна фаза за токенизирање.
  • Лексичка анализа - го дели изворниот код на мали делови наречени токени. Секој токен неделив дел од програмскиот јазик, на пример може да биде клучен збор, идентификатор, променлива или име на некој симбол. Синтаксата на токените е обично некој регуларен јазик, па со помош на некоја форма за Конечен Автомат за соодветен региларен израз тој токен може да биде препознаен. Софтверот кој се користи за лексичка анализа се нарекува лексер или лексички анализатор.
  • Препроцесирање - некои јазици како например С ја бараат оваа препроцесирачка фаза која поддржува макро супституција. Обично препроцесирањето се случува пред синтаксичката и семантичката анализа, како во примерот со програмскиот јазик С, и обично препроцесорот манипулира со лексички токени одколку со синтаксички форми. Но, постојат и некои јазици, како на пример Scheme, кои поддржуваат макро супституција но, базирана на синтаксички форми.
  • Синтаксната анализа вклучува парсирање на токените за да се идентификува структурата на програмата. Оваа фаза буквално гради парсирачко дрво, кое што ја заменува линеарната структура на токените структура на дрво според правилата на формалната граматика која што ја дефинира синтаксата на јазикот. Парсирачкото дрво обично се анализира, проширува и трансформира од подоцнежните фази во компајлирањето.
  • Семантичка анализа- е фаза во која цомпајлерот додава семантички информации на парсирачкото дрво и ја гради табелата на симболи. Оваа фаза врши семантички проверки како што се проверка на типот, одбивање на неточните програми , дефинирање на активностии сигнализира со пораки за внимание. За семантичка анализа обично е потребно цело парсирачко дрво, што значи дека оваа фаза логички следува после фазата за парсирање, и претходи на фазата за генерирање на код.


[уреди] Заден крај

Терминот “Заден крај” често се поистоветува генератор на код поради делумната функционалност на генерирање на асемблерски код. Некои литератури ја користат “Средната фаза” за да ги означат фазите на анализа и оптимизација.

Главните процеси се:

  • Анализа-Ова е собирање на информациите од програмата за интермедиална репрезентација дадена од влезот. Типични анализи се: анализа на протокот на податоците, анализа на зависностите , анализа на имињата, анализа на покажувачите и еscape анализата итн. Точноста на анлизите е основна за оптимизацијата.

Оптимизација- интермедиалната репрезентација на јазикот е трансформирана во некој функционален еквивалент но во побрзи (помали) форми.

Генерирање на код- трансформираниот јазик се преведува во излезен јазик, обично во соодветниот машински. Ова вклучува одлуки за ресурсите и меморијата, како што се која од променливите да се стави во некој од регистрите , потоа планирањето на меморија и селекцијата и распоредот на соодветните машински инструкции заедно со дадените адреси.

Постоењето на интерпроцедуралната анализа и оптимизација е вообичаена за компајлерите од IBM, SGI, Intel, Microsoft и Sun Microsystem.


[уреди] Пример за компајлер

Следнава програма презентира многу прост компајлер напишан во C. Овој компајлер компајлира изрази дефинирани со infix нотација во postfix нотација. Овој компајлер користи рекурзивна стратегија, која се препознава по тоа што секоја функција кореспондира со нетерминален симбол во јазичната граматика.


#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define MODE_POSTFIX    0
#define MODE_ASSEMBLY   1
char    lookahead;
int     pos;
int     compile_mode;
char    expression[20+1];
void error()
{
       printf("Syntax error!\n");
}
void match( char t )
{
       if( lookahead == t )
       {
               pos++;
               lookahead = expression[pos];            
       }
       else
               error();
}
void digit()
{
       switch( lookahead )
       {
               case '0':
               case '1':
               case '2':
               case '3':
               case '4':
               case '5':
               case '6':
               case '7':
               case '8':
               case '9':
                       if( compile_mode == MODE_POSTFIX )
                               printf("%c", lookahead);
                       else
                               printf("\tPUSH %c\n", lookahead);                     
                       
                       match( lookahead );
                       break;
               default:
                       error();
                       break;
       }
}
void term()
{
       digit();
       while(1)
       {
               switch( lookahead )
               {
                       case '*':
                               match('*');
                               digit();
                                                               
                               printf( "%s", compile_mode == MODE_POSTFIX ? "*" 
                                       : "\tPOP B\n\tPOP A\n\tMUL A, B\n\tPUSH A\n");
                                       
                               break;
                       case '/':
                               match('/');
                               digit();
                               printf( "%s", compile_mode == MODE_POSTFIX ? "/" 
                                       : "\tPOP B\n\tPOP A\n\tDIV A, B\n\tPUSH A\n");
                               break;
                       default:
                               return;
               }
       }
}
void expr()
{
       term();
       while(1)
       {
               switch( lookahead )
               {
                       case '+':
                               match('+');
                               term();
                               
                               printf( "%s", compile_mode == MODE_POSTFIX ? "+" 
                                       : "\tPOP B\n\tPOP A\n\tADD A, B\n\tPUSH A\n");
                               break;
                       case '-':
                               match('-');
                               term();
                               printf( "%s", compile_mode == MODE_POSTFIX ? "-" 
                                       : "\tPOP B\n\tPOP A\n\tSUB A, B\n\tPUSH A\n");
                               break;
                       default:
                               return;
               }
       }
}
int main ( int argc, char** argv )
{
       printf("Please enter an infix-notated expression with single digits:\n\n\t");
       scanf("%20s", expression);
       
       printf("\nCompiling to postfix-notated expression:\n\n\t");   
       compile_mode = MODE_POSTFIX;
       pos = 0;
       lookahead = *expression;
       expr();
               
       printf("\n\nCompiling to assembly-notated machine code:\n\n");        
       compile_mode = MODE_ASSEMBLY;
       pos = 0;
       lookahead = *expression;
       expr();
       return 0;
}

Можен излез на програмата

Please enter an infix-notated expression with single digits:
       3-4*2+2
Compiling to postfix-notated expression:
       342*-2+
Compiling to assembly-notated machine code:
       PUSH 3
       PUSH 4
       PUSH 2
       POP B
       POP A
       MUL A, B
       PUSH A
       POP B
       POP A
       SUB A, B
       PUSH A
       PUSH 2
       POP B
       POP A
       ADD A, B
       PUSH A


[уреди] Референци

  • Compiler textbook references A collection of references to mainstream Compiler Construction Textbooks
  • Compilers: Principles, Techniques and Tools by Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ullman (ISBN 0-201-10088-6) is considered to be the standard authority on compiler basics (undergraduate level), and makes a good primer for the techniques mentioned above. (It is often called the Dragon Book because of the picture on its cover showing a Knight of Programming fighting the Dragon of Compiler Design.) link to publisher
  • Advanced Compiler Design and Implementation by Steven Muchnick (ISBN 1-55860-320-4). One of the widely-used text books for advanced compiler courses (graduate level).
  • Engineering a Compiler by Keith D. Cooper and Linda Torczon . Morgan Kaufmann 2004, ISBN 1-55860-699-8. This is a very practical compiler book.
  • Understanding and Writing Compilers: A Do It Yourself Guide (ISBN 0-333-21732-2) by Richard Bornat is an unusually helpful book, being one of the few that adequately explains the recursive generation of machine instructions from a parse tree. The authors experience from the early days of mainframes and minicomputers, provides useful insights that more recent books often fail to convey.
  • An Overview of the Production Quality Compiler-Compiler Project by Leverett, Cattel, Hobbs, Newcomer, Reiner, Schatz and Wulf. Computer 13(8):38-49 (August 1980)
  • Compiler Construction by Niklaus Wirth (ISBN 0-201-40353-6) Addison-Wesley 1996, 176 pages, also available at [3]. Step-by-step guide to using recursive descent parser. Describes a compiler for Oberon-0, a subset of the author's programming language, Oberon.
  • "Programming Language Pragmatics" by Michael Scott (ISBN 0-12-633951-1) Morgan Kaufmann 2005, 2nd edition, 912 pages. This book offers a broad and in-depth introduction to compilation techniques and programming languages, illustrated with many examples. More information on the book can be found at the author's site.
  • "A History of Language Processor Technology in IBM", by F.E. Allen, IBM Journal of Research and Development, v.25, no.5, September 1981.mk:Компајлер