Compiler Design

Course Title: Compiler Design

Course No: ENCT 326

Nature of the Course: Theory + Lab

Semester: 5

Full Marks: 40 + 60 + 25

Pass Marks: 16 + 24 + 10

Credit Hours: 3

Course Description

This course develops a clear understanding of the structure, components, and design principles of a compiler. It focuses on the key phases of compilation, including lexical analysis, parsing, semantic analysis, and code generation. The course also introduces optimization techniques and error-handling strategies to enhance the efficiency and reliability of compilers.

Course Objectives

The objective of this course is to develop a clear understanding of the structure, components, and design principles of a compiler. It focuses on the key phases of compilation, including lexical analysis, parsing, semantic analysis, and code generation. The course also introduces optimization techniques and error-handling strategies to enhance the efficiency and reliability of compilers.

Course Contents

1. Introduction

5 hrs

1.1. Compiler and Interpreter

1.2. Compiler structure: Analysis and synthesis model of compilation, different subphases within the analysis and synthesis phases

1.3. Basic concepts like preprocessor, macros, symbol table, and error handler

2. Lexical Analysis

9 hrs

2.1. The role of the lexical analyzer

2.2. Specification and recognition of tokens

2.3. Input buffering

2.4. Finite automata and their relevance to compiler construction

2.5. Design of a lexical analyzer generator

2.6. Error handling in lexical analysis

3. Syntax Analysis (Parsing)

8 hrs

3.1. Role of syntax analysis

3.2. Context-free grammars and parse trees

3.3. Parsing techniques: Top-down (recursive descent, LL(1)) and bottom-up (LR(1))

3.4. Operator precedence

3.5. Handling issues like left recursion and ambiguity

4. Syntax-Directed Translation and Semantic Analysis

9 hrs

4.1. Syntax-directed definitions (SDD) and syntax-directed translation (SDT)

4.2. Synthesized and inherited attributes

4.3. Syntax tree construction

4.4. Intermediate code generation

4.5. Semantic analysis, including static and dynamic checks

4.6. Type checking and type systems

4.7. Symbol table construction, attributes, and data structures for symbol table

4.8. Run-time storage management

5. Code Generation

7 hrs

5.1. Factors affecting a code generator

5.2. Basic blocks and flow graphs

5.3. Optimization of basic blocks

5.4. Register allocation and assignment

5.5. Dynamic programming code-generation algorithm

6. Code Optimization

7 hrs

6.1. Loops in flow graphs, constant propagation, partial redundancy elimination

6.2. Data-flow analysis and solving data-flow equations

6.3. Storage organization and allocation strategies (Stack, heap)

6.4. Need and criteria of code optimization and basic optimization techniques

6.5. Basic block optimization

6.6. Case studies of some compilers, like the C compiler, the C++ compiler

Laboratory Works

Practical sessions covering lexical analysis setup, Lex/Flex tools, implementing context-free grammars, designing a basic recursive descent parser, syntax analysis with YACC/Bison, and semantic analysis and intermediate code generation.

1.Setting lexical analysis
2.Introduction to Lex/Flex tools
3.Implementing context-free grammars
4.Designing a basic recursive descent parser
5.Syntax analysis with YACC/Bison
6.Semantic analysis and intermediate code generation

Text Books

1.Aho, A. V., Lam, M. S., Sethi, R., Ullman, J. D. (2006). Compilers: Principles, techniques, and tools. Pearson.
2.Cooper, K. D., Torczon, L. (2011). Engineering a compiler. Morgan Kaufmann.

Reference Books

1.Hopcroft, J. E., Motwani, R., Ullman, J. D. (2006). Introduction to automata theory, languages, and computation. Addison-Wesley.
2.Muchnick, S. (1997). Advanced compiler design and implementation (Latest Publication). Morgan Kaufmann.
3.Thain, D. (2020). Introduction to compilers and language design. Douglas Thain.

Notes:

This syllabus follows the official BCE curriculum of Tribhuwan University. In case of any doubt or revision, the university's published syllabus shall be considered authoritative. https://ioe.tu.edu.np/pages/computer-engineering-curriculum-structure-2635

Complier Design