[Prev][Next][Index][Thread]
Thesis: Syntax Definition for Language Prototyping

To: types@cs.indiana.edu

Subject: Thesis: Syntax Definition for Language Prototyping

From: Eelco Visser <visser@wins.uva.nl>

Date: Thu, 04 Sep 1997 15:39:59 +0200

DeliveryDate: Thu, 04 Sep 1997 08:40:40 0500
Last week my PhD thesis was delivered from the printer:
Syntax Definition for Language Prototyping
Eelco Visser
ISBN 9074795757
University of Amsterdam
1997
383 pages + viii
I have a few copies left. So if you are interested drop me an email
with your address.
Regards,
Eelco Visser
P.S. The complete thesis is not available online, but
http://adam.wins.uva.nl/~visser/thesis/
contains some excerpts from the thesis including the complete
introduction.

mail:visser@acm.org
http://adam.wins.uva.nl/~visser/

>From the introduction

Language prototyping is the activity of designing and testing
definitions of new or existing computer languages. An
important aspect of a language definition is the definition of
its syntax. The subject of this thesis are new formalisms and
techniques that support the development and prototyping of
syntax definitions. There are four main subjects: (1)
Techniques for parsing and disambiguation of contextfree
languages. (2) Design and implementation of a new syntax
definition formalism. (3) Design of a multilevel algebraic
specification formalism. (4) Study of polymorphic syntax
definition.

This thesis is concerned with the design and implementation of
methods to enhance the expressive power and usability of the
syntactic aspects of language definition formalisms. The main
theme is the development of techniques for providing an
expressive syntax definition formalism. The point of departure
is the syntax definition formalism SDF of Heering et
al. (1989) that is used in combination with the algebraic
specification formalism ASF of Bergstra et al. (1989). This
setting provides the direct background and motivation for this
work, but the techniques developed are applicable in other
syntax definition settings as well. There are four main
results:
 Scannerless generalizedLR parsing is a new approach to
parsing without scanners that solves a number of problems of
conventional parsing techniques, by combining the following
techniques: parsing without scanner, generalizedLR parsing,
static disambiguation with priority and associativity
declarations, lexical disambiguation with follow restrictions
and reject productions.
 SDF2 is an expressive syntax definition formalism for
contextfree syntax defintion. It is a redesign of SDF as a
family of orthogonally defined features for syntax definition.
 The multilevel algebraic specification formalism MLS
extends firstorder manysorted algebraic specification by
making the sorts used in a signature a userdefinable
algebraic data type. This provides a simple and uniform
framework for the specification of advanced type constructs
including polymorphism and higherorder functions.
 Polymorphic syntax definition is the combination of the
flexible notation facilities of SDF with the flexible typing
facilities of MLS.

CONTENTS
1 Introduction 1
1.1 General 1
1.2 Part I: Contextfree Parsing Techniques 4
1.3 Part II: A Family of Syntax Definition Formalisms 6
1.4 Part III: MultiLevel Algebraic Specification 7
1.5 Part IV: Polymorphic Syntax Definition 9
1.6 Short Trips 9
1.7 Origins of the Chapters 11
2 Specification in ASF+SDF 13
2.1 Introduction 13
2.2 ManySorted Algebra 14
2.3 Grammars as Signatures 15
2.4 Conditional Equations 18
2.5 Term Rewriting 18
2.6 Modularization 18
2.7 The ASF+SDF MetaEnvironment 18
2.8 Literate Specification 19
2.9 Specification of Programming Languages 19
2.10 Literature 21
I ContextFree Parsing Techniques 23
3 Scannerless GeneralizedLR Parsing 25
3.1 Introduction 25
3.2 Scannerless Parsing 30
3.3 Grammar Normalization 36
3.4 Disambiguation 40
3.5 Parser Generation 45
3.6 Automatic Lexical Disambiguation 50
3.7 Reject Productions 52
3.8 GeneralizedLR Parsing 56
3.9 Implementation 66
3.10 Related Work 68
3.11 Conclusions 69
4 Disambiguation Filters 71
4.1 Introduction 71
4.2 Disambiguation 72
4.3 Preliminaries 74
4.4 Filters 76
4.5 Priorities 80
4.6 Prolog Operators 84
4.7 Offside Rule 86
4.8 Pattern Matching Filters 86
4.9 Discussion 90
4.10 Conclusions 92
5 A Case Study in Optimizing Parsing Schemata by Disambiguation Filters 93
5.1 Introduction 93
5.2 Preliminaries 95
5.3 Disambiguation Filters 96
5.4 Parsing Schemata 97
5.5 Priority Conflicts 99
5.6 From Earley to LR 102
5.7 Multiset Filter 107
5.8 Conclusions 111
II ContextFree Syntax Definition 113
6 A Family of Syntax Definition Formalisms 115
6.1 Introduction 115
6.2 An Overview of SDF2 118
6.3 Design 123
6.4 Organization 126
7 ContextFree Grammars 129
7.1 Symbols 129
7.2 Grammars 131
7.3 ContextFree Grammars (Kernel) 133
7.4 Basic Symbols 138
7.5 Parse Trees 144
8 Disambiguation and Abbreviation 157
8.1 Priorities 157
8.2 Regular Expressions 166
8.3 Lexical and ContextFree Syntax 174
8.4 Restrictions 181
9 Renaming and Modularization 185
9.1 Renamings 185
9.2 Aliases 192
9.3 Modules 195
10 The Syntax Definition Formalism SDF2 203
10.1 SDF2 203
10.2 Comparison to SDF 208
10.3 Discussion and Concluding Remarks 209
III MultiLevel Algebraic Specification 215
11 Extensions of FirstOrder Specification 217
11.1 Introduction 218
11.2 MultiLevel Specifications 220
11.3 Related Formalisms 223
11.4 Outline 226
12 Untyped and Simply Typed Specifications 227
12.1 Untyped Equational Specifications 227
12.2 OneLevel Specifications 232
12.3 Typechecking OneLevel Specifications 241
13 Examples of MultiLevel Specifications 253
13.1 Introduction 253
13.2 One Level 254
13.3 Two Levels 255
13.4 Polymorphic Data Types 257
13.5 Three Levels 262
13.6 Type Equations 264
14 Definition of MultiLevel Specifications 273
14.1 Syntax and Equational Logic 273
14.2 Modular Specifications 277
14.3 WellFormedness 279
14.4 Type Assignment 285
14.5 Typechecking 295
14.6 Discussion and Concluding Remarks 296
IV Polymorphic Syntax Definition 303
15 Polymorphic Syntax Definition 305
15.1 Introduction 305
15.2 Signatures and Grammars 307
15.3 TwoLevel Grammars 317
15.4 Examples 319
15.5 Properties 324
15.6 Parsing 327
15.7 Related Formalisms 330
15.8 Conclusions 332
V Epilogue 333
16 Concluding Remarks 335
16.1 Syntax 335
16.2 Type Systems 337
16.3 Program and Specification Schemata 337
VI Appendices 339
A Auxiliary Modules for the Specification of SDF2 341
A.1 Literals 341
A.2 ATerms 341
A.3 Renamings 346
A.4 SDF2 349
B Auxiliary Modules for MultiLevel Specifications 351
B.1 Library Modules 351
B.2 Term Utilities 354
C Samenvatting 365
C.1 Algemeen 365
C.2 Resultaten 367
D Bibliography 371
