Cooper_Engineering_a_Compiler(Second Edition) (1157546), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.6.1 Optimizing a Grammar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.6.2 Reducing the Size of LR(1) Tables . . . . . . . . . . . . . . . . . . . . . . . . . .Summary and Perspective . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Chapter Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .838585868992959698108110116118124136141141142143144147148150155156157Contents xiCHAPTER 4 Context-Sensitive Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . 1614.14.24.34.44.54.6Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .An Introduction to Type Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . .4.2.1 The Purpose of Type Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.2.2 Components of a Type System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .The Attribute-Grammar Framework . . . . . . . . . . . . . . . . . .

Характеристики

Список файлов учебной работы