TU Darmstadt / ULB / tuprints

Efficient and Compatible Bidirectional Formal Language Translators based on Extended Triple Graph Grammars

Klar, Felix :
Efficient and Compatible Bidirectional Formal Language Translators based on Extended Triple Graph Grammars.
TU Darmstadt
[Ph.D. Thesis], (2012)

[img]
Preview
PDF
diss-klar_screen_withcoloredhyperrefs.pdf
Available under Creative Commons Attribution Non-commercial No Derivatives.

Download (4Mb) | Preview
Item Type: Ph.D. Thesis
Title: Efficient and Compatible Bidirectional Formal Language Translators based on Extended Triple Graph Grammars
Language: English
Abstract:

In the context of model-driven engineering, models play an important role in everyday life. Models are used to abstract from certain subjects and to describe artifacts and procedures. In software engineering, a system under development is often modeled on different levels of abstraction and from multiple perspectives which results in plenty of models. Moreover, the resulting models depend on each other and the need for automatically translating between related models arises in order to reduce costs, errors, and laborious manual work and to speed-up development processes.

The model-driven engineering approach proposes model transformations as a key concept of model-based development which allows to automatically refine and transform models or translate between related models. Especially, bidirectional translators are often required which are able to automatically keep related models in a consistent state. The goal of bidirectional model transformations, which allow to execute transformations defined between a source and target model in both directions, is to assist in such situations. To be able to specify (bidirectional) model transformations the need for (bidirectional) model transformation languages arises.

Triple graph grammars (TGGs) are a formally founded bidirectional transformation language based on graph transformations with precisely defined semantics. A TGG specification describes correspondence relationships between two languages and consists of a set of productions that declaratively specify the simultaneous evolution of both related models. The main advantage of triple graph grammars is the possibility to automatically derive bidirectionally working forward and backward translators from a TGG specification that fulfill the fundamental properties efficiency and compatibility.

The grand challenge is to build translators that are efficient on the one hand and are compatible with respect to the TGG specification on the other hand. Compatibility means that translators are correct and complete with respect to the specification, i.e., pairs of models are in a consistent state after the translation operation and valid models are able to be translated into corresponding models. Moreover, the overall expressiveness of the triple graph grammar language has to be increased in order to create usable transformation specifications. But, it has to be ensured that derived translators still fulfill the fundamental properties.

In this thesis, the expressiveness of triple graph grammars is increased by supporting negative application conditions (NACs) that allow to restrict the applicability of transformation rules, which is required in certain cases. In addition, we accept the challenge of providing an efficiently working translation algorithm that still fulfills the properties correctness and completeness. We extend the expressiveness of triple graph grammars by a precisely defined class of NACs together with a new translation algorithm such that for the first time the fundamental properties of TGG-based translators are still satisfied. The resulting translators nevertheless have a polynomial runtime complexity and, therefore, can be considered efficient. Moreover, they are compatible with their triple graph grammar, which makes these translators usable in practice. In conclusion, the extended triple graph grammar formalism is applicable in real world scenarios, where model transformations are bidirectionally executed to keep related models in a consistent state.

Alternative Abstract:
Alternative AbstractLanguage
Im Zusammenhang mit der modellgetriebenen Entwicklung spielen Modelle eine wichtige Rolle im täglichen Leben. Modelle werden verwendet um von bestimmten Gegebenheiten zu abstrahieren und um Artefakte und Abläufe zu beschreiben. In der Software-Entwicklung wird ein zu entwickelndes System zumeist auf unterschiedlichen Abstraktionsebenen und von mehreren Perspektiven aus betrachtet, was in einer Vielzahl von Modellen resultiert. Die daraus resultierenden Modelle hängen voneinander ab und eine automatische Übersetzung zwischen diesen Modellen ist wünschenswert, um Kosten, Fehler und mühsame Handarbeiten zu reduzieren und Entwicklungsprozesse zu beschleunigen. Der modellgetriebene Entwicklungsansatz schlägt Modelltransformationen als ein Schlüsselkonzept der modellbasierten Entwicklung vor, das es erlaubt automatisch Modelle zu verfeinern und zu transformieren oder zwischen zueinander in Beziehung stehenden Modellen zu übersetzen. Insbesondere werden oft bidirektionale Übersetzer benötigt, die in der Lage sind in Beziehung stehende Modelle automatisch in einem konsistenten Zustand zu halten. Das Ziel von bidirektionalen Modelltransformationen ist es, in den genannten Situationen zu unterstützen. Bidirektionale Transformationen erlauben es, die zwischen einem Quell- und Zielmodell definierten Transformationen in beide Richtungen auszuführen. Um (bidirektionale) Modelltransformationen zu spezifizieren, werden (bidirektionale) Modelltransformationssprachen benötigt. Tripel-Graph-Grammatiken (TGGs) sind eine formal fundierte bidirektionale Transformationssprache, die auf Graphtransformationen beruht und eine präzise definierte Semantik besitzt. Eine TGG-Spezifikation gibt die übereinstimmenden Zusammenhänge zwischen zwei Sprachen an und besteht aus einem Satz von Produktionen, die in deklarativer Weise die simultane Entwicklung zweier in Beziehung stehender Modelle beschreibt. Ein Hauptvorzug von Tripel-Graph-Grammatiken ist die Möglichkeit automatisch bidirektional arbeitende Vorwärts- und Rückwärtsübersetzer aus einer TGG-Spezifikation abzuleiten, die die fundamentalen Eigenschaften "Effizienz" und "Kompatibilität" erfüllen. Die große Herausforderung ist es Übersetzer zu bauen, die auf der einen Seite effizient sind und auf der anderen Seite kompatibel bezogen auf ihre TGG-Spezifikation. Kompatibilität bedeutet, dass Übersetzer korrekt und vollständig bezogen auf ihre Spezifikation sind, d.h. Paare von Modellen sind nach dem Übersetzungsprozess in einem konsistenten Zustand und Modelle, die gültig gemäß Spezifikation sind, können in entsprechende Modelle übersetzt werden. Zudem wird die Ausdrucksstärke von Tripel-Graph-Grammatiken erhöht, um in der Lage zu sein benutzbare Transformations-Spezifikationen zu erstellen. Dabei muss immer darauf geachtet werden, dass abgeleitete Übersetzer die oben genannten fundamentalen Eigenschaften erfüllen. In dieser Arbeit wird die Ausdrucksstärke von Tripel-Graph-Grammatiken durch negative Anwendungsbedingungen (NACs) erhöht. Diese erlauben es die Anwendbarkeit von Transformationsregeln einzuschränken, was in bestimmten Fällen nötig ist. Zusätzlich stellen wir uns der Herausforderung einen effizient arbeitenden Übersetzungs-Algorithmus zu entwickeln, der zusätzlich die Eigenschaften "Korrektheit" und "Vollständigkeit" erfüllt. Wir erhöhen die Ausdrucksstärke von Tripel-Graph-Grammatiken um eine präzise definierte Klasse von NACs und stellen einen neuen effizienten Übersetzungs-Algorithmus vor, so dass gleichzeitig die fundamentalen Eigenschaften von TGG-basierenden Übersetzern erfüllt bleiben. Die resultierenden Übersetzer haben trotzdem polynomielle Laufzeitkomplexität und können daher als effizient angesehen werden. Desweiteren sind sie kompatibel mit ihrer Tripel-Graph-Grammatik, was diese Übersetzer in der Praxis einsetzbar macht. Zusammenfassend lässt sich sagen, dass der erweiterte Tripel-Graph-Grammatik-Formalismus in Alltagsszenarien einsetzbar ist, in denen Modelltransformationen bidirektional ausgeführt werden, um miteinander in Beziehung stehende Modelle in einem konsistenten Zustand zu halten.German
Alternative keywords:
Alternative keywordsLanguage
TGG, TGGs, bidirectional, model transformation, translation, metamodelEnglish
TGG, TGGs, bidirektional, Modelltransformation, Sprach-Übersetzung, MetamodellGerman
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Elektrotechnik und Informationstechnik > Echtzeitsysteme
Date Deposited: 20 Feb 2012 08:49
Last Modified: 07 Dec 2012 12:04
URN: urn:nbn:de:tuda-tuprints-28942
License: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0
Referees: Schürr, Prof. Dr. Andy and Zündorf, Prof. Dr. Albert
Refereed: 10 February 2012
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/2894
Export:

Actions (login required)

View Item View Item