Spring Semester 2011 - F6S:

Course - Compiler Construction (Sprog og Oversættelse)

---

Instructor:

• Dr. D. M. Akbar Hussain ( akh@es.aau.dk )
• Meetings: Send me an Email with Time and Date.
• Urgent or Personal Maters: Just walk in.
• Room #: H329
• Tel: 7729 (Direct)

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.

Objectives:

• This course provides an overview of the structure of modern compilers, with an emphasis on implementation techniques.
• Students learn Language Translation phases: Lexical analysis, Parsing techniques, Static type checking, Code generation, Dataflow analysis, Optimization techniques, Storage management, and Execution environments.  Machine independent and Machine dependent translation. 
• Students should be able to acquire the practical skills to write a compiler for a programming language.
• Students should also be able to use the acquired skills to more general software engineering tasks.

Course Outline & Structure

•     3 ECTS Course. 
•     This course will cover the following topics: It is important that students understand that it is not a programming class, it deals with basic building blocks the theory behind each block and how it can be constructed. Typically, students have a programming class in one of the earlier semesters, so here they need to apply that skills to build the compiler.

• 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

Week	Date	Room #	Time	Literature Study	Handouts
10	10-03-2011	B206	08:30	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.
13	31-03-2011	B206	08:30	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.
14	07-04-2011	B206	08:30	Bottom Up Parsing Reading: LR(0) Parsing, Items and Handles. SLR(1) Parsing, LR(1) and LALR(1) Parsing.	Lecture 5
15	14-04-2011	B206	08:30	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
17	28-04-2011	B206	08:30	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

http://aaue.dk/mailman/listinfo/f6s-students