Programming Language Pragmatics
FOURTH EDITION
Michael L. Scott
Department of Computer Science
University of Rochester
Morgan Kaufmann is an imprint of Elsevier
225 Wyman Street,Waltham, MA 02451, USA
British Library Cataloguing in Publication Data
A catalogue record for this book is available from the British Library
Library of Congress Cataloging-in-Publication Data
A catalog record for this book is available from the Library of Congress
For information on all MK publications
visit our website at http://store.elsevier.com/
ISBN: 978-0-12-410409-9
Copyright © 2016, 2009 , 2006, 1999 El se vier Inc.
About the Author
Michael L. Scott is a professor and past chair of the Department of Computer Sci-
ence at the University of Rochester. He received his Ph.D. in computer sciences in
1985 from the University of Wisconsin–Madison. From 2014–2015 he was a Vis-
iting Scientist at Google. His research interests lie at the intersection of program-
ming languages, operating systems, and high-level computer architecture, with an
emphasis on parallel and distributed computing. His MCS mutual exclusion lock,
co-designed with John Mellor-Crummey, is used in a variety of commercial and
academic systems. Several other algorithms, co-designed with Maged Michael,
Bill Scherer, and D oug Lea, appear in the
java.util.concurrent standard li-
brary. In 2006 he and D r. Mellor-Crummey shared the ACM SIGACT/SIGOPS
Edsger W. Dijkstra Prize in Distributed Computing.
Dr. Scott is a Fellow of the Association for Computing Machinery, a Fellow of
the Institute of Electr ical and Electronics Engineers, and a member of Usenix, the
Union of Concerned Scientists, and the American Association of University Pro-
fessors. The author of more than 150 refereed publications, he served as General
Chair of the 2003 ACM Symposium on Operating Systems Principles (SOSP) and
as Program Chair of the 2007 ACM SIGPLAN Workshop on Transactional Com-
puting (TRANSACT ), the 2008 ACM SIGPLAN Symposium on Principles and
Practice of Parallel Programming (PPoPP), and the 2012 International Confer-
ence on Architectural Support for Programming Languages and Operating Sys-
tems (ASPLOS). In 2001 he received the University of Rochester’s Robert and
Pamela Goergen Award for Distinguished Achievement and Artistry in Under-
gr aduate Teaching.
Contents
Foreword xxiii
Preface xxv
I FOUNDATIONS 3
1 Introduction 5
1.1 The Art of Language Design 7
1.2 The Programming Language Spectrum 11
1.3 Why Study Programming Languages? 14
1.4 Compilation and Interpretation 17
1.5 Programming Environments 24
1.6 An Overview of Compilation 26
1.6.1 Lexical and Syntax Analysis 28
1.6.2 Semantic Analysis and Intermediate Code Generation 32
1.6.3 Target Code Generation 34
1.6.4 Code Improvement 36
1.7 Summar y and Concluding Remarks 37
1.8 Exercises 38
1.9 Explorations 39
1.10 Bibliographic Notes 40
2 Programming Language Syntax 43
2.1 Specifying Syntax: Regular Expressions and Context-Free Grammars 44
2.1.1 Tokens and Regular Expressions 45
2.1.2 Context-Free Grammars 48
2.1.3 Derivations and P arse Trees 50
2.2 Scanning 54
2.2.1 Generating a Finite Automaton 56
2.2.2 Scanner Code 61
2.2.3 Table-Dr iven Scanning 65
2.2.4 Lexical Er rors 65
2.2.5 Pragmas 67
2.3 Parsing 69
2.3.1 Recursive Descent 73
2.3.2 Writing an LL(1) Grammar 79
2.3.3 Table-Driven Top-Down Parsing 82
2.3.4 Bottom-Up Parsing 89
2.3.5 Syntax Error s
C 1
.
102
2.4 Theoretical Foundations
C 13
.
103
2.4.1 Finite Automata
C 13
2.4.2 Push-Down Automata
C 18
2.4.3 Grammar and Language Classes
C 19
2.5 Summary and Concluding Remarks 104
2.6 Exercises 105
2.7 Explorations 112
2.8 Bibliographic Notes 112
3 Names, Scopes, and Bindings 115
3.1 The Notion of Binding Time 116
3.2 Object Lifetime and Storage Management 118
3.2.1 Static Allocation 119
3.2.2 Stack-Based Allocation 120
3.2.3 Heap-Based Allocation 122
3.2.4 Garbage Collection 124
3.3 Scope Rules 125
3.3.1 Static Scoping 126
3.3.2 Nested Subroutines 127
3.3.3 Declaration Order 130
3.3.4 Modules 135
3.3.5 Module Types and Classes 139
3.3.6 Dynamic Scoping 142
3.4 Implementing Scope
C 26
.
144
3.4.1 Symbol Tables
C 26
3.4.2 Association Lists and Central Reference Tables
C 31
