Parsing mixfix expressions [Elektronische Ressource] : dealing with user-defined mixfix operators efficiently / vorgelegt von Jacob Wieland

Sujets

• Informatik

Informations

• Publié par: technische_universitat_berlin
• Publié le: 01 janvier 2009
• Nombre de lectures: 12
• Langue: English

Extrait

Parsing Mixfix Expressions
Dealing with User-Defined Mixfix Operators
Efficiently
vorgelegt von
Diplom Informatiker
Jacob Wieland
aus Berlin
Von der Fakult¨at IV - Elektrotechnik und Informatik
Technische Universit¨at Berlin
zur Erlangung des akademischen Grades
Doktor der Ingenieurwissenschaften
Dr. ing.
genehmigte Dissertation
Promotionsausschuss:
Vorsitzender: Prof. Dr. rer. nat. Volker Markl
Berichter: Prof. Dr. rer. nat. Peter Pepper
Berichter: Prof. Dr. ref. nat. Sabine Glesner
Tag der wissenschaftlichen Aussprache: 12.10.2009
Berlin 2009
D 831Acknowledgements
I want to thank my mother Karla Wieland for always supporting and motivating
me through childhood and education, and my father Robert Wieland who sparked
my interest into languages and mathematics.
I also want to thank my professor Prof. Peter Pepper for inspiring and allowing
me to write this thesis on the basis of his vision of future programming languages,
as well as giving me lots of feedback while working on it. Prof. Sabine Glesner also
gave me some useful pointers into the right direction.
I found the lively discussions with my colleagues Baltasar Trancon-y-Widemann
and Markus Lepper very enlightening, while implementing the algorithms together
with Diez B. Roggisch in a few Extreme Programming sessions helped me a lot to
finish the experimental aspect of the work.
Finally, I want to thank my wife Jessica for discussing my work with me and
making me finish it and also my friend Alexander Lorenz for proof-reading and
English language consultation.
23Contents
1 Introduction 8
1.1 Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.1 Computer Languages - What Are They Good For? . . . . . . 8
1.1.2 Documentation: Formal vs. Natural Language . . . . . . . . 8
1.2 Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.1 Natural-Language-Like Computer Language . . . . . . . . . . 9
1.2.2 Different Approaches To Parsing . . . . . . . . . . . . . . . . 9
1.3 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Algorithmic Approach . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.1 Integration of Parsing and Checking Phase . . . . . . . . . . 10
1.4.2 Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Overview 12
2.1 Notes on Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.1 Mixfix Operator Declaration . . . . . . . . . . . . . . . . . . 12
2.1.2 Built-In Mixfix Operators . . . . . . . . . . . . . . . . . . . . 13
2.1.3 Mixfix Operator Variables . . . . . . . . . . . . . . . . . . . . 13
2.2 Mixfix Operators — General Motivation . . . . . . . . . . . . . . . . 15
2.3 Motivations for Mixfix Operators . . . . . . . . . . . . . . . . . . . 16
2.3.1 Common Types of Mixfix Operators . . . . . . . . . . . . . . 16
2.3.2 Why User-Defined Mixfix Operators . . . . . . . . . . . . . . 23
2.3.3 Common Practices . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.4 The Problems to Solve . . . . . . . . . . . . . . . . . . . . . . 26
2.4 A Functional Mixfix Expression Language . . . . . . . . . . . . . . 27
2.4.1 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4.2 Means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5 Causes of Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5.1 Ambiguity of Mixfix Expressions in General . . . . . . . . . . 29
2.5.2 Ensuring Syntactic Unambiguity . . . . . . . . . . . . . . . . 31
2.5.3 Fixity and Precedence . . . . . . . . . . . . . . . . . . . . . . 33
2.5.4 Converter Operators . . . . . . . . . . . . . . . . . . . . . . . 35
2.5.5 Backbone Ambiguity . . . . . . . . . . . . . . . . . . . . . . . 36
2.5.6 Adjacent Operands . . . . . . . . . . . . . . . . . . . . . . . . 39
2.5.7 Polymorphism and Semantic Ambiguity . . . . . . . . . . . . 42
3 Description Tools 44
3.1 Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Separators, Identifiers and Backbones . . . . . . . . . . . . . . . . . 47
3.2.1 Backbone Grammar . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Fixities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.4 Syntactic Interpretations and Parse Trees . . . . . . . . . . . . . . . 49
43.5 Unification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5.1 Unification and Higher-Order-Functions . . . . . . . . . . . . 50
3.6 Precedence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.7 Two-Level Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4 A Functional Mixfix Expression Language 55
4.1 Mixfix Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.1 Phrases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.2 Meta Operators . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.3 Mixfix Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2 Meta Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2.1 Meta Type Expressions . . . . . . . . . . . . . . . . . . . . . 57
4.2.2 Enclosed Expressions . . . . . . . . . . . . . . . . . . . . . . . 58
4.2.3 Built-In Type Constructors . . . . . . . . . . . . . . . . . . . 58
4.2.4 Placeholders and Sections . . . . . . . . . . . . . . . . . . . . 59
4.2.5 Lifted Sections . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.2.6 Annotation Expressions . . . . . . . . . . . . . . . . . . . . . 61
4.2.7 Precedences of the Meta Operators . . . . . . . . . . . . . . . 62
4.2.8 Context-Free Meta Grammar . . . . . . . . . . . . . . . . . . 63
4.3 Mixfix Expression Language . . . . . . . . . . . . . . . . . . . . . . . 64
4.3.1 Mixfix Expressions . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3.2 Context-Free Mixfix Grammar . . . . . . . . . . . . . . . . . 65
4.4 Mixfix Language Type System . . . . . . . . . . . . . . . . . . . . . 66
4.4.1 Types and Values. . . . . . . . . . . . . . . . . . . . . . . . . 66
4.4.2 Type-Correctness and Ambiguity . . . . . . . . . . . . . . . . 66
4.4.3 Multi-Level Signatures . . . . . . . . . . . . . . . . . . . . . . 67
4.4.4 Bottom-Up Type Inference . . . . . . . . . . . . . . . . . . . 70
4.4.5 Top-Down Bottom-Up Type Inference . . . . . . . . . . . . . 71
4.4.6 Relationship between Bottom-Up and Top-Down Type Infer-
ence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.4.7 Sufficiency of Top-Down Bottum-Up Inference for Parsing . . 75
5 Ambiguity 76
5.1 Kinds of Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2 Normal Approaches to Ambiguity . . . . . . . . . . . . . . . . . . . 77
5.2.1 Syntactic Language Restrictions . . . . . . . . . . . . . . . . 77
5.2.2 Semantic Lan Restrictions . . . . . . . . . . . . . . . . 78
5.2.3tic Filters . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.3 Causes of Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.4 Shared Separator Tokens . . . . . . . . . . . . . . . . . . . . . . . . . 81
5.4.1 Avoiding Backbone Ambiguity by Backbone Parsing . . . . . 81
5.4.2 Avoiding Backbone Ambiguity by Separator Analysis . . . . 82
5.5 Adjacent Operands vs. Invisible Operators . . . . . . . . . . . . . . 83
5.5.1 Left-Weighted Interpretations . . . . . . . . . . . . . . . . . . 83
5.5.2 Adjacent Empty Operands . . . . . . . . . . . . . . . . . . . 87
5.5.3 Adjacent Concatenation Operands . . . . . . . . . . . . . . . 87
5.5.4 Adjacent Postfix and Prefix Operands . . . . . . . . . . . . . 88
5.5.5 Empty Operands in Concatenations . . . . . . . . . . . . . . 89
5.5.6 Unambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.6 Left-Open vs. Right-Open Operators . . . . . . . . . . . . . . . . . . 91
5.6.1 Natural Precedence. . . . . . . . . . . . . . . . . . . . . . . . 92
5.6.2 Ad-Hoc Precedence. . . . . . . . . . . . . . . . . . . . . . . . 98
5.6.3c Prec of Concatenation Operators . . . . . . . 104
55.7 Polymorphism and Converter Operators . . . . . . . . . . . . . . . . 105
5.7.1 Semantic Ambiguity caused by Polymorphism . . . . . . . . . 105
5.7.2 Converter Operators . . . . . . . . . . . . . . . . . . . . . . . 105
5.8 Proof of Unambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6 Two-Level Mixfix Grammars 110
6.1 From Context-Free Mixfix-Grammar to Two-Level Mixfix-Grammar 110
6.1.1 Two-Level Meta-Operator Grammar . . . . . . . . . . . . . . 111
6.1.2 Twel Mixfix-Operator Grammar . . . . . . . . . . . . . 111
6.1.3 Expression Attributes . . . . . . . . . . . . . . . . . . . . . . 112
6.1.4 Type Inference . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6.2 Mixfix-Grammar Constraints . . . . . . . . . . . . . . . . . . . . . . 117
6.2.1 Operator Kinds . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.2.2 Normal Operator Instantiations . . . . . . . . . . . . . . . . . 118
6.2.3 Type Annotation . . . . . . . . . . . . . . . . . . . . . . . . . 124
6.2.4 Scope Ann . . . . . . . . . . . . . . . . . . . . . . . . 124
6.2.5 Parenthesis Operator . . . . . . . . . . . . . . . . . . . . . . . 124