Historie konstrukce překladače - History of compiler construction

Historie výpočtů
Hardware
Software
Počítačová věda
Moderní koncepty
Podle země
Časová osa výpočtu
Glosář počítačové vědy
  • Kategorie Kategorie

v výpočetní, a překladač je počítačový program který se transformuje zdrojový kód napsáno v a programovací jazyk nebo počítačový jazyk ( zdrojový jazyk), do jiného počítačového jazyka ( cílový jazyk, často s binární formou známou jako kód objektu nebo strojový kód ). Nejběžnějším důvodem pro transformaci zdrojového kódu je vytvoření spustitelný program.

Libovolný program napsaný v a programovací jazyk na vysoké úrovni musí být přeložen do objektového kódu, než může být spuštěn, takže všichni programátoři používající takový jazyk používají kompilátor nebo tlumočník. Překladače jsou tedy pro programátory velmi důležité. Vylepšení kompilátoru mohou vést k velkému počtu vylepšených funkcí ve spustitelných programech.

The Kompilátor kvality produkce - kompilátor na konci 70. let představil principy organizace překladačů, které se dnes ještě široce používají (např. front-end syntaxe a sémantika zpracování a back-end generující strojový kód).

První kompilátoři

Software pro starší počítače byl primárně napsán v montážní jazyk. Pro programátora je obvykle produktivnější používat jazyk na vysoké úrovni a programy psané v jazyce na vysoké úrovni mohou být znovu použit na různých druzích počítačů. Přesto překladačům trvalo nějakou dobu, než se ustálili, protože generovali kód, který nefungoval tak dobře jako ručně psaný assembler, sami od sebe skličovali vývojové projekty a velmi omezené Paměť kapacita starších počítačů způsobila mnoho technických problémů pro praktické implementace kompilátoru.

První praktický překladač napsal Corrado Böhm, v roce 1951, pro jeho Disertační práce. První implementovaný kompilátor napsal Grace Hopper, který také vytvořil termín „kompilátor“,[1][2] s odkazem na ni Systém A-0 který fungoval jako nakladač nebo linker, ne moderní pojem kompilátoru. První Automatický kód a překladač v moderním smyslu byly vyvinuty společností Alick Glennie v roce 1952 na University of Manchester pro Marek 1 počítač.[3][4] The FORTRAN tým vedený John W. Backus v IBM představil první komerčně dostupný kompilátor v roce 1957, jehož vytvoření trvalo 18 osoboroků.[5]

První ALGOL 58 překladač byl dokončen koncem roku 1958 autorem Friedrich L. Bauer, Hermann Bottenbruch, Heinz Rutishauser, a Klaus Samelson pro Z22 počítač. Bauer a kol. pracoval na technologii kompilátoru pro Sequentielle Formelübersetzung (tj. sekvenční překlad vzorců) v předchozích letech.

V roce 1960 byl na internetu k dispozici rozšířený překladač Fortran, ALTAC Philco 2000, takže je pravděpodobné, že byl vytvořen program Fortran pro IBM i Philco počítačové architektury v polovině roku 1960.[6] První známý prokázal napříč platformami jazyk na vysoké úrovni byl COBOL. Na demonstraci v prosinci 1960 byl program COBOL sestaven a proveden na obou UNIVAC II a RCA 501.[2]

Self-hosting kompilátory

Nesmí být zaměňována s Překladač překladač.

Stejně jako jakýkoli jiný software existují výhody implementace kompilátoru v jazyce na vysoké úrovni. Zejména může být kompilátor samoobslužný - tj. Napsaný v programovacím jazyce, který kompiluje. Vytváření kompilátoru pro vlastní hostování je a bootstrapping problém, tj. první takový kompilátor pro jazyk musí být buď ručně psaný strojový kód, nebo zkompilovaný kompilátorem napsaným v jiném jazyce, nebo zkompilovaný spuštěním kompilátoru v tlumočník.

Corrado Böhm disertační práce

Corrado Böhm vyvinul ve své disertační práci z roku 1951 jazyk, stroj a metodu překladu pro kompilaci tohoto jazyka na stroji. Popsal nejen úplného překladače, ale také poprvé definoval tento překladač ve svém vlastním jazyce. Jazyk byl sám o sobě zajímavý, protože každý příkaz (včetně vstupních, výstupních a řídicích) byl zvláštním případem prohlášení o zadání[Citace je zapotřebí ].

NELIAC

The Navy Electronics Laboratory International ALGOL Překladač nebo NELIAC byl dialekt a překladač implementace ALGOL 58 programovací jazyk vyvinutý společností Laboratoř námořní elektroniky v roce 1958.

NELIAC byl duchovním dítětem Harry Huskey - poté předseda ACM a dobře známý počítačový vědec (a později akademický školitel Niklaus Wirth ), a podporován Maury Halsteadem, vedoucím výpočetního centra v NEL. Nejstarší verze byla implementována na prototypu USQ-17 počítač (volal hraběnku) v laboratoři. Byl to první kompilátor na světě - kompilátor byl nejprve kódován ve zjednodušené podobě v assembleru ( bootstrap), poté přepsán ve svém vlastním jazyce a zkompilován bootstrapem a nakonec znovu zkompilován sám, čímž je bootstrap zastaralý.

Lisp

Další brzy vlastní hosting překladač byl napsán pro Lisp Tim Hart a Mike Levin v MIT v roce 1962.[7] Napsali kompilátor Lisp v Lispu a testovali jej uvnitř existujícího tlumočníka Lisp. Jakmile vylepšili kompilátor do bodu, kdy mohl kompilovat svůj vlastní zdrojový kód, byl to samohostitel.[8]

Kompilátor, jak existuje na standardní pásce kompilátoru, je program v strojovém jazyce, který byl získán pomocí S-výraz definice práce překladače na sobě prostřednictvím tlumočníka. (AI Memo 39)[8]

Tato technika je možná pouze v případě, že již existuje tlumočník pro stejný jazyk, který má být kompilován. Půjčuje si přímo z představy o spuštění programu jako vstupu, který se také používá v různých důkazech v teoretická informatika, například důkaz, že zastavení problému je nerozhodnutelný.

Forth

Forth je příklad kompilátoru s vlastním hostitelem. The vlastní kompilace a křížová kompilace rysy Forth jsou běžně zaměňovány metakompilace a metakompilery.[Citace je zapotřebí ] Jako Lisp, Forth je rozšiřitelné programování Jazyk. To je rozšiřitelné programování jazykové funkce Forth a Lisp, které jim umožňují generovat nové verze sebe samých nebo se přenášet do nových prostředí.

Bezkontextové gramatiky a analyzátory

A analyzátor je důležitou součástí kompilátoru. Analyzuje zdrojový kód počítačového programovacího jazyka a vytváří nějakou formu interní reprezentace. Programovací jazyky mají tendenci být specifikovány v podmínkách a bezkontextová gramatika protože pro ně lze napsat rychlé a efektivní analyzátory. Analyzátory lze psát ručně nebo generovat a generátor analyzátoru. Bezkontextová gramatika poskytuje jednoduchý a přesný mechanismus pro popis toho, jak jsou konstrukce programovacích jazyků vytvářeny z menších bloky. Formalismus bezkontextových gramatik byl vyvinut v polovině 50. let 20. století Noam Chomsky.[9]

Blokovou strukturu zavedl do počítačových programovacích jazyků projekt ALGOL (1957–1960), který v důsledku toho obsahoval také bezkontextovou gramatiku pro popis výsledné syntaxe ALGOL.

Bezkontextové gramatiky jsou natolik jednoduché, že umožňují konstrukci efektivních algoritmů syntaktické analýzy, které pro daný řetězec určují, zda a jak jej lze z gramatiky vygenerovat. Pokud je návrhář programovacího jazyka ochoten pracovat v rámci některých omezených podmnožin bezkontextových gramatik, jsou možné efektivnější analyzátory.

Analýza LR

Hlavní článek: Analyzátor LR

The Analyzátor LR (zleva doprava) vynalezl Donald Knuth v roce 1965 v příspěvku „O překladu jazyků zleva doprava“. An Analyzátor LR je analyzátor, který čte vstup z Left doprava (jak by to vypadalo, kdyby se zobrazilo vizuálně) a vytvoří a Rnejpravděpodobnější odvození. Termín LR (k) analyzátor se také používá, kde k odkazuje na počet nespotřebovaných dívat se dopředu vstupní symboly, které se používají při rozhodování o analýze.

Knuth dokázal, že LR (k) gramatiky lze analyzovat s časem provádění v podstatě úměrným délce programu a že každý LR (k) gramatika pro k > 1 lze mechanicky transformovat do gramatiky LR (1) pro stejný jazyk. Jinými slovy, k analýze libovolného je nutné mít pouze jeden vyhledávací symbol deterministická bezkontextová gramatika (DCFG).[10]

Korenjak (1969) jako první ukázal, že pomocí těchto technik lze vyrábět analyzátory programovacích jazyků.[11] Frank DeRemer vymyslel praktičtější Jednoduché LR (SLR) a Do budoucna LR (LALR) techniky, publikoval ve své disertační práci na MIT v roce 1969.[12][13] To byl důležitý průlom, protože překladače LR (k), jak je definoval Donald Knuth, byly příliš velké na implementaci do počítačových systémů v 60. a 70. letech.

V praxi nabízí LALR dobré řešení; přidaná síla analyzátorů LALR (1) nad analyzátory SLR (1) (to znamená, že LALR (1) dokáže analyzovat složitější gramatiky než SLR (1)), je užitečná, a přestože LALR (1) není srovnatelná s LL ( 1) (Viz níže) (LALR (1) nemůže analyzovat všechny gramatiky LL (1)), většinu gramatik LL (1), se kterými se v praxi setkáváme, lze analyzovat pomocí LALR (1). LR (1) gramatiky jsou opět výkonnější než LALR (1); gramatika LR (1) však vyžaduje a kanonický analyzátor LR který by byl extrémně velký a nepovažuje se za praktický. Syntaxe mnoha programovací jazyky jsou definovány gramatikami, které lze analyzovat pomocí analyzátoru LALR (1), a proto jsou analyzátory LALR často používány kompilátory k provádění syntaktické analýzy zdrojového kódu.

A analyzátor rekurzivního výstupu implementuje analyzátor LALR pomocí vzájemně rekurzivních funkcí spíše než tabulek. Analyzátor tedy je přímo zakódováno v hostitelském jazyce podobném jazyku rekurzivní sestup. Přímé kódování obvykle poskytuje analyzátor, který je rychlejší než jeho ekvivalent řízený tabulkou[14] ze stejného důvodu je kompilace rychlejší než interpretace. Je také (v zásadě) možné ručně upravit rekurzivní analyzátor výstupu, zatímco tabulková implementace je pro průměrného člověka téměř nečitelná.

Rekurzivní výstup poprvé popsal Thomas Pennello ve svém článku „Velmi rychlá analýza LR“ v roce 1986.[14] Techniku ​​později vysvětlil G.H. Roberts[15] v roce 1988 a také v článku Leermakers, Augusteijn, Kruseman Aretz[16] v roce 1992 v časopise Teoretická informatika.

Analýza LL

Hlavní článek: Analyzátor LL

An Analyzátor LL analyzuje vstup z Left doprava a konstruuje a Leftmost derivation věty (tedy LL, na rozdíl od LR). Třída gramatik, které lze tímto způsobem analyzovat, je známá jako LL gramatiky. LL gramatiky jsou ještě omezenější třídou bezkontextových gramatik než LR gramatiky. Přesto je pro spisovatele překladačů velmi zajímavý, protože takový analyzátor je snadno a efektivně implementovatelný.

LL (k) gramatiky lze analyzovat pomocí a analyzátor rekurzivního sestupu který je obvykle kódován ručně, ačkoli zápis jako META II alternativně lze použít.

Návrh ALGOL vyvolal vyšetřování rekurzivního sestupu, protože samotný jazyk ALGOL je rekurzivní. Koncept analýzy rekurzivního sestupu byl projednán v lednu 1961 CACM v samostatných dokumentech A.A. Grau a Edgar T. „Ned“ Irons.[17][18]Richard Waychoff a jeho kolegové také implementovali rekurzivní sestup v Burroughs Kompilátor ALGOL v březnu 1961,[19] obě skupiny používaly různé přístupy, ale byly alespoň v neformálním kontaktu.[20]

Myšlenku gramatik LL (1) představili Lewis a Stearns (1968).[21][22]

Rekurzivní sestup popularizoval Niklaus Wirth s PL / 0, an vzdělávací programovací jazyk používá se k výuce konstrukce překladačů v 70. letech.[23]

Analýza LR zvládne větší rozsah jazyků než Analýza LL, a je také lepší při hlášení chyb (To je sporné, je vyžadována REFERENCE), tj. detekuje syntaktické chyby, když vstup co nejdříve neodpovídá gramatice.

Earley parser

V roce 1970 Jay Earley vynalezl to, co začalo být známé jako Earley parser. Analyzátory Earley jsou přitažlivé, protože mohou analyzovat všechny bezkontextové jazyky přiměřeně efektivně.[24]

Jazyky gramatického popisu

John Backus navrhl „metalingvistické vzorce“[25][26]popsat syntaxi nového programovacího jazyka IAL, dnes známého jako ALGOL 58 (1959). Backusova práce byla založena na Postkanonický systém vymyslel Emil Post.

Další vývoj ALGOLu vedl k ALGOL 60; ve své zprávě (1963), Peter Naur pojmenoval Backusovu notaci Backus normální forma (BNF) a zjednodušil jej tak, aby se minimalizovala použitá znaková sada. Donald Knuth však tvrdil, že BNF by mělo být spíše chápáno jako Backus – Naurova forma,[27] a to se stalo běžně přijímaným zvykem.

Niklaus Wirth definována rozšířená forma Backus – Naur (EBNF), rafinovaná verze BNF, na začátku 70. let pro PL / 0. Augmented Backus – Naur forma (ABNF) je další varianta. Jak EBNF, tak ABNF se široce používají k určení gramatiky programovacích jazyků, jako vstupů do generátorů syntaktických analyzátorů a v dalších oblastech, jako je definování komunikačních protokolů.

Analyzátorové generátory

Úplnější seznam, který zahrnuje také generátory analyzátorů LL, SLR, GLR a LR, viz Porovnání generátorů syntaktických analyzátorů

A generátor analyzátoru generuje lexikální analyzátor část kompilátoru. Jedná se o program, který bere popis a formální gramatika konkrétního programovacího jazyka a vytvoří analyzátor pro tento jazyk. Tento analyzátor lze použít v kompilátoru pro konkrétní jazyk. Analyzátor detekuje a identifikuje vyhrazená slova a symboly konkrétního jazyka z proudu textu a vrací je jako tokeny do kódu, který implementuje syntaktické ověření a překlad do kódu objektu. Tuto druhou část kompilátoru lze také vytvořit pomocí překladač-překladač jako vstup použijeme formální popis syntaxe pravidel priority.

První překladač-překladač použít toto jméno napsal Tony Brooker v roce 1960 a byl použit k vytvoření překladačů pro Atlas počítač na univerzitě v Manchesteru, včetně Atlas Autocode překladač. Bylo to však dost odlišné od moderních překladačů a překladačů a dnes by se to pravděpodobně dalo popsat jako někde mezi vysoce přizpůsobitelným obecným překladačem a jazyk rozšiřitelné syntaxe. Název „kompilátor-kompilátor“ byl mnohem vhodnější pro Brookerův systém než pro většinu moderních kompilátorů-kompilátorů, které jsou přesněji popsány jako generátory syntaktických analyzátorů. Je téměř jisté, že název „kompilátor kompilátoru“ je kvůli běžnému použití běžně používán Yacc spíše než si pamatovat Brookerovu práci.[Citace je zapotřebí ]

Na začátku 60. let Robert McClure v Texas Instruments vynalezl kompilátor-kompilátor s názvem TMG, název převzatý z „transmogrifikace“.[28][29][30][31] V následujících letech byla TMG přeneseno několika UNIVAC a sálové počítače IBM.

The Multics projekt, společný podnik mezi MIT a Bell Labs, byl jedním z prvních, kdo vyvinul operační systém v jazyce na vysoké úrovni. PL / I. jako jazyk byl vybrán, ale externí dodavatel nemohl dodat fungující kompilátor.[32] Tým Multics vyvinul vlastní dialekt podmnožiny PL / I. známý jako Early PL / I (EPL) jako jejich implementační jazyk v roce 1964. TMG bylo přeneseno do Řada GE-600 a používá se k vývoji EPL do Douglas McIlroy, Robert Morris, a další.

Nedlouho po té Ken Thompson napsal první verzi Unix pro PDP-7 v roce 1969 vytvořil Doug McIlroy první jazyk vyšší úrovně nového systému: implementaci McClureova TMG.[33] TMG byl také nástrojem pro definici překladače, který použil Ken Thompson k napsání překladače pro Jazyk B. na svém PDP-7 v roce 1970. B byl bezprostředním předkem C.

Brzy Generátor analyzátoru LALR byl nazýván „TWS“, vytvořili Frank DeRemer a Tom Pennello.

XPL

XPL je dialektem PL / I. programovací jazyk, který se používá pro vývoj překladačů pro počítačové jazyky. Byl navržen a implementován v roce 1967 týmem s William M. McKeeman, James J. Horning, a David B. Wortman v Stanfordská Univerzita a Kalifornská univerzita, Santa Cruz. Poprvé to bylo oznámeno v roce 1968 Fall Joint Computer Conference v San Francisku.[34][35]

XPL představoval relativně jednoduchý systém psaní překladatelů dabovaný ANALYZÁTOR, na základě a kompilátor zdola nahoru nazývá se technika analýzy priorit MSP (smíšená priorita strategie). XPL byl bootstrapován přes Burroughse Algola na IBM System / 360 počítač. (Některé následující verze XPL použité na Windows University of Toronto interní projekty využívaly analyzátor SLR (1), ale tyto implementace nebyly nikdy distribuovány).

Yacc

Yacc je generátor analyzátoru (volně, překladač-překladač ), nesmí být zaměňována s lex, což je lexikální analyzátor často používá jako první fázi Yacc. Yacc vyvinul Stephen C. Johnson v AT&T pro Unix operační systém.[36] Název je zkratka pro „Ještě další Kompilátor Kompilátor "Generuje kompilátor LALR (1) na základě gramatiky napsané v zápisu podobném formě Backus – Naur.

Johnson pracoval na Yacc na začátku 70. let v Bell Labs.[37] Znal TMG a jeho vliv lze vidět v Yaccu a designu programovacího jazyka C. Protože Yacc byl výchozím generátorem kompilátoru na většině unixových systémů, byl široce distribuován a používán. Deriváty jako např GNU Bison se stále používají.

Kompilátor generovaný Yacc vyžaduje a lexikální analyzátor. Generátory Lexical Analyzer, jako např lex nebo flex jsou široce dostupné. The IEEE POSIX Standard P1003.2 definuje funkčnost a požadavky pro Lex i Yacc.

Coco / R

Coco / R je generátor analyzátoru který generuje LL (1) analyzátory v Modula-2 (s pluginy pro jiné jazyky) ze vstupních gramatik napsaných ve variantě EBNF. Byl vyvinut Hanspeterem Mössenböckem na Švýcarském federálním technologickém institutu v Curychu (ETHZ) v roce 1985.

ANTLR

ANTLR je generátor analyzátoru který generuje LL (*) analyzátory v Javě ze vstupních gramatik napsaných ve variantě EBNF. Byl vyvinut Terence Parrem na univerzitě v San Francisku na počátku 90. let jako nástupce dřívějšího generátoru s názvem PCCTS.

Metacompilers

Hlavní článek: metakompilátor

Metacompilers se liší od generátorů syntaktických analyzátorů, přičemž jako vstup a program napsáno v a metajazyk. Jejich vstup spočívá v analýze vzorců gramatiky a transformačních operacích, které vytvářejí abstraktní syntaxové stromy, nebo v jednoduchém výstupu přeformátovaných textových řetězců, které mohou být strojovým kódem zásobníku.

Mnoho z nich může být naprogramováno ve svém vlastním metajazyku, což jim umožňuje sestavit se, což z nich dělá samohostitelské rozšiřitelné jazykové překladače.

Mnoho metakompilátorů staví na práci Dewey Val Schorre. Jeho META II překladač, který byl poprvé vydán v roce 1964, byl prvním dokumentovaným metakompilátorem. Program META II, schopný definovat svůj vlastní jazyk a další, přijal syntaxový vzorec zapuštěné výstup (výroba kódu). Přeložilo se to také do jednoho z prvních případů a virtuální stroj. Lexikální analýza byla provedena pomocí vestavěných funkcí rozpoznávání tokenů: .ID, .STRING a .NUMBER. Citované řetězce ve vzorci syntaxe rozpoznávají lexémy, které nejsou uchovávány.[38]

TREE-META, metakompilátor Schorre druhé generace, se objevil kolem roku 1968. Rozšířil možnosti META II a přidal neobvyklá pravidla oddělující produkci kódu od gramatické analýzy. Produkce operací transformace stromu v syntaxi vzorce abstraktní syntaxové stromy že neproporcionální pravidla fungují. Poskytnuto přizpůsobení vzoru stromu optimalizace kukátka schopnost.

CWIC, popsaný v publikaci ACM z roku 1970, je metakompilátor Schorre třetí generace, který do analýzy gramatiky přidal pravidla lexingu a operátory zpětného sledování. LISP 2 byl ženatý s nezvyklými pravidly TREEMETA v jazyce generátoru CWIC. Díky zpracování LISP 2 může CWIC generovat plně optimalizovaný kód. CWIC také poskytla generování binárního kódu do pojmenovaných sekcí kódu. Jednopásmové a víceprůchodové kompilace lze implementovat pomocí CWIC.

CWIC zkompilovaný do 8bitových bajtových adresovatelných instrukcí strojového kódu primárně navržených k produkci kódu IBM System / 360.

Pozdější generace nejsou veřejně dokumentovány. Jednou důležitou vlastností by byla abstrakce cílové sady instrukcí procesoru, generující do sady instrukcí pseudo stroje, makra, která by mohla být samostatně definována nebo mapována podle instrukcí skutečného stroje. Optimalizace aplikované na sekvenční instrukce by pak mohly být aplikovány na instrukci pseudo před jejich rozšířením do cílového strojového kódu.

Křížová kompilace

A křížový překladač běží v jednom prostředí, ale vytváří objektový kód pro jiné. Křížové překladače se používají pro vestavěný vývoj, kde má cílový počítač omezené možnosti.

Prvním příkladem křížové kompilace bylo AIMICO, kde byl použit program FLOW-MATIC na UNIVAC II ke generování montážního jazyka pro IBM 705, který byl poté sestaven na počítači IBM.[2]

The ALGOL 68C kompilátor vygenerován ZCODE výstup, který by pak mohl být buď zkompilován do kódu místního počítače pomocí a ZCODE tlumočník nebo tlumočník. ZCODE je střední jazyk založený na registrech. Tato schopnost interpretovat nebo kompilovat ZCODE podpořil přenesení ALGOL 68C na řadu různých počítačových platforem.

Optimalizace překladačů

Optimalizace kompilátoru je proces zlepšování kvality objektového kódu beze změny výsledků, které vytváří.

Vývojáři prvního kompilátoru FORTRAN si kladli za cíl vygenerovat kód, který byl lepší než průměrný ručně kódovaný assembler, aby zákazníci skutečně používali jejich produkt. V jednom z prvních skutečných překladačů často uspěli.[39]

Pozdější překladače, jako kompilátor Fortran IV od IBM, kladly větší důraz na dobrou diagnostiku a rychlejší provádění na úkor optimalizace objektového kódu. Teprve v řadě IBM System / 360 poskytla společnost IBM dva samostatné kompilátory: rychlou kontrolu kódu a pomalejší optimalizaci.

Frances E. Allen, pracující samostatně a společně s John Cocke, představil mnoho konceptů pro optimalizaci. Allenův papír z roku 1966, Optimalizace programu,[40] představil použití datové struktury grafů kódovat obsah programu pro optimalizaci.[41] Její dokumenty z roku 1970, Analýza toku řízení[42] a Základ pro optimalizaci programu[43] stanovena intervaly jako kontext pro efektivní a efektivní analýzu a optimalizaci toku dat. Její papír z roku 1971 s Cockem, Katalog optimalizace transformací,[44] poskytl první popis a systematizaci optimalizačních transformací. Její dokumenty z roku 1973 a 1974 o meziprocesu analýza toku dat rozšířil analýzu na celé programy.[45][46] Její práce z roku 1976 s Cockem popisuje jednu ze dvou hlavních analytických strategií, které se dnes používají při optimalizaci překladačů.[47]

Allen vyvinula a implementovala své metody jako součást překladačů pro IBM 7030 Stretch -Sklizeň a experimentální Pokročilý výpočetní systém. Tato práce stanovila proveditelnost a strukturu moderních optimalizátorů nezávislých na strojích a jazycích. Pokračovala v založení a vedení projektu PTRAN pro automatické paralelní provádění programů FORTRAN.[48] Její tým PTRAN vyvinul nová schémata detekce paralelismu a vytvořil koncept grafu závislosti programu, primární strukturovací metody používané většinou paralelizujících kompilátorů.

Programovací jazyky a jejich překladače John Cocke a Jacob T. Schwartz, publikovaná počátkem roku 1970, věnovala optimalizačním algoritmům více než 200 stránek. Zahrnovalo mnoho nyní známých technik, jako je nadbytečná eliminace kódu a snížení síly.[49]

Optimalizace kukátka

Optimalizace kukátka je velmi jednoduchá, ale účinná optimalizační technika. To bylo vynalezeno William M. McKeeman a publikováno v roce 1965 v CACM.[50] Byl použit v kompilátoru XPL, který McKeeman pomohl vyvinout.

Optimalizátor Capex COBOL

Capex Corporation vyvinul "COBOL Optimizer" v polovině 70. let pro COBOL. Tento typ optimalizátoru závisel v tomto případě na znalostech „slabin“ ve standardním kompilátoru IBM COBOL a skutečně byl nahrazen (nebo opravený ) části objektového kódu s efektivnějším kódem. Náhradní kód může nahradit lineární vyhledávání v tabulce s binární vyhledávání například nebo někdy jednoduše nahradit relativně „pomalou“ instrukci známou rychlejší instrukcí, která byla jinak funkčně ekvivalentní v jeho kontextu. Tato technika je nyní známá jako „Snížení síly "Například na hardwaru IBM System / 360 CLI instrukce byla v závislosti na konkrétním modelu dvakrát až pětkrát rychlejší než a CLC instrukce pro jednobajtové srovnání.[51][52]

Moderní překladače obvykle poskytují možnosti optimalizace, takže programátoři si mohou vybrat, zda provedou optimalizační průchod.

Diagnostika

Když překladač dostane syntakticky nesprávný program, je užitečná dobrá a jasná chybová zpráva. Z pohledu spisovatele kompilátoru je často obtížné dosáhnout.

The WATFIV Kompilátor Fortran byl vyvinut na University of Waterloo, Kanada na konci 60. let. Byl navržen tak, aby poskytoval lepší chybové zprávy než tehdejší překladače Fortranu od IBM. WATFIV byl navíc mnohem použitelnější, protože kombinoval kompilaci, propojení a provedení do jednoho kroku, zatímco kompilátoři IBM měli ke spuštění tři samostatné komponenty.

PL / C

PL / C byl počítačový programovací jazyk vyvinutý na Cornell University na začátku 70. let. Zatímco PL / C byla podmnožinou jazyka PL / I od IBM, byla navržena se specifickým cílem, který bude používán pro výuku programování. Dva vědci a akademičtí učitelé, kteří navrhli PL / C, byli Richard W. Conway a Thomas R. Wilcox. Podali slavný článek „Návrh a implementace diagnostického kompilátoru pro PL / I“ publikovaný v Komunikaci ACM v březnu 1973.[53]

PL / C eliminoval některé ze složitějších funkcí PL / I a přidal rozsáhlé nástroje pro ladění a zotavení po chybě. Kompilátor PL / C měl neobvyklou schopnost nikdy nezkomplikovat žádný program, a to díky použití rozsáhlé automatické opravy mnoha chyb syntaxe a převedením zbývajících chyb syntaxe na výstupní příkazy.

Just in Time kompilace

Hlavní článek: Just-in-time kompilace

Just in time kompilace (JIT ) je generování spustitelného kódu za běhu nebo co nejblíže jeho skutečnému provedení, aby bylo možné využít doby běhu metriky nebo jiné možnosti zvýšení výkonu.

Mezilehlé zastoupení

Hlavní článek: Mezilehlé zastoupení

Většina moderních překladačů má lexer a parser, které vytvářejí střední reprezentaci programu. Mezilehlá reprezentace je jednoduchá posloupnost operací, které lze použít optimalizátorem a generátor kódů který vytváří pokyny v jazyk stroje cílového procesoru. Protože generátor kódu používá mezilehlou reprezentaci, lze stejný generátor kódu použít pro mnoho různých jazyků na vysoké úrovni.

Existuje mnoho možností pro mezilehlou reprezentaci. Kód se třemi adresami, také známý jako a čtyřnásobek nebo čtyřkolka je běžná forma, kde je operátor, dva operandy a výsledek. Kód se dvěma adresami nebo trojnásobek mít zásobník, do kterého se zapisují výsledky, na rozdíl od explicitních proměnných kódu se třemi adresami.

Statické jedno přiřazení (SSA) vyvinula Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, a F. Kenneth Zadeck, vědci v IBM v 80. letech.[54] V SSA má proměnná hodnotu pouze jednou. Namísto úpravy existující se vytvoří nová proměnná. SSA zjednodušuje optimalizaci a generování kódu.

Generování kódu

Hlavní článek: Generování kódu (kompilátor)

Generátor kódu generuje instrukce strojového jazyka pro cílový procesor.

Registrovat přidělení

Sethi – Ullmanův algoritmus nebo Sethi-Ullmanovo číslování je metoda k minimalizaci počtu registrů potřebných k uchovávání proměnných.

Pozoruhodné překladače

Viz také: ALGOL 60: Časová osa implementací ALGOL 60 a Seznam překladačů
Tento seznam je neúplný; můžete pomoci přidání chybějících položek s spolehlivé zdroje.

Viz také

Reference

  1. ^ Maurice V. Wilkes. 1968. Počítače dříve a nyní. Časopis Asociace pro výpočetní techniku, 15 (1): 1–7, leden. p. 3 (komentář v závorkách přidaný editorem), „(Nemyslím si, že by se termín kompilátor [1953] tehdy obecně používal, i když ho ve skutečnosti zavedla Grace Hopperová.)“
  2. ^ A b C [1] První kompilátoři COBOL na světě Archivováno 13. října 2011 v Wayback Machine
  3. ^ Knuth, Donald E .; Pardo, Luis Trabb. "Časný vývoj programovacích jazyků". Encyclopedia of Computer Science and Technology. 7: 419–493.
  4. ^ Peter J. Bentley (2012). Digitalizované: Věda o počítačích a jak formuje náš svět. Oxford University Press. p. 87. ISBN  9780199693795. Archivováno z původního dne 29. srpna 2016.
  5. ^ Backus a kol. „Automatický kódovací systém FORTRAN“, Proc. AFIPS 1957 Western Joint Computer Conf., Spartan Books, Baltimore 188–198
  6. ^ [2] Rosen, Saule. ALTAC, FORTRAN a kompatibilita. Sborník z 16. národního setkání ACM z roku 1961
  7. ^ T. Hart a M. Levin „The New Compiler“, AIM-39[trvalý mrtvý odkaz ] CSAIL Digital Archive - Artificial Intelligence Laboratory Series
  8. ^ A b Tim Hart; Mike Levin. „AI Memo 39 - Nový kompilátor“ (PDF). Citováno 23. května 2008.[trvalý mrtvý odkaz ]
  9. ^ Chomsky, Noam (září 1956). Msgstr "Tři modely pro popis jazyka". Transakce IEEE na teorii informací. 2 (3): 113–124. doi:10.1109 / TIT.1956.1056813. S2CID  19519474.
  10. ^ Knuth, Donald. „K překladu jazyků zleva doprava“ (PDF). Archivovány od originál (PDF) dne 15. března 2012. Citováno 29. května 2011.
  11. ^ Korenjak, A. „Praktická metoda pro konstrukci procesorů LR (k),“ komunikace ACM, sv. 12, č. 11, 1969
  12. ^ DeRemer, F. Praktičtí překladatelé pro jazyky LR (k). Disertační práce, MIT, 1969.
  13. ^ DeRemer, F. „Jednoduché gramatiky LR (k),“ komunikace ACM, sv. 14, č. 7, 1971.
  14. ^ A b Thomas J. Pennello (1986). „Very fast LR parsing“. Oznámení ACM SIGPLAN. 21 (7).
  15. ^ G.H. Roberts (1988). "Rekurzivní výstup: analog LR k rekurzivnímu sestupu".
  16. ^ Leermakers, Augusteijn, Kruseman Aretz (1992). „Funkční analyzátor LR“.CS1 maint: více jmen: seznam autorů (odkaz)
  17. ^ A.A. Grau, "Rekurzivní procesy a překlad ALGOL", Commun. ACM, 4, č. 1, str. 10–15. Leden 1961
  18. ^ Edgar T. Irons, "Kompilátor zaměřený na syntaxi pro ALGOL 60", Commun. ACM, 4, č. 1, leden 1961, s. 51–55.
  19. ^ „Příběhy modelu B5000 a lidí, kteří tam byli“ (PDF).
  20. ^ „Konference Burroughs B5000, Charles Babbage Institute“. hdl:11299/107105. Citovat deník vyžaduje | deník = (Pomoc)
  21. ^ P. M. Lewis, R. E. Stearns, „Syntaxí řízená transdukce“, focs, s. 21–35, 7. výroční symposium o změně a teorii automatů (SWAT 1966), 1966
  22. ^ Lewis, P. a Stearns, R. „Transduction-Directed Transduction“, Journal of ACM, sv. 15, č. 3, 1968.
  23. ^ „Překladač / tlumočník PL / 0“. Archivovány od originál dne 8. prosince 2008. Citováno 7. července 2011.
  24. ^ J. Earley, „Efektivní algoritmus pro analýzu bez kontextu“, Komunikace Asociace pro výpočetní techniku, 13:2:94-102, 1970.
  25. ^ Backus, J. W. (1959). „Syntax a sémantika navrhovaného mezinárodního algebraického jazyka konference v Curychu ACM-GAMM“. Sborník z mezinárodní konference o zpracování informací: 125–132.
  26. ^ Farrell, James A. (srpen 1995). „Extended Backus Naur Form“. Základy kompilátoru. Citováno 11. května 2011.
  27. ^ Donald E. Knuth, "Backus normální forma vs. Backus Naur Form", komunik. ACM, 7 (12): 735–736, 1964.
  28. ^ „TMG Meta Compiler“. reocities.com. Archivovány od originál dne 4. března 2016. Citováno 30. června 2011.
  29. ^ „Archivovaná kopie“. Archivovány od originál dne 21. září 2007. Citováno 30. června 2011.CS1 maint: archivovaná kopie jako titul (odkaz)
  30. ^ „Programovací jazyky pro nečíselné zpracování — 1“. acm.org.
  31. ^ R. M. McClure, TMG - překladač se syntaxí Proc. 20. národní konfederace ACM (1965), str. 262–274.
  32. ^ „Multics PL / I“. multicians.org.
  33. ^ „Archivovaná kopie“. Archivovány od originál dne 10. ledna 2015. Citováno 3. srpna 2011.CS1 maint: archivovaná kopie jako titul (odkaz) Dennis M. Ritchie. Vývoj jazyka C.
  34. ^ McKeeman, William Marshall; Horning, James J .; a Wortman, David B., Generátor kompilátoru (1971), ISBN  978-0-13-155077-3.
  35. ^ Oddělení informatiky, University of Toronto, „Programovací jazyk XPL“
  36. ^ Johnson, S.C., „Yacc - Yet Another Compiler Compiler“, technická zpráva Computing Science 32, AT&T Bell Labs, 1975
  37. ^ Hamilton, Naomi. „A-Z programovacích jazyků: YACC“. TechWorld.
  38. ^ „META II - syntaxově orientovaný psací jazyk překladače“. acm.org.
  39. ^ "Comp.compilers: Re: Historie a vývoj překladačů". iecc.com.
  40. ^ Optimalizace programu F.E. Allen. In Mark I. Halpern a Christopher J. Shaw, redaktoři, Annual Review in Automatic Programming, svazek 5, strany 239–307. Pergamon Press, New York, 1969.
  41. ^ Frances E. Allen a John Cocke. Grafické teoretické konstrukce pro analýzu toku řízení programu. Technická zpráva IBM Res. Rep. RC 3923, IBM T.J. Watson Research Center, Yorktown Heights, NY, 1972.
  42. ^ Frances E. Allen. Analýza kontrolního toku. Oznámení ACM SIGPLAN, 5 (7): 1–19, červenec 1970.
  43. ^ Frances E. Allen. Základ pro optimalizaci programu. V Proc. Kongres IFIP 71, strany 385–390. Severní Holandsko, 1972.
  44. ^ Frances E. Allen a John Cocke. Katalog optimalizačních transformací. V R. Rustin, editor, Design and Optimization of Compilers, strany 1–30. Prentice-Hall, 1971.
  45. ^ Frances E. Allen. Analýza meziprocedurálních toků dat. V Proc. Kongres IFIP 74, strany 398–402. Severní Holandsko, 1974.
  46. ^ Frances E. Allen. Metoda určování vztahů dat programu. In Andrei Ershov and Valery A. Nepomniaschy, editors, Proc. International Symposium on Theoretical Programming, Novosibirsk, SSSR, August 1972, volume 5 of Lecture Notes in Computer Science, strany 299–308. Springer-Verlag, 1974.
  47. ^ Frances E. Allen a John Cocke. Procedura analýzy toku dat programu. Komunikace ACM, 19 (3): 137–147, březen 1976.
  48. ^ Vivek Sarkar. Systém paralelního programování PTRAN. In Parallel Functional Programming Languages ​​and Compilers, edited by B. Szymanski, ACM Press Frontier Series, strany 309–391, 1991.
  49. ^ John Cocke a Jacob T. Schwartz, Programovací jazyky a jejich překladače. Courant Institute of Mathematical Sciences, New York University, duben 1970.
  50. ^ McKeeman, W.M. Optimalizace kukátka. Commun. ACM 8, 7 (červenec 1965), 443–444
  51. ^ http://www.bitsavers.org/pdf/ibm/360/A22_6825-1_360instrTiming.pdf
  52. ^ „Softwarové inženýrství pro prostředí Cobol“. acm.org.
  53. ^ CACM březen 1973, s. 169–179.
  54. ^ Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K .; Wegman, Mark N .; Zadeck, F. Kenneth (1991). "Efektivní výpočet statického jednoho přiřazovacího formuláře a graf závislosti ovládání" (PDF). Transakce ACM v programovacích jazycích a systémech. 13 (4): 451–490. CiteSeerX  10.1.1.100.6361. doi:10.1145/115372.115320. S2CID  13243943.

Další čtení

externí odkazy