Generátor překladačů ( nebo ) je v matematické informatice nástroj pro programování, který vytváří syntaktický analyzátor, interpret nebo překladač z formálního popisu jazyka a cílového stroje. Nejstarším a dosud nejrozšířenějším typem generátorů překladačů je generátor syntaktických analyzátorů (), jehož vstupem je gramatika (obvykle v BNF) programovacího jazyka a výstupem zdrojový text syntaktického analyzátoru, který lze použít jako součást překladače. Existují také generátory generátorů kódu () (jako například JBurg), ale zatím nedosáhly potřebné zralosti.
Ideální generátor překladačů by měl z popisu programovacího jazyka a cílové instrukční sady automaticky vygenerovat použitelný překladač. Ale tohoto stupně dokonalosti zatím nedosáhly ani nejmodernější generátory, a většina generátorů překladačů zatím není schopna zpracovávat informace o sémantice nebo cílové architektuře.
Varianty Typický generátor syntaktických analyzátorů přiřazuje každému pravidlu gramatiky programový kód, který má být vykonán, když syntaktický analyzátor použije příslušné pravidlo. Tyto fragmenty kódu se někdy označují jako sémantické akce, protože definují sémantiku syntaktické struktury analyzované syntaktickým analyzátorem. V závislosti na požadovaném typu syntaktického analyzátoru mohou tyto akce vytvářet derivační strom () nebo syntaktický strom () nebo přímo generovat proveditelný kód.
Jedním z prvních, ale překvapivě výkonných, generátorů překladačů je META II vytvořený roku 1964, který přijímal gramatiky a pravidla pro generování kódu a byl schopen přeložit sebe sama i jiné jazyky.
Některé pokusné generátory překladačů používají jako vstup formální popis sémantiky programovacího jazyka. Tento přístup je často nazývaný 'používání sémantického překladu' a vyvinul jej Peter Mosses jako Systém implementace sémantiky (SIS) v roce 1978Peter Mosses, „SIS: Compiler-Generator System Using Denotational Semantics," Report 78-4-3, Dept. of Computer Science, University of Aarhus, Denmark, June 1978. Nicméně jak generované překladače, tak kód, který vytvářejí, byly časově i prostorově neefektivní. V současnosti nejsou žádné překladače přepisovacích pravidel vytvářeny tímto způsobem, ale výzkum pokračuje.
Projekt Production Quality Compiler-Compiler v Carnegie-Mellon University neformalizuje sémantiku, ale používá poloformální rámec pro popis stroje.
Existuje mnoho variant generátorů překladačů, včetně generátorů přepisovacích strojů zdola nahoru (viz JBurg) používaných pro pokrytí derivačních stromů podle přepisovací gramatiky pro generování kódu a generátory syntaktických analyzátorů používající atributové gramatiky (jako například ANTLR) může být používán pro současnou typovou kontrolu, šíření konstant a další úkoly během fáze analýzy.
Historie První generátor překladačů, který používal jméno Compiler-Compiler, vytvořil Tony Brooker v roce 1960 a sloužil pro vytvoření překladače pro počítač Atlas na University of Manchester, včetně překladače Atlas Autocode. Tyto nástroje se však značně lišily od moderních generátorů překladačů a dnes by pravděpodobně byl zařazován někam mezi vysoce přizpůsobitelné obecné překladače a jazyky s rozšiřitelnou syntaxí. Přestože název Compiler-Compiler – generátor překladačů by byl daleko přilehavější pro Brookerův systém než pro většinu moderních generátorů překladačů, které jsou často pouhými generátory syntaktických analyzátorů. Je téměř jisté, že název „Compiler Compiler“ se rozšířil díky programu Yacc, a ne Brookerova výtvoru.
Dalšími příklady generátorů syntaktických analyzátorů ve stylu programu Yacc jsou ANTLR, Coco/R, CUP, GNU bison, Eli, FSL, SableCC a JavaCC. Přestože jsou užitečné, prosté generátory syntaktických analyzátorů řeší z celého překladače pouze analýzu jazyka. Nástroje se širším záběrem, jako například PQCC, Coco/R a DMS Software Reengineering Toolkit poskytují významnou podporu pro obtížnější činnosti následující po syntaktické analýze, jako například sémantickou analýzu, generování a optimalizaci kódu.
Některé generátory překladačů ANTLR Bison Coco/R DMS Software Reengineering Toolkit, systém pro transformaci programů s generátory syntaktických analyzátorů. ELI, integrovaná sada nástrojů pro konstrukci překladačů. Grako, Python EBNF-to-PEG generátor syntaktických analyzátorů. Lemon META II parboiled, Knihovna pro jazyk Java pro vytváření syntaktických analyzátorů. Packrat parser PackCC, packrat parser s podporou levé rekurze. PQCC, generátor překladačů, který není jenom generátorem syntaktických analyzátorů. SYNTAX, integrovaná sada nástrojů pro konstrukci překladačů. TREEMETA Yacc XPL JavaCC
Odkazy
Reference
Literatura
Brooker, R.., Morris, D. a Rohl, J. S., Experience with the Compiler Compiler, Computer Journal, Vol. 9, p. 350. (February 1967). Johnson, Stephen C., Yacc—yet another compiler-compiler, Computer Science Technical Report 32, Bell Laboratories, Murray Hill, NJ, July 1975
Související články Gramatika parsovacích výrazů (PEG) LL analyzátor LR analyzátor SLR analyzátor LALR analyzátor GLR analyzátor Doménově specifický jazyk Metacompiler Historie překladačů
Externí odkazy Computer50.org, Brooker Autocodes Catalog.compilertools.net , Katalog nástrojů pro konstrukci překladačů Labraj.uni-mb.si , Lisa Skenz.it, Nástroje Jflex a Cup Gentle.compilertools.net , Systém pro konstrukci překladačů Gentle Accent.compilertools.net , Accent: Překladač pro celou třídu bezkontextových jazyků Grammatica.percederberg.net Generátor syntaktických analyzátorů pro .NET a Java s otevřeným zdrojovým kódem
Kategorie:Syntaktická analýza Kategorie:Programovací software Kategorie:Doménově specifické jazyky