How can I learn about compiler theory - online/free resources

Question

I'm interested in learning - at depth - about compiler theory...

• parsing
• EBNF
• LALR?

Are all terms I'm familiar with but don't really understand how to actually implement/use..

I'm looking for links, tutorials, and other resources; all online, preferably all free...

I'm more interested in simple / complete implementations, than complex / incomplete or convoluted implementations.

Update:

I know there are other similar links, but those didn't have the narrow focus on online and free links/resources..

Further Update

Any more high level answers?

Answer 1

• Parsing on Wikipedia
• EBNF on Wikipedia
• LALR on Wikipedia

Start there and dig into the references you find. Each article has external links.

Answer 2

Theres a WikiBook about Compiler construction here. It is convering many aspects of compiler construction. I would suggest you'll take a look at tools like flex and/or bison (if you're planning to write an compiler in C) or the equivalent tools for your language. These tools help you to generate a parser for the grammar of your language.

Best wishes, Fabian

Answer 3

MIT has open course ware on this topic...

Answer 4

Lex and Yacc are tools for deterministically turning source into a tree -i.e., you specify your language grammer for the two tools and it generates a program to help you structure the code into a syntax tree.

LALR and EBNF are compiler front-end related terms and lex and yacc are the practical tools for it. Just by focusing your energy on learning how to use lex and yacc to build a parse tree you should have a starting point for building a compiler. Dynamic languages are easier to compile since they either have lots of runtime machinery or are fully interpreted, so you could just stop your search here :D.

These are standard UNIX tools so you should find plenty of resources on them.

I got this answer from someone about optimizing C++. If your going into this direction then you can learn a lot here.

Answer 5

I still rely on the classics -- "Principles of Compiler Design" by Aho and Ullman (Green Dragon Book) and "Compilers: Principles, Techniques, and Tools" by Aho, Ullman, and Sethi (Red Dragon Book.)

Ah...memories...

Answer 6

You need to understand parsing in general, and then how parsers are used. Recursive descent parsers are the easiest to understand, IMHO, with LALR/YACC/... being more difficult to graph because the tools are complex.

I learned recursive descent parsing and code generation from one enormously fun techical paper. That paper has been turned into a website, which walks you through building a completely self-contained compiler system that can compile itself and other languages:

MetaII Compiler Tutorial

This is all based on an amazing little 10-page technical paper by Val Schorre: META II: A Syntax-Oriented Compiler Writing Language from honest-to-god 1964. I learned how to build compilers from this back in 1970. There's a mind-blowing moment when you finally grok how the compiler can regenerate itself....

I know the website author from my college days, but have nothing to do with the website.

Answer 7

See those links :

http://www.stanford.edu/class/cs143/

See also this :

http://www.cs.princeton.edu/~appel/modern/java/ you can find it on google books also.

Answer 8

There's a free tutorial called Let's build a compiler. Quote from the introduction;

"This series of articles is a tutorial on the theory and practice of developing language parsers and compilers. Before we are finished, we will have covered every aspect of compiler construction, designed a new programming language, and built a working compiler."