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
Unit 1: Finite Automata and Regular Languages
9 hoursAlphabets, 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
- Deterministic finite automata
- Nondeterministic finite automata and NFA to DFA conversion
- Epsilon-NFA and its conversion
- Regular expressions
- Conversions between regular expressions and finite automata
- Closure and decision properties of regular languages
- Pumping lemma for regular languages
- Minimisation of DFA
Unit 2: Grammars, Pushdown Automata and Turing Machines
9 hoursThe 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
- Chomsky hierarchy and applications of CFGs
- Context-free grammars and derivations
- Ambiguous grammars
- Simplification of CFGs
- Chomsky and Greibach normal forms
- Pushdown automata
- Equivalence of PDA and CFG
- Variants of Turing machines
Unit 3: Compilers, Lexical Analysis and Parsing
9 hoursLanguage 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
Unit 4: Syntax-Directed Translation
9 hoursSyntax-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
Unit 5: Intermediate Code, Storage and Basic-Block Optimisation
9 hoursVariants 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).