Historia budowy kompilatora - History of compiler construction

W informatyce , o kompilator to program komputerowy , który przekształca kod źródłowy napisany w języku programowania lub języka komputerze ( język źródłowy ) na inny język komputerze ( języka docelowego , często mając binarną postać znaną jako kodu obiektowego lub kodu maszynowego ). Najczęstszym powodem przekształcania kodu źródłowego jest stworzenie programu wykonywalnego .

Każdy program napisany w języku programowania wysokiego poziomu musi zostać przetłumaczony na kod wynikowy przed jego wykonaniem, więc wszyscy programiści używający takiego języka używają kompilatora lub interpretera . Dlatego kompilatory są bardzo ważne dla programistów. Ulepszenia kompilatora mogą prowadzić do dużej liczby ulepszonych funkcji w programach wykonywalnych.

Produkcja Jakość Generator Parserów , pod koniec 1970 roku, wprowadzono zasady organizacji kompilatora, które są nadal powszechnie stosowane (np front-end obsługi składni i semantyki i back-end generowania kodu maszynowego).

Pierwsze kompilatory

Oprogramowanie dla wczesnych komputerów było pisane głównie w języku asemblera , a wcześniej bezpośrednio w kodzie maszynowym . Dla programisty zazwyczaj bardziej produktywne jest używanie języka wysokiego poziomu, a programy napisane w języku wysokiego poziomu mogą być ponownie wykorzystywane na różnych rodzajach komputerów . Mimo to kompilatorom zajęło trochę czasu, aby się ugruntować, ponieważ generowały kod, który nie działał tak dobrze, jak ręcznie napisany asembler, same w sobie były zniechęcającymi projektami programistycznymi, a bardzo ograniczona pojemność pamięci wczesnych komputerów stworzyła wiele problemy techniczne dla praktycznych implementacji kompilatorów.

Pierwszy praktyczny kompilator został napisany przez Corrado Böhma w 1951 r. na potrzeby jego pracy doktorskiej . Pierwszy zaimplementowany kompilator został napisany przez Grace Hopper , która również ukuła termin „kompilator”, odnosząc się do jej systemu A-0, który funkcjonował jako loader lub linker , a nie współczesne pojęcie kompilatora. Pierwszy Autokod i kompilator we współczesnym znaczeniu zostały opracowane przez Alicka Glennie w 1952 roku na Uniwersytecie w Manchesterze dla komputera Mark 1 . Zespół FORTRAN kierowany przez Johna W. Backusa z IBM wprowadził w 1957 roku pierwszy komercyjnie dostępny kompilator, którego stworzenie zajęło 18 osobolat.

Pierwszy kompilator ALGOL 58 został ukończony pod koniec 1958 roku przez Friedricha L. Bauera , Hermanna Bottenbrucha, Heinza Rutishausera i Klausa Samelsona dla komputera Z22 . Bauer i in. w poprzednich latach pracował nad technologią kompilatora dla Sequentielle Formelübersetzung (tj. sekwencyjnego tłumaczenia formuł ).

Do 1960 roku rozszerzony kompilator Fortran, ALTAC, był dostępny na Philco 2000, więc jest prawdopodobne, że program Fortran został skompilowany zarówno dla architektur komputerowych IBM, jak i Philco w połowie 1960 roku. Pierwszym znanym zademonstrowanym wieloplatformowym językiem wysokiego poziomu był COBOL . Podczas demonstracji w grudniu 1960 r. program COBOL został skompilowany i uruchomiony zarówno na UNIVAC II, jak i RCA 501.

Kompilatory samoobsługowe

Jak każde inne oprogramowanie, implementacja kompilatora w języku wysokiego poziomu przynosi korzyści. W szczególności kompilator może być samohostowany – to znaczy napisany w języku programowania, który kompiluje. Budowanie samohostującego się kompilatora jest problemem z ładowaniem początkowym , tzn. pierwszy taki kompilator dla danego języka musi być albo ręcznie napisanym kodem maszynowym, albo skompilowany przez kompilator napisany w innym języku, albo skompilowany przez uruchomienie kompilatora w interpreterze .

Praca doktorska Corrado Böhma

Corrado Böhm opracował język, maszynę i metodę tłumaczenia do kompilacji tego języka na maszynie w swojej pracy doktorskiej z 1951 r. Nie tylko opisał kompletny kompilator, ale także po raz pierwszy zdefiniował ten kompilator w jego własnym języku. Język sam w sobie był interesujący, ponieważ każda instrukcja (w tym instrukcje wejściowe, instrukcje wyjściowe i instrukcje sterujące) była szczególnym przypadkiem instrukcji przypisania .

NELIAC

Navy Electronics Laboratory Międzynarodowy ALGOL Compiler lub NELIAC był dialekt i kompilator realizacja ALGOL 58 język programowania opracowany przez Naval Electronics Laboratory w 1958 roku.

NELIAC był pomysłem Harry'ego Huskeya — ówczesnego przewodniczącego ACM i znanego informatyka (a później naukowego kierownika Niklausa Wirtha ), wspierany przez Maury Halsteada, szefa centrum obliczeniowego w NEL. Najwcześniejsza wersja została zaimplementowana na prototypowym komputerze USQ-17 (zwanym hrabiną) w laboratorium. Był to pierwszy na świecie samokompilujący się kompilator - kompilator został najpierw zakodowany w uproszczonej formie w języku asemblerowym ( bootstrap ), następnie przepisany we własnym języku i skompilowany przez bootstrap, a w końcu ponownie sam skompilowany, tworząc bootstrap przestarzały.

Seplenienie

Inny wczesny samohostujący się kompilator został napisany dla Lispa przez Tima Harta i Mike'a Levina z MIT w 1962 roku. Napisali kompilator Lispu w Lispie, testując go wewnątrz istniejącego interpretera Lispu. Po ulepszeniu kompilatora do punktu, w którym mógł skompilować własny kod źródłowy, stał się on samoobsługowy.

Kompilator w postaci, w jakiej istnieje na standardowej taśmie kompilatora, jest programem w języku maszynowym, który został uzyskany dzięki definicji wyrażenia S kompilatora działającego na sobie za pośrednictwem interpretera. (Notatka AI 39)

Ta technika jest możliwa tylko wtedy, gdy istnieje już interpreter dla tego samego języka, który ma być skompilowany. Zapożycza bezpośrednio z pojęcia uruchamiania programu jako danych wejściowych, które jest również używane w różnych dowodach w informatyce teoretycznej , takich jak dowód, że problem zatrzymania jest nierozstrzygnięty .

Naprzód

Forth jest przykładem kompilatora samoobsługującego. Funkcje autokompilacji i kompilacji krzyżowej Forth są często mylone z metakompilacją i metakompilatorami . Podobnie jak Lisp , Forth jest rozszerzalnym językiem programowania . To rozszerzalne funkcje języków programowania Forth i Lisp umożliwiają im generowanie nowych wersji samych siebie lub przenoszenie się do nowych środowisk.

Gramatyki i parsery bezkontekstowe

Parser jest ważnym składnikiem kompilatora. Analizuje kod źródłowy języka programowania komputerowego, aby stworzyć jakąś formę reprezentacji wewnętrznej. Języki programowania są zwykle określane w kategoriach gramatyki bezkontekstowej, ponieważ można dla nich napisać szybkie i wydajne parsery. Parsery mogą być pisane ręcznie lub generowane przez generator parserów . Gramatyka bezkontekstowa zapewnia prosty i precyzyjny mechanizm opisywania, w jaki sposób konstrukcje języka programowania są budowane z mniejszych bloków . Formalizm gramatyk bezkontekstowych został opracowany w połowie lat pięćdziesiątych przez Noama Chomsky'ego .

Struktura blokowa została wprowadzona do języków programowania komputerowego przez projekt ALGOL (1957-1960), który w konsekwencji zawierał również gramatykę bezkontekstową do opisu powstałej składni ALGOL.

Gramatyki bezkontekstowe są na tyle proste, że umożliwiają konstruowanie wydajnych algorytmów parsowania, które dla danego łańcucha określają, czy i jak można go wygenerować z gramatyki. Jeśli projektant języka programowania chce pracować z pewnymi ograniczonymi podzbiorami gramatyk bezkontekstowych, możliwe są bardziej wydajne parsery.

Parsowanie LR

Parser LR (od lewej do prawej) został wynaleziony przez Donald Knuth w 1965 roku w artykule „O tłumaczeniu Języków od lewej do prawej”. Parser LR jest parser, który odczytuje dane wejściowe z L EFT do prawej (jak wydaje się, jeżeli wyświetlany wizualnie) i tworzy R wyprowadzenie ightmost . Termin parser LR( k ) jest również używany, gdzie k odnosi się do liczby nieużywanych symboli wejściowych z wyprzedzeniem, które są używane przy podejmowaniu decyzji dotyczących analizy.

Knuth udowodnił, że gramatyki LR( k ) mogą być parsowane z czasem wykonania zasadniczo proporcjonalnym do długości programu, oraz że każda gramatyka LR( k ) dla k  > 1 może być mechanicznie przekształcona w gramatykę LR(1) dla tego samego język. Innymi słowy, do przeanalizowania dowolnej deterministycznej gramatyki bezkontekstowej (DCFG) wystarczy mieć tylko jeden symbol lookahead .

Korenjak (1969) jako pierwszy pokazał parsery języków programowania, które mogą być tworzone przy użyciu tych technik. Frank DeRemer opracował bardziej praktyczne techniki Simple LR (SLR) i Look-ahead LR (LALR), opublikowane w jego rozprawie doktorskiej na MIT w 1969 roku. Był to ważny przełom, ponieważ tłumacze LR(k), zgodnie z definicją Donalda Knutha, były zbyt duże do wdrożenia w systemach komputerowych w latach 60. i 70. XX wieku.

W praktyce LALR oferuje dobre rozwiązanie; dodatkowa moc parserów LALR(1) w stosunku do parserów SLR(1) (to znaczy, LALR(1) może analizować bardziej złożone gramatyki niż SLR(1)) jest przydatna i chociaż LALR(1) nie jest porównywalny z LL( 1) (Patrz poniżej) (LALR (1) nie może przeanalizować wszystkich gramatyk LL (1)), większość gramatyk LL (1) napotkanych w praktyce może zostać przeanalizowanych przez LALR (1). Gramatyki LR(1) są znowu bardziej wydajne niż LALR(1); jednak gramatyka LR(1) wymaga kanonicznego parsera LR, który byłby bardzo duży i nie jest uważany za praktyczny. Składnia wielu języków programowania jest zdefiniowana przez gramatyki, które mogą być analizowane za pomocą parsera LALR(1) iz tego powodu parsery LALR są często używane przez kompilatory do przeprowadzania analizy składni kodu źródłowego.

A rekurencyjne wynurzania parser narzędzia parser LALR użyciu funkcji wzajemnie cyklicznych zamiast tabelach. W ten sposób parser jest bezpośrednio zakodowany w języku hosta, podobnie jak w przypadku rekursywnego pochodzenia . Kodowanie bezpośrednie zwykle daje parser, który jest szybszy niż jego odpowiednik oparty na tabeli z tego samego powodu, dla którego kompilacja jest szybsza niż interpretacja. Jest również (w zasadzie) możliwa ręczna edycja parsera rekurencyjnego ascent, podczas gdy implementacja tabelaryczna jest prawie nieczytelna dla przeciętnego człowieka.

Rekursywne wynurzanie zostało po raz pierwszy opisane przez Thomasa Pennello w jego artykule „Very fast LR parsing” w 1986 roku. Technikę tę przedstawił później GH Roberts w 1988 roku, a także w artykule Leermakers, Augusteijn, Kruseman Aretz w 1992 roku w czasopiśmie Theoretical Informatyka .

Parsowanie LL

Parser ll przetwarza sygnał wejściowy z L EFT do prawej i tworzy L wyprowadzenie eftmost zdania (LL stąd, w przeciwieństwie do R). Klasa gramatyk, które można przeanalizować w ten sposób, jest znana jako gramatyki LL . Gramatyki LL są jeszcze bardziej ograniczoną klasą gramatyk bezkontekstowych niż gramatyki LR. Niemniej jednak cieszą się dużym zainteresowaniem twórców kompilatorów, ponieważ taki parser jest prosty i wydajny w implementacji.

Gramatyki LL(k) mogą być analizowane przez rekurencyjny parser zstępujący, który jest zwykle kodowany ręcznie, chociaż alternatywnie może być używana notacja taka jak META II .

Projekt ALGOL zapoczątkował badania nad rekurencyjnym pochodzeniem, ponieważ sam język ALGOL jest rekurencyjny. Pojęcie parsowania rekurencyjnego opadania zostało omówione w styczniowym numerze Communications of the ACM w osobnych artykułach AA Grau i Edgara T. „Neda” Ironsa . Richard Waychoff i jego współpracownicy również zaimplementowali opadanie rekurencyjne w kompilatorze Burroughs ALGOL w marcu 1961 r. Obie grupy stosowały różne podejścia, ale pozostawały w przynajmniej nieformalnym kontakcie.

Ideę gramatyk LL(1) wprowadzili Lewis i Stearns (1968).

Pochodzenie rekurencyjne zostało spopularyzowane przez Niklausa Wirtha z PL/0 , edukacyjnym językiem programowania używanym do nauki budowy kompilatorów w latach 70-tych.

Parsowanie LR może obsługiwać większy zakres języków niż parsowanie LL , a także jest lepsze w raportowaniu błędów (jest to dyskusyjne, wymagane jest REFERENCE), tj. wykrywa błędy składniowe, gdy dane wejściowe nie są zgodne z gramatykami tak szybko, jak to możliwe.

Parser Earleya

W 1970 roku Jay Earley wynalazł coś, co stało się znane jako parser Earleya . Parsery Earleya są atrakcyjne, ponieważ mogą dość wydajnie analizować wszystkie języki bezkontekstowe .

Języki opisu gramatyki

John Backus zaproponował „formuły metajęzykowe” opisujące składnię nowego języka programowania IAL, znanego dziś jako ALGOL 58 (1959). Praca Backusa opierała się na systemie kanonicznym Posta autorstwa Emila Posta .

Dalszy rozwój ALGOL doprowadził do ALGOL 60 ; w swoim raporcie (1963) Peter Naur nazwał notację Backusa formą normalną Backus (BNF) i uprościł ją, aby zminimalizować używany zestaw znaków. Donald Knuth przekonywał jednak, że BNF należy raczej odczytywać jako formę Backusa–Naura , co stało się powszechnie akceptowane.

Niklaus Wirth zdefiniował rozszerzoną formę Backusa-Naura (EBNF), udoskonaloną wersję BNF, na początku lat 70. dla PL/0. Kolejnym wariantem jest rozszerzona forma Backusa-Naura (ABNF). Zarówno EBNF, jak i ABNF są szeroko stosowane do określania gramatyki języków programowania, jako dane wejściowe do generatorów parserów oraz w innych dziedzinach, takich jak definiowanie protokołów komunikacyjnych.

Generatory parserów

Parser generator wytwarza część słownikowa analizatorze kompilatora. Jest to program, który pobiera opis gramatyki formalnej określonego języka programowania i tworzy parser dla tego języka. Ten parser może być używany w kompilatorze dla tego konkretnego języka. Parser wykrywa i identyfikuje zastrzeżone słowa i symbole określonego języka ze strumienia tekstu i zwraca je jako tokeny do kodu, który implementuje walidację składniową i translację na kod obiektowy. Ta druga część kompilatora może być również utworzona przez kompilator-kompilator przy użyciu formalnego opisu składni reguł pierwszeństwa jako danych wejściowych.

Pierwszy kompilator-kompilator, który używał tej nazwy, został napisany przez Tony'ego Brookera w 1960 roku i był używany do tworzenia kompilatorów dla komputera Atlas na Uniwersytecie w Manchesterze , w tym kompilatora Atlas Autocode . Jednak różnił się on raczej od nowoczesnych kompilatorów-kompilatorów, a dziś prawdopodobnie zostałby opisany jako gdzieś pomiędzy wysoce konfigurowalnym kompilatorem generycznym a językiem rozszerzalnym składni . Nazwa „kompilator-kompilator” była o wiele bardziej odpowiednia dla systemu Brookera niż dla większości nowoczesnych kompilatorów-kompilatorów, które są dokładniej opisane jako generatory parserów. Jest prawie pewne, że nazwa „Compiler-Compiler” weszła do powszechnego użytku ze względu na to, że pamięta się raczej Yacc niż pracę Brookera.

We wczesnych latach 60. Robert McClure z Texas Instruments wynalazł kompilator-kompilator o nazwie TMG , nazwa zaczerpnięta od „transmogryfikacji”. W kolejnych latach TMG zostało przeniesione na kilka komputerów mainframe UNIVAC i IBM.

Projekt Multics , wspólne przedsięwzięcie MIT i Bell Labs , był jednym z pierwszych, który opracował system operacyjny w języku wysokiego poziomu. Jako język wybrano PL/I , ale zewnętrzny dostawca nie mógł dostarczyć działającego kompilatora. Zespół Multics opracował własny podzbiór dialektu PL/I znany jako Early PL/I (EPL) jako język implementacji w 1964 roku. TMG został przeniesiony do serii GE-600 i wykorzystany do opracowania EPL przez Douglasa McIlroya , Roberta Morrisa i innych .

Niedługo po tym, jak Ken Thompson napisał pierwszą wersję Uniksa dla PDP-7 w 1969 roku, Douglas McIlroy stworzył pierwszy język wyższego poziomu dla nowego systemu: implementację TMG firmy McClure. TMG było także narzędziem do definiowania kompilatorów używanym przez Kena Thompsona do napisania kompilatora dla języka B na jego PDP-7 w 1970 roku. B był bezpośrednim przodkiem C .

Wczesny generator parserów LALR nazywał się „TWS”, stworzony przez Franka DeRemera i Toma Pennello.

XPL

XPL to dialekt języka programowania PL/I , używany do tworzenia kompilatorów języków komputerowych. Został zaprojektowany i wdrożony w 1967 roku przez zespół z Williamem M. McKeemanem , Jamesem J. Horningiem i Davidem B. Wortmanem na Uniwersytecie Stanforda i Uniwersytecie Kalifornijskim w Santa Cruz . Po raz pierwszy ogłoszono to na jesiennej konferencji komputerowej w San Francisco w 1968 roku .

XPL zawierał stosunkowo prosty system pisania tłumacza nazwany ANALYZER , oparty na oddolnej technice parsowania pierwszeństwa kompilatora zwanej MSP (mixed strategy precedence). XPL został załadowany przez Burroughs Algol do komputera IBM System/360 . (Niektóre kolejne wersje XPL używane w projektach wewnętrznych Uniwersytetu w Toronto wykorzystywały parser SLR(1), ale te implementacje nigdy nie były rozpowszechniane).

Yacc

Yacc to generator parserów (w skrócie kompilator-kompilator ), którego nie należy mylić z lex , który jest analizatorem leksykalnym często używanym jako pierwszy etap przez Yacc. Yacc został opracowany przez Stephena C. Johnsona w AT&T dla systemu operacyjnego Unix . Nazwa jest akronimem od „ Jeszcze inny kompilator kompilatora ”. Generuje kompilator LALR(1) na podstawie gramatyki zapisanej w notacji podobnej do formy Backusa-Naura.

Johnson pracował nad Yacc na początku lat 70. w Bell Labs . Znał TMG, a jego wpływ widać w Yacc i projektowaniu języka programowania C. Ponieważ Yacc był domyślnym generatorem kompilatora w większości systemów uniksowych, był szeroko rozpowszechniany i używany. Pochodne, takie jak GNU Bison, są nadal w użyciu.

Kompilator generowany przez Yacc wymaga analizatora leksykalnego . Generatory analizatorów leksykalnych, takie jak lex lub flex, są powszechnie dostępne. Standard IEEE POSIX P1003.2 definiuje funkcjonalność i wymagania zarówno dla Lex, jak i Yacc.

Coco/R

Coco/R to generator parserów, który generuje parsery LL(1) w Modula-2 (z wtyczkami dla innych języków) z gramatyk wejściowych napisanych w wariancie EBNF. Został opracowany przez Hanspetera Mössenböcka w Szwajcarskim Federalnym Instytucie Technologii w Zurychu (ETHZ) w 1985 roku.

ANTLR

ANTLR to generator parserów, który generuje parsery LL(*) w Javie z gramatyk wejściowych napisanych w wariancie EBNF. Został opracowany przez Terence'a Parra na Uniwersytecie w San Francisco na początku lat 90. jako następca wcześniejszego generatora o nazwie PCCTS.

Metakompilatory

Metakompilatory różnią się od generatorów parserów, przyjmując jako dane wejściowe program napisany w metajęzyku . Ich dane wejściowe składają się z formuły analizy gramatycznej połączonej z osadzonymi operacjami przekształcania, które konstruują abstrakcyjne drzewa składni lub po prostu wyprowadzają przeformatowane ciągi tekstowe, które mogą być kodem maszynowym stosu.

Wiele z nich można zaprogramować we własnym metajęzyku, umożliwiając im samodzielną kompilację, dzięki czemu są samoobsługowymi, rozszerzalnymi kompilatorami języka.

Wiele metakompilatorów opiera się na pracy Deweya Val Schorre'a . Jego kompilator META II , wydany po raz pierwszy w 1964 roku, był pierwszym udokumentowanym metakompilatorem. Potrafi zdefiniować własny język i inne, META II zaakceptował formułę składniową z osadzonym wyjściem (produkcja kodu) . Przekłada się również na jedną z najwcześniejszych instancji maszyny wirtualnej . Analizę leksykalną przeprowadzono za pomocą wbudowanych funkcji rozpoznających tokeny: .ID, .STRING oraz .NUMBER. Cytowane ciągi znaków w formule składni rozpoznają leksemy, które nie są przechowywane.

TREE-META , metakompilator Schorre'a drugiej generacji, pojawił się około 1968 roku. Rozszerzył możliwości META II, dodając reguły nieprzetwarzania, oddzielające tworzenie kodu od analizy gramatycznej. Operacje przekształcania drzewa w formule składni dają abstrakcyjne drzewa składni , na których działają reguły unparsowania. Dopasowanie wzorca drzewa unparse zapewniło możliwość optymalizacji wizjera .

CWIC , opisany w publikacji ACM z 1970 roku, jest metakompilatorem Schorre'a trzeciej generacji, który dodał do analizy gramatycznej reguły leksykania i operatory wycofywania. LISP 2 ożenił się z nieparzystymi regułami TREEMETA w języku generatora CWIC. Dzięki przetwarzaniu LISP 2[[]], CWIC może generować w pełni zoptymalizowany kod. CWIC zapewnił również generowanie kodu binarnego w nazwanych sekcjach kodu. Kompilacje jedno- i wieloprzebiegowe mogą być realizowane przy użyciu CWIC.

CWIC skompilowany do 8-bitowych instrukcji kodu maszynowego adresowalnych bajtów, zaprojektowanych głównie do tworzenia kodu IBM System/360.

Późniejsze pokolenia nie są publicznie udokumentowane. Jedną z ważnych cech jest abstrakcja zestawu instrukcji procesora docelowego, generowanie do pseudozestawu instrukcji maszynowych makr, które mogą być oddzielnie definiowane lub mapowane na instrukcje rzeczywistej maszyny. Optymalizacje mające zastosowanie do instrukcji sekwencyjnych można następnie zastosować do pseudoinstrukcji przed ich rozwinięciem do docelowego kodu maszynowego.

Kompilacja krzyżowa

Krzyż kompilator działa w jednym środowisku, ale produkuje kod obiektu na inny. Kompilatory krzyżowe są używane do tworzenia aplikacji wbudowanych, gdy komputer docelowy ma ograniczone możliwości.

Wczesnym przykładem kompilacji krzyżowej było AIMICO, gdzie program FLOW-MATIC na UNIVAC II został użyty do wygenerowania języka asemblera dla IBM 705 , który został następnie zmontowany na komputerze IBM.

ALGOL 68C kompilator generowane ZCODE wyjście, które mogą następnie być albo kompilowane do kodu maszynowego lokalnej przez ZCODE tłumacza lub uruchomić interpretowane. ZCODE to język pośredni oparty na rejestrach. Ta umiejętność interpretacji lub kompilacji ZCODE zachęciła do przenoszenia ALGOL 68C na wiele różnych platform komputerowych.

Optymalizacja kompilatorów

Optymalizacja kompilatora to proces poprawiania jakości kodu wynikowego bez zmiany uzyskiwanych wyników.

Twórcy pierwszego kompilatora FORTRAN mieli na celu wygenerowanie kodu , który byłby lepszy niż przeciętny ręcznie pisany asembler, tak aby klienci faktycznie korzystali z ich produktu. W jednym z pierwszych prawdziwych kompilatorów często im się to udawało.

Późniejsze kompilatory, takie jak kompilator IBM Fortran IV , kładły większy nacisk na dobrą diagnostykę i szybsze wykonywanie, kosztem optymalizacji kodu wynikowego. Dopiero w serii IBM System/360 IBM dostarczył dwa oddzielne kompilatory — szybko działający kontroler kodu i wolniejszy, optymalizujący.

Frances E. Allen , pracując samodzielnie i wspólnie z Johnem Cocke , wprowadziła wiele koncepcji optymalizacji. Artykuł Allena z 1966 r., Optymalizacja programu, wprowadził wykorzystanie grafowych struktur danych do kodowania zawartości programu w celu optymalizacji. Jej artykuły z 1970 roku, Control Flow Analysis i A Basis for Program Optimization, ustanowiły interwały jako kontekst dla wydajnej i efektywnej analizy i optymalizacji przepływu danych. Jej praca z 1971 roku z Cocke, A Catalog of Optimizing Transformations , dostarczyła pierwszego opisu i systematyzacji transformacji optymalizujących. Jej artykuły z 1973 i 1974 dotyczące międzyproceduralnej analizy przepływu danych rozszerzyły analizę na całe programy. Jej artykuł z 1976 roku wraz z Cocke'em opisuje jedną z dwóch głównych strategii analitycznych stosowanych obecnie w optymalizacji kompilatorów.

Allen opracowała i zaimplementowała swoje metody jako część kompilatorów dla IBM 7030 Stretch - Harvest i eksperymentalnego Advanced Computing System . Prace te pozwoliły ustalić wykonalność i strukturę nowoczesnych optymalizatorów niezależnych od maszyny i języka. Następnie założyła i poprowadziła projekt PTRAN dotyczący automatycznego równoległego wykonywania programów FORTRAN. Jej zespół PTRAN opracował nowe schematy wykrywania równoległości i stworzył koncepcję grafu zależności programu, podstawowej metody strukturyzacji używanej przez większość kompilatorów zrównoleglonych.

Języki programowania i ich kompilatory Johna Cocke'a i Jacoba T. Schwartza , opublikowane na początku 1970 roku, poświęciły ponad 200 stron algorytmom optymalizacji. Zawierał wiele znanych obecnie technik, takich jak eliminacja nadmiarowego kodu i redukcja siły działania .

Optymalizacja wizjera

Optymalizacja wizjera to prosta, ale skuteczna technika optymalizacji. Został wynaleziony przez Williama M. McKeemana i opublikowany w 1965 roku w CACM. Został użyty w kompilatorze XPL, który McKeeman pomógł opracować.

Optymalizator CAPEX COBOL

Firma Capex Corporation opracowała „COBOL Optimizer” w połowie lat 70. dla COBOL . Ten typ optymalizatora zależał w tym przypadku od znajomości "słabości" w standardowym kompilatorze IBM COBOL i faktycznie zastępował (lub załatał ) sekcje kodu wynikowego bardziej wydajnym kodem. Kod wymiana może zastąpić liniowej odnośnika tabeli z binarnego wyszukiwania , na przykład, a czasem po prostu zastąpić stosunkowo „wolno” instrukcją ze znaną szybciej, którą można było inaczej funkcjonalny odpowiednik w jego kontekście. Ta technika jest obecnie znana jako „ redukcja siły ”. Na przykład na sprzęcie IBM System/360 instrukcja CLI była, w zależności od konkretnego modelu, od 2 do 5 razy szybsza niż instrukcja CLC dla porównań jednobajtowych.

Nowoczesne kompilatory zazwyczaj udostępniają opcje optymalizacji, aby umożliwić programistom wybór, czy wykonać przebieg optymalizacji.

Diagnostyka

Gdy kompilator otrzymuje program niepoprawny składniowo, pomocny jest dobry, jasny komunikat o błędzie. Z perspektywy autora kompilatora często jest to trudne do osiągnięcia.

WATFIV Fortran kompilator został opracowany na Uniwersytecie Waterloo w Kanadzie pod koniec 1960 roku. Został zaprojektowany, aby dawać lepsze komunikaty o błędach niż kompilatory IBM Fortran z tamtych czasów. Ponadto WATFIV był znacznie bardziej użyteczny, ponieważ łączy kompilację, łączenie i wykonanie w jednym kroku, podczas gdy kompilatory IBM miały do ​​uruchomienia trzy oddzielne komponenty.

PL/C

PL/C był językiem programowania komputerowego opracowanym na Uniwersytecie Cornell we wczesnych latach siedemdziesiątych. Chociaż PL/C był podzbiorem języka IBM PL/I, został zaprojektowany z myślą o wykorzystaniu do nauczania programowania. Dwóch badaczy i nauczycieli akademickich, którzy zaprojektowali PL/C, to Richard W. Conway i Thomas R. Wilcox. Zgłosili słynny artykuł „Projektowanie i implementacja kompilatora diagnostycznego dla PL/I” opublikowany w Komunikatach ACM w marcu 1973 roku.

PL/C wyeliminował niektóre z bardziej złożonych funkcji PL/I i dodał rozbudowane funkcje debugowania i odzyskiwania błędów. Kompilator PL/C miał niezwykłą zdolność kompilowania żadnego programu, dzięki zastosowaniu rozległej automatycznej korekty wielu błędów składniowych i konwersji wszelkich pozostałych błędów składniowych na instrukcje wyjściowe.

Kompilacja just-in-time

Kompilacja just-in-time (JIT) to generowanie kodu wykonywalnego w locie lub jak najbliżej jego rzeczywistego wykonania, aby skorzystać z metryk środowiska uruchomieniowego lub innych opcji zwiększających wydajność.

Przedstawicielstwo pośrednie

Większość nowoczesnych kompilatorów posiada leksykon i parser, które tworzą pośrednią reprezentację programu. Reprezentacja pośrednia to prosta sekwencja operacji, która może być użyta przez optymalizator i generator kodu, który wytwarza instrukcje w języku maszynowym procesora docelowego. Ponieważ generator kodu używa reprezentacji pośredniej, ten sam generator kodu może być używany dla wielu różnych języków wysokiego poziomu.

Istnieje wiele możliwości reprezentacji pośredniej. Kod trójadresowy , znany również jako czwórka lub czwórka, jest powszechną formą, w której występuje operator, dwa operandy i wynik. Kod dwuadresowy lub trójki mają stos, na którym zapisywane są wyniki, w przeciwieństwie do jawnych zmiennych kodu trzyadresowego.

Static Single Assignment (SSA) został opracowany przez Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman i F. Kenneth Zadeck , badacze IBM w latach osiemdziesiątych. W SSA zmienna otrzymuje wartość tylko raz. Zamiast modyfikować istniejącą tworzona jest nowa zmienna. SSA upraszcza optymalizację i generowanie kodu.

Generowanie kodu

Generator kodu generuje instrukcje języka maszynowego dla procesora docelowego.

Przydział rejestru

Algorytm Sethi-Ullmana lub numeracja Sethi-Ullmana to metoda minimalizacji liczby rejestrów potrzebnych do przechowywania zmiennych.

Znani kompilatorzy

Zobacz też

Bibliografia

Dalsza lektura

Zewnętrzne linki