Theory of Computation and Compiler Design (CSE2002)
Credits : 4
NOTE:
The name might be scary, but this subject is one of the easy ones, if you grasp the underlying concept (there are some mugging portions too), NO ONE can stop you from getting the S grade.
One of the best websites to refer is GeeksforGeeks (GFG), this website contains golden information, for the TOC subject:
This Course is usually broken down into 2 divisions
a. Theory of Computation
b. Compiler Design
Some playlists which will be very helpful:
Module 1 - Introduction to Languages and Grammars
TOC - Overview of a computational model - Languages and grammars – alphabets – Strings - Operations on languages
Gate Smashers – Lec 1 to Lec 5
Compiler - Introduction to Compilers - Analysis of the Source Program - Phases of a Compiler
Gate Smashers (CD) – Lec 2
Module 2 - Regular Expressions and Finite Automata
TOC - Finite automata – DFA – NFA – Equivalence of NFA and DFA (With Proof) - Regular expressions – Conversion between RE and FA (With Proof)
Education 4u - Lec 6 to Lec 22 and Lec 40 to Lec 43
CD - Lexical Analysis - Recognition of Tokens - Designing a Lexical Analyzer using finite automata
Module 4 - CFG, PDAs and Turing Machines
TOC - CFG – Chomsky Normal Forms - NPDA – DPDA - Membership algorithm for CFG
Gate Smashers – Lec 45 to 55 and 63-64
Education 4u – Lec 48 to Lec 77
CD - Syntax Analysis - Top-Down Parsing - Bottom-Up Parsing - Operator-Precedence Parsing - LR Parsers
Education 4u - Lec 8 to 25 (Same topics can be found also in Gate Smashers’ Compiler Design Playlist)
Module 5 - Turing Machines
TOC - Turing Machines – Recursive and recursively enumerable languages – Linear bounded automata - Chomsky's hierarchy – Halting problem
Module 6 - Intermediate Code Generation
CD - Intermediate Code Generation - Intermediate Languages – Declarations - Assignment Statements - Boolean Expressions - Case Statements – Backpatching - Procedure Calls
Education 4u – lec 51
Rest to be covered from faculty’s slides
Module 7 – Code Optimisation
CD - Code Optimization - Basic Blocks and Flow Graphs – The DAG Representation of Basic Blocks - The Principal Sources of Optimization - Optimization of Basic Blocks - Loops in Flow Graphs - Peephole Optimization - Introduction to Global Data-Flow Analysis
Module 8 – Code Generation
CD - Code Generation – Issues in the Design of a Code Generator - The Target Machine - Run-Time Storage Management - Next-Use Information - Register Allocation and Assignment - A Simple Code Generator - Generating Code from DAG Recent Trends – Just-in-time compilation with adaptive optimization for dynamic languages - Parallelizing Compilers Total Lecture Hours
90% percent is already covered in the previous module videos, it will be beneficial to cover them like said above, as they all are linked and will help you to understand better.
Faculty’s slides will be useful to cover this module.