CS3501 COMPILER DESIGN LTPC

3 024

COURSE OBJECTIVES:
 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 the front-end of the compiler.
 To learn to implement code generator.
 To learn to implement code optimization.

UNIT I INTRODUCTION TO COMPILERS & LEXICAL ANALYSIS 8

Introduction- Translators- Compilation and Interpretation- Language processors -The Phases of

Compiler – Lexical Analysis – Role of Lexical Analyzer – Input Buffering – Specification of Tokens
– Recognition of Tokens – Finite Automata – Regular Expressions to Automata NFA, DFA –
Minimizing DFA - Language for Specifying Lexical Analyzers – Lex tool.

UNIT II SYNTAX ANALYSIS 11

Role of Parser – Grammars – Context-free grammars – Writing a grammar Top Down Parsing -
General Strategies - 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-YACC tool - Design of a syntax Analyzer for a
Sample Language

UNIT III SYNTAX DIRECTED TRANSLATION & INTERMEDIATE CODE GENERATION 9

Syntax directed Definitions-Construction of Syntax Tree-Bottom-up Evaluation of S-Attribute

Definitions- Design of predictive translator - Type Systems-Specification of a simple type Checker-
Equivalence of Type Expressions-Type Conversions. Intermediate Languages: Syntax Tree, Three
Address Code, Types and Declarations, Translation of Expressions, Type Checking, Back
patching.

UNIT IV RUN-TIME ENVIRONMENT AND CODE GENERATION 9

Runtime Environments – source language issues – Storage organization – Storage Allocation

Strategies: Static, Stack and Heap allocation - Parameter Passing-Symbol Tables - Dynamic
Storage Allocation - Issues in the Design of a code generator – Basic Blocks and Flow graphs -
Design of a simple Code Generator - Optimal Code Generation for Expressions– Dynamic
Programming Code Generation.

UNIT V CODE OPTIMIZATION 8

Principal Sources of Optimization – Peep-hole optimization - DAG- Optimization of Basic Blocks -
Global Data Flow Analysis - Efficient Data Flow Algorithm – Recent trends in Compiler Design.

45 PERIODS

95
LIST OF EXPERIMENTS:

1. Using the LEX tool, 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. Generate YACC specification for a few syntactic categories.

a. Program to recognize a valid arithmetic expression that uses operator +, -, * and /.

b. Program to recognize a valid variable which starts with a letter followed by any
number of letters or digits.
c. Program to recognize a valid control structures syntax of C language (For loop,
while loop, if-else, if-else-if, switch-case, etc.).
d. Implementation of calculator using LEX and YACC

4. Generate three address code for a simple program using LEX and YACC.
5. Implement type checking using Lex and Yacc.
6. Implement simple code optimization techniques (Constant folding, Strength reduction and
Algebraic transformation)
7. Implement back-end of the compiler for which the three address code is given as input and
the 8086 assembly language code is produced as output.
30 PERIODS
TOTAL: 75 PERIODS
COURSE OUTCOMES:
On Completion of the course, the students should be able to:

CO1:Understand the techniques in different phases of a compiler.

CO2:Design a lexical analyser for a sample language and learn to use the LEX tool.
CO3:Apply different parsing algorithms to develop a parser and learn to use YACC tool
CO4:Understand semantics rules (SDT), intermediate code generation and run-time environment.
CO5:Implement code generation and apply code optimization techniques.

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. Randy Allen, Ken Kennedy, Optimizing Compilers for Modern Architectures: A Dependence
based Approach, Morgan Kaufmann Publishers, 2002.
2. Steven S. Muchnick, Advanced Compiler Design and Implementation‖, Morgan Kaufmann
Publishers - Elsevier Science, India, Indian Reprint 2003.
3. Keith D Cooper and Linda Torczon, Engineering a Compiler‖, Morgan Kaufmann Publishers
Elsevier Science, 2004.
4. V. Raghavan, Principles of Compiler Design‖, Tata McGraw Hill Education Publishers, 2010.
5. Allen I. Holub, Compiler Design in C‖, Prentice-Hall Software Series, 1993.

96
CO’s-PO’s & PSO’s MAPPING
CO’s PO’s PSO’s
1 2 3 4 5 6 7 8 9 10 11 12 1 2 3
1 3 3 3 3 - - - - 3 3 1 3 2 3 2
2 3 3 3 3 3 - - - 3 2 3 2 2 1 2
3 3 3 2 2 3 - - - 3 1 1 1 2 2 3
4 3 2 2 1 1 - - - 2 3 2 3 1 2 1
5 3 3 3 2 1 - - - 2 1 1 3 2 1 2
AVg. 3.00 2.80 2.60 2.20 2.00 - - - 2.60 2.00 1.60 2.40 1.80 1.80 2.00
1 - low, 2 - medium, 3 - high, ‘-“- no correlation

CB3491 CRYPTOGRAPHY AND CYBER SECURITY L T P C

3 0 0 3
COURSE OBJECTIVES:
 Learn to analyze the security of in-built cryptosystems.
 Know the fundamental mathematical concepts related to security.
 Develop cryptographic algorithms for information security.
 Comprehend the various types of data integrity and authentication schemes
 Understand cyber crimes and cyber security.

UNIT I INTRODUCTION TO SECURITY 9

Computer Security Concepts – The OSI Security Architecture – Security Attacks – Security Services
and Mechanisms – A Model for Network Security – Classical encryption techniques: Substitution
techniques, Transposition techniques, Steganography – Foundations of modern cryptography:
Perfect security – Information Theory – Product Cryptosystem – Cryptanalysis.

UNIT II SYMMETRIC CIPHERS 9

Number theory – Algebraic Structures – Modular Arithmetic - Euclid‘s algorithm – Congruence and
matrices – Group, Rings, Fields, Finite Fields

SYMMETRIC KEY CIPHERS: SDES – Block Ciphers – DES, Strength of DES – Differential and
linear cryptanalysis – Block cipher design principles – Block cipher mode of operation – Evaluation
criteria for AES – Pseudorandom Number Generators – RC4 – Key distribution.

UNIT III ASYMMETRIC CRYPTOGRAPHY 9

MATHEMATICS OF ASYMMETRIC KEY CRYPTOGRAPHY: Primes – Primality Testing –
Factorization – Euler’s totient function, Fermat’s and Euler’s Theorem – Chinese Remainder
Theorem – Exponentiation and logarithm

ASYMMETRIC KEY CIPHERS: RSA cryptosystem – Key distribution – Key management – Diffie
Hellman key exchange -– Elliptic curve arithmetic – Elliptic curve cryptography.

UNIT IV INTEGRITY AND AUTHENTICATION ALGORITHMS 9

Authentication requirement – Authentication function – MAC – Hash function – Security of hash
function: HMAC, CMAC – SHA – Digital signature and authentication protocols – DSS – Schnorr
Digital Signature Scheme – ElGamal cryptosystem – Entity Authentication: Biometrics, Passwords,
Challenge Response protocols – Authentication applications – Kerberos
MUTUAL TRUST: Key management and distribution – Symmetric key distribution using symmetric
and asymmetric encryption – Distribution of public keys – X.509 Certificates.
97