top of page

Course Code - ITE1006
Credits - 3
Modules - 8

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:

  1. Gate Smasher (Theory of Computation)

  2. Education 4u (Theory of Computation)

  3. Gate Smashers (Compiler Design)

  4. Education 4u (Compiler Design)


 
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

Gate Smashers - Lec 3 and Lec 4


 
Module 3 - Myhill-Nerode Theorem

TOC - Myhill-Nerode Theorem - Minimization of FA – Decision properties of regular languages – Pumping lemma for Regular languages (With Proof)

Myhill Nerode Theorem

Gate Smashers – Lec26, 31, 45

Education 4u – Lec 23 , 24, 46, 47


 
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

Gate Smashers – lec 56 to 62

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

Education 4u – Lec 32 to 58


 
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.


 


bottom of page