Formal Language and Regular Expressions: Languages, Definition Languages regular expressions, Finite Automata – DFA, NFA. Conversion of regular expression to NFA, NFA to DFA. Applications of Finite Automata to lexical analysis, lex tools
Context Free grammars and parsing : Context free grammars, derivation, parse trees, ambiguity LL(K) grammars and LL(1) parsing Bottom up parsing, handle pruning, LR Grammar Parsing, LALR parsing, parsing ambiguous grammars, YACC programming specification
Semantics : Syntax directed translation, S-attributed and L-attributed grammars, Intermediate code – abstract syntax tree, translation of simple statements and control flow statements. Context Sensitive features – Chomsky hierarchy of languages and recognizers. Type checking, type conversions, equivalence of type expressions, overloading of functions and operations
Symbol table, Storage organization, storage allocation strategies scope access to now local names, parameters, language facilities for dynamics storage allocation. Code optimization Principal sources of optimization, optimization of basic blocks, peephole optimization, flow graphs, optimization techniques
Code generation : Machine dependent code generation, object code forms, generic code generation algorithm, Register allocation and assignment. Using DAG representation of Block LIST OF EXPERIMENTS: 1. Develop a lexical analyzer to recognize a few patterns in C. (Ex. identifiers, constants, comments, operators etc.). Create a symbol table, while recognizing identifiers. 2. Implement a Lexical Analyzer using Lex Tool 3. Implement an Arithmetic Calculator using LEX and YACC 4. Generate three address code for a simple program using LEX and YACC. 5. Implement simple code optimization techniques (Constant folding, Strength reduction and Algebraic transformation) 6. Implement back-end of the compiler for which the three address code is given as input and the 8086 assembly language code is produced as output
Reference Book:
1. Tremblay J P, Sorenson G P: “The Theory & Practice of Compiler writingâ€, 1st Edition, BSP publication, 2010. 2. Appel W & Andrew G M: “Modern Compiler Implementation in Câ€, 1st Edition, Cambridge University Press, 2003. 3. Louden: “Compiler Construction, Principles &Practiceâ€, 1st Edition, Thomson Press, 2006. 4. Sipser Michael: “Introduction to Theory of computationâ€, 1st Edition, Thomson, 2009
Text Book:
1. John E. Hopcroft, Rajeev M & J D Ullman: “Introduction to Automata Theory Languages &Computationâ€, 3rd Edition, Pearson Education, 2007. 2. Aho, Ullman, Ravisethi: “Compilers Principles, Techniques and Toolsâ€, 2nd Edition, Pearson Education, 2009
