Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-2333
Main Title: Parsing Mixfix Expressions. Dealing with User-Defined Mixfix Operators Efficiently
Translated Title: Parsieren von Mixfix-Ausdrücken. Effizienter Umgang mit Nutzer-Definierten Mixfix-Operatoren
Author(s): Wieland, Jacob
Advisor(s): Pepper, Peter
Granting Institution: Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Die Arbeit beschäftigt sich mit dem Thema Mixfix-Operatoren, einem Konzept, welches eine Verallgemeinerung der in gängigen Programmiersprachen üblichen Operatoren, Funktionen, Prozeduren und sonstigen Konstrukte darstellt. Es soll gezeigt werden, daß es möglich ist, dem Nutzer von Programmiersprachen zu erlauben, solche Operatoren in fast beliebiger Form selbst inneralb dieser Sprachen zu definieren, um diese dann in sogenannten Mixfix-Ausdrücken benutzen zu können. Dies soll zur besseren Schreib- und Lesbarkeit von Programmiersprachen beitragen und damit zur ihrer besseren Benutzbarkeit sowie erhöhter Wartbarkeit von darin geschriebenen Programmen aus softwaretechnischer Sicht. Sprachen mit solchen Ausdrücken können außerdem besser an die Bedürfnisse der sie benutzenden Kreise angepasst werden. Es werden notwendige Einschränkungen der definierbaren Operatoren vorgestellt, so daß die Sprache der Mixfix-Ausdrücke syntaktisch eindeutig wird und effiziente Verfahren der syntaktischen Analyse solcher Ausdrücke möglich werden, welche ebenfalls erläutert werden. Die Gründe für diese Einschränkungen werden motiviert durch die möglichen Ursachen für syntaktische Mehrdeutigkeit in Mixfix-Ausdrücken, nämlich in mehreren Operatoren vorkommende Separator-Teile, aneinander angrenzende Operanden und unsichtbare Operatoren, natürliche und benutzerdefinierte Präzendenz von Operatoren, sowie Konverter-Operatoren und Polymorphie von Operatoren. Es werden bewußt keine Einschränkungen auf die Sprache der Mixfix- Ausdrücke eingeführt, die auf das Verfahren der Parsierung zurückzuführen sind, sondern nur solche, die aus den oben genannten Gründen zwingend notwendig sind. Die Arbeit diskutiert kritisch die bisherigen Ansätze, mit Mixfix-Operatoren in Programmiersprachen umzugehen und legt Gründe offen, warum diese Ansätze für eine so mächtige Sprache von Mixfix-Ausdrücken wie der hier vorgestellten nicht angemessen sind. Ein von der klassischen Vorgehensweise abweichender Ansatz wird diskutiert, bei dem aus den vom Nutzer definierten Mixfix-Operatoren Zwei-Stufen- Grammatiken für die Sprache der Mixfix-Ausdrücke abgeleitet werden. Die Implementation des Parsierungsvorgangs verwendet diese Grammatiken derart, daß die syntaktische Analyse mit Teilen der semantischen Analyse verquickt wird und somit Typ-Inferenz auf die Parsierung Einfluß nehmen kann. Das Verfahren wird am Beispiel einer modernen funktionalen Programmiersprache geschildert. Es sollte gezeigt werden, dass so gut wie keine Einschränkungen der Konzepte dieser sehr mächtigen Sprachen notwendig sind, wenn benutzerdefinierte Mixfix-Operatoren darin eingeführt werden. Es wäre dementsprechend ebenso möglich, solche Operatoren auch in weniger ausdrucksmächtigen Sprachen einzuführen.
This thesis revolves around mixfix operators, a concept which is a generalization of the usual operators, functions, procedures and other structured constructs to be found in common programming languages. We show that it is possible to allow the user of a programming language to define such operators in almost arbitrary fashion inside the language itself to be used in so-called mixfix expressions. This shall contribute to a heightened readability and easier writing of such programming languages, thus making them more easily usable and by that better maintainable from a software- engineering point of view. As an additional benefit, programming languages containing mixfix expressions also allow better customization to the needs of the circles using them. We describe the necessary restrictions to be imposed on the user-defined mixfix operators and expressions so that the latter become unambiguous while still allowing efficient algorithms for syntactic analysis, which will also be proposed. These restrictions are motivated solely by the four causes of possible ambiguity of mixfx expressions that we have determined, namely shared sep- arator tokens between operators, adjacent operands and invisible operators, natural and user-defined ad-hoc precedence relations between operators, as well as converter operators and polymorphism. We expressly refrain from re- strictions motivated by different efficient parsing strategies, but only introduce restrictions which are definitely necessary to avoid the causes of ambiguity. The commonly used approaches to the problems imposed by mixfix operators in programming languages are criticized concluding that they are ill fit to deal adequately with such operators in a general mixfix expression language. Therefore, we propose a strategy which diverts from the classic approaches by using two-level grammars for the mixfix expressions derived directly from the user-defined mixfix operator signatures. The implementation of the parsing process of such expressions uses these grammars in such a way that parts of the semantic analysis, i.e. partial type-inference, can have an influence on the syntactical analysis. The whole process is explained by using as an example a modern functional programming language. We aim to show that if the possibility to define and apply user-defined mixfix operators is introduced into such a language almost no restrictions on its powerful concepts need to be added. Following that, it would likewise be possible to introduce such operators also in languages with less powerful expression concepts.
URI: urn:nbn:de:kobv:83-opus-25083
http://depositonce.tu-berlin.de/handle/11303/2630
http://dx.doi.org/10.14279/depositonce-2333
Exam Date: 12-Oct-2009
Issue Date: 8-Jan-2010
Date Available: 8-Jan-2010
DDC Class: 004 Datenverarbeitung; Informatik
Subject(s): Backbone
Mixfix-Ausdruck
Mixfix-Operator
Mixfix-Parsierung
Zwei-Stufen-Grammtik-Transformationen
Backbone
Mixfix expression
Mixfix operator
Mixfix parsing
Two-level grammar transformations
Creative Commons License: https://creativecommons.org/licenses/by-sa/2.0/de
Appears in Collections:Fakultät 4 Elektrotechnik und Informatik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_46.pdf706.12 kBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons