Generátor překladačů

Generátor překladačů (anglicky compiler-compiler nebo compiler generator) 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ů (anglicky parser generator), 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 (anglicky code generator-generators) (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 (anglicky parse tree) nebo syntaktický strom (anglicky abstract syntax tree) 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[1]. 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 https://web.archive.org/web/20130608172614/https://javacc.java.net/

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Compiler-compiler na anglické Wikipedii.

  1. ↑ Peter Mosses, „SIS: Compiler-Generator System Using Denotational Semantics," Report 78-4-3, Dept. of Computer Science, University of Aarhus, Denmark, June 1978

Literatura

  • BROOKER, R .A.; MACCALLUM, I. R.; MORRIS, D. The compiler-compiler. Svazek 3. [s.l.]: [s.n.], 1963. 
  • 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
  • MCKEEMAN, William M.; HORNING, James J.; WORTMAN, David B. A Compiler Generator. Englewood Cliffs, N.J.: Prentice-Hall, 1970. Dostupné online. ISBN 0-13-155077-2. 

Související články

Externí odkazy