Compiler Design

Course Objectives:

1. To introduce the major concept areas of language translation and compiler design.
2. To enrich the knowledge in various phases of compiler ant its use, code optimization techniques, machine code generation, and use of symbol table.
3. To extend the knowledge of parser by parsing LL parser and LR parser.
4. To provide practical programming skills necessary for constructing a compiler.

Course Outcomes (CO)

• CO 1 Able to apply the knowledge of LEX tool & YACC tool to develop a scanner & parser.
• CO 2 Able to design & implement a software system for backend of the compiler.
• CO 3 Able to design syntax tree and intermediate code generator.
• CO 4 To understand the concept of symbol table and to use various code optimization techniques

UNIT-I

Compilers and translators, need of translators, structure of compiler: its different phases, compiler construction tools, Lexical analysis: Role of lexical analyzer, Input Buffering, A simple approach to the design of Lexical Analyzers, Specification and recognition of tokens, Finite automata, From regular expressions to automata, and vice versa, minimizing number of states of DFA, A language for specifying Lexical Analyzers, Design and implementation of lexical analyzer.

UNIT-II

The role of the parser, Context free grammars, Writing a grammar: Lexical versus Syntactic analysis, Eliminating ambiguity, Elimination of left recursion, Left factoring, Top Down Parsing: Recursive- Decent parsing, Non-recursive Predictive parsing, LL(1) grammars, Bottom Up Parsing: Shift Reduce Parsing, Operator precedence parsing, LR Parsing: SLR, LALR and Canonical LR parser, Parser Generators.

UNIT-III

Syntax Directed Translation: Syntax directed definitions, Evaluation orders for SDD’s, construction of syntax trees, syntax directed translation schemes, implementation of syntax directed translation, Intermediate Code Generation: Kinds of intermediate code: Postfix notation, Parse trees and syntax trees, Three-address code, quadruples and triples, Semantic Analysis: Types and Declarations, Translation of Expressions, Type checking.

UNIT - IV

Symbol Table: Symbol tables, its contents, Data Structure for Symbol Table: lists, trees, linked lists, hash tables, Error Detection and Recovery: Errors, lexical phase errors, syntactic phase errors, semantic errors, Error seen by each phase.

Code Optimization: The principal sources of optimizations, Loop optimization, Basic blocks and Flow Graphs, DAG representation of basic blocks, Code Generation: Issues in the design of code generation, A simple target machine mode, A Simple Code Generator, Peep-hole optimization, Register allocation and assignment.

Textbook(s):

1. Alfred V. Aho, Monica S. Lam, Ravi Sethi and Jeffrey D. Ullman, “Compilers Principle, Techniques, & Tool”, Pearson.
2. Alfred V. Aho, Ravi Sethi and Jeffrey D. Ullman, “Compilers Principle, Techniques, and Tool”, Addison Wesley.

References:

1. Trembley and Sorenson, “Theory and Practice of Compiler Writing”, McGraw Hill.
2. Jhon R. Levine, Tony Mason and Doug Brown, ―Lex &Yacc, O‘Reilly.
3. M. Joseph, “Elements compiler Design”, University Science Press.