KBCNMU TY Computer syllabus

KBCNMU · Third Year B.E. Computer Engineering · NEP 2020

Theory of Computation and Compiler Design

CS-503 · Semester V · 3 credits · ISE 40 + ESE 60

  1. Unit 1: Finite Automata and Regular Languages

    9 hours

    Alphabets, strings and languages; DFA, NFA and ε-NFA, ε-closure and the subset construction; regular expressions and their equivalence with finite automata; closure properties and the pumping lemma; minimising finite automata.

    Examined in the 60-mark end-semester paper

  2. Unit 2: Grammars, Pushdown Automata and Turing Machines

    9 hours

    The Chomsky hierarchy, derivations and parse trees, ambiguity, simplification of CFGs and Chomsky normal form; PDAs, acceptance by final state and empty stack, equivalence of PDA and CFG; Turing machines and their variants.

    Examined in the 60-mark end-semester paper

  3. Unit 3: Compilers, Lexical Analysis and Parsing

    9 hours

    Language processors and the structure of a compiler; the lexical analyser, input buffering and LEX; recursive-descent parsing, FIRST and FOLLOW sets and LL(1) grammars; LR(0) items, SLR, canonical LR(1) and LALR tables; YACC with ambiguous grammars.

    Examined in the 60-mark end-semester paper

    • Language processors: compilers, interpreters, assemblers, linkers and loaders
    • Phases of a compiler
    • Role of the lexical analyser and input buffering
    • Lex and Flex
    • Top-down parsing: recursive descent and LL(1)
    • FIRST and FOLLOW sets and predictive parsing tables
    • LR parsers: SLR, CLR and LALR
    • Parser generators: YACC and Bison
  4. Unit 4: Syntax-Directed Translation

    9 hours

    Syntax-directed definitions evaluated on the parse tree, dependency graphs, constructing syntax trees and type structures; postfix translation schemes and their parser-stack implementation, actions inside productions, eliminating left recursion, L-attributed SDTs.

    Examined in the 60-mark end-semester paper

    • Syntax-directed definitions and translation schemes
    • S-attributed and L-attributed definitions
    • Type checking
  5. Unit 5: Intermediate Code, Storage and Basic-Block Optimisation

    9 hours

    Variants of syntax trees and DAGs for expressions, the value-number method; three-address code as quadruples and triples, and static single-assignment form; static and dynamic storage allocation; the target machine and instruction costs; optimising basic blocks with DAGs.

    Examined in the 60-mark end-semester paper

    • Intermediate code: syntax trees, postfix and three-address code
    • Quadruples, triples and indirect triples
    • Storage allocation strategies
    • Code generator design and the target machine
    • DAG representation of basic blocks

Unit contents are summarised from the official KBCNMU syllabus . AiCanCode.org is not affiliated with Kavayitri Bahinabai Chaudhari North Maharashtra University (KBCNMU).