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.
|Author: Abhijeet Gaikwad 17 Nov 2009||Member Level: Gold Points : 2|
Assignments for PCD are (As per University Syllabus):
1. Choose a hypothetical system of significant complexity and write an SRS for the same.
2. Draw one or more Use Case diagrams for capturing and representing requirements of the system. Use case diagrams must include template showing description and steps of the Use Case for various scenarios.
3. Draw one or more Package diagram to organize and manage your large and complex systems as well as their complex models.
4. Draw activity diagrams to display either business flows or like flow charts.
5. Draw basic class diagrams to identity and describe key concepts like classes, types in your system and their relationships.
6. Draw advanced class diagrams to depict advanced relationships, other classifiers like interfaces.
7. Draw sequence diagrams OR communication diagrams with advanced notation for'your system to show objects and their message exchanges.
8. Draw state machine to model the behavior of a single object, specifying the sequence of events that an object goes through during its lifetime in response to events.
9. Draw component diagrams assuming that you will build your system reusing existing components along with a few new ones.
10. Draw deployment diagrams to model the runtime architecture of your system.