by Jack Crenshaw
This series of articles is a tutorial on the theory and practice of developing language parsers and compilers. Before we arefinished, we will have covered every aspect of compiler construction, designed a new programming language, and built a working compiler.
Though I am not a computer scientist by education (my Ph.D. is in a different field, Physics), I have been interested in compilers for many years. I have bought and tried to digest the contentsof virtually every book on the subject ever written. I don't mind telling you that it was slow going. Compiler texts arewritten for Computer Science majors, and are tough sledding for the rest of us. But over the years a bit of it began to seep in. What really caused it to jell was when I began to branch off onmy own and begin to try things on my own computer. Now I plan to share with you what I have learned. At the end of this series you will by no means be a computer scientist, nor will you knowall the esoterics of compiler theory. I intend to completely ignore the more theoretical aspects of the subject. What you_WILL_ know is all the practical aspects that one needs to know to build a working system.
This is a "learn-by-doing" series. In the course of the series I will be performing experiments on a computer. You will be expected to follow along, repeating the experiments that I do, and performing some on your own. I will be using Turbo Pascal4.0 on a PC clone. I will periodically insert examples written in TP. These will be executable code, which you will be expected to copy into your own computer and run. If you don't have a copy of Turbo, you will be severely limited in how well you will be able to follow what's going on. If you don't have a copy, I urge you to get one. After all, it's an excellent product, good formany other uses!
Some articles on compilers show you examples, or show you (as inthe case of Small-C) a finished product, which you can then copy and use without a whole lot of understanding of how it works. I hope to do much more than that. I hope to teach you HOW the things get done, so that you can go off on your own and not only reproduce what I have done, but improve on it.
This is admittedly an ambitious undertaking, and it won't be donein one page. I expect to do it in the course of a number ofarticles. Each article will cover a single aspect of compiler theory, and will pretty much stand alone. If all you're interested in at a given time is one aspect, then you need tolook only at that one article. Each article will be uploaded asit is complete, so you will have to wait for the last one before you can consider yourself finished. Please be patient.
The average text on compiler theory covers a lot of ground that we won't be covering here. The typical sequence is:
- An introductory chapter describing what a compiler is.
- A chapter or two on syntax equations, using Backus-Naur Form (BNF).
- A chapter or two on lexical scanning, with emphasis on deterministic and non-deterministic finite automata.
- Several chapters on parsing theory, beginning with top-down recursive descent, and ending with LALR parsers.
- A chapter on intermediate languages, with emphasis on P-code and similar reverse polish representations.
- Many chapters on alternative ways to handle subroutines and parameter passing, type declarations, and such.
- A chapter toward the end on code generation, usually for some imaginary CPU with a simple instruction set. Most readers (and in fact, most college classes) never make it this far.
- A final chapter or two on optimization. This chapter often goes unread, too...........