Language Implementation Patterns: Create Your Own Domain-Specific and General Programming Languages

Contents......Page 7
Acknowledgments......Page 11
Preface......Page 12
What to Expect from This Book......Page 13
How This Book Is Organized......Page 14
Who Should Read This Book......Page 15
How to Read This Book......Page 16
Languages and Tools Used in This Book......Page 17
Getting Started with Parsing......Page 19
The Big Picture......Page 20
A Tour of the Patterns......Page 22
Dissecting a Few Applications......Page 26
Choosing Patterns and Assembling Applications......Page 34
Designing High-Level Interpreter Memory Systems......Page 0
Identifying Phrase Structure......Page 38
Building Recursive-Descent Parsers......Page 40
Parser Construction Using a Grammar DSL......Page 42
Tokenizing Sentences......Page 43
Mapping Grammars to Recursive-Descent Recognizers......Page 45
LL(1) Recursive-Descent Lexer......Page 50
LL(1) Recursive-Descent Parser......Page 54
LL(k) Recursive-Descent Parser......Page 59
Enhanced Parsing Patterns......Page 65
Parsing with Arbitrary Lookahead......Page 66
Directing the Parse with Semantic Information......Page 68
Backtracking Parser......Page 71
Memoizing Parser......Page 78
Predicated Parser......Page 84
Analyzing Languages......Page 87
Building Intermediate Form Trees......Page 88
Why We Build Trees......Page 90
Building Abstract Syntax Trees......Page 92
Quick Introduction to ANTLR......Page 99
Constructing ASTs with ANTLR Grammars......Page 101
Parse Tree......Page 105
Homogeneous AST......Page 109
Normalized Heterogeneous AST......Page 111
Irregular Heterogeneous AST......Page 114
Walking and Rewriting Trees......Page 116
Walking Trees and Visitation Order......Page 117
Encapsulating Node Visitation Code......Page 120
Automatically Generating Visitors from Grammars......Page 122
Decoupling Tree Traversal from Pattern Matching......Page 125
Embedded Heterogeneous Tree Walker......Page 128
External Tree Visitor......Page 131
Tree Grammar......Page 134
Tree Pattern Matcher......Page 138
Tracking and Identifying Program Symbols......Page 146
Collecting Information About Program Entities......Page 147
Grouping Symbols into Scopes......Page 149
Resolving Symbols......Page 154
Symbol Table for Monolithic Scope......Page 156
Symbol Table for Nested Scopes......Page 161
Managing Symbol Tables for Data Aggregates......Page 170
Building Scope Trees for Structs......Page 171
Building Scope Trees for Classes......Page 173
Symbol Table for Data Aggregates......Page 176
Symbol Table for Classes......Page 182
Enforcing Static Typing Rules......Page 196
Computing Static Expression Types......Page 199
Automatic Type Promotion......Page 208
Enforcing Static Type Safety......Page 216
Enforcing Polymorphic Type Safety......Page 223
Building Interpreters......Page 231
Building High-Level Interpreters......Page 232
Tracking Symbols in High-Level Interpreters......Page 235
Processing Instructions......Page 237
Syntax-Directed Interpreter......Page 238
Tree-Based Interpreter......Page 243
Building Bytecode Interpreters......Page 252
Programming Bytecode Interpreters......Page 254
Defining an Assembly Language Syntax......Page 256
Bytecode Machine Architecture......Page 258
Where to Go from Here......Page 263
Bytecode Assembler......Page 265
Stack-Based Bytecode Interpreter......Page 272
Register-Based Bytecode Interpreter......Page 280
Translating and Generating Languages......Page 289
Translating Computer Languages......Page 290
Syntax-Directed Translation......Page 292
Rule-Based Translation......Page 293
Model-Driven Translation......Page 295
Constructing a Nested Output Model......Page 303
Syntax-Directed Translator......Page 307
Rule-Based Translator......Page 313
Target-Specific Generator Classes......Page 319
Generating DSLs with Templates......Page 323
Getting Started with StringTemplate......Page 324
Characterizing StringTemplate......Page 327
Generating Templates from a Simple Input Model......Page 328
Reusing Templates with a Different Input Model......Page 331
Using a Tree Grammar to Create Templates......Page 334
Applying Templates to Lists of Data......Page 341
Building Retargetable Translators......Page 347
Finding Patterns in Protein Structures......Page 358
Using a Script to Build 3D Scenes......Page 359
Processing XML......Page 360
Reading Generic Configuration Files......Page 362
Tweaking Source Code......Page 363
Adding a New Type to Java......Page 364
Pretty Printing Source Code......Page 365
Compiling to Machine Code......Page 366
Bibliography......Page 368
B......Page 370
C......Page 371
F......Page 372
H......Page 373
L......Page 374
M......Page 375
P......Page 376
R......Page 377
S......Page 378
T......Page 380
V......Page 382
X......Page 383