PRINCIPLES OF COMPILER DESIGN

CS1352                       PRINCIPLES OF COMPILER DESIGN               3  1  0  100

 

AIM

At the end of the course the student will be able to design and implement a simple compiler.

OBJECTIVES

·          To understand, design and implement a lexical analyzer.

·          To understand, design and implement a parser.

·          To understand, design code generation schemes.

·          To understand optimization of codes and runtime environment.

UNIT I                 INTRODUCTION TO COMPILING                         9

Compilers - Analysis of the source program - Phases of a compiler - Cousins of the Compiler - Grouping of Phases - Compiler construction tools - Lexical Analysis - Role of Lexical Analyzer - Input Buffering - Specification of Tokens.

                                                                                                                                                                                     

UNIT II                      SYNTAX ANALYSIS                                                         9         

Role of the parser -Writing Grammars -Context-Free Grammars - Top Down parsing - Recursive Descent Parsing - Predictive Parsing - Bottom-up parsing - Shift Reduce Parsing - Operator Precedent Parsing - LR Parsers - SLR Parser - Canonical LR Parser - LALR Parser.

UNIT III        INTERMEDIATE CODE GENERATION                                  9

Intermediate languages - Declarations - Assignment Statements - Boolean Expressions - Case Statements - Back patching - Procedure calls.

Parse Tree

• Inner nodes of a parse tree are non-terminal symbols.

•  The leaves of a parse tree are terminal symbols.

•  A parse tree can be seen as a graphical representation of a derivation

Ambiguity

Parsing Derivations – Principles of Compiler Design

E Þ E+E

—E+E derives from E

—we can replace  E by E+E

—to able to do this, we have to have a production rule  E®E+E in our grammar.

—

E Þ E+E Þ id+E Þ id+id

—A sequence of replacements of non-terminal symbols is called a derivation of id+id from E.

  Þ   : derives in one step

  Þ  : derives in zero or more steps

  Þ  : derives in one or more steps

Means   E-> E+E -> id + E -> id + id

Parsing – Principles of Compiler Design

Need of a Parser

•Syntax Analyzer creates the syntactic structure of the given source program.

•This syntactic structure is mostly a parse tree.

•Syntax Analyzer is also known as Parser.

•The syntax of a programming is described by a context-free grammar (CFG).

•The syntax analyzer (Parser) checks whether a given source program satisfies the rules implied by a context-free grammar or not.

–If it satisfies, the parser creates the parse tree of that program.

–Otherwise the parser gives the error messages.

Parser