K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 2
Текст из файла (страница 2)
Structure matters; engineering detaildetermines a compiler’s efficiency and robustness. Elegance matters; a well-designed compiler,in which the algorithms and data structures flow smoothly from one pass to another, can be athing of beauty.We are delighted to have John Outram’s work grace the cover of this book.Duncan Hall’s ceiling is an interesting technological artifact.
Outram drew the original designon one sheet of paper. It was photographed and scanned at 1200 dpi yielding roughly 750 mbof data. The image was enlarged to form 234 distinct 2 × 8 foot panels, creating a 52 × 72 footimage. The panels were printed onto oversize sheets of perforated vinyl using a 12 dpi acrylicink printer. These sheets were precision mounted onto 2 × 8 foot acoustic tiles and hung on thevault’s aluminum frame.viiiContentsAbout the Authors .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivAbout the Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . viiiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xixCHAPTER 1 Overview of Compilation . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.11.21.31.4Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Compiler Structure . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Overview of Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3.1 The Front End . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .1.3.2 The Optimizer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3.3 The Back End . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . .Summary and Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1169101415212223CHAPTER 2 Scanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252.12.22.32.42.5Introduction . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Recognizing Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.1 A Formalism for Recognizers . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .2.2.2 Recognizing More Complex Words . . . . . . . . . . . . . . . . . . . . . . . . . .Regular Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.1 Formalizing the Notation . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.3 Closure Properties of REs . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . .From Regular Expression to Scanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.4.1 Nondeterministic Finite Automata . . . . . . . . . . . . . . . . . . . . . . . . . . .2.4.2 Regular Expression to NFA: Thompson’sConstruction . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.4.3 NFA to DFA: The Subset Construction . . . . . . . . . . . . . . . . . . . . . .2.4.4 DFA to Minimal DFA: Hopcroft’s Algorithm . . . . . . . . . . . . . . .2.4.5 Using a DFA as a Recognizer . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .Implementing Scanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.5.1 Table-Driven Scanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.5.2 Direct-Coded Scanners . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.5.3 Hand-Coded Scanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.5.4 Handling Keywords . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .25272931343536394243454753575960656972ixx Contents2.62.7Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.6.1 DFA to Regular Expression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.6.2 Another Approach to DFA Minimization:Brzozowski’s Algorithm . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.6.3 Closure-Free Regular Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . .Chapter Summary and Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Chapter Notes . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .74747577787880CHAPTER 3 Parsers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 833.13.23.33.43.53.63.7Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Expressing Syntax . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2.1 Why Not Regular Expressions? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2.2 Context-Free Grammars . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .3.2.3 More Complex Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2.4 Encoding Meaning into Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2.5 Discovering a Derivation for an Input String .
. . . . . . . . . . . . . . .Top-Down Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.3.1 Transforming a Grammar for Top-Down Parsing . . . . . . . . . . .3.3.2 Top-Down Recursive-Descent Parsers .
. . . . . . . . . . . . . . . . . . . . . .3.3.3 Table-Driven LL(1) Parsers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Bottom-Up Parsing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . .3.4.1 The LR(1) Parsing Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.4.2 Building LR(1) Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.4.3 Errors in the Table Construction . . . . . . . . . . . . . . . . . . . .
. . . . . . . . .Practical Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.5.1 Error Recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.5.2 Unary Operators . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .3.5.3 Handling Context-Sensitive Ambiguity . . . . . . . . . . . . . . . . . . . . .3.5.4 Left versus Right Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Advanced Topics . . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
