| URL: |
http://kops.ub.uni-konstanz.de/volltexte/2004/1199/ |
| Institut:
| Fachbereich Informatik und Informationswissenschaft
|
| Dokumentart: |
Diplomarbeit, Magisterarbeit |
| Sprache: |
Englisch |
| Erstellungsjahr: |
2003 |
| Publikationsdatum: |
04.03.2004 |
| Kurze Inhaltszusammenfassung auf Englisch |
For two regular types, the check for a subtype-relationship between them is in the context of constructing compiler for typed languages usually performed by an algorithm, which is based on the comparison of the finite automata corresponding to the original expressions. This algorithm induces some expensive operations on these automata. This thesis describes an approach of subtyping for two regular tree types, which avoids this expensive operations by using a term-rewriting system for regular expressions, based on the term-rewriting calculus of Valentin Antimirov. This approach induces a better runtime behaviour than the classical approach. The thesis also describes a prototypical object-oriented implementation of the calculus using the JAVA-language. |
| Kurze Inhaltszusammenfassung auf Deutsch |
Die Überprüfung zweier regulärer Typen, ob zwischen ihnen eine Subtyp-Beziehung besteht, wird ihm Rahmen der Konstruktion von Compilern für typisierte Sprachen üblicherweise durch einen Algorithmus geleistet, der auf dem Vergleich der zu diesen Typen korrespondierenden Automaten basiert. Dieses Verfahren beinhaltet z.T. recht teure Operationen. Diese Arbeit stellt einen Ansatz vor, der die Subtyp-Beziehung zwischen zwei regulären Baum-Typen durch ein Termersetzungssystem für reguläre Ausdrücke löst, basierend auf dem Termersetzungskalkül von Valentin Antimirov. Dieses Verfahren führt zu besserem Laufzeitverhalten, als der klassische Ansatz. Die Arbeit beschreibt auch eine exemplarische Implementation des Kalküls in der Sprache JAVA. |
| Freie Schlagwörter (Englisch): |
subtyping antimirov regular expressions tree-types |
| DDC-Sachgruppe: |
Informatik |
| Urheberrecht:
| Hinweis zum Urheberrecht |
PDF 373kB
