Compiler design in C / Allen I. Holub.

Includes index.

1. Basic Concepts
1.1 The Parts of a Compiler
1.1.1 The ljexical Analyzer.
1.1.2 Ihe Parser
1.1.3 The Code Generator
1.2 Representing Computer Languages
1.2.1 Grammars and Parse Trees
1.2.2 An Expression Grammar
1.2.3 Syntax Diagrams
1.3 A Recursive-Descent Expression Compiler
1.3.1 The Lexical Analyzer .
1.3.2 The Basic Parser
1.3.3 Improving the Parser .
1.3.4 Code Generation
1.4 Exercises
2. Input and Lexical Analysis
2.1 TheLe^iical Analyzer as Part of a Compiler*
2.2 Error Recovery in Lexical Analysis*
2.3 Input Systems*
2.3.1 An Example Input System*
2.3.2 An Example Input System—Implementation
2.4 Lexical Analysis*
2.4.1 Languages*
2.4.2 Regular Expressions*
2.4.3 Regular Definitions*
2.4.4 Finite Automata*
2.4.5 Sute-Machine-Driven Lexical Analyzers*
2.4.6 Implementing a Sute-Machine-Driven Lexical Analyar
2J IfX—A Lcxictl-Analyzcr Gfncraior*
2.5.1 Thonipsort'=-Constniclion: From a Regular Expression to an NFA*
2.5.2 Implementing Thompson's Construction ,
2.5.2.1 Data Structures
2.5.2.2 A Regular-Expression Grammar
2.5.2.3 File Header
2.5.2.4 Error-Message Processing
2.5.2.5 Memory Management
2.5J 6 Macro Support
2.5.2.7 EX'S Lexical Analyzer
2.5.2.8 Parsing
2.5.3 Interpreting an NFA—^Theory*
2.5.4 Interpreting an NFA—Implementation .
2.5.5 Subset Construction: Converting an NFA to a DFA—Theory*
2.5.6 Subset Construction: Converting an NFA to a DFA—Implementation
2.5.7 DFA Minimization—Theory*
2.5.8 DFA Minimization—Implementation
2.5.9 Compressing and Printing the Tables
2.5.9.1 Urtcomprcssed Tables
2.5.9.2 Pair-ComprcssedTables
2.5.9.3 Redundant-Row-and-Column-Compressed Tables
2.5.10 Tying It All Together
2.6 Exercises
3. Context-Free Grammars
3.1 Sentences, Phrases, and Context-Free Grammars
3.2 Derivations and Sentential Forms
3.2.1 LLand LR Grammars
3.3 Parse Trees and Semantic Difficulties
3.4 £ Productions
3.5 The End-of-Input Marker
3.6 Right-Linear Grammars
3.7 Lists, Recursion, and Associativity
'3.7.1 Simple Lists
3.7.2 The Number of Elements in a List
3.7.3 Lists with Delimiters
3.8 Expressions
3.9 Ambiguous Grammars
3.10 Syntax-Directed Translation
3.10.1 Augmented Grammars
3.10.2 Attributed Grammars
3.11 Representing Generic Grammars
3.12 Exercises.
4. TopiDown Parsing .
4.1 Push-Down Automata*
4.1.1 Recursive-Descent Parsers as Push-Down Automata*
4.2 Using a PDA fw a Top-Down Parse*
4.3 Error Recovery in a Top-Down Parser*
4.4 Augmented Grammars and Table-Driven Parsers*
4.4.1 Implementing Attributed Grammars in a PDA*
4.5 Automating the Top-Down Parse Process*
4.5.1 Top-Down Parse Tables*
4.6 LL( I) Grammars and Their Limitations'^
4.7 Making the Parse Tables*"
4.7.1 HRST Sets'*
4.7.2 FOLLOW Sets'*
4.7.3 LL(I)Selection Sets*
4.8 Modifying Grammars*
4.8.1 Unreachable Productions*
4.8.2 Left Factoring*
4.8.3 Comer Substitution*
4.8.4 Singleton Substitution*
4.8.5 Eliminating Ambiguity*
4.8.6 Eliminating Left Recursion*
4.9 Implementing LL( I) Parsers
4.9.1 Top-Down, Table-Driven Parsing—^Tlie LLama Output File
4.9.2 Decs and LLama Debugging Sup^rt—yydebug.c
4.10 LLama—Implementing an LL(I) Parser-Generator
4.10.1 LLama's Parser
4.10.2 Creating Tl.e Tables
4.10.2.1 Computing FIRST, FOLLOW, and SELECT Sets
4.10.3 The Rest of LLama
4.11 Exercises
5. Bottom-Up Parsing
5.1 How Bottom-Up Parsing Works* .
5.2 Recursion in Bottom-Up Parsing*
5.3 Implementing the Parser as a State Machine*
5.4 Error Recovery m an LR Parser*
5.5 The Value Stack and Attribute Processing*
5.5.1 A Notation for Bottom-Up Attributes*
5.5.2 Imbedded Actions*
5.6 Creating LR Parse Tables—Theory*
5.6.1 LR(0) Grammars*
5.6.2 SLR( I) Grammars*
5.6.3 LR(1) Grammars*
5.6.4 LALR(l)Grammars'*
5.7. Representing LR State Tables
5.8 Eliminating Single-Reduction States*
5.9 Using Ambiguous Grammars*-
5.10 Implementing an LALR(I) Parser—The Occs Output File
5.11 Implementing an LALR(l) Parser Generator—Occs Internals
5.1 I.I Modifying the Symbol Table for LALR(I) Grammars
5.12 ParserrFile Generation
5.13 Generating LALR(l) Parse Tables
5.14 Exercises
6. Code Generation
6.1 Intermediate Languages
^ 2 C-code: An Intermediate Language and Virtual Machine
6.2.1 Names and White Space
6.2.2 Basic Types
6.2.3 The Virtual Machine; Registers, Stack, and Memory
6.2.4 Memory Organization: Segments
6.2.5 Variable Declarations: Storage Classes and Alignment
6.2.6 Addressing Modes
<S.2.7 Manipulating the Slack
6.2.8 Subrouiines
6.2.9 Stack Frames: Subroutine Arguments and Automatic Variables
6.2.10 Subroutine Return Values
6.2.11 Operators
6.2.12 Type Conversions
6.2.13 Labels and Control Flow .
6.2.14 Macros and Constant Expressions
6.2.1.5 File Organization
6.2.16 Miscellany
6.2.17 Caveats
6.3 The Symbol Table
6.3.1 Symbol-Table Requirements
6.3.2 Symbol-Table Data-Base Data Structures
6.3.3 Implementing the Symbol Table
6.3.4 Representing Types—Theory
6.3.5 Representing Types—Implementation
6.3.6 Implementing the Symbol-Table Maintenance Layer
6.4 The Parser: Configuration
6.5 The Lexical Analyzer
6.6 Declarations
6.6.1 Simple Variable [)cclaration$
6.6.2 Structure and Union Declarations
6.6.3 Enumerated-Type Declarations
6.6.4 Function Declarations
6.6.5 Compound Statements and Local Variables
6.6.6 Front-End/Back-End Considerations
6.7 The gen () Subroutine
6.8 Expressions
6.8.1 Temporary-Variable Allocation
6.8.2 Lvalues and Rvalues
6.8.3 Implementing Values, Higher-Level Temporary-Variable Support
6.8.4 Unary Operators
6.8.5 Binary Operators
6.9 Statements and Control Flow
6.9.1 Simple Statements andi£/«ls«
6.9.2 Loops,br«ak, and conbinu#
6.9.3 The switch Statement
6.10 Exercises
7. Optimization Strategies
7.1 Parser Optimizations
7.2 Lifiear (Peephole) Optimizations
7.2.1 Strength Reduction
7.2.2 Constant Folding and Constant Prdpagation
7.2.3 Dead Variables and Dead Code
7.2.4 Peephole Optimization: An Example
7.3 Structural Optimizations
7.3.1 Postfix and Syntax Trees
7.3.2 Common-Subexpression Elimination
7 3.3 Register Allocation
7.3.4 Lifetime Analysis
7.3.5 Loop Unwinding
7.3.6 Replacing Indexes with Pointers
7.3.7 Loop-Invariant Code Motion
7.3.8 Loop Induction
7.4 Aliasing Problems
7.5 Exercises