Theory of Computation and Compilers

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., approximate solutions versus precise ones). The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language). The name "compiler" is primarily used for programs that translate source code from a high-level programming language to a low-level programming language (e.g. assembly language, object code, or machine code) to create an executable program.

Content Video

Theory of Computation and Compilers
- Theory of Computation
- Compilers

Theory of Computation and Compilers

Unit	Details Contents
Unit -I	Theory of Computation Formal Language Non-Computational Problems Diagonal Argumen Russels’s Paradox
Unit -II	Regular Language Models Deterministic Finite Automaton (DFA) Non-Deterministic Finite Automaton (NDFA) Equivalence of DFA and NDFA Regular Languages Regular Grammars Pumping Lemma Non-Regular Languages Lexical Analysis
Unit -III	Context Free Language Pushdown Automaton (PDA) Non-Deterministic Pushdown Automaton (NPDA) Context Free Grammar Chomsky Normal Form Greibach Normal Form, Ambiguity Ambiguity Parse Tree Representation of Derivation Trees Equivalence of PDA’s and Context Free Grammars Properties of Context Free Language
Unit -IV	Turing Machines (TM) Standard Turing Machine and its Variations Universal Turing Machines Models of Computation and Church-Turing Thesis Recursive and RecursivelyEnumerable Languages Context-Sensitive Languages Unrestricted Grammars Chomsky Hierarchy of Languages Construction of TM for Simple Problems
Unit -V	Unsolvable Problems and Computational Complexity Unsolvable Problem Halting Problem Post Correspondence Problem Unsolvable Problems for Context-Free Languages Measuring and Classifying Complexity Tractable and Intractable Problems
Unit -VI	Syntax Analysis Associativity & Precedence Grammar Transformations Top Down Parsing Recursive Descent Predictive Parsing LL(1) Parsing Bottom up Parsing LR Parser LALR(1) Parser
Unit -VII	Semantic Analysis Attribute Grammar Syntax Directed Definitions Inherited and Synthesized Attributes Dependency Graph Evaluation Order S-attributed and Lattributed Definitions Type-Checking
Unit -VIII	Run Time System Storage Organization Activation Record Activation Tree Stack Allocation of Activation Records Parameter Passing Mechanisms Symbol Table
Unit -IX	Intermediate Code Generation Intermediate Code Generation Intermediate Representations Translation of Declarations Assignments Control Flow Boolean Expressions and Procedure Calls
Unit -X	Code Generation and Code Optimization Control-flow Data-flow Analysis Local Optimization Global Optimization Loop Optimization Peep-Hole Optimization Instruction Scheduling