Compiler Design

Course Title: Compiler Design

Course No: CSIT.313

Nature of the Course: Theory + Lab

Semester: 5

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 10 + 10

Credit Hours: 3

Course Description

This course is designed to develop acquaintance with fundamental concepts of compiler design. The course starts with the basic concepts and also includes different phases of compilers like lexical analysis, syntax analysis, syntax-directed translation, type checking etc. in detail.

Course Objectives

Develop their knowledge in compiler design. Develop lexical analyzers, parsers, and small compilers using different tools. Develop lexical analyzers, parsers, and small compilers by using general purpose programming languages.

Course Contents

1. Introduction

3 hrs

1.1. Overview of Compilers

Compilers

Analysis of the Source Program

Phases of a Compiler

1.2. Compiler Support

Cousins of the Compiler

Compiler Construction Tools

2. Lexical Analysis

8 hrs

2.1. Lexical Analyzer Fundamentals

The Role of the Lexical Analyzer

Input Buffering

Specification of Tokens

Recognition of Tokens

2.2. Automata and Pattern Matching

Finite Automata

From Regular Expression to an NFA

Optimization of DFA-Based Pattern Matches

3. Syntax Analysis

12 hrs

3.1. Grammars and the Parser

The Role of Parser

Context Free Grammars

Writing a Grammar

3.2. Parsing Techniques

Top-Down Parsing

Bottom-Up Parsing

3.3. Advanced Parsing

Operator-Preceding Parsing

LR Parsers

Using Ambiguous Grammars

4. Syntax-Directed Translation

6 hrs

4.1. Definitions and Trees

Syntax-Directed Definition

Construction of Syntax Trees

4.2. Attribute Evaluation

Bottom-Up Evaluation of S-Attributed Definitions

L-Attributed Definitions

4.3. Translation Strategies

Top-Down Translation

Bottom-Up Evaluations of Inherited Attributes

5. Type Checking

3 hrs

5.1. Type Systems and Checkers

Type Systems

Specification of a Simple Type Checker

5.2. Type Conversions and Attribute Grammar

Type conversions

Attribute Grammar for a Simple Type Checking System

6. Intermediate Code Generation

4 hrs

6.1. Languages and Declarations

Intermediate Languages

Declarations

Assignments Statements

6.2. Control Structures

Boolean Expressions

Case Statements

Backpatching

6.3. Procedure Calls

7. Code Generator

5 hrs

7.1. Design and Storage

Issues in the Design of a Code Generator

The Target Machine

Run-Time Storage Management

7.2. Code Generation Techniques

Basic Blocks and Flow Graphs

Next Use Information

A Simple Code Generator

7.3. DAG-Based Code Generation

The Dag Representation of Basic Blocks

Generating Code from Dags

8. Introduction to Code Optimization

4 hrs

8.1. Optimization Foundations

Introduction

The Principal Sources of Optimization

8.2. Optimization Techniques

Peephole Optimization

Optimization of Basic Blocks

Loops in Flow Graphs

Laboratory Works

The laboratory work develops practical knowledge on different concepts of compiler design. Students should be able to develop a project using lexical analyzer generator to specify lexical analyzer, using parser generator to facilitate the construction of the front end of a compiler and using general purpose programming languages like C/C++.

1.Lexical Analyzer
2.Parser Construction
3.General Purpose Implementation

Text Books

1.Compilers Principles, Techniques, and Tools, Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman; Pearson Education

Reference Books

1.Compiler Design, Sandeep Saxena, Rajkumar Singh Rathore, S.Chand
2.Introduction to Automata Theory, Languages, and Computation, Johne E. Hopcroft, Rajeev Motwani, Jeffrey D. Ulman, Pearson Education

Notes:

This syllabus follows the official CSIT curriculum of Far Western University. In case of any doubt or revision, the university's published syllabus shall be considered authoritative. https://cdc.fwu.edu.np/faculties.html

Complier Design