Cocktail Toolbox

Beschreibung

Die Cocktail Toolbox ist eine Sammlung von Programmgeneratoren oder Übersetzerbau-Werkzeugen für nahezu alle Phasen eines Übersetzers. Die Übersetzerbau-Werkzeuge unterstützen die weitgehend automatische Generierung von Compilern für imperative Programmiersprachen. Die Entwurfsziele für diesen Werkzeugkasten waren praktische Brauchbarkeit, deutlich reduzierter Erstellungsaufwand für Übersetzer und hohe Qualität der generierten Übersetzer. Besonders hinsichtlich Effizienz sind die Werkzeuge konkurrenzfähig zur Programmierung von Hand. Mit den Werkzeugen können Übersetzermodule in den Implementierungssprachen C, C++, Modula-2 oder Java erzeugt werden. Viele realistische Anwendungen demonstrieren die ausgezeichnete Leistungsfähigkeit der Werkzeuge und zeigen, daß die Werkzeuge die Konstruktion von Übersetzern und Sprachverarbeitungs-Software in Produktionsqualität erlauben.

Die Cocktail Übersetzerbau-Werkzeuge sind wesentlich leistungsfähiger als die UNIX Tools Lex und Yacc. Dies betrifft z. B. die Effizienz der generierten Scanner und Parser, die Behandlung von Syntaxfehlern und die Unterstützung bei Grammatik-Konflikten. Darüberhinaus bleibt Cocktail nicht bei der lexikalischen und syntaktischen Analyse stehen, sondern bietet auch Werkzeuge für Syntaxbäume, semantische Analyse und zur Transformation von attributierten Bäumen in Zwischen- oder Zielsprachen an.

Die Cocktail Toolbox läuft auf allen Varianten von Linux, Unix und Windows (9x, ME, NT, 2000, XP, Vista, 7, 8).
Der Name Cocktail steht für COmpiler Compiler ToolkIt KArLsruhe.

Werkzeuge

Die Cocktail Toolbox enthält die folgenden Werkzeuge:

RexGenerator für lexikalische Analysatoren
LarkLR(1) und LALR(2) Parser-Generator mit Backtracking und Prädikaten
Ell LL(1) Parser-Generator
Ast Generator für abstrakte Syntaxbäume
Ag Generator für Attributauswerter
PumaTransformation abstrakter Syntaxbäume mit Patternmatching
ReuseBibliothek wiederverwendbarer Module

Distribution

Zwei verschiedene Ausgaben der Cocktail Toolbox sind erhältlich: CD-ROM und ESD (Electronic Software Distribution).

Eine CD-ROM Ausgabe enthält:

Über ESD (Electronic Software Distribution) ist eine ausführbare Binärversion erhältlich. Folgende Objekte können von CoCoLab's Webserver heruntergeladen werden:

Hinweis: Die ESD-Ausgabe gibt es nur als Einzelplatzversion. Zur Freischaltung der Software muß ein Lizenz-Schlüssel von CoCoLab erworben werden. Die ESD-Ausgabe gibt es nur für Linux oder Microsoft Windows (9x, ME, NT, 2000, XP, Vista, 7, 8). Quellcode ist darin nicht enthalten. Eine Anleitung zum Herunterladen und zur Installation befindet sich auf der ESD Seite.

Updates

Updates für die Quellcode-Version der Cocktail Toolbox können von der Updates Seite heruntergeladen werden.

Dokumentation

Die Handbücher und die Dokumentation der Cocktail Toolbox in den Formaten PDF und Postscript können von der Dokumentation Seite heruntergeladen werden.

Rex

Rex (Regular EXpression tool) ist ein Generator für lexikalische Analysatoren. Seine Spezifikationen basieren auf regulären Ausdrücken und beliebigen semantischen Aktionen, die in einer der Implementierungssprachen C, C++, Modula-2 oder Java geschrieben sein können. Falls zur eindeutigen Erkennung der Symbole der Kontext betrachtet werden muß, so kann der rechte Kontext durch einen zusätzlichen regulären Ausdruck spezifiziert werden. Der linke Kontext wird mit sogenannten Start-Zuständen behandelt. Die erzeugten lexikalischen Analysatoren berechnen automatisch die Zeilen- und Spalten-Position für jedes erkannte Symbol und sie enthalten einen Mechanismus für Include-Dateien. Bezeichner und Schlüsselwörter können effizient in Groß- oder Kleinbuchstaben normalisiert werden. Die lexikalischen Analysatoren sind tabellengesteuert und laufen sehr schnell.

Lark

Lark ist ein Generator für LR(1) und LALR(2) Parser oder Syntax-Analysatoren. Lark akzeptiert Grammatiken, die in BNF-Notation geschrieben sind. Die Grammatikregeln können mit semantischen Aktionen versehen werden, die direkt in einer der Implementierungssprachen formuliert sind. Der Generator stellt einen Mechanismus zur S-Attributierung zur Verfügung, d. h. synthetisierte Attribute können während des Parsens berechnet werden. Im Falle von LR-Konflikten liefert Lark nicht wie andere Generatoren nur Information über aus Mengen von Situationen bestehenden Zuständen, sondern druckt einen Ableitungsbaum, der wesentlich nützlicher zur Analyse des Konflikts ist. Konflikte können durch die Angabe von Priorität und Assoziativität für Operatoren und Produktionen gelöst werden sowie durch die Angabe von syntaktischen und semantischen Prädikaten. Die generierten Parser beinhalten eine automatische Fehlerbehandlung mit Fehlermeldungen und -reparatur. Die Parser sind tabellengesteuert und laufen sehr schnell. Es können Parser in den Implementierungssprachen C, C++, Modula-2 oder Java erzeugt werden.

Weitere Eigenschaften von Lark sind:

Ell

Ell ist ein Generator für LL(1) Parser oder Syntax-Analysatoren. Ell akzeptiert Grammatiken in erweiterter BNF Notation. Während des Parsens kann eine L-Attributierung ausgewertet werden. Die erzeugten Parser beinhalten eine automatische Fehlerbehandlung mit Fehlermeldungen und -reparatur wie Lark. Die Parser sind nach dem Verfahren des rekursiven Abstiegs implementiert und laufen sehr schnell. Die möglichen Implementierungssprachen sind C, C++ oder Modula-2. Die Eingabesprachen der Werkzeuge sind verbesserte Versionen der Eingaben von Lex und Yacc. Alle Werkzeuge verstehen auch Lex und Yacc Syntax unter Zuhilfenahme von Präprozessoren.

Ast

Ast ist ein Generator für Programm-Module, welche die Strukturen abstrakter Syntaxbäume definieren und allgemeine Prozeduren zur Verarbeitung von Bäumen zur Verfügung stellen. Die Knoten der definierten Bäume können mit Attributen mit beliebigen Datentypen versehen werden. Neben Bäumen können auch Graphen verarbeitet werden. Die Struktur der Bäume wird mit einem Formalismus definiert, der auf kontext-freien Grammatiken basiert. Die generierten Module enthalten Prozeduren um Bäume auf- und abzubauen, um Bäume auf Dateien zu schreiben und sie von Dateien einzulesen, sowie um sie auf gebräuchliche Arten zu traversieren. Die genannte Ein-/Ausgabe auf Dateien arbeitet sowohl mit Text- als auch mit Binär-Darstellung der Bäume. Alle Prozeduren funktionieren sowohl für Bäume als auch für Graphen.

Dieser Ansatz bietet folgende Vorteile: Es stehen Record-Aggregate zur Verfügung, und diese bieten eine kompakte Schreibweise an, um Baumknoten anzulegen. Damit ist es möglich, Bäume in Termschreibweise aufzubauen. Ein Erweiterungsmechanismus vermeidet Kettenregeln und erlaubt zum Beispiel Listen mit Elementen von verschiedenem Typ. Es stehen Ein-/Ausgabe-Prozeduren für Records und ganze Graphen zur Verfügung. Die Ausgabe-Prozeduren und der interaktive Graph-Browser erleichtern die Testphase, da sie lesbare Ausgaben produzieren und die Datenstruktur kennen. Der Anwender braucht sich nicht um Algorithmen zur Traversierung von Graphen kümmern. Er wird von der Aufgabe befreit, große Mengen relativ einfachen Codes zu schreiben. Alle diese Eigenschaften erhöhen wesentlich die Produktivität des Anwenders.

Weitere Eigenschaften von Ast sind:

Ag

Ag ist ein Generator für Attribut-Auswerter. Er verarbeitet geordnete Attribut-Grammatiken (OAGs), wohl-definierte Attribut-Grammatiken (WAGs) und "higher order" Attribut-Grammatiken (HAGs). Die Auswerter arbeiten auf abstrakten Syntaxbäumen, deren Struktur vollständig bekannt ist. Den Terminalen und Nichtterminalen können beliebig viele Attribute zugeordnet werden, welche beliebige Typen der Implementierungssprache haben können. Es sind auch baumwertige Attribute möglich. Ag erlaubt regel-lokale Attribute und bietet eine Erweiterungsmechanismus, welcher sowohl einfache als auch mehrfache Vererbung für Attribute und für Attribut-Berechnungen bietet. Damit ist auch die Elimination von Kettenregeln möglich. Die Attribut-Berechnungen werden in der Implementierungssprache formuliert und sollten in einem funktionalen Stil geschrieben sein. Der Aufruf von externen Prozeduren aus getrennt übersetzten Modulen ist möglich. Nicht-funktionale Anweisungen und Seiteneffekte sind möglich, verlangen jedoch ein bedachtsames Vorgehen. Die Syntax der Spezifikationssprache ist entworfen worden, um kompakte, modulare und lesbare Attribut-Grammatiken schreiben zu können. Eine Attribut-Grammatik kann aus mehreren Modulen bestehen, wobei die kontext-freie Grammatik nur einmal spezifiziert wird. Es gibt Kurzschreibweisen für Kopierregeln und sogenannte "gefädelte" Attribute, welche es dem Anwender erlauben, viele triviale Attribut-Berechnungen wegzulassen. Die generierten Attribut-Auswerter sind sehr laufzeit-effizient, denn sie bestehen aus direkt codierten rekursiven Prozeduren. Die Speicherung der Attribute für OAGs ist optimiert, indem Attribute als lokale Variablen und Prozedurparameter implementiert werden, falls ihre Lebenszeit innerhalb eines Besuchs liegt.

Weitere Eigenschaften von Ag sind:

Puma

Puma ist ein Werkzeug zur Transformation und Manipulation von attributierten Bäumen. Es basiert auf Pattern-Matching und rekursiven Prozeduren. Puma arbeitet mit dem Generator für abstrakte Syntaxbäume Ast zusammen, wodurch bereits die Definition, Erzeugung und Speicherung von Bäumen unterstützt werden. Puma fügt eine kompakte Schreibweise für die Analyse und Synthese von Bäumen hinzu. Das Pattern-Matching kann als die Beschreibung von Entscheidungstabellen angesehen werden. Puma erlaubt die implizite Deklaration von Variablen, führt eine Typprüfung in Bezug auf Bäume durch und überprüft die "single assignment"-Beschränkung für Variablen. Die Ausgabe ist der Quellcode eines Programm-Moduls in einer der Implementierungssprachen C, C++, Modula-2 oder Java. Dieses Modul implementiert die spezifizierten Transformations-Routinen. Es kann leicht in beliebigen Programm-Code integiert werden. Die erzeugten Routinen sind optimiert durch Elimination von gemeinsamen Teilausdrücken und Elimination von "tail"-Rekursion.

Referenzen

  1. J. Grosch, Generators for High-Speed Front-Ends, LNCS, 371, 81-92 (Oct. 1988), Springer Verlag.
  2. W. M. Waite, J. Grosch and F. W. Schröer, Three Compiler Specifications, GMD-Studie Nr. 166, GMD Forschungsstelle an der Universität Karlsruhe, Aug. 1989.
  3. J. Grosch, Efficient Generation of Lexical Analysers, Software-Practice & Experience, 19, 1089-1103 (Nov. 1989).
  4. J. Grosch, Efficient and Comfortable Error Recovery in Recursive Descent Parsers, Structured Programming, 11, 129-140 (1990).
  5. J. Grosch, H. Emmelmann, A Tool Box for Compiler Construction, LNCS, 477, 106-116 (Oct. 1990), Springer Verlag.
  6. J. Grosch, Object-Oriented Attribute Grammars, in: Proceedings of the Fifth International Symposium on Computer and Information Sciences (ISCIS V) (Eds. A. E. Harmanci, E. Gelenbe), Cappadocia, Nevsehir, Turkey, 807-816, (Oct. 1990).
  7. J. Grosch, Lalr - a Generator for Efficient Parsers, Software-Practice & Experience, 20, 1115-1135 (Nov. 1990).
  8. J. Grosch, Tool Support for Data Structures, Structured Programming, 12, 31-38 (1991).
  9. U. Aszmann, H. Emmelmann, J. Grosch, Stein auf Stein - Cocktail: Eine Compiler-Compiler-Toolbox, iX 2/1992, 123-127.
  10. J. Grosch, Transformation of Attributed Trees Using Pattern Matching, LNCS, 641, 1-15 (Oct. 1992), Springer Verlag.
  11. R. M. Bates, Examining the Cocktail Toolbox, Dr. Dobb's Journal, #245 March 1996, 78-82, 95-96.
  12. J. Grosch, Are Attribute Grammars Used in Industry?, Proceedings of the Second Workshop on Attribute Grammars and their Application (WAGA 99) (Eds. D. Parigot, M. Mernik), Amsterdam, 1-15, (March 1999).


Über uns
Übersicht
Geschichte
Team
Produkte
Anwendungen
Parser
Cocktail Toolbox
Dienstleistungen
Entwicklung
Wartung
Schulung
Downloads
Demo Software
Dokumentation
Updates
Cocktail
Information
Neuigkeiten
Partner
Kontakt

English