159 Pages
English
Gain access to the library to view online
Learn more

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

Gain access to the library to view online
Learn more
159 Pages
English

Description

Parsing Mixfix ExpressionsDealing with User-Defined Mixfix OperatorsEfficientlyvorgelegt vonDiplom InformatikerJacob Wielandaus BerlinVon der Fakult¨at IV - Elektrotechnik und InformatikTechnische Universit¨at Berlinzur Erlangung des akademischen GradesDoktor der IngenieurwissenschaftenDr. ing.genehmigte DissertationPromotionsausschuss:Vorsitzender: Prof. Dr. rer. nat. Volker MarklBerichter: Prof. Dr. rer. nat. Peter PepperBerichter: Prof. Dr. ref. nat. Sabine GlesnerTag der wissenschaftlichen Aussprache: 12.10.2009Berlin 2009D 831AcknowledgementsI want to thank my mother Karla Wieland for always supporting and motivatingme through childhood and education, and my father Robert Wieland who sparkedmy interest into languages and mathematics.I also want to thank my professor Prof. Peter Pepper for inspiring and allowingme 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 alsogave me some useful pointers into the right direction.I found the lively discussions with my colleagues Baltasar Trancon-y-Widemannand Markus Lepper very enlightening, while implementing the algorithms togetherwith Diez B. Roggisch in a few Extreme Programming sessions helped me a lot tofinish the experimental aspect of the work.

Subjects

Informations

Published by
Published 01 January 2009
Reads 12
Language English

Exrait

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
6.2.6 Binary Concatenation Operator . . . . . . . . . . . . . . . . . 125
6.2.7 Multi Concatenation Operators . . . . . . . . . . . . . . . . . 126
7 Two-Level Grammar Transformations 127
7.1 Motivation for Generalizing Grammar Transformations . . . . . . . . 127
7.1.1 Why Grammar Transformations? . . . . . . . . . . . . . . . . 127
7.1.2 Why Top-Down Transducers? . . . . . . . . . . . . . . . . . . 128
7.1.3 Why Two-Level Grammars? . . . . . . . . . . . . . . . . . . . 128
7.1.4 What about Semantic Actions? . . . . . . . . . . . . . . . . . 128
7.1.5 Usability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.2 Generalized Transformations . . . . . . . . . . . . . . . . . . . . . . 129
7.2.1 Unfolding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.2.2 Direct Left-Recursion Elimination . . . . . . . . . . . . . . . 130
7.2.3 Left Factorization . . . . . . . . . . . . . . . . . . . . . . . . 131
7.2.4 Action Shifting . . . . . . . . . . . . . . . . . . . . . . . . . . 132
7.2.5 Left Corner Transformation . . . . . . . . . . . . . . . . . . . 134
7.3 Optimizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.3.1 Partial Unfolding . . . . . . . . . . . . . . . . . . . . . . . . . 135
7.3.2 Avoiding Backtracking by Action Shifting . . . . . . . . . . . 136
7.4 Cyclic Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
7.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
8 Implementation Results 139
8.1 Mixfix Parsing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 139
8.1.1 Earley Backbone Parsing . . . . . . . . . . . . . . . . . . . . 139
8.1.2 Top-Down Backtrack Parsing . . . . . . . . . . . . . . . . . . 139
8.2 Mixfix Parsing Optimizations . . . . . . . . . . . . . . . . . . . . . . 140
8.2.1 Top-Down Restrictions for Adjacent Operators . . . . . . . . 140
8.2.2 Allowed Operand Operators . . . . . . . . . . . . . . . . . . . 141
8.2.3 Operator Hierarchies . . . . . . . . . . . . . . . . . . . . . . . 141
8.2.4 Maximal Application Depth . . . . . . . . . . . . . . . . . . . 144
8.2.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
69 Conclusion 148
9.1 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
9.2 The Functional Mixfix Language . . . . . . . . . . . . . . . . . . . . 148
9.3 Language Restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . 149
9.4 Parsing Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
9.5 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
9.6 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
9.6.1 Inspiration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
9.6.2 Comparison with Other Approaches to Mixfix Operators. . . 150
9.6.3 Programming Languages. . . . . . . . . . . . . . . . . . . . . 151
9.6.4 Two-Level Grammars . . . . . . . . . . . . . . . . . . . . . . 151
9.6.5 Type System . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
9.6.6 Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
9.7 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7Chapter 1
Introduction
1.1 Problem
1.1.1 Computer Languages - What Are They Good For?
Computer languages are used foremost as a means of communicating the demands
of the computer programmer to the machine that is supposed to process those de-
mands. For this purpose, they need to be formal and unambiguous, as well as
mechanically or automatically processable. High-level computer languages are also
used as a more or less abstract way of formulating algorithms, i.e. descriptions of
processes that solve certain problems to be used both by humans and machines.
Towards this purpose, computer languages have been developed which allow ab-
straction from the underlying architecture of the machine and to focus more on the
process description and program architecture, leaving the machine-specific details
to the automatic interpreter of the program. Modern programming languages even
include constructs that allow re-usability of existing programs to avoid constant
repetition of the same work by the programmers, and formal automatic or semi-
automatic reasoning about programs to ascertain specific properties they need to
fulfils to meet their purpose, e.g. that the number of computation steps needed
by the program is no larger than a certain amount to ensure that the program
terminates before the computation result is needed.
1.1.2 Documentation: Formal vs. Natural Language
1Normally, computer programs are often not easily readable , and thus not easily
understandable. In the modern world of computers, computer programs have be-
come so large and complex that it is imperative they are well documented, using
natural language, so that they can be understood by the human reader. But they
should also be well documented/specified for the machine, e.g. for automatically
finding errors in the program.
However, the problem with natural language documentation is that in general it
lacks the aforementioned properties of formality and unambiguity, therefore often
being a source of confusion to human readers, even if the documentation is in their
mother-tongue. The problem of course becomes even worse when natural language
2barriers have to be crossed between writer and reader .
To avoid such confusion, these properties of computer languages could make
them ideal as a means of communication between programmers as well, easing re-
1because of lots of parentheses, strange and arbitrary precedences between different operators,
etc.
2e.g. when everybody uses English, although it is not their mother-tongue
8useorrefactoringofprogramsfornewgoalsornewprogrammingenvironmentsand
finding of errors.
The reasons for the unreadability of common computer languages, even though
they resemble natural languages in some respects superficially, are mostly of a tech-
nical nature, stemming from restrictions imposed upon computers in the early days
of computer language development like very limited memory and slow processing
speed.
1.2 Solution
1.2.1 Natural-Language-Like Computer Language
The ideal solution for the understandability problem of computer programs would
be a computer language that is as close as possible to natural language, and thus
better understandable, but is still formal, unambiguous and efficiently processable
bymachines. Thiswouldmakethelanguagebothusefulasatoolforcommunication
between humans as well as between human and machine. Such a language would
have to resemble natural language more closely than common computer languages,
or at least allow using those formal constructs normally used by the programmers
3in their specific domains, and thus would be easier to read, write and understand .
1.2.2 Different Approaches To Parsing
Parsing Natural Language
A lot of the understandability problems of computer languages come from the dif-
ferent ways that languages are processed by humans and machines. In natural
languages, parsing, i.e. syntactic analysis and disambiguation, is often guided or
helped by semantic analysis and heuristic inferences from the context.
Parsing Common Computer Languages
In contrast, syntactic analysis of a computer program is normally done without
reference to context or semantics whatsoever, but instead simply uses rules de-
scribed by a context-free grammar. If that were not enough restriction already,
this grammar has to be syntactically unambiguous (i.e. allowing only one syntactic
interpretation of each sentence), or given additional rules to allow at most one syn-
tacticinterpretation(likeprecedencerulesbetweeninfixoperators). Certainclasses
of these grammars allow the automatic construction of efficient parsers using a for-
mal method, implemented by a computer program (e.g. yacc), that way largely
avoiding human programming errors during this task.
Parsing Natural-Language-Like Computer Languages
Taking the idea of the processes to parse natural languages, this thesis proposes
a different way of automatically parsing a computer language which allows user-
defined natural-language-like constructs, called mixfix operators. By tightly cou-
pling the syntactic and semantic analysis, using semantic and context information
4for syntactic disambiguation purposes, we will show that natural-language-like
computer languages are possible which have all the necessary properties and for
which there exist, nevertheless, efficient parsing methods.
3e.g. by allowing mathematicians or physicists to write down their formulae the same way they
would write them on paper
4i.e. parsing
9