Spring Semester 2011 - F6S:

Course - Compiler Construction (Sprog og Oversættelse)


Text Book:

Compilers: Principles, Techniques, and Tools, Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman

Lecture Slides: Prepared with Extra literature from: Compiler Construction: Principles and Practice, Kenneth Louden.


Course Outline & Structure

  • Concept of Compiler Design
  • Scanning or Lexical Analysis
  • Regular Expressions
  • Finite Automat (FA)
  • Deterministic and Non-deterministic Finite Automat (DFA/NFA)
  • Context Free Grammar and Parsing
  • Kinds of Parsing        
  • Semantic Analysis
  • Run Time Environment     
  • Code Generation and Optimization

 Project Proposals

Project Guidelines (Recommendations)

Guidance Plan For Students



Room #


Literature Study






First lecture will cover the whole course: Introducing all aspects of constructing a compiler beginning with scanning to code generation.  The idea is to provide students a complete run through of the subject, so that they can make a better judgment about selection of a project, if they opt to do a project in the compiler construction.  After that normal lectures of the course will continue.

Reading: Introductory Chapter of the Text Book (you can also read it from Dragon Book)

Lecture 1

Lecture 2

Scanning (Lexical Analysis)

Reading: Scanning Process, Regular Expressions and Finite Automata, Regular Expressions to DFA.





Parsing & Context Free Grammars

Reading: Parsing Process and Parse Trees, Grammars and Ambiguities.

Lecture 3

Lecture 4

Top Down Parsing

Reading: Recursive Descent Parsing, LL(1) Parsing, FIRST and FOLLOW Set Concept, ERROR Recovery in Top Down Parsers.





Bottom Up Parsing

Reading: LR(0) Parsing, Items and Handles. SLR(1) Parsing, LR(1) and LALR(1) Parsing.

Lecture 5





Semantic Analysis, Data Types and Type Checking

Reading: Attributes and Attribute Grammars, Data Types and Type Checking, Algorithms for Attribute Computation.

Runtime Environment

Reading: Various Kinds of Environments for Runtime.

Lecture 6

Lecture 7





Linking & Loading

Code Generation

Reading: Basic Code Generation, Intermediate Code Structure.

Code Optimization Techniques

Reading: Code Optimization journal

Lecture 8

Lecture 9

Useful Books & Resources

So, you want to write a compiler  

Compiler Implementation in C

Free more C and C++ Compilers

Compiler Implementation in Java 

A Simulator SPIM which runs MIPS code

Windows Platform Flex/Bison

Code Guru

Compiler Construction: Principles and Practice, Kenneth Louden.

John R. Levine, Tony Mason, Doug Brown, Lex & Yacc, ISBN: 1-56592-000-7, 1990.

Andrew W. Appel, Maia Ginsburg, Modern Compiler Implementation in C, Cambridge University Press; ISBN: 052158390X, 1998.

Andrew W. Appel , Modern Compiler Implementation in Java, Cambridge University Press; ISBN: 0521583888.

Thomas W. Parsons, Introduction to Compiler Construction, ISBN: 0-7167-8261-8, 1992.

Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs, and Koen G. Langendoen, Modern Compiler Design, John Wiley & Sons, Ltd., ISBN 0 471 97697, 2000.

Mak Ronald, Writing Compilers and interpreters – An applied Approach Using C++, John Wiley & Sons, ISBN: ASIN: 0471555800, 1996.

Charles Fischer, Richard LeBlanc, Crafting a Compiler with C, Addison Wesley, ISBN: 0-8053-2166-7, 1991.

Ravi Sethi, Tom Stone (Editor), Programming Languages : Concepts and Constructs, Addison-Wesley Pub Co; ISBN: 0201590654 , 1996.

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, (2nd Edition) Addison-Wesley Publishing; ISBN: 0201441241, 2000.

J. P. Bennett, Introduction to Compiling Techniques: A First Course Using ANSI C, Lex, and Yacc (The McGraw-Hill International Series in Software Engineering), ISBN: 007709221X; 2nd edition (September 1996).

Commonly Used Parsers:

1.     http://grammatica.percederberg.net/index.html

2.     http://www.mathematik.uni-ulm.de/modula/

3.     http://www.devincook.com/goldparser/  (Gold Parser)

4.     http://www.hwaci.com/sw/lemon/ (Lemon Parser)

5.     http://accent.compilertools.net/ (Accent Parser)

6.     http://www.musikwissenschaft.uni-mainz.de/~ag/tply/tply.html (Turbo Borland Pascal Parser)

7.     http://www.thefreecountry.com/sourcecode/grammars.shtml (Free Grammars for Programming Languages)


Mailing List For Messages, Discussions and Feedback