Compiler Design and Construction Syllabus (CSC 365) – TU BSc CSIT 6th Semester

Tribhuvan University
Institute of Science and Technology
Bachelor of Science in Computer Science and Information Technology

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 Objective:

• To develop knowledge in compiler design
• To develop lexical analyzers, parsers, and small compilers using different tools
• To develop lexical analyzers, parsers, and small compilers by using general purpose programming languages

Course Contents

Unit 1. Introduction to Compiler (3 Hrs.)

• 1.1 Compiler Structure: Analysis and Synthesis Model of Compilation, different sub-phases within analysis and synthesis phases
• 1.2 Basic concepts related to Compiler such as interpreter, simple One-Pass Compiler, preprocessor, macros, symbol table and error handler

Unit 2. Lexical Analyzer (19 Hrs.)

• 2.1 Lexical Analysis (5 Hrs.): The role of the lexical analyzer, Input buffering, Specification of tokens, Recognition of tokens, Finite Automata, Regular Expression to an NFA, Design of a lexical analyzer generator
• 2.2 Syntax Analysis: The role of parser, Context free grammars, Writing a grammar, Top-down parsing, Bottom-up parsing, Operator-precedence parsing, LR parsing, Ambiguous grammar
• 2.3 Syntax Directed Translation: Syntax-directed definition, Syntax tree and its construction, Evaluation of S-attributed definitions, L-attributed definitions, Top-down translation, Recursive evaluators
• 2.4 Type Checking: Type systems, Specification of a simple type checker, Type conversions

Unit 3. Symbol Table Design and Runtime Storage Management (4 Hrs.)

• 3.1 Symbol Table Design: Function of Symbol Table, Information provided by Symbol Table, Attributes and Data Structures for symbol table
• 3.2 Run-time storage management

Unit 4. Intermediate Code Generator, Code Generator, Optimization and Case Studies (19 Hrs.)

• 4.1 Intermediate Code Generator: High-level and Low-level Intermediate representation, Syntax tree & DAG representations, Three-address code, Quadruples, Triples, SDT for intermediate code, Intermediate code generation for Declarations, Assignments, Control Flow, Boolean Expressions and Procedure Calls; Back patching
• 4.2 Code Generator: Factors affecting a code generator, Target Language, Basic blocks and flow graphs, Dynamic programming code-generation algorithm
• 4.3 Code Optimization: Need and criteria of Code Optimization, Basic optimization techniques
• 4.4 Case Studies of some compilers like C compiler, C++ compiler

Laboratory Works

The laboratory work develops practical knowledge on different concepts of compiler design. Students should:

• Create a project by using a lexical analyzer generator or any high level language
• Create a parser by using a parser generator or any high level language
• Write programs for intermediate code generation and machine code generation
• Create the front end of a compiler using general purpose programming languages

Reference Books

1. Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman, “Compilers: Principles, Techniques, and Tools”, Pearson Education
2. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, “Introduction to Automata Theory, Languages, and Computation”, Pearson Education
3. Steven Muchnick, “Advanced Compiler Design and Implementation”, Morgan Kaufmann Publication