21CS1603                     COMPILER DESIGN                       L T P C

                                                                                                         3 0 2 4 

OBJECTIVES: 

To impart Knowledge on the following topics:  

• To learn the various phases of compiler.  

• To learn the various parsing techniques.  

• To understand intermediate code generation and run-time environment.  

• To learn to implement front-end of the compiler.  

• To learn to implement code generator. 

UNIT I   INTRODUCTION TO COMPILERS            9 

Phases of a compiler – Lexical Analysis – Role of Lexical Analyzer –Specification of Tokens – Recognition of Tokens – Lex – Finite Automata – Regular Expressions to Automata – Minimizing DFA - Error Detection and Recovery – Lexical Phase Error Management. 

SUGGESTED ACTIVITIES:  

• Symbol Table Creation  

• Develop a lexical analyzer to recognize a few patterns in C (Ex. identifiers, constants, comments, operators etc). 

•  Develop a lexical analyzer using lex tool.

SUGGESTED EVALUATION METHODS:  

• Assignment on Structure of Compiler.  

• Assessment on Finite Automata.  

• Seminar in Lexical Analyzer 

UNIT II SYNTAX ANALYSIS         12

Context-Free Grammar (CFG) – Derivation Trees – Ambiguity in Grammars and Languages – Need and Role of the parser - Top Down Parsing - Recursive Descent Parser - Predictive Parser - LL(1) Parser-Shift Reduce Parser - LR Parser - LR (0)Item - Construction of SLR Parsing Table - Introduction to LALR Parser - Error Handling and Recovery in Syntax Analyzer - Parser Generators -YACC 

SUGGESTED ACTIVITIES:  

• Generate YACC specification for a few syntactic categories  

• Using different parsing algorithms to develop the parsers for a given gramma  

• Implement an Arithmetic Calculator using LEX and YACC  

• Design and implement a parser using LEX and YACC tools. 

SUGGESTED EVALUATION METHODS:  

• Assignments on CFG  

• Group Work for Developing the Parsers  

UNIT III                INTERMEDIATE CODE GENERATION                       8 

Syntax Directed Definitions, Evaluation Orders for Syntax Directed Definitions, Inherited and Synthesized Attributes - Syntax Directed Translation - Construction of Syntax Tree-Type Systems-Specification of a simple type checker. Intermediate Languages: Three address code – Types of Three address code – Quadruple, Triples, Three-address code for Declarations, Arrays, Loops, Back patching. 

SUGGESTED ACTIVITIES:  

• Develop a Code to generate abstract syntax tree.  

• Generate three address codes for a simple program using LEX and YACC. 

• Design a simple Type Checker. 

SUGGESTED EVALUATION METHODS:  

• Assignments on SDD.  

• Quizzes on Three Address Code.  

• Seminar in Type Checking. 

UNIT IV CODE OPTIMIZATION 8 

Principal Sources of Optimization – Peep-hole optimization – DAG - Optimization of Basic Blocks Global Data Flow Analysis - Efficient Data Flow Algorithm.

SUGGESTED ACTIVITIES: 

• Develop an Algorithm for control flow analysis and data flow analysis.  

• Implementing simple code optimization techniques.

• Construction of DAG. 

SUGGESTED EVALUATION METHODS:  

• Quizzes on Optimization. 

UNIT V   RUN-TIME ENVIRONMENT AND CODE GENERATION         8

Storage Organization, Stack Allocation Space - Access to Non-local Data on the Stack - Heap Management - Issues in Code Generation - Design of a Simple Code Generator. 

SUGGESTED ACTIVITIES:  

• Implement storage allocation strategies like (heap, stack, and static).  

• Develop a Simple Code Generator. 

SUGGESTED EVALUATION METHODS:  

• Assignment on Storage Organization. 

• Group work for developing Simple Code Generator.  

• Assessment for issues in code Generation. 

LIST OF EXPERIMENTS:

1. Develop a lexical analyzer to recognize a few patterns in C. (Ex. identifiers, constants,comments, operators etc.). Create a symbol table, while recognizing identifiers.  

2. Implement a Lexical Analyzer using Lex Tool  

3. Implement an Arithmetic Calculator using LEX and YACC  

4. Generate three address code for a simple program using LEX and YACC.  

5. Implement simple code optimization techniques (Constant folding, Strength reductionand Algebraic transformation).

6. Implement back-end of the compiler for which the three address code is given as inputand the 8086 assembly language code is produced as output

OUTCOMES: At the end of the course, the student will be able to 

1. Design and implement a prototype compiler 

2. Apply the various optimization techniques 

3. Use the different compiler construction tools

4. Acquire knowledge in Syntax directed definition and Run time environment 

5. Develop the various parsing techniques and different levels of translation 

6. Build target code for backend compiler 

TEXT BOOK:

1. Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques and Tools‖, Second Edition, Pearson Education, 2009.

REFERENCES :

1.Des Watson,A Practical Approach to Compiler Construction- 2017. 

2. Allen I. Holub, Compiler Design in C‖, Prentice-Hall Software Series, 2014. 

3. Randy Allen, Ken Kennedy, and Optimizing Compilers for Modern Architectures:A Dependence based Approach, Morgan Kaufmann Publishers, 2002. 

4. Steven S. Muchnick, Advanced Compiler Design and Implementation‖, MorganKaufmann Publishers - Elsevier Science, India, Indian Reprint 2003. 

5. Keith D Cooper and Linda Torczon, Engineering a Compiler‖, Morgan KaufmannPublishers Elsevier Science, 2004. 

6. V. Raghavan, Principles of Compiler Design‖, Tata McGraw Hill Education Publishers, 2010