Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

It's not meant to be subjective or get advice on what would be the best path to take, but an objective list of things that must be known in order for me to pick up a book on compiler theory and understand it.

What level of mathematics, and related skills are required?

share|improve this question

closed as not constructive by gnat, Walter, World Engineer, ChrisF Oct 17 '12 at 20:23

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

    
The difficult part of the compiler theory is the optimization, where you would need to very well the ISA and even the architecture of the CPU. –  m3th0dman Oct 15 '12 at 9:10
    
@m3th0dman, most of the optimisations are target-agnostic. Only instruction selection and register allocation are really target-specific, but there is nothing really complicated there, these areas are well-researched. ABI is of course target-specific, but there is no algorithmic complexity at all in it. –  SK-logic Oct 15 '12 at 9:26
    
@SK-logic: Intelligent use of Count Leading Zeroes comes to mind, as well as the use of 32*32->64 multiplications. –  MSalters Oct 15 '12 at 11:30

3 Answers 3

up vote 7 down vote accepted

The key question really is: at what level? I'm going to assuming a fairly introductory one if you're asking this question. I have only done one course on compilers, so perhaps my knowledge is too elementary, but here's what is useful to know:

  • Basic 32-bit assembler, including how the stack works, and the usage of ebp, and the different kind of jmps
  • Good understanding of data structures: trees, linked lists, and some of the common algorithms associated with them (binary search, for example)
  • Basic understanding of complexity theory, mainly the big O notation
  • Knowledge of basic regular expressions

To be perfectly honest, if you wanted to pick up any book on compiler theory and read it, then you should have read an introduction to compilers and preferably implemented something basic yourself (so you get a good idea from how it works: parsing source code, generating parse trees, to code generation). After that, you can look at optimisations (e.g. age = 4 + 5 would be compiled directly as age = 9, the 4+5 computation would be done once at compile time and never again).

share|improve this answer
    
Thank you! What level of mathematics would you recommend? This is all for starting the study of compilers. –  PHython Oct 14 '12 at 23:18
3  
I honestly don't feel that any abstract mathematics is required. For example: if you had to evaluate (2 * 3) + ((4 + 5) * (6 + 7)), which bracket would you do first? This is much less about mathematics, and more about understanding the limitations of computers and using it to their full advantage. This is about as complicated as mathematical expressions would get. –  Jay Oct 14 '12 at 23:22
    
Thank you very much. The reason I assumed as much is because this subject is usually taught to juniors and seniors in CS curricula at different schools. –  PHython Oct 14 '12 at 23:31
3  
Precisely. I think the prerequisite on computer architecture is more important than mathematics. If this answers your question, I'd appreciate it if you could accept it (hollow tick under the vote count) :-) –  Jay Oct 14 '12 at 23:32
1  
I'm pretty sure this would be covered in any good introduction to compilers course, I don't think it necessary to know this beforehand (though I agree it's very valuable). –  Jay Oct 15 '12 at 13:07

Compilers are much, much simpler than they're usually perceived. You do not need any advanced knowledge. Understanding some basics of the graph theory might help (but it is certainly not a prerequisite). Understanding the term rewriting systems would also be beneficial. But the best approach is to just start learning the compilers theory and pick up what is missing on the way.

Many things that are discussed in detail in the popular compilers textbooks are totally irrelevant to the real world practice and even to the bleeding edge modern compilers research. Chances are, you'll never need to touch the formal languages (alas, parsing is overrated). There is no need to understand the computer architecture in detail (although it might help). No complicated data structures are required, besides very simple trees and DAGs.

share|improve this answer
    
Well, if all you want to do is a simple DSL it's not too complicated. If you want to do things like invariant code motion or escape analysis, or if you need to get into register allocation then it can get pretty intense. One of the reasons IA-64 never took off was the lack of a good production-quality compiler early on, and Intel has some very good compiler engineers. –  TMN Oct 15 '12 at 12:47
    
@TMN, Such problems are computationally complex (even simplest instruction selection is NP-complete), but it does not mean they're not easy to comprehend. Even a 6 years old person is able to understand, say, the traveling salesman problem, which is more complicated than anything you'll find in a compiler. As for escape analysis you've mentioned - it is about 10 lines of Datalog. An average CRUD application is 100s times more complicated. –  SK-logic Oct 15 '12 at 12:51
    
You find me a 6 year old that can explain the conditions required for loop-invariant code motion and I'll give them a job for life. –  Jay Oct 18 '12 at 23:14

Use different compilers and understand what a compiler can do, as a black box, before you adventure into writing one. Try to use different compilers from command line, see what options they have and what are the effects, what do they have in common, etc.

After that, you need to know a few things:

  • Basic arithmetic
  • Data structures
  • Graph theory
  • Computer architecture
  • Formal languages (might or might not be covered in detail by the compiler book)
  • Some advanced math might be required if you adventure in code optimization
share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.