Програмски преведувач
Програмски преведувач или компајлер (од англиски: compiler) е сметачки програм (или множество програми) кои го преведуваат текстот напишан во т.н. сметачки јазик (изворен јазик) во друг сметачки јазик- целниот јазик. Оригиналниот текст којшто му го даваме на сметачот да го преведе се нарекува изворен код, додека излезниот код се нарекува објектен код. Обично излезот е во форма со која можат да се обработуваат други програми, но може да биде и форма читлива за човекот-текстуална податотека.
Најзначајна причина поради која би сакале да го преведеме изворниот код е да создадеме т.н. извршна програма. Името ’компајлер’ првично се користело за преведување на кодови од вишите програмски јазици во нижи програмски јазици, на пример од асемблерски јазик во машински јазик. Додека програмот којшто преведува од нижи програмски јазици во виши се нарекува декомпајлер.
Обично компајлерот ги изведува следниве активности: лексичка анализа, предобработка, расчленување, семантичка анализа, оптимизација на кодот, создавање на код.
Историја
уредиСофтверот за првите сметачи се пишувал во асемблерски јазик многу години. Вишите програмски јазици не беа измислени сè додека не се доби поволноста тие да се користат на различни видови 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.
Преден крај
уредиВо фазата Преден крај се анализира изворниот код за да сеизгради интерна репрезентација на програмата, наречена Интермедиална Репрезрнтација или ИР . Исто така се работи со табелата на симболи којашто е податочна структура која секој симбол од изворниот код му ја придава информацијата како локација и тип. Тоа се прави во неколку фази, меѓу кои ги вклучува и следниве:
- Реконструкција на редовите - јазиците кои ги категоризираат нивните клучни зборови и дозволуваат празни места меѓу идентификаторите имаат потреба од фаза пред расчленувањето, којашто ги претвора влезните знаци во канонична форма подготвена за расчленувачот. Надолниот рекурзивен расчленувач кој користи табела користен во 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.