Objective: This document is not an introduction to parser generators. Readers should rather have a good understanding of them, especially of LALR parser generators. This document merely describes the main aspects of the implementation of a LALR parser generator named wisent. It is divided into a concise description of the programming interface and an overview over the data structures and specifics of the implementation of the wisent parser generator.

Objekt-Orientierung im Compilerbau Seit der Entwicklung der ersten Compiler wurden für sehr viele Programmiersprachen Compiler entwickelt. Jeder Informatikstudierende ist zum Beispiel der Umgang mit einem C- oder vielleicht auch Java-Compiler gewohnt. Am Anfang galten Compiler als nur sehr schwer zu implementierende Programme. Seitdem wurden aber systematische Techniken und Werkzeuge zur automatischen Erzeugung von (Teilen von) Compilern entwickelt. Nur wenige Personen kommen allerdings in die Situation, für eine höhere Programmiersprache einen Compiler zu entwickeln. Aber auch andere "Dinge" sind wie Programme einer Sprache zu analysieren und zu verarbeiten: Filter-Werkzeuge wie grep, sed oder awk agieren auf einem (zeilenweisen) Strom von Zeichen, analysieren die Zeichen und geben einen Strom von Zeichen aus. Applikationen lesen, untersuchen und schreiben Konfigurationsdateien. Pretty-Printer oder auch Präprozessoren erkennen Programme einer höheren Sprache und geben diese textuell abgeändert wieder aus. Techniken des Compilerbaus finden daher in der Entwicklung von Software auch weiterhin häufig Verwendung. Allerdings ist die Entwicklung derartiger Software noch immer nicht ohne Probleme: Die Entwicklung von Übersetzer-Software ist von Hand sehr mühsam und fehleranfällig, und die entwickelten Übersetzer sind nur schwer zu erweitern. Es empfiehlt sich daher, Werkzeuge zur Generierung von Software zu verwenden. Diese sind allerdings für Anfänger nicht leicht zu erlernen und fest auf ihre Funktionalität begrenzt. Eine Erweiterung der Werkzeuge ist kaum möglich. Xerox PARC hat, basierend auf Ideen der Sprache Simula, etwa um 1970 anhand der Programmiersprache Smalltalk die Technik der objekt-orientierten Programmierung erfunden. Objekt-orientierte Programmierung ist das Programmierkonzept der vergangenen Jahre. Viele der heute verwendeten Programmiersprachen sind entweder von Grund auf objekt-orientiert (zum Beispiel Java, C++ oder SmallTalk) oder wurden im Lauf der Zeit mit objekt-orientierten Erweiterungen versehen (zum Beispiel Basic oder Pascal). Selbst manche Skriptsprachen besitzen objekt-orientierte Eigenschaften (zum Beispiel JavaScript oder Python), und selbst nicht objekt-orientierte Sprachen wie C können objekt-orientiert verwendet werden. Es ist daher naheliegend, die Objekt-Orientierung auf das Problem der Verarbeitung von Sprachen anzuwenden, um zu zeigen, daß ... ... durch den Einsatz der objekt-orientierten Programmierung die Entwicklung von (Teilen von) Compilern vereinfacht werden kann. ... die so entwickelten Werkzeuge und deren Resultate an Mächtigkeit gegenüber den Werkzeugen und Resultaten der gängigen Techniken gewinnen. ... auch objekt-orientiert konzipierte Software des Compilerbaus der Vorteil der leichten Erweiterbarkeit zugute kommt. ... die Wiederverwendung von Klassen und Objekten die Entwicklung und Verwendung von Scannern oder Compilern erleichtert. ... die objekt-orientierte Programmierung ein Automatismus für divide & conquer ist und auch hier gewinnbringend genutzt werden kann. Selbst komplexe Algorithmen des Compilerbaus zerfallen so in kleine, einfache Teilprobleme und sind dadurch in der Lehre für Studierende leicht zu verstehen bzw. sogar selbständig zu entdecken. ... der Einsatz verschiedener typischer Entwurfsmuster der Objekt-Orientierung die Flexibilität und Erweiterbarkeit zum Beispiel eines Scanners oder eines Compilers wesentlich erhöht.

Objective: This document is not an introduction to parser generators. Readers should rather have a good understanding of them, especially of LALR parser generators. This document merely describes the main aspects of the implementation of a LALR parser generator named wisent. It is divided into a concise description of the programming interface and an overview over the data structures and specifics of the implementation of the wisent parser generator.

Die modellgetriebene Entwicklung (MDD) ist ein Ansatz, um formale Modelle automatisiert in ausführbare Software zu übersetzen. Obwohl dieses Vorgehen die Häufigkeit von Fehlern im generierten Quellcode verringert, können immer noch die Ausgangsmodelle fehlerhaft sein. Deshalb sind zusätzliche Prüfverfahren, wie z.B. die Verwendung eines Model Checkers sinnvoll. Er stellt automatisiert sicher, dass ein Modell alle gestellten Anforderungen erfüllt. Das Ziel dieser Arbeit ist daher die Integration eines Model Checkers in den modellgetriebenen Entwicklungsprozess, um die Qualität von Software-Produkten zu verbessern. Zu diesem Zweck wird das sogenannte DSL Verification Framework (DVF) vorgestellt. Es stellt Entwicklern vorgefertigte Sprachkonstrukte zur Verfügung, um die Implementierung von Parsern und Transformatoren zu erleichtern. Des Weiteren berücksichtigt es auch die "State Space Explosion", damit auch größere Modelle verifizierbar bleiben. Um die praktische Nutzung des DVF zu evaluieren, werden zwei Industriefallstudien durchgeführt.

In dieser Habilitationsschrift wird die formale Semantik der standardisierten Spezifikationssprache SDL (Specification and Description Language) beschrieben. Da SDL eine sehr umfangreiche Sprache ist, wurde eine repräsentative eingeschränkte Sprache RSDL (Restricted SDL) ausgewählt, um die Konzepte der formalen Definition von SDL darzustellen. Die vorliegende Habilitationsschrift umfaßt zwei große Teile: die Definition der formalen Semantik von RSDL und ihre Implementierung. Die formale Definition der Semantik von RSDL ist verständlich, leicht mit der informalen Beschreibung zu vergleichen und repräsentiert die grundsätzliche Vorstellung von RSDL. Für die Beschreibung werden zwei Teile unterschieden, nämlich die statische Semantik und die dynamische Semantik. Die statische formale Sprachdefinition besteht aus einer konkreten Syntax, einer Menge von Korrektheitsbedingungen, einer Menge von Transformationsregeln und einer abstrakten Syntax als Basis für die dynamische Semantik. Das Ergebnis der statischen Beschreibung ist eine Repräsentation der Spezifikation in abstrakter Syntax. Die Formalisierung der dynamischen Semantik beginnt mit der abstrakten Syntax. Aus dieser abstrakten Syntax wird ein Verhaltensmodell abgeleitet, das auf der mathematischen Theorie der Abstrakten Zustandmaschinen ASM (Abstract State Machines) basiert. Um die Definition der Semantik besonders übersichtlich zu gestalten, wird eine Spezielle Abstrakte Maschine (SAM) unter Nutzung von ASM definiert. Diese abstrakte Maschine stellt eine abstrakte SDL-Maschine dar. Die formale Semantik beschreibt die Eigenschaften von SDL exakt. Um jedoch herauszufinden, ob die Semantik korrekt ist, muß sie mit der Sprachbeschreibung und den Intentionen der Sprachentwickler verglichen werden. Dies geschieht am einfachsten durch eine korrekte Implementierung der Semantik. Die Implementierung der formalen Semantik basiert auf einer Repräsentation der Eingabe als abstrakter Syntaxbaum. Um die Semantik mit minimalem Aufwand zu implementieren, werden existierende Werkzeuge verwendet. Der Compiler wird mit den Standardwerkzeugen lex und yacc generiert. Nach der Syntaxanalyse wird die weitere Verarbeitung über dem abstrakten Syntaxbaum der Eingabe definiert. Die Verarbeitung von abstrakten Syntaxbäumen wird durch ein Werkzeug namens kimwitu erledigt. Mit der hier vorgestellten Technologie wurde die formale Semantik von RSDL implementiert. Entsprechend wird die formale Semantik von SDL implementiert. / In this habilitation thesis the formal semantics of the standardised specification language SDL (Specification and Description Language) is described. Because of the size of the language SDL a representative subset of the language called RSDL (Restricted SDL) was selected to present the concepts of the formal definition. In this thesis two major parts are covered: the definition of the formal semantics and its implementation. The RSDL formal semantics is intelligible, easily comparable with the informal description and represents the general understanding of RSDL. We distinguish between two phases of the definition, namely the static semantics and the dynamic semantics. The static semantics comprises the definition of a concrete grammar, a set of correctness constraints, a set of transformation rules and an abstract syntax as basis for the dynamic semantics. The result of the static semantics is a representation of the specification in abstract syntax. The dynamic semantics starts with the abstract syntax. From here a behaviour model is derived based on the theory of Abstract State Machines (ASM). In order to keep the presentation intelligible a special abstract machine is defined using ASM. This abstract machine in fact represents an abstract SDL-machine. The formal semantics describes the properties of SDL exactly. However, in order to check the correctness of the formalisation, it has to be compared with the informal language description and the intentions of the language designers. This is most easily done using a correct implementation of the semantics. The implementation of the semantics is based on a representation of the input as an abstract syntax tree. For implementing the semantics with minimal effort existing tools are used. The compiler is produced using the standard tools lex and yacc. After parsing the remaining processing is defined over abstract syntax trees, which is covered by a tool called kimwitu. The formal semantics of RSDL is implemented using these tools. The same approach is applicable for SDL.