The Definitive ANTLR Reference: Building Domain-Specific Languages

Terence Parr9780978739256, 0978739256, 0978739248

ANTLR v3 is the most powerful, easy-to-use parser generator built to date, and represents the culmination of more than 15 years of research by Terence Parr. This book is the essential reference guide to using this completely rebuilt version of ANTLR, with its amazing new LL(*) parsing technology, tree construction facilities, StringTemplate code generation template engine, and sophisticated ANTLRWorks GUI development environment. Learn to use ANTLR directly from the author!ANTLR is a “parser generator”-a program that generates code to translate a specified input language into a nice, tidy data structure. You might think that parser generators are only used to build compilers. But in fact, programmers usually use parser generators to build translators and interpreters for domain-specific languages such as proprietary data formats, common network protocols, text processing languages, and domain-specific programming languages.Domain-specific languages are important to software development because they represent a more natural, high fidelity, robust, and maintainable means of encoding a problem than simply writing software in a general-purpose language. For example, NASA uses domain-specific command languages for space missions to improve reliability, reduce risk, reduce cost, and increase the speed of development. Even the first Apollo guidance control computer from the 1960s used a domain-specific language that supported vector computations.This book is the definitive guide to using the completely rebuilt ANTLR v3 and describes all features in detail, including the amazing new LL(*) parsing technology, tree construction facilities, StringTemplate code generationtemplate engine, and sophisticated ANTLRWorks GUI development environment. You’ll learn all about ANTLR grammar syntax, resolving grammar ambiguities, parser fault tolerance and error reporting, embedding actions to interpret or translate languages, building intermediate-form trees, extracting information from trees, generating source code, and how to use the ANTLR Java API.

---

Table of contents :
Contents……Page 9
Acknowledgments……Page 13
Preface……Page 14
Why a Completely New Version of ANTLR?……Page 16
What’s in This Book?……Page 18
Introducing ANTLR and Computer Language Translation……Page 20
Getting Started with ANTLR……Page 21
The Big Picture……Page 22
An A-mazing Analogy……Page 26
Installing ANTLR……Page 27
Executing ANTLR and Invoking Recognizers……Page 28
ANTLRWorks Grammar Development Environment……Page 30
The Nature of Computer Languages……Page 34
Generating Sentences with State Machines……Page 35
The Requirements for Generating Complex Language……Page 38
The Tree Structure of Sentences……Page 39
Enforcing Sentence Tree Structure……Page 40
Ambiguous Languages……Page 43
Vocabulary Symbols Are Structured Too……Page 44
Recognizing Computer Language Sentences……Page 48
A Quick Tour for the Impatient……Page 59
Recognizing Language Syntax……Page 60
Using Syntax to Drive Action Execution……Page 68
Evaluating Expressions via an AST Intermediate Form……Page 73
ANTLR Reference……Page 85
ANTLR Grammars……Page 86
Describing Languages with Formal Grammars……Page 87
Overall ANTLR Grammar File Structure……Page 89
Rules……Page 94
Global Dynamic Attribute Scopes……Page 114
Grammar Actions……Page 116
ANTLR Grammar-Level Options……Page 117
language Option……Page 119
output Option……Page 120
backtrack Option……Page 121
tokenVocab Option……Page 122
rewrite Option……Page 124
superClass Option……Page 125
filter Option……Page 126
ASTLabelType Option……Page 127
TokenLabelType Option……Page 128
k Option……Page 129
Attributes and Actions……Page 130
Introducing Actions, Attributes, and Scopes……Page 131
Grammar Actions……Page 134
Token Attributes……Page 138
Rule Attributes……Page 141
Dynamic Attribute Scopes for Interrule Communication……Page 148
References to Attributes within Actions……Page 159
Tree Construction……Page 162
Proper AST Structure……Page 163
Implementing Abstract Syntax Trees……Page 168
Default AST Construction……Page 170
Constructing ASTs Using Operators……Page 174
Constructing ASTs with Rewrite Rules……Page 177
Tree Grammars……Page 191
Moving from Parser Grammar to Tree Grammar……Page 192
Building a Parser Grammar for the C- Language……Page 195
Building a Tree Grammar for the C- Language……Page 199
Generating Structured Text with Templates and Grammars……Page 206
Why Templates Are Better Than Print Statements……Page 207
Embedded Actions and Template Construction Rules……Page 209
A Brief Introduction to StringTemplate……Page 213
The ANTLR StringTemplate Interface……Page 214
Rewriters vs. Generators……Page 217
A Java Bytecode Generator Using a Tree Grammar and Templates……Page 219
Rewriting the Token Buffer In-Place……Page 228
Rewriting the Token Buffer with Tree Grammars……Page 234
References to Template Expressions within Actions……Page 238
Error Reporting and Recovery……Page 241
A Parade of Errors……Page 242
Enriching Error Messages during Debugging……Page 245
Altering Recognizer Error Messages……Page 247
Exiting the Recognizer upon First Error……Page 251
Manually Specifying Exception Handlers……Page 253
Errors in Lexers and Tree Parsers……Page 254
Automatic Error Recovery Strategy……Page 256
Understanding Predicated-LL(*) Grammars……Page 261
LL(*) Parsing……Page 262
The Relationship between Grammars and Recognizers……Page 263
Why You Need LL(*)……Page 264
Toward LL(*) from LL(k)……Page 266
LL(*) and Automatic Arbitrary Regular Lookahead……Page 268
Ambiguities and Nondeterminisms……Page 273
Using Semantic and Syntactic Predicates……Page 292
Syntactic Ambiguities with Semantic Predicates……Page 293
Resolving Ambiguities and Nondeterminisms……Page 306
Semantic Predicates……Page 317
Resolving Non-LL(*) Conflicts……Page 318
Gated Semantic Predicates Switching Rules Dynamically……Page 325
Validating Semantic Predicates……Page 327
Limitations on Semantic Predicate Expressions……Page 328
Syntactic Predicates……Page 331
How ANTLR Implements Syntactic Predicates……Page 332
Using ANTLRWorks to Understand Syntactic Predicates……Page 336
Nested Backtracking……Page 337
Auto-backtracking……Page 340
Memoization……Page 343
Grammar Hazards with Syntactic Predicates……Page 348
Issues with Actions and Syntactic Predicates……Page 353
Bibliography……Page 357
A……Page 359
C……Page 360
F……Page 361
I……Page 362
M……Page 363
P……Page 364
R……Page 365
S……Page 366
T……Page 367
V……Page 368
Z……Page 369