Dilla University
School of Computing and Informatics
Department of Computer Science
Course Title: Compiler Design
Course Code: CoSc 4104
Instructor Name: Shemse S
Course Description
The course builds on the student's core knowledge of languages, grammars and programming and
provides an opportunity to see how these core areas can come together to form an application area.
Also, it imparts the knowledge about the following to learn basic techniques used in compiler
construction such as lexical analysis, top-down and bottom-up parsing, context-sensitive analysis,
and intermediate code generation. To learn basic data structures used in compiler construction such
as abstract syntax trees, symbol tables, three-address code, and stack machines. To learn software
tools used in compiler construction such as lexical analyzer generators, and parser generators.
Course Objectives
By the end of this course, students will be able to:
✓ Implementing a small compiler using modern compiler writing tools.
✓ Providing the student with skills and knowledge (such as lexical analysis and parsing) which
are applicable to a broad range of computer science application areas (such as text editors,
information retrieval, etc...).
Course Outline
Chapter 1: Introduction (2hr)
➢ Phases of a Compiler
➢ Computer Language Representation
➢ Compiler Construction Tools
Page | 1
Chapter 2: Lexical Analysis (4hr)
➢ Token Specification
➢ Recognition of Tokens
➢ Recognition of Machines
➢ NFA to DFA Conversion
➢ Error Recovery
➢ A typical Lexical Analyzer Generator
➢ DFA Analysis
Chapter 3: Syntax Analysis (6hr)
➢ Parsing
➢ Top-down Parsing
✓ Predictive Parsing
✓ Top-down Parsing principles of CFG
✓ Regular Expression Vs Context Free Grammar (CFG)
✓ Top-down Parsing Implementation - Recursive Decent parsing
✓ Non-Recursive Predictive Parsing
✓ LL(1) Grammar
➢ Bottom-Up Parsing
✓ Handles
✓ Stack Implementation of Shift Reduce Parsing
✓ LR Parers-Implementation - LR Parsing Algorithms
✓ SLR, CLR and LALR parser
➢ Error Recovery
➢ Parser Generator
Chapter 4: Syntax Directed Translation (4hr)
➢ Syntax Directed Definitions (SDD)
➢ Evaluation Order for SDD
➢ Construction of Syntax Trees
Chapter 5: Type Checking (4hr)
➢ Rules of Type Checking
➢ Type Conversions
Page | 2
Chapter 6: Intermediate Languages (4hr)
➢ Three Address Code Rules
➢ Quadruples
➢ Declarations
➢ Declarations in Procedures
➢ Flow Control Statements
➢ Back Patching
➢ Procedure Calls
Chapter 7: Run time- Environments (4hr)
➢ Symbol table
➢ Hash Table
➢ Representing Scope Information
Chapter 8: Code Generation and Optimization (4hr)
➢ Simple Code Generation
➢ Register Allocation
➢ DAG Representation
➢ Peephole Optimization Techniques
Teaching - Learning methods
Assessment method
Quizzes 20%
Assignments 10%
Project/Lab 20%
Final Exam 50%
Total 100%
Teaching materials
Text Books:
➢ T1: Alfred Aho, Ravi Sethi, V.Jeffery Ullman D. “COMPILERS PRINCIPLES,TECHINQUES AND
TOOLS “, Addison- Wesley, 1988.
Reference Books:
➢ Allen Holub l. “Compiler Design in C”, Prentice Hall of India. 1990.
➢ Charles N.Fischer Richard J.Leblanc, “Crafting a compiler with C”, Benjamin Cummings, 1991
Page | 3
