Generátor překladačů

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 [url=http://jburg.sourceforge.net/]JBurg[/url]), 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. +more 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 1978. +more 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 [url=http://jburg. sourceforge. +morenet/]JBurg[/url]) 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í. +more 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. +more 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ů. * [url=http://eli-project. +moresourceforge. net/]ELI[/url], integrovaná sada nástrojů pro konstrukci překladačů. * [url=https://pypi. python. org/pypi/grako/]Grako[/url], 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 * [url=http://sourceforge. net/p/packcc/wiki/Home/]PackCC[/url], 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 https://web. archive. org/web/20130608172614/https://javacc. java. net/.

Odkazy

Reference

Literatura

Brooker, R. , Morris, D. +more a Rohl, J. S. , [url=http://comjnl. oxfordjournals. org/cgi/content/abstract/9/4/345]Experience with the Compiler Compiler[/url], 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

[url=https://web. archive. +moreorg/web/20041031031946/http://www. computer50. org/mark1/gethomas/manchester_autocodes. html]Computer50. org[/url], Brooker Autocodes * [url=http://catalog. compilertools. net/]Catalog. compilertools. net[/url] , Katalog nástrojů pro konstrukci překladačů * [url=http://labraj. uni-mb. si/lisa]Labraj. uni-mb. si[/url], Lisa * [url=http://www. skenz. it/traduttori/]Skenz. it[/url], Nástroje Jflex a Cup * [url=http://gentle. compilertools. net/index. html]Gentle. compilertools. net[/url] , Systém pro konstrukci překladačů Gentle * [url=http://accent. compilertools. net/]Accent. compilertools. net[/url] , Accent: Překladač pro celou třídu bezkontextových jazyků * [url=http://grammatica. percederberg. net]Grammatica. percederberg. net [/url] 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