That represents the remaining N-k instructions, and reprocess instruction I.
#Compiler design dragon book code#
The size of the machine will really be determined by lenght of the longest peephole optimization we care to do, but if that length is P, the entire machine need not be P states deep.Įach state has transitions to a next state based on the "next" instruction I produced by your code generator. But it is practical to remember the last two or three for the most common machine instructions (load, add, cmp, branch, store). Since there are typically many kinds of machine instructions, as practical matter you can't remember too many in a row or the state machine will become enormous. To do useful work, we want the machine to capture as long a sequence as possible.
#Compiler design dragon book generator#
At any moment, you need to be able to emit the unemitted instructions ("flush") if you do this all the time, your peephole generator captures the next instruction and then emits it, doing no useful work. A special start state remembers the empty string of instructions. A state thus implicitly remembers a (short) sequence of generated but un-emitted instructions it also has to remember the key parameters of the instructions it has captured, such as a register name, a constant value, and/or addressing modes and abstract target memory locations. The state machine captures instructions that your code generator produces, and remembers sequences of 0 or more generated instructions by transitioning between states. We assume you have a raw code generator that generates instructions but does not emit them, and an emit routine that sends actual code to the object stream. If you insist only buying one, the Dragon book is still pretty good.Īn easy way to do this is to implement your peephole optimizer as a finite state machine. Even the reviewed book is likely to be pretty good Dick Grune is one of the editors, and he reallys knows his parsing stuff, and has a good rep in the academic space on compilers. My solution: just buy them all (if you are building compilers you are going to have a hard time convincing me you don't have the money) most have something useful to say that the other ones don't. You'd be foolish to decide not to use it, if you do anything serious in compiling. But complementing isn't the same as replacing. There are other compiler books (yes, including Torczon/Cooper) that are really good and go into topics beyond what the Dragon Book covers. (This is on the Springer page that is trying to "sell" the book looks like marketing fluff). If your quote is accurate, I wouldn't put a lot of stock in it. (Really good parsers these days are "GLR"). Regarding the review: I've never heard of "LH" parsing, and I think I keep track. There's little reason to believe it has suddenly gotten less good. Is really good at describing the basics of compiling. I've been building parser and program analysis/transformation rules for 40+ years.