Subject Code : 410444
Subject Name : Principles Of Compiler Design
Theory: 100 Marks Duration : 3 Hrs
• To learn and understand the design of a compiler
• To learn and use tools for construction of a compiler
UNIT I: Introduction to Compiler:
Translator issues, why to write compiler, compilation process in brief, front end and backend model, compiler construction tools, Interpreter and the related issues, Cross compiler, Incremental compiler, Boot strapping, byte code compilers.
Lexical Analysis. Review of lexical analysis: alphabet, token, lexical error, Block schematic of lexical analyser, "Automatic construction of lexical analyser-(LEX), LEX specification and features.
UNIT II Syntax Analysis
Introduction: Role of parsers, Top down-RD parser, Predictive parsers, LL (k) parsers, Bottom up Parsers - Operator precedence parsers, shift-Reduce: SLR, LR (k), LALR etc. using ambiguous grammars. Error detection and recovery, Automatic construction of parsers (YACC), YACC specifications
Semantic Analysis Need of semantic analysis, type checking and type conversion
Syntax directed translation
Syntax directed definitions, construction of syntax trees, bottom-up evaluation of S-attributed
Definitions, L-attributed definitions, Top-down translation, bottom-up evaluation of inherited
attributes -Intermediate Code Generation Intermediate languages, declarations, assignment statements, iterative statements, case statements, arrays, structures, conditional statements, Boolean expressions, back patching, procedure calls, Intermediate code generation using YACC .
Runtime Storage Organization
Source language issues, Storage organization and allocation strategies, for block structured and non block structured languages, Activation record, variable-length data, procedure parameters, nested procedures, access to non-local names, procedure Call and return, static and dynamic scope, Symbol Table organization and management
Introduction: Issues in code generation, Target machine description, Basic blocks and flow graphs, next-use information, Register allocation and assignment, Dag representation of basic blocks, Peephole optimization, Generating code from a DAG, Dynamic programming, Code generator- The write-ups for any diagram can include small examples to cover notation that has not been referred to in your submitted diagram. Generally any UML diagram has accompanied document to explain the diagram further for example use case descriptions, non-functional requirements, scripts, notes, assumptions, project management aspects.
Introduction, Classification of optimization, Principle sources Of Optimization, optimization of basic blocks, Loops in flow graphs, Optimizing transformations: compile time evaluation, Common sub-expression elimination, variable propagation, code movement, strength reduction, dead code elimination and loop optimization, Local optimization, DAG based local optimization. Global Optimization: Control and data flow analysis, Computing Global Data flow information: meet over paths, Data flow equations, Data flow analysis, Iterative data flow analysis: Available expressions, live range identification
1.A V Aho, R. Sethi, .J D Ullman, "Compilers: Principles,Techniques,and Tools", Pearson Education, ISBN 81 - 7758 - 590 - 8
Reference Books -
1.K. Cooper, L, Torczon, "Engineering a Compiler", Morgan Kaufinann Publishers, ISBN 81-8147-369-8.
2.K. Louden, "Compiler Construction: Principles and Practice", Thomson Brookes/Cole (ISE), 2003, ISBN 981 - 243 - 694-4:
3.J. R. Levine, T. Mason, D. Brown, "Lex & Yacc", O'Reilly, 2000, ISBN 81-7366 -061-X.
4.S. Chattopadhyay, "Compiler Design", Prentice-Hall of India, 2005, ISBN 81-203-2725-X.