Introduction Definition of Programming Languages

Cover......Page 0000
Copyright......Page 0002
Contents......Page 0005
Preface......Page 0009
1.1 Reasons for having a definition......Page 0011
1.2 Desirable qualities......Page 0013
1.3 The scope of this book......Page 0014
2.1.1 Background......Page 0016
2.1.2 The definition of a grammar......Page 0018
2.1.3 The Chomsky hierarchy......Page 0021
2.2.1 The parsing problem......Page 0022
2.2.2 Recursive descent......Page 0025
2.2.3 Ambiguity in grammars......Page 0028
2.3 Grammars for parsing......Page 0029
2.3.1 LL(k)-grammars......Page 0030
2.3.2 LR(k)-grammars......Page 0033
2.3.3 Comparing LL- and LR-grammars......Page 0036
2.4 Theoretical results......Page 0037
3.1.1 The history of FORTRAN......Page 0040
3.1.2 Implementation considerations......Page 0044
3.1.3 The 1966 FORTRAN Standards......Page 0047
3.1.4 The FORTRAN 77 Standard......Page 0048
3.2 The Revised ALGOL 60 Report......Page 0052
3.2.1 The ALGOL 60 syntax......Page 0053
3.2.2 Deficiencies in BNF notation......Page 0056
3.2.3 Extensions to BNF notation......Page 0057
3.2.4 Semantics and other sections......Page 0063
3.2.5 Further comments......Page 0067
3.2.6 Conclusions......Page 0069
3.2.7 The Modified Report on ALGOL 60......Page 0070
3.3.1 S-expressions......Page 0071
3.3.2 M-expressions......Page 0073
3.3.3 The lambda notation......Page 0075
3.3.4 Conversion from M-expressions to S-expressions......Page 0076
3.3.5 The LISP interpreter......Page 0077
3.3.6 Commentary......Page 0079
4.1.1 History......Page 0081
4.1.2 Syntax......Page 0082
4.1.3 The T-notation......Page 0084
4.1.4 Expressions......Page 0086
4.1.5 Conclusions on syntax......Page 0090
4.1.6 Semantics......Page 0091
4.2.1 History......Page 0093
4.2.2 The 1968 Standard......Page 0095
4.2.3 The definition of clauses......Page 0097
4.2.4 The 1974 Standard......Page 0100
4.3 BASIC......Page 0101
5.1 The history of PL/I and its definitions......Page 0105
5.2 The PL/I Standard......Page 0108
5.2.1 Summary of the definition method......Page 0109
5.2.2 Syntactic notation......Page 0110
5.2.3 The concrete and abstract syntaxes......Page 0114
5.2.4 The interpreter......Page 0117
5.2.5 Combining the different aspects of the PL/I definition......Page 0119
5.3 The Vienna Definition Language......Page 0121
5.3.1 The set of objects......Page 0123
5.3.2 The mu-operator......Page 0125
5.3.3 Predicates......Page 0128
5.3.4 Lists of objects......Page 0129
5.3.5 Abstract syntax......Page 0131
5.3.6 The abstract machine......Page 0133
5.3.7 The interpreter......Page 0140
5.4 Final remarks......Page 0146
6. Definitions of PASCAL......Page 0148
6.1.1 Motivation......Page 0149
6.1.2 Attribute grammars......Page 0153
6.1.3 Algorithms and theoretical results......Page 0157
6.2.1 Introductory remarks......Page 0162
6.2.2 Application to PASCAL......Page 0163
6.3 Axiomatic semantics......Page 0169
6.3.1 Program verification......Page 0170
6.3.2 Notation and terminology......Page 0175
6.3.3 Application to PASCAL......Page 0178
6.3.4 Commentary on the axiomatic approach......Page 0182
7.1 Introductory remarks......Page 0185
7.2 Representations......Page 0188
7.3 The standard environment......Page 0190
7.4.1 Skeleton syntax......Page 0193
7.4.2 Production rules of the language......Page 0196
7.4.3 Inserting modes into the syntax......Page 0201
7.4.4 Introducing predicates into the syntax......Page 0206
7.4.5 Some examples......Page 0210
7.5 Semantics......Page 0213
7.6 Concluding remarks......Page 0214
8. Denotational semantics......Page 0219
8.1 Introduction to basic ideas......Page 0220
8.2 The lambda calculus......Page 0222
8.3 Self-application and inconsistency......Page 0228
8.4 The idea of approximation......Page 0230
8.5 The semantic domains......Page 0233
8.6 Application of Scott\'s work......Page 0235
8.7 Environments and stores......Page 0237
8.8 Continuations......Page 0239
8.9 Illustrations......Page 0242
8.10 Language design......Page 0246
9.1 Syntax......Page 0250
9.2 Semantics......Page 0252
9.3 Other directions of progress......Page 0254
9.4 Final remarks......Page 0259
Miscellaneous exercises......Page 0261
References......Page 0265
Author index......Page 0271
Subject index......Page 0273