Let's Build a Compiler!

Jack W. Crenshaw

Revision History
Revision 0.12004-08-05
Import all the original texts.
Revision 0.22004-08-16
Basic formating done. Initial import to CVS.

Abstract

This document is reformated version of Jack “Let's Build a Compiler!


Table of Contents

Note From Editor
Preface
1. Introduction
1.1. The Cradle
2. Expression Parsing
2.1. Getting Started
2.2. Single Digits
2.3. Binary Expressions
2.4. General Expressions
2.5. Using the Stack
2.6. Multiplication and Division
2.7. Parentheses
2.8. Unary Minus
2.9. A Word About Optimization
3. More Expressions
3.1. Variables
3.2. Functions
3.3. More on Error Handling
3.4. Assignment Statements
3.5. Multi-Character Tokens
3.6. White Space
4. Interpreters
4.1. The Interpreter
4.2. A Little Philosophy
5. Control Constructs
5.1. The Plan
5.2. Some Groundwork
5.3. The IF Statement
5.4. The WHILE Statement
5.5. The LOOP Statement
5.6. Repeat - Until
5.7. The FOR Loop
5.8. The DO statement
5.9. The BREAK Statement
5.10. Conclusion
6. Boolean Expressions
6.1. The Plan
6.2. The Grammar
6.3. Relops
6.4. Fixing The Grammar
6.5. The Parser
6.6. Merging With Control Constructs
6.7. Adding Assignments
7. Lexical Scanning
7.1. Lexical Scanning
7.2. State Machines and Alternatives
7.3. Some Experiments In Scanning
7.4. White Space
7.5. State Machines
7.6. Newlines
7.7. Operators
7.8. Lists, Commas And Command Lines
7.9. Getting Fancy
7.10. Returning A Character
7.11. Distributed vs Centralized Scanners
7.12. Merging Scanner And Parser
7.13. Conclusion
8. A Little Philosophy
8.1. The Road Home
8.2. Why Is It So Simple?
8.3. Conclusion
9. A Top View
9.1. The Top Level
9.2. The Structure Of Pascal
9.3. Fleshing It Out
9.4. Declarations
9.5. The Structure of C
10. Introducing "TINY"
10.1. Getting Started
10.2. Declarations
10.3. Declarations And Symbols
10.4. Initializers
10.5. The Symbol Table
10.6. Executable Statements
10.7. Booleans
10.8. Control Structures
10.9. Lexical Scanning
10.10. Multi-Character Variable Names
10.11. More Relops
10.12. Input/Output
10.13. Conclusion
11. Lexical Scan Revisited
11.1. Background
11.2. The Problem
11.3. The Solution
11.4. Fixing Up The Compiler
11.5. Conclusion
12. Miscellany
12.1. Semicolons
12.2. Comments
12.3. Conclusion
13. Procedures
13.1. One Last Digression
13.2. The Basics
13.3. A Basis For Experiments
13.4. Declaring A Procedure
13.5. Calling The Procedure
13.6. Passing Parameters
13.7. The Semantics Of Parameters
13.8. Local Variables
13.9. Conclusion
14. Types
14.1. What's Coming Next?
14.2. The Symbol Table
14.3. Adding Entries
14.4. Allocating Storage
14.5. Declaring Types
14.6. Assignments
14.7. The Coward's Way Out
14.8. A More Reasonable Solution
14.9. Literal Arguments
14.10. Additive Expressions
14.11. Why So Many Procedures?
14.12. Multiplicative Expressions
14.13. Multiplication
14.14. Division
14.15. Brginning To Wind Down
14.16. To Coerce Or Not To Coerce
14.17. Conclusion
15. Back To The Future
15.1. New Starts, Old Directions
15.2. Starting Over?
15.3. The Input Unit
15.4. The Output Unit
15.5. The Error Unit
15.6. Scanning And Parsing
15.7. The Scanner Unit
15.8. Decisions, Decisions
15.9. Parsing
15.10. References
16. Unit Construction
16.1. Just Like Classical?
16.2. Fleshing Out The Parser
16.3. Terms And Expressions
16.4. Assignments
16.5. Booleans
16.6. Boolean AND

List of Examples

1.1. Cradle
7.1. KISS v.0
7.2. KISS
10.1. TINY version 1.0
11.1. TINY version 1.1