DBATU · Third Year B.Tech Information Technology · NEP 2020
Compiler Design
26AF1246PC505 · Semester V · 3 credits · Continuous assessment 20 + mid-semester 20 + end-semester 60
Unit 1: Automata Theory and Finite State Machines
7 hoursSymbols, alphabets, strings and languages; natural versus formal languages; DFA and NFA; regular expressions and their algebraic laws; the pumping lemma for regular languages.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Strings, languages and finite automata
- Deterministic finite automata
- NFA and ε-NFA
- Regular expressions and identities
- Pumping lemma for regular languages
Unit 2: Context-free Grammars and Pushdown Automata
7 hoursCFGs, parse trees and YACC; ambiguity; the Chomsky hierarchy; pushdown automata, their notation and language.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Context-free grammars and derivations
- Parse trees and ambiguity
- Chomsky hierarchy
- Pushdown automata and acceptance
Unit 3: Lexical Analysis
7 hoursThe phases of a compiler and their grouping; compiler-construction tools; the role of the lexical analyser; input buffering; specifying tokens; a lexical-analyser generator.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Compiler phases
- Compiler-construction tools
- Lexical analysis and input buffering
- Specifying and recognising tokens
- Lexical-analyser generators: Lex
Unit 4: Syntax Analysis and Syntax-directed Translation
7 hoursThe role of the parser; FIRST and FOLLOW; LL(1) parsing; LR and operator-precedence parsing; syntax-directed definitions, syntax trees and dependency graphs; synthesized and inherited attributes; S- and L-attributed grammars.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Top-down parsing: FIRST, FOLLOW and LL(1)
- Bottom-up parsing: LR parsers
- Operator-precedence parsing
- Syntax-directed translation
Unit 5: Intermediate Code Generation and Optimization
8 hoursSyntax-tree variants and three-address code; types, declarations and type checking; control flow and backpatching; procedure calls; code-generation design issues; basic blocks and flow graphs; optimisation and peephole optimisation.
Examined in the 60-mark end-semester paper, and in the mid-semester exam if it is taught by then
- Three-address code
- Type checking
- Control flow and backpatching
- Code generation issues
- Basic blocks and flow graphs
- Code optimisation and peephole optimisation
Unit contents are summarised from the official DBATU syllabus . AiCanCode.org is not affiliated with Dr. Babasaheb Ambedkar Technological University (DBATU).