This module was prepared by Wachemo University

COMPILER DESIGN Module

Course Code: CoSc 4103

Developed By:

1. Abraham Wolde(Msc in Computer Science and Engineering)

Compiled and edited by

July, 2025

Hossana, Ethiopia

i
 Module Preface
This resource module is designed and developed in support of the Compiler Design Course. It
provides learning resources as well as teaching ideas.
Dear students, in chapter one you have been studied about Introduction of compiler, Phases of a
Compiler, Computer Language Representation, and Compiler Construction Tools within week
1.
In chapter two, Lexical Analysis have been studied, understanding of lexical analysis and how
lexical analysis works, and examples of lexical analyzer, how to handle errors in the lexical
phase , and how to convert NFA to DFA are also studied within weeks 2-3.
In chapter Three, Syntax Analyzer have been studied, understanding of syntax analysis and
how syntax analyzer works, and examples of syntax analyzer, the difference between syntax
and parse tree, understanding of types of parsing ,and how to handle errors recovery in the
syntax phase are also studied within weeks 4-6.
In chapter four, the overview of SDT have been studied, the difference between SDT versus
SDD, understanding Attribute grammar, design the evaluation orders for SDD, and how to
construct the syntax tree are well studied within weeks 7-8.
In chapter Five, introduction of Type checking in compiler design concepts have been studied,
and identify the types of conversion are well studied within weeks 9-10.
In chapter Six, Overview of Intermediate Language have been studied, understanding of kinds of
intermediate language and kinds of three address statement, how to represent the three address
code in flow control statement, back patching and procedure call are well studied within weeks
11-12.
In chapter Seven , Overview of Run time- Environment have been studied , definition of Symbol
table and hash table and their uses , representation of scope information are well studied within
weeks 13-14.
In chapter Eight, Overview of Code Generation and Optimization have been studied , how to
represent DAG , understanding of flow blocks and loops, and peephole optimization Techniques
and characteristics are also well studied within weeks 15-16.

ii | P a g e
Table of Contents
Module Preface ............................................................................................................................................. ii
List of Figures ............................................................................................................................................... vi
CHAPTER ONE INTRODUCTION ............................................................................................................ 1
Introduction .................................................................................................................................................. 1
1.1. Introduction to Compilers ............................................................................................................. 1
1.1.1. Parts of Compilation ................................................................................................. 3
1.1.2. Analysis of the Source Program ............................................................................... 5
1.2. Phases of a Compiler .................................................................................................................... 5
1.2.1. The Analysis Phases of the Compiler ....................................................................... 8
1.3. Computer Language Representation ................................................................................................ 13
CHAPTER TWO LEXICAL ANALYSIS ................................................................................................. 19
Introduction ................................................................................................................................................ 19
2.1. Overview of Lexical Analysis..................................................................................................... 19
2.1.1. The Role of the Lexical Analyzer ........................................................................... 20
2.1.2. Issues in Lexical Analysis ....................................................................................... 21
2.1.3. Tokens, Patterns, Lexemes ..................................................................................... 21
2.2. Specification and Recognition of Token ..................................................................................... 24
2.2.1. Specification of Tokens .......................................................................................... 25
2.2.2. Recognition of Tokens ............................................................................................ 28
2.3. Formal definition of a Finite Automaton .................................................................................... 30
2.3.1. NFA to DFA Conversion ........................................................................................ 31
2.4. Lexical Error ............................................................................................................................... 36
2.5. Lexical Analyzer Generator ......................................................................................................... 36
CHAPTER THREE SYNTAX ANALYSIS............................................................................................... 38
3.1. Overview of Syntax Analysis ..................................................................................................... 38
3.1.1. Role of a Parser ....................................................................................................... 39
3.3. Syntax Tree versus Parse Tree .................................................................................................... 44
3.3.1. Derivation .................................................................................................................... 45
3.3.2. Parse Tree .................................................................................................................... 47
3.3.3. Ambiguity .................................................................................................................... 48
iii | P a g e
 3.3.4. Eliminating Left Recursion ..................................................................................... 50
3.3.5. Left Factoring.......................................................................................................... 52
3.4. Regular Expression Versus Context Free Grammar ................................................................... 53
3.5. Parsing......................................................................................................................................... 54
TYPES OF PARSING ............................................................................................................................ 54
3.5.1 Top-Down Parsing .................................................................................................. 56
3.5.2. Bottom up parsing ................................................................................................... 71
3.6. Error Recovery Strategies ........................................................................................................... 77
CHAPTER FOUR SYNTAX DIRECTED TRANSLATION ..................................................................................... 80
Introduction ................................................................................................................................................. 80
4.1. Overview of Syntax Directed Translation (SDT) .......................................................................... 80
4.2. Syntax Directed Definitions ........................................................................................................ 82
4.3. Syntax-Directed Translation Schemes (SDT) ............................................................................. 82
4.4. Inherited and Synthesized Attributes .......................................................................................... 83
4.5. Attribute Grammars .................................................................................................................... 86
4.6. Evaluation Orders for SDD's ...................................................................................................... 87
4.6.1. Dependency Graphs ................................................................................................ 87
4.7. Construction of Syntax Tree ....................................................................................................... 88
CHAPTER FIVE TYPE CHECKING ................................................................................................................... 90
Introduction ................................................................................................................................................ 90
5.1. Introduction to Type Checking .................................................................................................... 90
5.1.1. Designing a Type Checker ...................................................................................... 91
5.2. Rules for Type Checking ............................................................................................................ 93
5.3. Type Conversion ......................................................................................................................... 93
5.3.1. Implicit Conversion ................................................................................................ 94
5.3.2. Explicit Conversion (Casts) .................................................................................... 96
5.3.3. User-defined Conversion ........................................................................................ 97
CHAPTER SIX INTERMEDIATE LANGUAGES ................................................................................... 98
Introduction ................................................................................................................................................. 98
6.1. Overview of Intermediate Language ................................................................................................ 98
6.2. Implementation of Three-address Statements ........................................................................... 102

iv | P a g e
 6.2.1. Quadruples ............................................................................................................ 102
6.2.2. Triples ................................................................................................................... 102
6.2.3. Indirect triples ....................................................................................................... 103
6.3. Flow of Control Statement ........................................................................................................ 104
6.4. BACKPATCHING ................................................................................................................... 107
6.5. Procedure Calls ......................................................................................................................... 108
CHAPTER SEVEN RUN TIME- ENVIRONMENTS.......................................................................................... 110
Introduction .............................................................................................................................................. 110
7.1. Run-Time Environment ................................................................................................................. 110
7.2. Symbol Table ................................................................................................................................. 110
7.2.1. Symbol Table Entries ............................................................................................ 112
7.2.2. Operations of Symbol Table ................................................................................. 113
7.2.3. Implementation of Symbol Table ......................................................................... 114
7.3. Hash Table ................................................................................................................................ 116
7.4. Representing Scope Information ............................................................................................... 118
CHAPTER EIGHT CODE GENERATION AND OPTIMIZATION....................................................................... 121
Introduction .............................................................................................................................................. 121
8.1. Introduction to Code Generation and Optimization .................................................................. 121
8.1.1. Issues in the Design of a Code Generator ............................................................. 121
8.2. The Target Machine .................................................................................................................. 125
8.3. Run-time Storage Management ................................................................................................ 125
8.4. Basic Blocks and Flow Graphs ................................................................................................. 125
8.4.1. Basic Blocks.......................................................................................................... 125
8.4.2. Flow Graphs .......................................................................................................... 129
8.4.3. Loops..................................................................................................................... 130
8.5. A Simple Code Generator ......................................................................................................... 131
8.6. Register and Address Descriptors ............................................................................................. 131
8.7. The DAG Representation of Basic Blocks ............................................................................... 131
8.8. The Principal Sources of Optimization ..................................................................................... 132
8.9. Peephole Optimization .............................................................................................................. 135
References ................................................................................................................................................ 136

v|Page
List of Figures
Figure1. 1: Major function of Compiler ......................................................................................... 2
Figure1. 2: Syntax Tree for Position: =initial rate*60 .................................................................... 3
Figure1. 3: Block Diagram of Phases of Compiler ......................................................................... 7
Figure1. 4: The data structure in (b) is for the tree in (a)................................................................ 9
Figure 1. 5: Source program Examples of each Phases ................................................................ 12
Figure1. 6: Language Processing System ..................................................................................... 16
Figure 2. 1: Interaction of Lexical Analyzer with Parser .............................................................. 20
Figure 2. 2:Finite Automata State Graph ...................................................................................... 31
Figure 3. 1: CFG and RE Diagram ............................................................................................... 39
Figure 3. 2: Position of parser in compiler model ....................................................................... 40
Figure 3. 3: Example of Syntax and Parse Tree............................................................................ 45
Figure 3. 4: left recursion .............................................................................................................. 51
Figure 3. 5: Types of parsing ........................................................................................................ 56
Figure 3. 6: Example of Top down and Bottom up approach ....................................................... 56
Figure 3. 7: Top-down parse for id + id * id................................................................................. 58
Figure 3. 8: LL(1) grammar .......................................................................................................... 66
Figure 3. 9: Types of errors recovery............................................................................................ 77
Figure 4. 1: synthesis and Inherited attribute ................................................................................ 84
Figure 4. 2: Dependency graphs ................................................................................................... 87
Figure 4. 3: Examples of Annotated parse tree ............................................................................. 89
Figure 6. 1: Intermediate Language ............................................................................................. 98
Figure 6. 2: Abstract syntax tree representation ......................................................................... 100
Figure 6. 3: Syntax-directed definition for flow-of-control statements ...................................... 105
Figure 6. 4: SDD for if-then, if-then-else, and while-do statements........................................... 107
Figure 7. 1: Representing scope information .............................................................................. 120
Figure 8. 1: Position of code generator ....................................................................................... 121
Figure 8. 2:Flow graph for the vector dot product ...................................................................... 130

vi | P a g e
 CHAPTER ONE
INTRODUCTION

Introduction
In this chapter, you have been studied about Introduction of compiler, Phases of a Compiler,
Computer Language Representation, and Compiler Construction Tools

After completing this chapter, the students will be able to:

► understanding of Introduction of compiler and Phases of a Compiler,

► know basic Computer Language Representation, and Compiler Construction Tools

1.1. Introduction to Compilers

 Computer programs are formulated in a programming language and specify classes of

computing processes. Computers, however, interpret sequences of particular instructions, but
not program texts. Therefore, the program text must be translated into a suitable instruction
sequence before it can be processed by a computer. This translation can be automated, which
implies that it can be formulated as a program itself. The translation program is called a
compiler, and the text to be translated is called source text (or sometimes source code).
 A Compiler is a program that reads a program written in one language - the source
Language - and translates it in to an equivalent program in another language - the target
language without changing the meaning of the program. Most specifically a compiler takes a
computer program and translates it into an object program. Some other tools associated with
the compiler are responsible for making an object program into executable form.
 The compiler reports to its user the presence of errors in the source program.

1
 Figure1. 1: Major function of Compiler

♦ Source Program: - It is normally a program written in a high-level programming

language. It contains a set of rules, symbols, and special words used to construct a
computer program.
♦ Target Program: - It is normally the equivalent program in machine code. It contains the
binary representation of the instructions that the hardware of computer can perform.
♦ Error Message: - A message issued by the compiler due to detection of syntax errors in
the source program.
Features of Compiler
 Correctness
 Speed of compilation
 Preserve the correct meaning of the code
 The speed of the target code
 Recognize the legal or illegal program constructs
 Helps in code debugging
List of Compilers
1. Ada compilers 2. 5. C compilers
2. ALGOL compilers 6. C++ compilers
3. BASIC compilers 7. COBOL compilers
4. C# compilers 8. Java compilers

2|Page
1.1.1. Parts of Compilation

There are two parts to compilation:-

1) Analysis
2) Synthesis
► The analysis part breaks up the source program into constituent pieces and creates an intermediate representation of the source
program.
► The synthesis part constructs the desired target program from the intermediate representation. Of the two parts, synthesis requires
the most specialized techniques.
► During analysis, the operations implied by the source program are determined and recorded in a hierarchical structure called a
tree.
► Often, a special kind of tree called a syntax tree is used, in which each node represents an operation and the children of a node
represent the arguments of the operation.

Figure1. 2: Syntax Tree for Position: =initial rate*60

► Many software tools that manipulate source programs first perform some kind of analysis. Some examples of such tools are:
 Structure editor

3|Page
  Pretty printers
 Static checkers
 Interpreters

Structure Editor
► A structure editor takes as input a sequence of commands to build a source program.
► The structure editor not only performs the text-creation and modification functions of an ordinary text editor, but it also analyzes
the program text, putting an appropriate hierarchical structure on the source program.
► For example, it can check that the input is correctly formed, can supply keywords automatically (e-g.. when the user types while.
the editor supplies the matching do and reminds the user that a conditional must come between them), and can jump from a
begin or left parenthesis to its matching end or right parenthesis.

Pretty Printers
► A pretty printer analyzes a program and prints it in which a way that the structure of the program becomes clearly visible.
► For example, comments may appear in a special font, and statements may appear with an amount of indentation proportional to
the depth of their nesting in the hierarchical organization of the statements.

Static Checkers
► A static checker reads a program, analyzes it, and attempts to discover potential bugs without running the program.
► For example, a static checker may detect that parts of the source program can never be executed.
► It can catch logical errors such as trying to use a real variable as a pointer.

Interpreters
► Interpreter performs the operations implied by the source program.

4|Page
 ► For an assignment statement, for example, an interpreter might build a tree like Fig. 1.2, and then carry out the operations at the
nodes as it "walks" the tree.
► Interpreters are frequently used to execute command languages, since each operator executed in a command language is usually
an invocation of a complex routine such as an editor or compiler.
► The analysis portion in each of the following examples is similar to that of a conventional compiler.

1.1.2. Analysis of the Source Program

There are Analysis consists of three parts. These are:-

1) Linear Analysis:- is called lexical analysis or scanning. It is the process of reading a character from left-to-right and grouped
into tokens that are sequences of characters having a collective meaning.
2) Hierarchical Analysis:- is called as syntax analysis or parsing. In this analysis the characters or tokens are grouped
hierarchically into nested collections with collective meaning.
3) Semantic Analysis:- in which certain checks are performed to ensure that the components of a program fit together
meaningfully. i.e.; it check the source program for semantic errors and gathers type information for subsequent code generation
phase.

1.2. Phases of a Compiler

► A compiler operates in phases, each of which transforms the source program from one representation to another.
► A typical decomposition of a compiler is shown in Fig 1.2.
► The first three phases forming the bulk of the analysis portion of a compiler.
► Symbol table management and error handling, are shown interacting with the six phases of the compiler.

Symbol Table Management

5|Page
► An essential function of a compiler is to record the identifiers used in the source program and collect information about various
attributes of each identifier.
► These attributes may provide information about the storage allocated for an identifier, its type, its scope and, in the case of
procedure names, such things as the number and types of its arguments, the method of passing each argument and the type
returned.
► A symbol table is a data structure containing a record for each identifier, with fields for the attributes of the identifier. The data
structure allows us to find the record for each identifier quickly and to store or retrieve data from that record quickly.
► When an identifier in the source program is detected by the lexical analyzer, the identifier is entered into the symbol table.
► However, the attributes of an identifier cannot normally determined during lexical analysis. For example, in a Pascal declaration
like
var position, initial, rate: real;
► The type real is not known when position, initial, and rate are seen by the lexical analyzer.
► The remaining phases enter information about identifiers into the symbol table and then use this information in various ways.

6|Page
 Figure1. 3: Block Diagram of Phases of Compiler

Error Detection and Reporting

► Each phase can encounter errors. However, after detecting an error, a phase must deal with that error, so that compilation can
proceed, allowing further errors in the source program to be detected.
► The lexical phase can detect errors where the characters remaining in the input do not form any token of the language.
► Errors where the token stream violates the structure rules of the language are determined by the syntax analysis phase.

7|Page
 During semantic analysis the compiler tries to detect constructs that have the right syntactic structure but no meaning to the
operation involved.

1.2.1. The Analysis Phases of the Compiler

Lexical Analysis

► Lexical Analysis or Scanners reads the source program one character at a time, carving the source program into a sequence of
automatic units is called tokens.
► The lexical analysis phase reads the characters in the source program and groups them into a stream of tokens.
► Each token represents a logically cohesive sequence of characters, such as an identifier, a keyword (if, while, etc.), a punctuation
character, or a multi-character operator like :=.
► The character sequence forming a token is called the lexeme for the token.
► Certain tokens will be augmented by a "lexical value."
► The lexical analyzer not only generates a token, say id, but also enters the lexeme rate into the symbol table.
► Consider the above expression
Position:= initial + rate * 60

► The representation of the above expression after the lexical analysis is

id1 = id2 + id3 * 60

Syntax Analysis

► The second stage of translation is called syntax analysis or parsing. In this phase expressions, statements, declarations etc…
are identified by using the results of lexical analysis.
► Syntax analysis is aided by using techniques based on formal grammar of the programming language.

8|Page
 ► It groups token together into syntactic structures. (Fig.1.11a.. syntax tree)
► A typical data structure for the tree is shown in Fig. 1.11(b) in which an interior node is a record with a field for the operator and
two fields containing pointers to the records for the left and right children.
► A leaf is a record with two or more fields, one to identify the token at the leaf, and the others to record information about the
token.

Figure1. 4: The data structure in (b) is for the tree in (a)

Semantic Analysis

► An important component of semantic analysis is type checking. Here the compilers checks that each operator has operands that
are permitted by the source language specification.
► For example; many programming language definition require a compiler to report an error every time a real number is used to
index an array.
► However, the language specification may permit some operand coercions, for example, when a binary arithmetic operator is
applied to an integer and real, in this case, the compiler may need to convert the integer to a real.
9|Page
Intermediate Code Generation

► After syntax and semantic analysis, some compilers generates an explicit intermediate representation of the source program.
► An intermediate representation of the final machine language code is produced. This phase bridges the analysis and synthesis
phases of translation.
► This intermediate representation should have two important properties. It should be easy to produce and easy to translate into the
target program.
► The intermediate representation can have a variety of forms and one of the forms is called “Three address code”, which is like
the assembly language for a machine in which every memory location can act like a register.
► Three address code consists of a sequence of instructions, each of which has at most three operands.
► Three address code for the statement position : = initial + rate * 60 is
temp1:=int to real(60)
temp2:=id3*temp1
temp3:=id2*temp2
id1:=temp3
Inter mediate form has several properties.

► First, each three-address instruction has at most one operator in addition to the assignment. Thus, when generating these
instructions, the compiler has to decide on the order in which operations are to be done; the multiplication precedes the addition
in the source program of (1.1).
► Second, the compiler must generate a temporary name to hold the value computed by each instruction.
► Third, some "three address" instructions have fewer than three operands, e.g., the first and last instructions in (1.3).
Code Optimization

10 | P a g e
 ► The code optimization phase attempts to improve the intermediate code, so that the output faster running machine code and
takes less space.
► The above intermediate code is optimized like this,
temp1:=id3*60.0
id1:=id2+temp1
► int to real operation can be eliminated by the conversion of 60 integer in to real and temp3 is used only once, to transmit its
value to id1, so it can be eliminated.

Code Generation

► The final phase of the compiler is the generation of target code, consisting normally of relocatable machine code or assembly
code, Memory locations are selected for each of the variables used by the program.
► Then, intermediate instructions are each translated into a sequence of machine instructions that perform the same task.
► A crucial aspect is the assignment of variables to registers. For example, using registers 1and 2, the translation of the code of the
above code might become:
MOVF id3, R2
MULF #60.0, R2
MOF id2, R1
ADDF R2, R1
MOVF R1, id1
► The first and second operands of each instruction specify a source and destination, respectively. The F in each instruction tells us
that instructions deal with floating-point numbers.
► This code moves the contents of the address id3 into register 2, then multiplies it with the real constant 60.0

11 | P a g e
 ► The third instruction moves id2 into register 1 and adds to it the value previously computed in register 2. Finally, the value in
register 1 is moved into the address of id1.

Figure 1. 5: Source program Examples of each Phases

EXERCISE 1.1

12 | P a g e
 1. Write output of all the phases of compiler for following statements:
A. x=b-c*2
B. I=P*n*r/100
C. E=M * C**2

1.3. Computer Language Representation

Preprocessors
A preprocessor, generally considered as a part of compiler, is a tool that produces input for compilers. It deals with macro-processing,
augmentation; file inclusion, language extension, etc. They may perform the following functions:
1) Macro Processing: - A preprocessor may allow a user to define macros that are short hands for longer constructs.
2) File Inclusion: - A preprocessor may include header files into the program text. For example, the C preprocessor causes the
contents of the file <global.h> to replace the statement #include <global.h> when it processes a file containing this statement.
3) Rational Preprocessors:- These processors augment older languages with more modern flow-of-control and data-structuring
facilities. For example, such a preprocessor might provide the user with built-in macros for constructs like while-statements or if-
statements, where none exist in the programming language itself.
4) Language Extensions:- These preprocessors attempt to add capabilities to the language by what amounts to built-in macros, For
example. The language Equel is a database query language embedded in C.
► Statements beginning with ## are taken by the preprocessor to be database-access statements, unrelated to C, and are translated
into procedure calls on routines that perform the database access.
► Macro processors deal with two kinds of statement:-
 macro definition
 macro use

13 | P a g e
 ► Definitions are normally indicated by some unique character or keyword, like define or macro. They consist of a name for the
macro being defined and a body, forming its definition.
► The use of a macro consists of naming the macro and supplying actual parameters, that is values for its formal parameters. The
macro processor substitutes the actual parameters for the formal parameters in the body of the macro; the transformed body
then replaces the macro use itself.

Assemblers

► Some compilers produce assembly code that is passed to an assembler for further processing, other compilers perform the job of
the assembler, producing relocatable machine code that can be passed directly to the loader/link-editor.
► Assembly code is a mnemonic version of machine code, in which names are used instead of binary codes for operations, and
names are also given to memory addresses.
► A typical sequence of assembly instruction might be :
MOV a, R1
ADD #2, R1
MOV R1, b
► This code moves the contents of the address a in to register 1, then adds the constant 2 to it and finally stores the result in the
location named by b. Thus, it computes b: = a + 2.

Two Pass Assembly

► The simplest form of assembler makes two passes over the input, where a pass consists of reading an input file once. In the first
pass, all the identifiers that denote storage locations are found and stored in a symbol table.

14 | P a g e
► Identifiers are assigned storage locations as they are encountered for the first time, so after reading, the symbol table might contain
the entries shown in Figure. In that figure, we have assumed that a word, consisting of four bytes, is set aside for each identifier,
and that addresses are assigned starting from byte 0.
Symbol table

IDENTIFIER ADDRESS
a 0
b 4
► In the second pass, the assembler scans the input again. This time, it translates each operation code into the sequence of bits
representing that operation in machine language, and it translates each identifier representing a location into the address given for
that identifier in the symbol table.
► The output of the second pass is usually relocatable machine code, meaning that it can be loaded starting at any location L in
memory.

Loaders and Link-editors

► Usually, a program called a loader performs the two functions of loading and link-editing.
► The process of loading consists of taking relocatable machine code, altering the relocatable addresses, and placing the altered
instructions and data in memory at the proper locations.
► The link-editor allows us to make a single program from several files of relocatable machine code, these files may have been the
result of several different compilations, and one or more may be library files of routines provided by the system and available to
any program that needs them.

15 | P a g e
► If the files art to be used together in a useful way, there may be some external references, in which the code of one file refers to a
location in another file. This reference may be to a data location defined in one file and used in another, or it may be to the entry
point of a procedure that appears in the code for one file and is called from another file.
► The relocatable machine code file must retain the information in the symbol table for each data location or instruction label that is
referred to externally. If we do not know in advance what might be referred to, we in effect must include the entire assembler
symbol table as part of the relocatable machine code.

Figure1. 6: Language Processing System

1.3. Compiler Construction Tools

► In addition to these software development tools, other more specialized tool has been developed for helping implements various
phases of a compiler.
► Some general tools have been created for the automatic design of specific compiler components, these tools use specialized
languages for specifying and implementing the component, and many use algorithms that are quite sophisticated.

16 | P a g e
► The following is a list of some useful compiler construction tools:
1) Parser generators:- These produce syntax analyzers, normally from input that is based on a context-free grammar. In early
compilers, syntax analysis consumed not only a large fraction of the running time of a compiler, but a large fraction of the
intellectual effort of writing a compiler. This phase is now considered one of the easiest to implement. Many parser generators
utilize powerful parsing algorithms that are too complex to be carried out by hand.
2) Scanner generators:- These automatically generate lexical analyzers, normally from a specification based on regular expressions.
The basic organization of the resulting lexical analyzer is in effect a finite automaton.
3) Syntax-directed translation engines:- These produce collections of routines that walk the parse tree, such as intermediate code.
The basic idea is that one or more "translations" are associated with each node of the parse tree, and each translation is defined in
terms of translations at its neighbor nodes in the tree.
4) Automatic code generators:- Such a tool takes a collection of rules that define the translation of each operation of the
intermediate language into the machine language for the target machine. The rules must include sufficient detail that we can
handle the different possible access methods for data; e.g.. Variables may be in registers, in a fixed (static) location in memory, or
may be allocated a position on a stack.
The basic technique is "template matching." The intermediate code statements are replaced by "templates" that represent
sequences of machine instructions, in such a way that the assumptions about storage of variables match from template to template.
5) Data flow engines:- Much of the information needed to perform good code optimization involves "data-flow analysis," the
gathering of information about how values are transmitted from one part of a program to each other part. Different tasks of this
nature can be performed by essentially the same routine, with the user supplying details of the relationship between intermediate
code statements and the information being gathered.
Features of compiler construction tools:

17 | P a g e
 ► Lexical Analyzer Generator: This tool helps in generating the lexical analyzer or scanner of the compiler. It takes as
input a set of regular expressions that define the syntax of the language being compiled and produces a progra m that
reads the input source code and tokenizes it based on these regular expressions.
► Parser Generator: This tool helps in generating the parser of the compiler. It takes as input a context-free grammar that
defines the syntax of the language being compiled and produces a program that parses the input tokens and builds an
abstract syntax tree.
► Code Generation Tools: These tools help in generating the target code for the compiler. They take as input the abstract
syntax tree produced by the parser and produce code that can be executed on the target machine.
► Optimization Tools: These tools help in optimizing the generated code for efficiency and performance. They can
perform various optimizations such as dead code elimination, loop optimization, and register allocation.
► Debugging Tools: These tools help in debugging the compiler itself or the programs that are being compiled. They can
provide debugging information such as symbol tables, call stacks, and runtime errors.
► Profiling Tools: These tools help in profiling the compiler or the compiled code to identify performance bottlenecks and
optimize the code accordingly.
► Documentation Tools: These tools help in generating documentation for the compiler and the programming language
being compiled. They can generate documentation for the syntax, semantics, and usage of the language.
► Language Support: Compiler construction tools are designed to support a wide range of programming languages,
including high-level languages such as C++, Java, and Python, as well as low-level languages such as assembly language.
► Cross-Platform Support: Compiler construction tools may be designed to work on multiple platforms, such as
Windows, Mac, and Linux.
► User Interface: Some compiler construction tools come with a user interface that makes it easier for developers to work
with the compiler and its associated tools.

18 | P a g e
 CHAPTER TWO
LEXICAL ANALYSIS

Introduction
In this chapter, Lexical Analysis have been studied, understanding of lexical analysis and how lexical analysis works, and examples of lexical
analyzer, how to handle errors in the lexical phase , and how to convert NFA to DFA

After completing this chapter, the students will be able to:

 Understanding of the overview of lexical analysis, the role of lexical analyzer, and their issues of lexical analyzer
 Identify the basic terms of lexical analyzer:- tokens, lexemes, and pattern
 Identifies and understand the Specification and Recognition of Token, and formal definition of finite automata
 Analyze and develop lexical error and Lexical Analyzer Generator

2.1. Overview of Lexical Analysis

► Lexical analysis is the first phase of a compiler. It takes modified source code from language preprocessors that are written in
the form of sentences.
► The lexical analyzer breaks these syntaxes into a series of tokens, by removing any whitespace or comments in the source
code. If the lexical analyzer finds a token invalid, it generates an error.
► The lexical analyzer works closely with the syntax analyzer. It reads character streams from the source code, checks for legal
tokens, and passes the data to the syntax analyzer when it demands
► To identify the tokens we need some method of describing the possible tokens that can appear in the input stream. For this
purpose we introduce regular expression, a notation that can be used to describe essentially all the tokens of programming
language.
19 | P a g e
 ► Secondly, having decided what the tokens are, we need some mechanism to recognize these in the input stream. This is done
by the token recognizers, which are designed using transition diagrams and finite automata.
2.1.1. The Role of the Lexical Analyzer
► The lexical analyzer is the first phase of a compiler. Its main task is to read the input characters, group them into lexemes and
produce as output a sequence of tokens that the parser uses for syntax analysis. It is common for the lexical analyzer to interact
with the symbol table as well.
► When the lexical analyzer discovers a lexeme constituting an identifier, it needs to enter that lexeme into the symbol table. This
process is shown in the following figure.
► Upon receiving a "Get next token" command from the parser, the lexical analyzer reads input characters until it can identify the
next token.

Figure 2. 1: Interaction of Lexical Analyzer with Parser

► When lexical analyzer identifies the first token it will send it to the parser, the parser receives the token and calls the lexical
analyzer to send next token by issuing the getNextToken() command. This Process continues until the lexical analyzer identifies
all the tokens. During this process the lexical analyzer will neglect or discard the white spaces and comment lines.

20 | P a g e
Secondary Tasks

► One such task is stripping out from the source program comments and white space in the form of blank, tab, and newline
characters.
Another is correlating error messages from the compiler with the source program. For example, the lexical analyzer may keep track of
the number of newline characters seen, so that a line number can be associated with an error message.

2.1.2. Issues in Lexical Analysis

► There are a number of reasons why the analysis portion of a compiler is normally separated into lexical analysis and parsing
(syntax analysis) phases.
 Simplicity of design:- The separation of lexical analysis from syntax analysis often allows us to simplify one or the other of
these phases. For example, a parser embodying the conventions for comments and white space is significantly more complex
than one that can assume comments and white space have already been removed by a lexical analyzer.
 Compiler efficiency is improved:- A separate lexical analyzer allows us to construct a specialized and potentially more
efficient processor for the task. A large amount of time is spent reading the source program and partitioning it into tokens.
Special buffering techniques for reading input characters and processing tokens can significantly speed up the performance of
a compiler.
 Compiler portability is enhanced:- Input alphabet peculiarities and other device-specific anomalies can be restricted to the
lexical analyzer.

2.1.3. Tokens, Patterns, Lexemes

Token:
► A lexical token is a sequence of characters that can be treated as a unit in the grammar of the programming languages.

21 | P a g e
 Example of tokens:- keywords, operators, identifiers, constants, literal strings, and punctuation symbols such as parentheses,
commas, and semicolons.
► In programming, a token is the smallest unit of meaningful data; it may be an identifier, keyword, operator, or symbol.
► A token represents a series or sequence of characters that cannot be decomposed further.
► Tokens may be divided into three categories:
1. Terminal Symbols (TRM) : Keywords and operators.
2. Literals (LIT) : Values like numbers and strings.
3. Identifiers (IDN) : Names defined by the user.
Example 1: In c programming language how many total number of tokes?
int a=2; // input source code

Tokens
int (keyword), a(identifier), =(operator), 2(constant) and ;(punctuation-semicolon)
Total number of tokens = 5

Pattern:-
► There is a set of strings in the input for which the same token is produced as output. This set of strings is described by a
rule called a pattern associated with the token. The pattern is said to match each string in the set.
► A pattern is a description of the form that the lexemes of a token may take [or match]. In the case of a keyword as a
token, the pattern is just the sequence of characters that form the keyword. For identifiers and some other tokens, the
pattern is a more complex structure that is matched by many strings.
E.g. The pattern for the identifier token id, is id-> letter(letter/digit)*
► A pattern is a rule describing the set of lexemes that can represent a particular token in source program.

22 | P a g e
 Lexeme:-
► A lexeme is a sequence of characters in the source program that is matched by the pattern for a token and is identified by
the lexical analyzer as an instance of that token.
► Lexemes: - are the specific character strings that make up a token.
For example, in the Pascal statement, const pi = 3.1416
The substring pi is a lexeme for the token "identifier".
 For example: abc and 123
 main is lexeme of type identifier(token)
 (,),{,} are lexemes of type punctuation(token)

TOKEN INFORMAL DESCRIPTION SAMPLE LEXEMES

If Character i,f if
Else Character e,l,s,e else
Comparison <or>or<=or >= or == or != <=,>=, !=
Id Letter followed by letters and digits Pi,score,D2
Number any numeric constant 3.14159,0.66
Literal Anything but “,surrounded by ” “‟‟s “core dumped”
Example: total= sum+35 Lexemes for the above c language
Lexemes for identifier: total, sum
Lexemes for operator: =,+
Lexemes for constant: 35

23 | P a g e
 Tokens for the above C language
Total identifier 1
= operator 1
Sum identifier 2 tokens
+ operator2
35 constant
Exercises
Q1. Identify the numbers of tokens from c programming language source code and how many total number of tokens for
given c language code?
int main() {
//printf()sends the string inside quotation to the standard output (the display)
printf(“Welcome to Computer Science!”);
return 0;
}
Q2. C source language expression: - W=x+y; write output of lexical analyzer

2.2. Specification and Recognition of Token

► In compiler design, tokens are the smallest individual units of a program that are meaningful to the compiler. They are the
building blocks of any programming language and include keywords, identifiers, operators, and punctuations. The process
of converting a program into a stream of tokens is known as lexical analysis.

Types of Tokens

24 | P a g e
 ► Keywords: Reserved words that have a special meaning to the compiler and cannot be used for naming variables or
functions. Examples include int, char,[Link].
► Identifiers: Names given to various components in the program, such as variables and functions. Keywords cannot be used
as identifiers.
► Operators: Symbols used to perform operations in a programming language, such as +, -, *, /.
► Punctuations: Special symbols that separate different code elements, such as commas, semicolons, and braces.

2.2.1. Specification of Tokens

► Let us understand how the language theory undertakes the following terms:

Alphabets

 Any finite set symbols

 {0,1} is a set of binary alphabets,
 {0123456789ABCDEF} is a set of Hexadecimal alphabets,
 {a-z, A-Z} is a set of English language alphabets.
► In compiler design, tokens are specified using three main methods: Strings, Languages, and Regular Expressions.
Strings

► Any finite sequence of alphabets (characters) is called a string.

► Length of the string is the total number of occurrence of alphabets, e.g., the length of the string Compiler is 8 and is
denoted by |compiler| = 8.
► A string having no alphabets, i.e. a string of zero length is known as an empty string and is denoted by (epsilon).

Operations on strings include:

25 | P a g e
  Prefix: A string obtained by removing zero or more characters from the end.
 Suffix: A string obtained by removing zero or more characters from the beginning.
 Substring: A string obtained by removing any prefixes and suffixes.
 Subsequence: A string obtained by eliminating zero or more symbols, not necessarily consecutive.
 Concatenation: The addition of two strings.

Special symbols
♦ A typical high-level language contains the following symbols:-

Arithmetic Symbols Addition(+), Subtraction(-), Modulo(%), Multiplication(*),

Division(/)
Punctuation Comma(,), Semicolon(;), Dot(.), Arrow(->)
Assignment =
Special Assignment +=, /=, *=, -=
Comparison ==, !=, , >=
Preprocessor #
Location Specifier &
Logical &, &&, |, ||, !
Shift Operator >>, >>>,

Languages

 A language is a finite set of strings over some symbols or alphabets.

26 | P a g e
 Operations on languages include:

1. Union:
► Combines two languages by including all strings from both.
► Union of two languages L and M is written as L U M = {s | s is in L or s is in M}
2. Concatenation:
► Links strings from one language to all strings of another.
► Concatenation of two languages L and M is written as LM = {st | s is in L and t is in M}
3. Kleene Closure:
► Provides a set of all strings obtained by concatenating a language zero or more times.
► The Kleene Closure of a language L is written as L* = Zero or more occurrence of language L.
4. Positive Closure:
► Provides a set of all strings obtained by concatenating a language one or more times

Regular Expressions

► Regular expressions are strings of characters that define a searching pattern. They are used to specify tokens in a
programming language. Common symbols in regular expressions include:
 Asterisk (*): Indicates that the preceding symbol can be repeated any number of times.
 Plus (+): Indicates that the preceding symbol can be repeated one or more times.
 Wildcard (.): Can be replaced by any character.
 Character Class: Represents multiple characters, such as [a-z]
► The lexical analyzer needs to scan and identify only a finite set of valid string/token/lexeme that belong to the language in
hand. It searches for the pattern defined by the language rules.
27 | P a g e
 ► Regular expressions have the capability to express finite languages by defining a pattern for finite strings of symbols.
► The grammar defined by regular expressions is known as regular grammar.
► The language defined by regular grammar is known as regular language.
Notations

If r and s are regular expressions denoting the languages L(r) and L(s), then

♦ Union : (r)|(s) is a regular expression denoting L(r) U L(s)

♦ Concatenation : (r)(s) is a regular expression denoting L(r)L(s)
♦ Kleene closure : (r)* is a regular expression denoting (L(r))*
♦ (r) is a regular expression denoting L(r)

Importance of Token Specification

► The specification of tokens is crucial in compiler design as it helps in the accurate parsing and interpretation of code.
► Tokens, patterns, and lexemes represent the basic elements of any programming language, aiding in breaking down and
understanding the code
► Understanding the specification of tokens ensures that the code is parsed correctly and that valid sequences for tokens are
predefined, helping in the efficient analysis and compilation of programs

2.2.2. Recognition of Tokens

► Token recognition is the process of breaking down source code into meaningful units (tokens) for further processing
in a compiler.
► In programming, token recognition is part of the lexical analysis phase, where a scanner or tokenizer breaks down the
source code into tokens such as keywords, identifiers, operators, and literals.
28 | P a g e
 ► In compiler design, token recognition (also known as lexical analysis) is the process of breaking down the source code
into tokens, which are the smallest meaningful units of the programming language.
► It addresses the question of how to recognize them

Key Concepts in Token Recognition

1. Tokens: These are the basic building blocks of a program. Examples include:
 Keywords (e.g., if, for, while)
 Identifiers (e.g., variable names, function names)
 Literals (e.g., numbers, strings, characters)
 Operators (e.g., +, -, =, ==)
 Punctuation (e.g., commas, semicolons, braces)
2. Lexical Analyzer (Scanner):
 The component of the compiler responsible for token recognition.
 It reads the source code character by character and groups them into tokens.
 It also handles tasks like removing whitespace, comments, and other irrelevant characters.
3. Regular Expressions:
 Used to define patterns that match different types of tokens.
 The lexical analyzer uses these patterns to identify and classify tokens.
4. Token Stream:
 After tokenization, the compiler receives a sequence of tokens, which is then passed to the next phase (syntax analysis).

Purpose of Token Recognition:

29 | P a g e
  To convert the raw source code into a structured format (tokens) that can be processed by the compiler.
 To detect syntax errors early in the compilation process.
 To provide a common interface for the rest of the compiler (e.g., syntax analysis, semantic analysis, code generation).

Example

Consider the source code:

int main() {
int x = 10;
return 0;
}
The lexical analyzer would break this into the following tokens: int, main, (, ), {, int, x, =, 10, ;, return, 0, ;, }

2.3. Formal definition of a Finite Automaton

 An automaton can be represented by a 5-tuple (Q, ∑, δ, q0, F), where
 Q is a finite set of states.
 ∑ is a finite set of symbols, called the alphabet of the automaton.
 δ is the transition function.
 q0 is the initial state from where any input is processed (q0 ∈ Q).
 F is a set of final state/states of Q (F ⊆ Q).
 Regular expressions = Specification
 Finite automata = Implementation
 Languages: “A language is a collection of sentences of finite length all constructed from a finite alphabet of symbols”
30 | P a g e
  Example − If the language takes all possible strings of length 2 over ∑ = {a, b}, then L = { ab, aa, ba, bb }
 Grammars: “A grammar can be regarded as a device that enumerates the sentences of a language”.

Figure 2. 2:Finite Automata State Graph

2.3.1. NFA to DFA Conversion

► NFA to DFA Conversion in Compiler Design refers to the process of converting a Non-deterministic Finite Automaton
(NFA) into a Deterministic Finite Automaton (DFA).
► This is a key step in lexical analysis (token recognition) in compiler design, where the scanner (or lexical analyzer) uses a finite
automaton to recognize patterns in the input source code.

Steps for converting NFA to DFA:

Step 1: Convert the given NFA to its equivalent transition table:

31 | P a g e
  To convert the NFA to its equivalent transition table, we need to list all the states, input symbols, and the transition rules. The
transition rules are represented in the form of a matrix, where the rows represent the current state, the columns represent the
input symbol, and the cells represent the next state.
Step 2: Create the DFA‟s start state:

 The DFA‟s start state is the set of all possible starting states in the NFA. This set is called the “epsilon closure” of the NFA‟s
start state. The epsilon closure is the set of all states that can be reached from the start state by following epsilon (λ) transitions.
Step 3: Create the DFA‟s transition table:

 The DFA‟s transition table is similar to the NFA‟s transition table, but instead of individual states, the rows and columns
represent sets of states. For each input symbol, the corresponding cell in the transition table contains the epsilon closure of the
set of states obtained by following the transition rules in the NFA‟s transition table.
Step 4: Create the DFA‟s final states:

 The DFA‟s final states are the sets of states that contain at least one final state from the NFA.
Step 5: Simplify the DFA:

 The DFA obtained in the previous steps may contain unnecessary states and transitions. To simplify the DFA, we can use
the following techniques:
 Remove unreachable states: States that cannot be reached from the start state can be removed from the DFA.
 Remove dead states: States that cannot lead to a final state can be removed from the DFA.
 Merge equivalent states: States that have the same transition rules for all input symbols can be merged into a single state.
Step 6: Repeat steps 3-5 until no further simplification is possible:

32 | P a g e
  After simplifying the DFA, we repeat steps 3-5 until no further simplification is possible. The final DFA obtained is the
minimized DFA equivalent to the given NFA.
example1: Convert the given NFA to DFA.

 Solution: For the given transition diagram we will first construct the transition table.

 Now we will obtain δ' transition for state q0.

 The δ' transition for state q1 is obtained as:

33 | P a g e
  Now we will obtain δ' transition on [q0, q1].

 Similarly,

 As in the given NFA, q1 is a final state, then in DFA wherever, q1 exists that state becomes a final state. Hence in the DFA,
final states are [q1] and [q0, q1]. Therefore set of final states F = {[q1], [q0, q1]}.
 The transition table for the constructed DFA will be:

34 | P a g e
  The Transition diagram will be:

 Even we can change the name of the states of DFA.

 Suppose


 With these new names the DFA will be as follows:

35 | P a g e
2.4. Lexical Error
► Lexical errors are the errors thrown by the lexer when unable to continue.
► Which means that there‟s no way to recognise a lexeme as a valid token for you lexer? Syntax errors, on the other side, will be
thrown by your scanner when a given set of already recognized valid tokens don't match any of the right sides of your grammar
rules.
► If the string fi is encountered in a C program for the first time in the context
 fi (a==b)
► "Panic mode" recovery will be taken that delete successive characters from the remaining input until the lexical analyzer can
find a well-formed token.
► Other possible error-recovery actions are:
 Deleting an extraneous character e.g printff-> printf
 Inserting a missing character in to the remaining input e.g prinf->insert t = printf
 Replacing an incorrect character by a correct character e.g. frintf-> printf
 Transposing two adjacent characters. e.g. rpintf-> printf

2.5. Lexical Analyzer Generator

► Creating a lexical analyzer with Lex:
 First, a specification of a lexical analyzer is prepared by creating a program lex.l in the Lex language.
 Then, lex.l is run through the Lex compiler to produce a C program [Link].c.
 Finally, [Link].c is run through the C compiler to produce an object program [Link], which is the lexical analyzer that transforms
an input stream into a sequence of tokens.

36 | P a g e
 Lex Specification
► A Lex program consists of three parts:
{ definitions } %%
{ rules }
%%
{user subroutines }
 Definitions include declarations of variables, constants, and regular definitions
 Rules are statements of the form p1 {action1}p2 {action2} … pn {action}
 Where pi is regular expression and actioni describes what action the lexical analyzer should take when pattern pi
matches a lexeme. Actions are written in C code.
 User subroutines are auxiliary procedures needed by the actions. These can be compiled separately and loaded with the
lexical analyzer.

37 | P a g e
 CHAPTER THREE
SYNTAX ANALYSIS
After completing this chapter, the students will be able to:

 Understanding of basic concepts of syntax analysis

 Develop how syntax analyzer works, and examples of syntax analyzer
 Identify and Evaluate difference between syntax and parse tree
 Understanding of types of parsing, and how to handle errors recovery in the syntax phase

3.1. Overview of Syntax Analysis

In this chapter, we shall learn the basic concepts used in the construction of a parser. Syntax analysis or parsing is the second phase of
a compiler. We have seen that a lexical analyzer can identify tokens with the help of regular expressions and pattern rules. But a
lexical analyzer cannot check the syntax of a given sentence due to the limitations of the regular expressions. Regular expressions
cannot check balancing tokens, such as parenthesis. Therefore, this phase uses context-free grammar (CFG), which is recognized by
push-down automata.
CFG, on the other hand, is a superset of Regular Grammar, as depicted below:

38 | P a g e
 Figure 3. 1: CFG and RE Diagram

► It implies that every Regular Grammar is also context-free, but there exists some problems, which are beyond the scope of Regular
Grammar.
► CFG is a helpful tool in describing the syntax of programming languages.

3.1.1. Role of a Parser

► Syntax Analyzer is also known as Parser.
► Syntax analysis is the second phase of a compiler.
► As we see in chapter two, a lexical analyzer can identify tokens with the help of regular expressions and patterns or rules.
► As the second phase, a syntax analyzer or parser takes the input from a lexical analyzer in the form of token streams.
► The parser analyzes the source code (token stream) against the production rules to detect any errors in the code.

39 | P a g e
 Figure 3. 2: Position of parser in compiler model
► Parser obtains a string of token from the lexical analyzer and reports syntax error if any otherwise generates syntax tree. In this way, the
parser accomplishes two tasks,
1. parsing the code and looking for errors and
2. Generates a parse tree as the output of the phase.

[Link]. Context-Free Grammar (CFG)

► In compilation, the parser obtains a string of tokens from the lexical analyzer, and expected to parse the whole code even if
some errors exist in the program.
► A lexical analyzer cannot check the syntax of the given sentence due to the limitations of the regular expressions.
► Regular expression cannot check balancing tokens, such as parenthesis.
► Therefore, the syntax analysis phase uses Context-Free Grammar (CFG), which is recognized by push-down automata.
► The syntax of a language is specified by a context-free grammar (CFG).
► CFG is a helpful tool in describing the syntax of programming languages.
► The rules in a CFG are mostly recursive.

40 | P a g e
 ► A syntax analyzer checks whether a given program satisfies the rules implied by a CFG or not.
► If it satisfies, the syntax analyzer creates a parse tree for the given program.
► A Context-Free Grammar is a quadruple that consists of terminals, non-terminals, start symbol and productions.
► A context-free grammar has four components; G= {V, €, P, S}
1. Non-terminals (V): are a set of syntactic variables that defines set of strings.
 They are represented by Capital letters and they can be further derivate.
2. Terminals Symbols (€): are the basic symbols from which strings are formed, also set of tokens.
 Terminals are represented by small letters and they don‟t have further derivation.
3. Production (P): is a set of production of a grammar specify the manner in which the terminals and non-terminals can be
combined to form strings.
► Each production consists of three things:-
i. a non-terminals (called left side of the production)
ii. an arrow, and
iii. a sequence of tokens with non-terminals (right side of the production)
4. Start symbols(S): is one of the non-terminals from where the production begins.
Example1
exprexpr op expr
expr(expr)
id,+,-*,/,(,) are Terminals
expr-expr expr,op,are non-terminals
exprid
expr is the start symbol
op+
op- Each line is production

41 | P a g e
 op*
op/
Class activity
1. The given grammar is CFG or not
A. EaB
B. a bSa
C. SbSa
D. aba
2. Distinguish the following CFG compononts: as Production, terminals, non-terminals and start symbol.

II. S AaAb
Aa
Bb
III. EE+E
E( E*E)
E id

Notational Conventions

To avoid always having to state that "these are the terminals," "these are the non-terminals," and so on, the following notational conventions for
grammars will be used throughout the remainder of this book.

1) These symbols are terminals:

(a) Lowercase letters early in the alphabet, such as a, b, c.
(b) Operator symbols such as +, *, and so on.
(c) Punctuation symbols such as parentheses, comma, and so on.
42 | P a g e
 (d) The digits 0, 1, . . . , 9.
(e) Boldface strings such as id or if, each of which represents a single terminal symbol.
2) These symbols are non-terminals:
(a) Uppercase letters early in the alphabet, such as A, B, C.
(b) The letter S, which, when it appears, is usually the start symbol.
(c) Lowercase, italic names such as expr or stmt.
(d) When discussing programming constructs, uppercase letters may be used to represent non-terminals for the constructs. For example, non-
terminals for expressions, terms, and factors are often represented by E, T, and F, respectively.
3) Uppercase letters late in the alphabet, such as X, Y, Z, represent grammar symbols; that is, either non-terminals or terminals.
4) Lowercase letters late in the alphabet, chiefly u, v, . . . , x, represent (possibly empty) strings of terminals.
5) Lowercase Greek letters, σ, β, γ for example, represent (possibly empty) strings of grammar symbols. Thus, a generic production can be
written as A σ, where A is the head and σ the body.
6) A set of productions A σ 1, A σ2 , ...,A σk with a common head A (call them A-productions), may be written A σ 1| σ2|

σ2|...|σk. Call σ1, σ2, …, σk the alternatives for A.

7) Unless stated otherwise, the head of the first production is the start symbol.
Example: let us we take the problem of palindrome language; L= {w | w= wR},

This language cannot be described by means of regular expression, because it is not regular language, but it can be described by means of CFG, as
illustrated below:

G= {V, €, P, S}; where G –is a grammar,

 V= {Q, Z, N}, which is set of non-terminals

 €= {0, 1}, which is set of terminals
 P= {Q Z | Q N |Q €|Z 0Q0 | N 1Q1}, which is set of production

43 | P a g e
  S= {Q}, which is start symbol
This grammar describes palindrome language, such as: 1001. 11100111, 00100, 1010101, 11111, etc.

3.3. Syntax Tree versus Parse Tree

► Syntax tree
 It is a variant of a parse tree in which each leaves node represents an operand and each interior nodes represents an
operator.
 It represents the abstract syntax tree of a program.
 Syntax tree contains only meaningful information.
► A parse tree
 It may be viewed as a graphical representation for a derivation that filters out the choice regarding replacement order.
 Each interior nodes of a parse tree is labeled by some non-terminals A and that the leaves of the node are labeled
from left to right by symbols in the right side of the production by which this A was replaced in the derivation.
 The leaves of the parse tree are terminal symbols.
 It contains unusable information also.

44 | P a g e
 Grammar: E E * E | E + E | id
Grammar: E E * E | E + E | id
String: id + id * id or a + b* c
String: id + id * id or a + b* c
E
+

id E * E
*

id id E + E id

id id

Figure 3. 3: Example of Syntax and Parse Tree

► A parse tree is the graphical representation of the structure of a sentence according to its grammar.
► Parsing is performed at the Syntax Analysis phase where a streams of tokens is taken as input from the Lexical Analysis and parser
produces the parse tree for the tokens against the syntax error.
► The concept of parsing is basically address various concepts such as; Derivation, Parse tree, Ambiguity, Left recursion.

3.3.1. Derivation
► The construction of a parse tree can be made precise by taking a derivational view, in which productions are treated as
rewriting rules.
► Beginning with the start symbol, each rewriting step replaces a nonterminal by the body of one of its productions.
► This derivational view corresponds to the top-down construction of a parse tree, but the precision afforded by derivations will
be especially helpful when bottom-up parsing.

45 | P a g e
 ► A derivation is basically a sequence of production rules, in order to get the input string. During parsing, we take two decisions
for some sentential form of input. Deciding the non-terminal which is to be replaced and deciding the production rules, by
which the non-terminal will be replaced.
► Derivation means to replace a non-terminal by the body of its production. It is used to find whether the string belongs to a
given grammar or not.
► There are two types of derivations are leftmost derivation and rightmost derivation.
1. Leftmost Derivation

A derivation of a string in a grammar G is a left most derivation if at every step the left most non-terminal is replaced. Here, the sentential form of
an input is scanned and replaced from left to right. Sentential form derived from left-most derivation is called a left-sentential form.

2. Rightmost Derivation

A derivation of a string in a grammar G is a right most derivation if at every step the right most non-terminal is replaced. It is all called canonical
derivation. Here, we scan and replace the input with production rules, from right to left. Sentential form derived from right-most derivation is
called right-sentential form.

Example: Consider the following production rules:

EE+E
E E+E
E id
For the input string: id + id * id
The left-most derivation is:
E E*E
E E+E*E
Eid+E*E

46 | P a g e
 Eid+id*E
Eid+id*id
The right-most derivation is:
EE+E
E E+E*E
EE+E*id
EE+id*id
E id+id*id
N.B:

 In left-most derivation, the left-most side non-terminal is always processed first; whereas
 In right-most derivation, the right-most side non-terminal is always processed first.

3.3.2. Parse Tree

► A parse tree is a graphical representation of a derivation sequence of a sentential form.
► In a 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.
► A parse tree depicts associativity and precedence of operators.
► The deepest sub-tree is traversed first, therefore the operator in that sub-tree gets precedence over the operator which is in the parent
nodes.
► N.B. Parse tree is also convenient to see how strings are derived from the start symbol. The start symbol of the derivation becomes the
root of the parse tree. All leaf nodes are terminals and all interior nodes are non-terminals.
47 | P a g e
Example: let us take the left-most derivation of given input string; a + b * c and draw the parse tree. Assume the production rule E E + E | E *
E | id.

The left-most derivation is a + b * c is

E E*E Step1: E * E E Step2: E * E + E E

E E+E *E
E id + E * E
E id + id * E E * E E * E
E id + id * id
E + E
Step3: id * E + E Step4: id * id + E Step5: id * id + id
E E E
E * E
E * E E * E
E + E
id id E + E id
E + E
id id
id

3.3.3. Ambiguity
 A grammar that produces more than one parse tree for some sentence is said to be ambiguous grammar.
 Put another way, an ambiguous grammar is one that produces more than one leftmost derivation or more than one rightmost derivation for
the same sentence.
 A grammar G is said to be ambiguous if it has more than one parse tree (either left or right derivation) for at least one string.
 Example: using the production rule, generates two parse trees, for the string id – id + id

48 | P a g e
E E+E E E
E E-E
E id E + E E - E

id E + E
E - E id

id id
id id

 Here, two leftmost derivation for string a +a * a is possible hence, above grammar is ambiguous.
 The language generated by an ambiguous grammar is known as inherently ambiguous.
 There is no any method to detect and remove ambiguity automatically, it is not good.

49 | P a g e
  Ambiguity can be removed by either re-writing the whole grammar without ambiguity, or by setting and following associativity and
precedence constraints.
I. Associativity
► If an operand has operators on both sides, the side on which the operator takes this operand is decided by the associativity of those
operators.
► If the operation is left-associative, then the operand will be taken by the left operator or if the operation is right-associative, the right
operator will take the operand.
► The operations like Addition, Multiplication, Subtraction, and Division are left associative.
► For example; if the expression contains: id op id op id it will be evaluated as: (id op id) op id i.e.; (id + id) +id. Operations like
Exponentiation are right associative.
II. Precedence
► If two different operators share a common operand, the precedence of operators decides which will take the operand.
► For example, 2 +3 * 4 have two different parse tree; (2+3)*4 and 2+ (3*4).
► By setting precedence among operators, this problem can easily removed. i.e.; mathematically *(multiplication) has precedence over +
(addition), so the expression 2+3*4 will always be interpreted as: 2+ (3*4).

3.3.4. Eliminating Left Recursion

► A grammar is said to be left recursive if it has a non-terminal A such that there is a derivation A=>Aα for some string α.
► Top-down parsing methods cannot handle left-recursive grammars. Hence, left recursion can be eliminated as follows:
Aσ |β;
► If there is a production A Aσ |β it can be replaced with a sequence of two productions
A βA‟
A‟σ A‟|ɛ
Without changing the set of strings derivable from A.

50 | P a g e
 ► A grammar becomes left-recursive if it has any non-terminal „A‟ whose derivation contains „A‟ itself as the left-most symbol.
► Left-recursive grammar is considered as a problem for top-down parser.
► Top-down parsers start parsing from the start symbol, which in itself is non-terminal.
► So, when the parser encounters the same non-terminal in its derivation, it becomes hard for it to judge when to stop parsing the left non-
terminal and it goes into an infinite loop.
Example: A => Aσ |β; this is an example of immediate left recursion, where A is any non-terminal symbol and σ represents a string of non-
terminals.

S => Aσ |β A => Sd; this is an example of indirect-left recursion.

► A top-down parser will first parse the A, in-turn A will produce a string consisting of A itself and the parser may go into a loop forever.
This is called left recursion problem.

A Aσ
Aσ

A σ
A Aσ Aσ

A σ
A Aσ
Aσ

A σ

Figure 3. 4: left recursion

51 | P a g e
 3.3.5. Left Factoring
► Left factoring is a grammar of transformations in which the common parts of two productions are isolated into a single production. It is
suitable for predictive parsing.
► It is a grammar transformation that is useful for producing a grammar suitable for predictive parsing.
► When it is not clear which of two alternative productions to use to expand a non-terminal A, we can rewrite the A-productions to defer the
decision until we have seen enough of the input to make the right choice.
► If there is any production A → αβ1 | αβ2, it can be rewritten as
A → αA‟
A‟ → β1 | β2
► Consider the grammar, G: S → iEtS | iEtSeS | a
E→b
Left factored, this grammar becomes
S → iEtSS‟ | a
S‟ → eS | ɛ
E→b

Process of Eliminating Left Factoring

► Any production of the form A → αβ1 | αβ2 (where α is common) can be replaced the following productions,
A → αA‟

A‟ → β1 | β2
► Left factoring is required because it is difficult to decide which production is to select either αβ1 | αβ2 to expand A. In left factoring, we
defer this decision by expanding A to A‟ until we have seen enough input to make the right choice.
For example, consider CFG,

52 | P a g e
 S → iEtS | iEtSeS
E→b
► In this grammar, the common part is iEtS. Then after elimination of left factoring, the productions are
S → iEtSS‟
S‟ → eS | ɛ
E→b

3.4. Regular Expression Versus Context Free Grammar

Regular Expression Context Free Grammar
It is used to describe the tokens of programming It consists of a quadruple where S → start symbol, P
languages. → production, T → terminal, V → variable or non-
terminal.
It is used to check whether the given input is valid or It is used to check whether the given input is valid or
not using transition diagram. not using derivation.
The transition diagram has set of states and edges. The context-free grammar has set of productions.
It has no start symbol. It has start symbol.
It is useful for describing the structure of lexical It is useful in describing nested structures such as
constructs such as identifiers, constants, keywords, balanced parentheses, matching begin-end‟s and so
and so forth. on.
 The lexical rules of a language are simple and RE is used to describe them.
 Regular expressions provide a more concise and easier to understand notation for tokens than grammars.
 Efficient lexical analyzers can be constructed automatically from RE than from grammars.

53 | P a g e
 Separating the syntactic structure of a language into lexical and non-lexical parts provides a convenient way of modularizing the front end into
two manageable-sized components.

3.5. Parsing

► Parsing is the activity of checking whether a string of symbols is in the language of some grammar, where this string is usually the stream
of tokens produced by the lexical analyzer. If the string is in the grammar, we want a parse tree, and if it is not, we hope for some kind of
error message explaining why not.
► Parsing is a technique that takes input string and produces output either a parse tree, if string is valid sentence of grammar, or an error
message indicating that string is not a valid.
► It is the process of analyzing a continuous stream of input in order to determine its grammatical structure with respect to a given formal
grammar.
► Parser is that phase of the compiler which takes tokens as input and with the help of CFG, converts it into the corresponding parse tree.
► Parser is also called Syntax Analyzer.

TYPES OF PARSING

There are two main kinds of parsing in use, named for the way they build the parse trees:-

1) Top down parsing:- A top-down parser attempts to construct a tree from the root, applying productions forward to expand non-terminals into
strings of symbols. In top down parsing parser build parse tree from top to bottom.
Example: LL Parsers

► A top down parsers starts at the root of the parse tree and grows towards leaves. At each node, the parser picks a production and tries to
match the input. However, the parser may pick the wrong production in which case it will need to backtrack. Some grammars are
backtrack- free.

54 | P a g e
 ► Top down parser generates parse tree for the given input string with the help of grammar productions by expanding the non-terminals, i.e.;
it starts from the start symbol and ends on the terminals. It uses leftmost derivation.
2) Bottom up parsing:- A bottom-up parser builds the tree starting with the leaves, using productions in reverse to identify strings of symbols
that can be grouped together. In bottom up parser starts from leaves and work up to the root.
Example: LR Parsers

► A bottom up parser starts at the leaves and grows toward root of the parse tree. As input is consumed, the parser encodes possibilities in an
internal state. The bottom- up parser starts in a state valid for legal first tokens. Bottom-up parsers handle a large class of grammars.
Bottom up parser generates the parse tree for the given input string with the help of grammar productions by compressing the non-
terminals, i.e.; it start from the terminals and ends in the start symbol. It uses reverse of rightmost derivation.
► In both cases the construction of derivation is directed by scanning the input sequence from left to right, one symbol at a time.

55 | P a g e
 Figure 3. 5: Types of parsing

Figure 3. 6: Example of Top down and Bottom up approach

3.5.1 Top-Down Parsing

► It can be viewed as an attempt to find a left-most derivation for an input string or an attempt to construct a parse tree for the input starting
from the root to the leaves.

56 | P a g e
 ► Top-down parsing can be viewed as the problem of constructing a parse tree for the given input string, starting from the root and creating
the nodes of the parse tree in preorder (depth-first left to right).
► Equivalently, top-down parsing can be viewed as finding a leftmost derivation for an input string.

These parsing techniques work on the following principle:-

(1) The parser scans the input from left to right and identifies that the derivation is left most or right most.
(2) The parser makes use of production rules for choosing the appropriate derivation. The different parsing techniques use different approaches in
selecting the appropriate rules for derivation. And finally a parse tree is constructed.
Example: The sequence of parse trees for the input id + id * id is a top-down parse according to grammar:

ETE‟

E‟+TE‟ |ɛ

TFT‟

T‟*FT‟ |ɛ

F (E) |id

This sequence of trees corresponds to a leftmost derivation of the input.

57 | P a g e
 Figure 3. 7: Top-down parse for id + id * id
58 | P a g e
[Link]. Predictive Parsing
► Predictive parsing is a special case of recursive descent parsing where no backtracking is required.
► It is possible to build a non-recursive predictive parser by maintaining a stack explicitly, rather than implicitly via recursive calls.
► The key problem during predictive parsing is that of determining the production to be applied for a nonterminal in case of alternatives.
► The non-recursive parser in figure looks up the production to be applied in parsing table.
► In what follows, we shall see how the table can be constructed directly from certain grammars.

[Link]. Recursive Descent Parsing

► Recursive descent parsing is one of the top-down parsing techniques that uses a set of recursive procedures to scan its input.
► This parsing method may involve backtracking, that is, making repeated scans of the input.
► Recursive descent parsing is a top-down parsing technique that constructs the parse tree from the top and the input is read from left to
right.
► It uses procedures for every non-terminal entity.
► This parsing technique recursively parses the input to make a parse tree which may or may not require back-tracking.
► But the grammar associated with it (if not left factored) cannot avoid back-tracking.
► in backtracking, expansion of nonterminal symbol we choose one alternative and if any mismatch occurs then we try another alternative.

Example for: backtracking

Consider the grammar G: S → cAd

A→ab|a

And the input string w=cad.

The parse tree can be constructed using the following top-down approach:
59 | P a g e
Step 1:

Step 2:

Step 3:
60 | P a g e
Step 4: Now try the second alternative for A.

 Now we can halt and announce the successful completion of parsing.

Example for recursive decent parsing:

 A left-recursive grammar can cause a recursive-descent parser to go into an infinite loop. Hence, elimination of left-recursion
must be done before parsing.

Consider the grammar for arithmetic expressions

EE+T |T

61 | P a g e
 TT*F |T

F(E) |id

After eliminating the left-recursion the grammar becomes,

ETE‟
E‟+TE‟ |ɛ
TFT‟
T‟*FT‟ |ɛ
F (E) |id
 Now we can write the procedure for grammar as follows:

Recursive procedure

E()
begin
T()
EPRIME();
end
procedure EPRIME()
begin

62 | P a g e
 if input_symbol=‟+‟ then
ADVANCE();
T();
EPRIME();
end
procedure T()
begin
F();
TPRIME();
end
procedure TPRIME()
begin
if input_symbol=‟*‟ then
ADVANCE();
F();
TPRIME();
end
procedure F()
begin
if input_symbol=‟id‟ then
ADVANCE();
else if input_symbol=‟(‟ then

63 | P a g e
 ADVANCE();
E();
else if input_symbol=‟)‟ then
ADVANCE();
end
else ERROR();

Stack implementation:

 To recognize input: id + id * id:

64 | P a g e
[Link]. LL (1) Grammar
► Predictive parsers are those recursive descent parsers needing no backtracking.
► LL(1) is non-recursive top down parser.
65 | P a g e
 1. First L indicates input is scanned from Left to Right.
2. The second L means it uses Leftmost derivation for input string.
3. 1 means it uses look-ahead of only one input symbol to predict the parsing process.
► The parsing table entries are single entries. So each location has not more than one entry. This type of grammar is called LL(1) grammar.

Figure 3. 8: LL(1) grammar

► The table-driven predictive parser has

 An input buffer,
 Stack,

66 | P a g e
  A parsing table and An output stream.
► Input buffer: It consists of strings to be parsed, followed by $ to indicate the end of the input string.
► Stack: It contains a sequence of grammar symbols preceded by $ to indicate the bottom of the stack. Initially, the stack contains the start
symbol on top of $.
► Parsing table: It is a two-dimensional array M[A, a], where „A‟ is a non-terminal and „a‟ is a terminal.
► Predictive parsing program:
 The parser is controlled by a program that considers X, the symbol on top of stack, and a, the current input symbol.
 These two symbols determine the parser action.
 There are three possibilities:
1) If X = a = $, the parser halts and announces successful completion of parsing.
2) If X = a ≠ $, the parser pops X off the stack and advances the input pointer to the next input symbol.
3) If X is a non-terminal , the program consults entry M[X, a] of the parsing table M. This entry will either be an X-production of the
grammar or an error entry.
 If M[X, a] = {X → UVW},the parser replaces X on top of the stack by WVU.
 If M[X, a] = error, the parser calls an error recovery routine.

[Link]. Top-down Parsing Implementation

Implementation of Predictive Parser:-

1. Elimination of left recursion, left factoring and ambiguous grammar.
2. Construct FIRST() and FOLLOW() for all non-terminals.
3. Construct predictive parsing table.
4. Parse the given input string using stack and parsing table
Predictive Parsing Table Construction
 The construction of a predictive parser is aided by two functions associated with a grammar G :

67 | P a g e
 1) FIRST
2) FOLLOW
 FIRST and FOLLOW are two functions associated with a grammar that help us fill in the entries of an M-table.
Benefits of First() and Follow()
 Can be used to prove the LL(K) characteristic of a grammar
 Can be used to aid in the construction of predictive parsing table.
 Provides selection information for recursive descent parsers.
FIRST:
 First() is a function which gives the set of terminals that begins strings derived from the production rule.
 It computes the set of terminal symbols with which the RHS of the productions begin.
 Rules for First( ):
1. If X is terminal, then FIRST(X) is {X}.
2. If X → € is a production, then add € to FIRST(X).
3. If X is non-terminal and X → aα is a production then add a to FIRST(X).
4. If X is non-terminal and X → Y1 Y2…Yk is a production, then place a in FIRST(X) if for some i, a is in FIRST(Yi), and € is in all of
FIRST(Y1),…,FIRST(Yi-1); that is, Y1,…. Yi-1 => € . If is in FIRST(Yj) for all j=1,2,..,k, then add € to FIRST(X).
Follow:
 Follow() is a function which gives the set of terminals that can appear immediately to the right of a given symbol.
 It is nothing but the set of terminal symbols of the grammar that are immediately following the Non-terminal A.
 Rules for Follow( ):
1. $ is an element of follow(S), where S is start symbol and $ indicates the end of the input.
2. If X → αXY is a production, the set First(Y) is in the set Follow(X), excluding € .
3. If X → αX or X → αXY are productions and FIRST(Y) has an element €, the set Follow(X) is in the set Follow(Y)

Example: Consider the following grammar:

68 | P a g e
 EE+T |T

TT*F |T

F(E) |id

After eliminating the left-recursion the grammar becomes,

ETE‟
E‟+TE‟ |ɛ
TFT‟
T‟*FT‟ |ɛ
F (E) |id

 After eliminating left-recursion the grammar is

69 | P a g e
Predictive parsing Table

70 | P a g e
 3.5.2. Bottom up parsing
Bottom-up parser builds a derivation by working from the input sentence back towards the start symbol S. Right most derivation in
reverse order is done in bottom-up parsing.

Top down Vs Bottom-up parsing:

Top-down Bottom-up

71 | P a g e
 1. Construct tree from root to leaves 1. Construct tree from leaves to root

2. “Guers” which RHS to substitute for 2. “Guers” which rule to “reduce”

nonterminal terminals

3. Produces left-most derivation 3. Produces reverse right-most derivation.

4. Recursive descent, LL parsers
5. Recursive descent, LL parsers 4. Shift-reduce, LR, LALR, etc.
6. Easy for humans 5. “Harder” for humans.

Example – 1: Right-most derivation

72 | P a g e
 S aAcBe SaAcBe

AAb/b aAcde

Bd aAbcde

input string: abbcde abbcde

Example – 3: Right most derivation:

SaABe
AAbc/b
Bd
1/p: abbcde

aABe
aAde Since ( ) Bd
aAbcde Since ( ) AAbc
abbcde Since ( ) Ab

[Link]. Handles
► Always making progress by replacing a substring with LHS of a matching production will
not lead to the goal/start symbol.
For example:
abbcde
aAbcde A→b
aAAcde A→b
Struck
► Informally, A Handle of a string is a substring that matches the right side of a production,
and whose reduction to the non-terminal on the left side of the production represents one step
along the reverse of a right most derivation. If the grammar is unambiguous, every right
sentential form has exactly one handle. More formally, A handle is a production A→ and a
position in the current right-sentential form  such that:
SA/
73 | P a g e
For example grammar, if current right-sentential form is
a/Abcde
Then the handle is A→Ab at the marked position. „a‟ never contains non-terminals.
HANDLE PRUNING:
Keep removing handles, replacing them with corresponding LHS of production, until we reach S.
Example:
E→E+E/E*E/(E)/id
Right-sentential form Handle Reducing production
a+b*c a E→id
E+b*c b E→id
E+E*C C E→id
E+E*E E*E E→E*E
E+E E+E E→E+E
E
The grammar is ambiguous, so there are actually two handles at next-to-last step. We can use
parser-generators that compute the handles for us.

[Link]. Shift- Reduce Parsing

► Shift Reduce Parsing uses a stuck to hold grammar symbols and input buffer to hold string to
be parsed, because handles always appear at the top of the stack i.e., there‟s no need to look
deeper into the state. A shift-reduce parser has just four actions:
1. Shift-next word is shifted onto the stack (input symbols) until a handle is formed.
2. Reduce – right end of handle is at top of stack, locate left end of handle within the stack.
Pop handle off stack and push appropriate LHS.
3. Accept – stop parsing on successful completion of parse and report success.
4. Error – call an error reporting/recovery routine.

Possible Conflicts:

► Ambiguous grammars lead to parsing conflicts.

1. Shift-reduce: Both a shift action and a reduce action are possible in the same state
(should we shift or reduce) Example: dangling-else problem

74 | P a g e
 2. Reduce-reduce: Two or more distinct reduce actions are possible in the same state.
(Which production should we reduce with 2).

Shift – reduce parsing example: (Stack implementation)

Grammar: E→E+E/E*E/(E)/id Input: id1+id2+id3

► One Scheme to implement a handle-pruning, bottom-up parser is called a shift-reduce

parser. Shift reduce parsers use stack and an input buffer.

The sequence of steps is as follows:

1. initialize stack with $.

2. Repeat until the top of the stack is the goal symbol and the input token is “end of
life”. a. Find the handle . If we don‟t have a handle on top of stack, shift an
input symbol onto the stack.
b. Prune the handle If we have a handle (A→) on the stack, reduce
(i) pop // symbols off the stack
(ii) push A onto the stack.
Stack input Action
$ id1+id2*id3$ Shift
$ id1 +id2*id3$ Reduce by E→id
$E +id2*id3$ Shift
$E+ id2*id3$ Shift
$E+ id2 *id3$ Reduce by E→id
$E+E *id3$ Shift
$E+E* id3$ Shift
$E+E* id3 $ Reduce by E→id
$E+E*E $ Reduce by E→E*E
$E+E $ Reduce by E→E+E
$E $ Accept

75 | P a g e
 [Link]. Operator – Precedence Parsing
► Precedence/ Operator grammar: The grammars having the property:
1. No production right side is should contain .
2. No production sight side should contain two adjacent non-terminals. Is called an
operator grammar.
► Operator – precedence parsing has three disjoint precedence relations, between certain pairs
of terminals. These precedence relations guide the selection of handles and have the
following meanings:
Relation Meaning
a<.b „a‟ yields precedence to „b‟.
a=b „a‟ has the same precedence „b‟
a.>b „a‟ takes precedence over „b‟.
► Operator precedence parsing has a number of disadvantages:
1. It is hard to handle tokens like the minus sign, which has two different
precedence.
2. Only a small class of grammars can be parsed.
3. The relationship between a grammar for the language being parsed and the
operator- precedence parser itself is tenuous, one cannot always be sure the parser
accepts exactly the desired language.
Disadvantages:
1. L(G) L(parser)
2. error detection
3. usage is limited
4. They are easy to analyze manually Example:
Grammar: E→EAE|(E)|-E/id
A→+|-|*|/|
Input string: id+id*id
The operator – precedence relations are:
Id + * $
Id .> .> .>

76 | P a g e
+ <. .> <. .>
* <. .> .> .>
$ <. <. <.
Solution: This is not operator grammar, so first reduce it to operator grammar form, by
eliminating adjacent non-terminals.
Operator grammar is: E→E+E|E-E|E*E|E/E|EE|(E)|-E|id
The input string with precedence relations interested is: $<.id.>+<.id.> *<.id.> $
Input string Precedence relations inserted Action
id+id*id $<.id.>+<.id.>*<.id.>$
E+id*id $+<.id.>*<.id.>$ E→id
E+E*id $+*<.id.>$ E→id
E+E*E $+*$
E+E*E $<.+<.*.>$ E→E*E
E+E $<.+$
E+E $<.+.>$ E→E+E
E $$ Accepted

3.6. Error Recovery Strategies

There are two basic types of errors. These are:- compile time and run time

Figure 3. 9: Types of errors recovery

77 | P a g e
compile time error can be classified into four major parts.

1. Lexical Error
 Lexical errors can be detected during lexical analysis phase.
 Typical lexical phase errors are:-
 Spelling errors
 Exceeding length of identifier or numeric constants
 Appearance of illegal characters
Example:

fi ()

In the above code „fi‟ cannot be recognized as misspelling of keyword if rather lexical analyzer will
understand that it is an identifier and will return it as its valid identifier. Thus misspelling causes errors in
token formation.

2. Syntax Error
 Syntax error appear during syntax analysis phase of compiler.
 Typical syntax phase errors are:-
 Errors in structure
 Missing operators
 Unbalanced parenthesis or missing parenthesis
The parser demands for tokens from lexical analyzer and if the tokens do not satisfy the grammatical rules
of programming language then the syntactical errors get raised.

Example:

printf(“Hello world!!”) // Error: semicolon missing

3. Semantic Error
 Semantic error detected during semantic analysis phase.
 Typical semantic phase errors are:-
 Incompatible types of operands
 Undeclared variable

78 | P a g e
  Not matching of actual argument with formal argument
Example:

id1=id2 + id3 * 60 (Note: id1, id2, id3 real)

(Directly we cannot perform multiplication due to incompatible types of variables)

4. Logical Error
 It is next to impossible for the compilers to handle the logical errors. Infinite loops is the example of
logical error. In these type of errors code is correct syntactically but it does not operate as indeed.
 A good compiler have following goals for error handling:
 Detect the presence of errors and produce, “meaningful” diagnostics.
 To recover quickly enough to be able to detect subsequent errors.
 Error handling components should not significantly slow down the compilation of syntactically
correct programs.

79 | P a g e
 CHAPTER FOUR
SYNTAX DIRECTED TRANSLATION

Introduction
In this chapter four, the overview of SDT have been studied, the difference between SDT versus
SDD, understanding Attribute grammar, design the evaluation orders for SDD, and how to
construct the syntax tree are well studied

After completing this chapter, the students will be able to:

 Define the term SDT, and identify the difference between SDT versus SDD
 understanding Attribute grammar
 design the evaluation orders for SDD
 Construct the syntax tree

4.1. Overview of Syntax Directed Translation (SDT)

► It refers to a method of compiler implementation where the source language translation is
completely driven by the parser, i.e., based on the syntax of the language.
► It combines grammar rules with semantic actions, allowing for the systematic transformation
of source code into intermediate or machine code.
► The parsing process and parse trees are used to direct semantic analysis and the translation
of the source program.
► Almost all modern compilers are syntax-directed.
► SDT can be a separate phase of a compiler or we can augment our conventional grammar
with information to control the semantic analysis and translation. Such grammars are called
attribute grammars.
► We augment a grammar by associating attributes with each grammar symbol that describes its
properties.
► With each production in a grammar, we give semantic rules/ actions, which describe how to compute
the attribute values associated with each grammar symbol in a production.
► The general approach to Syntax-Directed Translation is to construct a parse tree or syntax tree and
then compute the values of attributes at the nodes of the tree by visiting them in some order.
► In many cases, translation can be done during parsing without building an explicit tree.
► A class of syntax-directed translations called "L-attributed translations" (L for left-to- right) includes
almost all translations that can be performed during parsing.
80 | P a g e
► Similarly, "S-attributed translations" (S for synthesized) can be performed easily in connection with a
bottom-up parse.
 There are two ways to represent the semantic rules associated with grammar symbols.

 Syntax-Directed Definitions (SDD)

 Syntax-Directed Translation Schemes (SDT)
Key components of SDT
 Syntax Trees: SDT utilizes syntax trees to represents the hierarchical structure of the source
code based on the grammar rules. Each node in the tree corresponds to a language construct,
while the edge depicts relationships between these constructs.
 Attributes: are additional information associated with grammar symbols. they help carry data
related to the semantics of language constructs, guiding the translation process by storing
relevant information. Attributes can be synthesized (computed from child nodes) or inherited
(passed down from parent nodes).
 Semantic Actions: are operations or transformations performed during the translation
process. Semantic actions are linked to specific grammar rules and executed when the
corresponding constructs are recognized in the source code. They utilize the information
stored in attributes to generate equivalent code in the target language.

Advantages of SDT
♦ Clarity: the association of semantic actions with grammar rules provides a clear
representation of the translation process, enhancing the understanding of the
compiler‟s behavior.
♦ Modularity: the modular nature of SDT allows for easy addition or modification of
language constructs, making it adaptable to changes in programming languages.
♦ Efficiency: by integrating syntax analysis with semantic actions, SDT facilitates
efficient translation of source code into executable forms.
In summary, Syntax Directed Translation is a fundamental technique in compiler design that
effectively bridges the gap between syntax and semantics, enabling the accurate and efficient
translation of programming languages. It plays a crucial role in the development of compilers
and an interpreter, ensuring that source code is transformed correctly into executable code.

81 | P a g e
 4.2. Syntax Directed Definitions
 Syntax Directed Definition is a context free grammar with semantic rules attached to the
productions.
 The semantic rules define values for attributes associated with the non-terminal symbols of the
production.
 SDD is a CFG which consists of attributes and rules.
1. Attributes:- They are associated with grammar symbols.
2. Rules: - They are associated with productions.
 An attribute has a name and an associated value: a string, a number, a type, a memory location, an
assigned register.
 For example, if X is grammar symbol and „b‟ is one of its attributes, then we write X.b denotes the
value of „b‟ at a particular parse tree node labeled as „X‟.
 If we implement the nodes of the parse tree by records or objects, then the attributes of X can be
implemented by data fields in the records that represent the nodes for X.
 The attributes are evaluated by the semantic rules attached to the productions.
 Example: PRODUCTION SEMANTIC RULE

E  E1  T [Link]  [Link] || T .code || ' 'E1

 This production has two non-terminals, E and T; the subscript in distinguishes the occurrence of E
in the production body from the occurrence of E as the head.
 Both E and T have a string-valued attribute code.
 The semantic rule specifies that the string [Link] is formed by concatenating .code , [Link], and
the character ‘+’.
 While the rule makes it explicit that the translation of E is built up from the translations of , T,
and ‘+’, it may be inefficient to implement the translation directly by manipulating strings.
 SDDs are highly readable and give high-level specifications for translations. But they hide many
implementation details.
 For example, they do not specify order of evaluation of semantic actions.

4.3. Syntax-Directed Translation Schemes (SDT)

 SDT embeds program fragments called semantic actions within production bodies as in
E  E1  T { print '+' }
 By convention, semantic actions are enclosed within curly braces. (If curly braces occur
as grammar symbols, we enclose them within single quotes, as in ‘{‘ and ‘}’).
82 | P a g e
  The position of semantic action in a production body determines the order in which the
action is executed.
 In the above production, the action occurs at the end, after all the grammar symbols; in
general, semantic actions may occur at any position in a production body.
 Between the two notations,
 Syntax-directed definitions can be more readable, and hence more useful for
specifications.
 However, syntax-directed translation schemes can be more efficient, and hence more
useful for implementations.
Syntax Directed Definition (SDD) versus Syntax Directed Translation (SDT)

Syntax Directed Definition Syntax Directed Translation(SDT)

 It is a context-free grammar  It refers to the translation of a string

where attributes and rules are into an array of actions. This is done
combined and associated with by adding an action to a rule of
grammar symbols and context-free grammar.
productions, respectively.
 Attribute Grammar  Translation Schemes
 Specifies the values of attributes  Embeds program fragments (also
by associating semantic rules with called semantic actions) within
the productions. production bodies.
 E → E1 + T { [Link] := [Link] +  E → E + T { print(„+‟); }
[Link] }

4.4. Inherited and Synthesized Attributes

 Terminals can have synthesized attributes, which are given to it by the lexer (not the parser).
 Terminals can have synthesized attributes, but not inherited attributes.
 There are no rules in an SDD giving values to attributes for terminals.
 Terminals do not have inherited attributes.
 There are two kinds of attributes for non-terminals.
1) Synthesized attributes
83 | P a g e
 2) Inherited attributes
Synthesized Attribute

 A synthesized attribute for a non-terminal A at a parse-tree node N is defined by a semantic rule

associated with the production at N.

 Note that the production must have A as its head.

 A synthesized attribute at node N is defined only in terms of attribute values at the children of N
and at N itself.

 An attribute is synthesized if all its dependencies point from child to parent in the parse-tree.

 The value of synthesized attribute at a node is computed from the values of attributes at the
children of that node in the parse tree.

 Synthesized attribute for a non terminal S at the parse tree with node N is defined by a semantic
rule with production at N.

 Here S is the head of the production.

 For example: E  E1  E2 has semantic rule ae [Link]=[Link]  E2 .val

and can be written as:

Here [Link] is synthesized attribute. Let us see another fig to make the concept

Figure 4. 1: synthesis and Inherited attribute

Inherited Attribute
84 | P a g e
  An inherited attribute for a non-terminal B at a parse-tree node N is defined by a semantic rule
associated with the production at the parent of N.
 Note that the production must have B as a symbol in its body.
 An inherited attribute at node N is defined only in terms of attribute values at N's parent, N
itself, and N's siblings.
 The value of inherited attribute is computed from the values of attributes at the siblings and
parent of that node.
 Inherited attribute for non-terminal A at the parse tree with node N is defined by a semantic rule
associated with the production at the parent node N.
 The following example shows the SDD for a simple desk calculator, „n‟ is end marker.

 Example 1: In SDD, each of the non-terminals or variables consists of a single synthesized

attribute „val‟.

SNO PRODUCTION SEMANTIC RULE

1. LEn [Link]=[Link]
2. EE+T [Link]=[Link]+[Link]
3. ET [Link]=[Link]
4. TT*F [Link]=[Link]*[Link]
5. TF [Link]=[Link]
6. F(E) [Link]=[Link]
7. Fdigit [Link]=[Link]

♦ The rule for production 1, L  En , sets [Link] to [Link] which we shall see is the numerical
value of the entire expression.
♦ Production 2, E  E1  T , also has one rule, which computes the val attribute for the head
E as the sum of the values at and T. At any pare-tree node N labeled E, the value of val for
E is the sum of the values of val at the children of node N labeled E and T.
♦ Production 3, E  T , has a single rule that defines the values of val for E to be the same
as the values of val at the child for T.
♦ Production 4, is similar to the second production; its rule multiplies the values at the children
instead of adding them.
♦ The rules for production 5 and 6 copy values at a child, like that for the third production.

85 | P a g e
 ♦ Production 7 gives [Link] the value of a digit, that is, the numerical value of the token digit
that the lexical analyzer returned.
♦ Symbols E, T and F are associated with a synthesized attribute val.
♦ The token digit has a synthesized attribute lexval (it is assumed that it is evaluated by the
lexical analyzer).

Production Semantic Rules

DTL [Link]=[Link]
Tint [Link]=integer
Treal [Link]=real
LL1id L1in=[Link], add type ([Link], [Link])
Lid add type([Link], [Link])
♦ Symbol T is associated with a synthesized attribute type.
♦ Symbol L is associated with an inherited attribute in.

4.5. Attribute Grammars

 Every grammar is associated with a set of attributes.
 Semantic rules specify how each attribute is to be computed.
 The attributes of a grammar symbol are partitioned into two sets: inherited and
synthesized.
 That is for any particular grammar symbol, a given attribute cannot be inherited in the
same places and synthesized in others.
S-Attributed Grammars and L-Attributed Grammars

 Grammar containing only synthesized attributes is called S-attributed grammar.

 Synthesized attributes can be conveniently handled during bottom up parsing as it builds
the parse tree bottom up.
 On the other hand grammar for which the attributes can always be evaluated by depth-
first L-to-R traversal of the parse tree, is called L-attributed grammar.
 In case of L-attributed grammar, all the attributes can be conveniently handled during
LL(1) parsing because the parse tree is built depth-first L-to-R.
 S-attributed grammars are a class of attribute grammars, comparable with L-attributed
grammars but characterized by having no inherited attributes at all.

86 | P a g e
  Inherited attributes, which must be passed down from parent nodes to children nodes of
the abstract syntax tree during the semantic analysis, pose a problem for bottom-up
parsing because in bottom-up parsing, the parent nodes of the abstract syntax tree are
created after creation of all of their children.
 Attribute evaluation in S-attributed grammars can be incorporated conveniently in both
top-down parsing and bottom-up parsing .

4.6. Evaluation Orders for SDD's

 "Dependency graphs" are a useful tool for determining an evaluation order for the
attribute instances in a given parse tree.
 While an annotated parse tree shows the values of attributes, and dependency graph helps
us to determine how those values can be computed.
Directed graph indicating interdependencies among the synthesized and inherited
attributes of various nodes in a parse tree.

Figure 4. 2: Dependency graphs

4.6.1. Dependency Graphs

 Implementing a SDD consists primarily in finding an order for the evaluation of
attributes. Each attribute value must be available when a computation is performed.
 Dependency graphs are the most general technique used to evaluate syntax directed
definitions with both synthesized and inherited attributes.
 The directed graph that represents the interdependencies between synthesized and
inherited attributes at nodes in the parse tree is called dependency graph.
 A dependency graph indicates the flow of information among the attribute instances in
a particular parse tree; an edge exists from one attribute instance to another means that
the value of the first is needed to compute the second.
87 | P a g e
  Edges express constraints implied by the semantic rules.
 For each parse-tree node, say a node labeled by grammar symbol X, the dependency
graph has a node for each attribute associated with X.
 If a semantic rule associated with a production p defines the value of synthesized
attribute A.b in terms of the value of X.c. Then the dependency graph has an edge from
X.c to A.b
 If a semantic rule associated with a production p defines the value of inherited attribute
B.c in terms of the value X.a. Then , the dependency graph has an edge from X.a to B.c.

4.7. Construction of Syntax Tree

 A syntax tree, also known as an abstract syntax tree (AST), is a tree representation of the
syntactic structure of source code written in a programming language.
 It is used in compiler design to represent the structure of the code in a way that is easier
to analyze and manipulate.
 Syntax trees are constructed by parsing the source code, which involves analyzing the
code and breaking it down into its individual components, such as tokens, variables, and
statements.
 A parse tree showing the values of attributes at each node is called an Annotated parse
tree.
 The process of computing the attributes values at the nodes is called annotating (or
decorating) of the parse tree.
 Of course, the order of these computations depends on the dependency graph induced by
the semantic rules.
Construct the syntax tree for the expression X * 7 – 5 +Z

88 | P a g e
  The corresponding annotated parse tree shown below, for the string 3*5+4n.

Figure 4. 3: Examples of Annotated parse tree

89 | P a g e
 CHAPTER FIVE
TYPE CHECKING

Introduction
In this chapter, introduction of Type checking in compiler design concepts have been studied,
and identify the types of conversion are well studied.

After completing this chapter, the students will be able to:

 understanding of Type checking in compiler design

 identify the types of conversion
 identify and mention the types of checking

5.1. Introduction to Type Checking

 A compiler must check that the source program should follow both the syntactic and
semantic rules of the source language.
 Some rules can be checked statically during compile time and other rules can be checked
dynamically during run time.
 Static checking includes the syntax checks performed by the parser and semantic checks
such as type checks, flow-of-control checks, uniqueness checks, and name related checks.
 In order to check types, one first must have a representation of those types(a type system)
and then one must implement comparison and composition operates on those types using
the semantic rules of the source language being compiled.
 Lastly, type checking will involve adding synthesized attributes through those parts of the
language grammar that involve expression and values.
 A compiler must check that the source program follows both syntactic and semantic
conventions of the source language. This checking, called static checking, detects and
reports programming errors.
 The type checker verifies that the type of a construct matches that expected by its content.
 Type checker plays role between syntactic analysis and intermediate code generation as
follows;
 The process of verifying and enforcing the constraints of types.

90 | P a g e
  Type checking – may occur either at compile time (static check) or run time (dynamic
check).

5.1.1. Designing a Type Checker

 When designing a type checker for a compiler, we should follow the process below;
1. Identify the types that are available in the language
2. Identify the language constructs that have types associated with them
3. Identify the semantic rules for the language.
 If a problem is found, e.g.; one tries to add a char to a double in C, we encounter a type
error.
 A language is considered strongly-typed if each and every type error is detected during
compilation.
 Type checking can be done compilation, during execution, or divided across both.
Static Checking
 Static checking refers to the compile-time checking of programs to ensure that the
syntactic and semantic conventions of the source language are being followed.
 Some examples of static checks:
 Type Checks: - a compiler should report an error if an operator is applied to an
incompatible operand.
 Example: If an array variable and function variable are added together. Operators
and operands must have “compatible” types.
 Flow-of-Control Checks:- statements that cause flow of control to leave a construct
must have some place to which to transfer the flow of control.
 Example: An error occurs when an enclosing statement, such as break, does not
exist in switch statement.
 Uniqueness checks: - a language may dictate that in some contexts, an entity can be
defined exactly one that is identifiers in declarations, case statements in C.
 Name-related checks: - sometimes, the same name must appear two or more times, that
is in a loop or block can have a name that must appear at the beginning and at the end.
 Some or all of these activities can be folded into other activities, that is some checking
can be integrated with parsing.

91 | P a g e
  Type checking is a crucial process in compiler design that ensures the correctness of a
program by verifying that the types of all variables, expressions, and functions conform
to the rules of the programming language.
Static vs. Dynamic Typing Checking
 Dynamically-typed variable can hold values of any type (e.g.; integers, strings, or arrays).
Operations on dynamically-typed variables are checked at runtime.
 In a dynamically-typed program all( or most) variables are dynamically typed.
 Statically-typed variables are declared to hold values of a specific type.
 When using static typing, a program is type checked before running it.
 Type checking verifies that operations on a value are valid for the type of the value.
 For example, trying to add a string to an integer results in a type check error in a
statically-typed program.
 In a dynamically-typed program the error would be caught only at a runtime, and only
when that particular operation would be performed.
 Static Typing has the following main benefits:
 Reduced CPU usage since types don‟t need to be checked at runtime.
 Reduced memory usage since types don‟t need to be stored at runtime.
 Other type-directed optimizations
 Discovery of errors as early as possible.
 Dynamic typing has a different, complementary set of benefits:
 Easier to run and test since there are practically no compile-time or link-time
errors.
 Programs are not limited by the expressiveness of the type system of the
language.
 Allows for implicit open recursion, late binding dynamic scope, and duck typing.
 Programs are simpler since we don‟t have to worry about types.
 Benefits of Type Checking
 Type checking offers several benefits:
 Error Detection: Catches type-related errors early, improving program reliability.
 Optimization: Allows for compiler optimizations since types are known at
compile time.
92 | P a g e
  Safety: ensure that operations are performed on compatible data types, preventing
that runtime errors

5.2. Rules for Type Checking

 Type Checking can be Type Synthesis (TS) and Type Inference (TI).
 Type Synthesis (TS) uses the types of its subexpressions in order to build the type of
expression. TS require names to declare before they are used.
 Type Inference (TI) is used to determine the type of a language construct from the way it
is used.

5.3. Type Conversion

 Type conversion rules differ from one language to another.
 Java uses widening and narrowing conversions between primitive types.
 Depending on the language, specific conversion rules must be adopted by the compiler
to convert the type of one the operand of +.
 The type checker in a compiler can insert these conversion operators into the
intermediate code.
 Such an implicit type conversion is called Coercion.
 Let us see an example of java type conversion as follows:
 byte x;
 int y;
 long z;
 z=x + y;
1. Coerce the byte value of x to int.
2. Add the two int values to give an int sum.
3. Coerce the int sum to a long value.
4. Assign the long sum to the long variable z.
In C programming, we can convert the value of one data type (int, float, double, etc.) to
another. This process is known as type conversion. Let's see an example:

#include <stdio.h>
int main() {

93 | P a g e
 int number = 35.88;
printf("%d", number);
return 0;
}

// Output: 35
► This type of conversion is known as implicit type conversion. In C, there are two types of
type conversion:
1. Implicit Conversion
2. Explicit Conversion

5.3.1. Implicit Conversion

► No special syntax is required because the conversion is type safe and no data will be lost.
 Let us see an example of C language as follows:
int x=123;
double y=x;
 The conversion of data from int to double be done implicitly, in other words
programmers don’t need to specify any type operators.
 Implicit type conversions are also called Coercion
In implicit type conversion, the value of one type is automatically converted to the value of another
type. For example,

#include<stdio.h>

int main() {
// create a double variable
double value = 4150.12;
printf("Double Value: %.2lf\n", value);
// convert double value to integer
int number = value;
printf("Integer Value: %d", number);

94 | P a g e
 return 0;
}
//Outputs
Double Value: 4150.12

Integer Value: 4150

The above example has a double variable with a value 4150.12. Notice that we have assigned the
double value to an integer variable.

int number = value;

Here, the C compiler automatically converts the double value 4150.12 to integer value 4150.

Since the conversion is happening automatically, this type of conversion is called implicit type
conversion.

Example 2: Implicit Type Conversion

#include<stdio.h>
int main() {
// character variable
char alphabet = 'a';
printf("Character Value: %c\n", alphabet);

// assign character value to integer variable

int number = alphabet;
printf("Integer Value: %d", number);

return 0;
}
Output

Character Value: a
Integer Value: 97

95 | P a g e
The code above has created a character variable alphabet with the value 'a'. Notice that we are
assigning alphabet to an integer variable.

int number = alphabet;

Here, the C compiler automatically converts the character 'a' to integer 97. This is because, in C
programming, characters are internally stored as integer values known as ASCII Values.

5.3.2. Explicit Conversion (Casts)

 It requires a cast operator.
 Casting is required when information might be lost in the conversion, or when the
conversion might not succeed for other reasons.
 Typical examples include numeric conversion to a type that has less precision or a
smaller range, and conversion of base-class instances to a derived class.
In explicit type conversion, we manually convert values of one data type to another type.
For example,

#include<stdio.h>
int main() {
// create an integer variable
int number = 35;
printf("Integer Value: %d\n", number);
// explicit type conversion
double value = (double) number;
printf("Double Value: %.2lf", value);
return 0;
}
//Output
Integer Value: 35
Double Value: 35.00
We have created an integer variable named number with the value 35 in the above program.
Notice the code,
// explicit type conversion

96 | P a g e
double value = (double) number;
Here,
(double) - represents the data type to which number is to be converted
number - value that is to be converted to double type

5.3.3. User-defined Conversion

 They are performed by special methods that we can define to enable explicit and implicit
conversions between custom types that don‟t have a base class-derived class relationship.
Type Coercion

 Type coercion is the automatic conversion of a datum from one data type to another within
an expression.
 Coercion occurs because the datum is stored as one data type but it context requires a
different data type.
 E.g.; double x=1;
 In this statement, the constant 1 is an integer but its context requires a double value.
 Many programming languages, including java, allow type coercion as a convenience to the
programmer.
1. double average, sum;
2. int count;
3. average= sum/count;
 In line 3 the value of the count is automatically converted to double before executing.
Type Systems
 It is a collection rules for assigning type expressions to the various part of the program.
 It specified using syntax directed definitions.
 A type checker implements a type system.

97 | P a g e
 CHAPTER SIX
INTERMEDIATE LANGUAGES

Introduction
In this chapter, Overview of Intermediate Language have been studied, understanding of kinds of
intermediate language and kinds of three address statement, how to represent the three address code in
flow control statement, back patching and procedure call are well studied.

After completing this chapter, the students will be able to:

 Understanding of Overview of Intermediate Language, kinds of intermediate language,

and kinds of three address statement.
 Define the back patching and procedure call

6.1. Overview of Intermediate Language

 Intermediate code is used to translate the source code into the machine code.
 Intermediate code lies between the high-level language and the machine language.

Figure 6. 1: Intermediate Language

 If the compiler directly translates source code into the machine code without generating
intermediate code then a full native compiler is required for each new machine.

98 | P a g e
  The intermediate code keeps the analysis portions same for all the compilers that's why it
doesn't need a full compiler for every unique machine.
 Intermediate code generator receives input from its predecessor phase and semantic
analyzer phase. It takes input in the form of an annotated syntax tree.
 Using the intermediate code, the second phase of the compiler synthesis phase is
changed according to the target machine.
 There are three kinds of intermediate representations, they are
1. Syntax trees
2. Postfix notations
3. Three address code
Syntax trees
 A syntax tree depicts the natural hierarchical structure of a source program.
 In the parse tree, most of the leaf nodes are single child to their parent nodes.
 In the syntax tree, we can eliminate this extra information.
 Syntax tree is a variant of parse tree.
 In the syntax tree, interior nodes are operators and leaves are operands.
 Syntax tree is usually used when represent a program in a tree structure.
 A sentence id + id * id would have the following syntax tree:

 A syntax tree for the assignment statement a := b* - c + b* -c is

99 | P a g e
  Abstract syntax trees are important data structures in a compiler. It contains the least
unnecessary information.
 Abstract syntax trees are more compact than a parse tree and can be easily used by a
compiler.
 Abstract syntax tree can be represented as:

Figure 6. 2: Abstract syntax tree representation

Postfix notation
 Postfix notation is a linearized representation of a syntax tree; it is a list of the nodes of
the tree in which a node appears immediately after its children.
 It is the useful form of intermediate code if the given language is expressions.
100 | P a g e
  In the postfix notation, any expression can be written unambiguously without
parentheses.
 The ordinary (infix) way of writing the sum of x & y is with operator in the middle: x *
y. But in the postfix notation, we place the operator at the right end as xy *.
 In postfix notation, the operator follows the operand.
 The postfix notation for the syntax tree is abc uminus c*b uminus c*+assign
Three-Address Code
 In three-address code, the given expression is broken down into several separate
instructions. These instructions can easily translate into assembly language.
 Each three address code instruction has at most three operands. It is a combination of
assignment and a binary operator.

x : y op z
 Three address code is a sequence of statements of the general form where x, y, and z
are names, constants, or compiler-generated temporaries;
 op stands for any operator, such as a fixed or floating-point arithmetic operator, or a
logical operator on boolean-valued data.
 The reason for the term "three-address code" is that each statement usually contains three
addresses, two for the operands and one for the result.
 Example 1:
x  y*z
t1: y * z
t 2 : x  t1

 Example 2: Three address code for the syntax tree a: = b* - c + b* -c is

t1: c
t 2 : b * t1
t 3 : c
t 4 : b * t 3
t 5 : t 2  t 4
a : t 5

101 | P a g e
 6.2. Implementation of Three-address Statements
 A three address statement is an abstract form of intermediate code.
 There are three types of representations for three address code:-
1. Quadruples
2. Triples
3. Indirect Triples

6.2.1. Quadruples
 The quadruples have four fields to implement the three address code. The field of
quadruples contains the name of the operator, the first source operand, the second source
operand and the result respectively.
 A quadruple is a record structure with four fields, which we call op, arg1, arg2, and
result. The op field contains an internal code for the operator.
 The three-address statement x: = y op z is represented by placing y in arg 1, z in arg2, and
x in result.
 Statements with unary operators like x: = -y or x: = y does not use arg2.
 Quadruple for the statement a: = b* - c + b* -c is
Op Arg1 Arg2 result
(0) Uminus c t1
(1) * b t1 t2
(2) Uminus c t3
(3) * b t3 t4
(4) + t2 t4 t5
(5) := t5 a

6.2.2. Triples
 The triples have three fields to implement the three address code. The field of triples
contains the name of the operator, the first source operand and the second source
operand.

102 | P a g e
  Three-address statements can be represented by records with only three fields: op,
arg1 and arg2. Since three fields are used, this intermediate code format is known as
triples.
 The field‟s arg1 and arg2, for the arguments of op, are either pointers to the symbol
table or pointers into the triple structure.
 To avoid entering temporary names into the symbol table. We might refer to a
temporary value by the position of the statement that computes it.
Op Arg1 Arg2
(0) Uminus c
(1) * b (0)
(2) Uminus c
(3) * b (2)
(4) + (1) (3)
(5) Assign a (4)

6.2.3. Indirect triples

 Listing pointers to triples rather than listing the tuples themselves are called indirect
triples.
 Advantage: Indirect triples can save some space compared with quadruples, if the same
temporary value is used more than once.
 Indirect triple representation of a: = b* - c + b* -c

Statement
(0) (14)
(1) (15)
(2) (16)
(3) (17)
(4) (18)
(5) (19)

103 | P a g e
 Op Arg1 Arg2
(14) Uminus c
(15) * b (14)
(16) Uminus c
(17) * b (16)
(18) + (15) (17)
(19) Assign a (18)

6.3. Flow of Control Statement

 The following grammar generates the flow of control statements, if-then, if-then-else, and
while-do statements.
S If E then S1
| If E then S1 else S2
| While E do S1

 The Syntax Directed Definition for flow of control statement

104 | P a g e
 Figure 6. 3: Syntax-directed definition for flow-of-control statements

 Newlabel - returns a new symbolic label each time it is called

 [Link] - the labe1 to which control flows if E is true
 [Link] - the label to which control flows if E is false
 [Link] - a label that is attached to the first three address instruction to be executed after the
code for s.

If-Then
 In translating the if-then statement S  if E then S1, a new label [Link] is created and attached to
the first three-address instruction generated for the statement as in Fig, 8.22(a).
 The code for E generates a jump to [Link] if E is true and a jump to [Link] if E is false. We
therefore set [Link] to [Link].

If-then-else

105 | P a g e
 In translating the if-then-else statement S if E then S1 else S2. The code for the Boolean
expression E has jumps out of it to the first instruction of the code for S1 if E is true, and to
the first instruction of the code for S2 if E is false, as illustrated in Fig. 8.22(b).

While - do statement
 In translating Swhile E do S1, A new label [Link] is created and attached to the first
instruction generated for E. Another new label [Link] is attached to the first instruction for
S1.
 The code for E generates a jump to this label if E is true, a jump to [Link] if E is false and set
[Link] to be [Link]. After the code for S1 we place the instruction goto [Link], which
causes a jump back to the beginning of the code for the boolean expression,
 Example :

106 | P a g e
 Figure 6. 4: SDD for if-then, if-then-else, and while-do statements

6.4. BACKPATCHING
 Backpatching is a technique to solve the problem of replacing symbolic names into goto
statements by the actual target addresses.
 This problem comes up because if some languages do not allow symbolic names in the
branches.
 Backpatching can be used to do generate code for Boolean expression and control
statements in one pass.
 Leaving the labels as empty and filling them later.
 During one pass, the following steps are executed
1. Construct the syntax tree.
2. Generate jumps with unspecified targets.
3. Keep a list of such statements.
4. Subsequently fill in the labels.
 backpatch(p, i ) - inserts i as the target label for each of the statements on the list
pointed to by p.
Example: consider the expression a<b or c<d and e<f.
The six statements generated so far are thus:

107 | P a g e
 100: if a<b goto_
101: goto_
102: if c<d goto_
103: goto_
104: if e<f goto_
105: goto_
 The corresponding semantic action calls Backpatch ({102), 104) where (102) as argument
denotes a pointer to the list containing only 102, that list being the one pointed to by
[Link].
This call to backpatch fills in 104 in statement 102. The six statements generated so far are thus:
100: if a<b goto_
101: goto_
102: if c<d goto_
103: goto_
104: if e<f goto_
105: goto_
6.5. Procedure Calls
Procedures, also known as functions or subroutines, are fundamental building blocks in
programming languages. In compiler design, handling procedure calls efficiently and correctly is
crucial.
Steps during a Procedure Call:
1. Lexical Analysis and Parsing: The compiler identifies the procedure name and its arguments
during these initial stages.
2. Semantic Analysis: Type checking and argument passing mechanisms are verified to ensure
compatibility between actual parameters (arguments in the call) and formal parameters
(arguments defined in the procedure).
3. Code Generation: The compiler translates the procedure call into machine code instructions.
This involves:
 Activation Record Creation: A block of memory is allocated to store local variables,
parameters, and the return address for the called procedure.

108 | P a g e
  Argument Passing: The values of actual parameters are passed to the corresponding
formal parameters in the called procedure. Different mechanisms like pass-by-value or
pass-by-reference can be used.
 Control Flow Transfer: The program execution jumps to the beginning of the called
procedure's code.
4. Procedure Execution: The called procedure executes its instructions using the allocated
activation record for its local data.
5. Procedure Return:
 The called procedure performs any necessary actions before returning.
 The return address stored in the activation record is used to transfer control back to the
calling procedure's continuation point.
 The activation record of the called procedure might be deallocated depending on the
language and memory management strategy.
Challenges in Handling Procedure Calls:
 Recursion Handling: When a procedure calls itself (recursion), the compiler needs to manage
the activation record stack effectively to avoid stack overflow.
 Tail Recursion Optimization: Some compilers can optimize tail-recursive calls to improve
efficiency.
 Parameter Passing Mechanisms: Different languages have different mechanisms for passing
arguments, and the compiler needs to generate code accordingly.
 Example:
F(x1, x2, x3,…,xn)
Param x1
Param x2
Param x3
Call f,n Where f name of procedure, n number of parameter
Example: n=f(a[i]); a array of interger , f function from integers three address code is:
1. t1:=i*5
2. t2:=a[t1]
3. param t2
4. t3:=call f,1
5. n:=t3
109 | P a g e
 CHAPTER SEVEN
RUN TIME- ENVIRONMENTS

Introduction
In this chapter, Overview of Run time- Environment have been studied , definition of Symbol
table and hash table and their uses , representation of scope information are well studied

After completing this chapter, the students will be able to:

 Understand concepts of Run time- Environment

 Define the Symbol table and hash table and their uses

7.1. Run-Time Environment

► A program as a source code is merely a collection of text (code, statements etc.) and to make
it alive, it requires actions to be performed on the target machine.
► A program needs memory resources to execute instructions.
► A program contains names for procedures, identifiers etc., that require mapping with the
actual memory location at runtime.
► Runtime, we mean a program in execution.
► Runtime environment is a state of the target machine, which may include software libraries,
environment variables, etc., to provide services to the processes running in the system.
► Runtime support system is a package, mostly generated with the executable program itself
and facilitates the process communication between the process and the runtime
environment. It takes care of memory allocation and de-allocation while the program is
being executed
7.2. Symbol Table
► Symbol Table is an important data structure created and maintained by the compiler in
order to keep track of semantics of variables i.e. it stores information about the scope and
binding information about names, information about instances of various entities such as
variable and function names, classes, objects, etc. Symbol table is used by both the analysis
and the synthesis parts of a compiler.
 It is built-in lexical and syntax analysis phases.

110 | P a g e
  The information is collected by the analysis phases of the compiler and is used by the
synthesis phases of the compiler to generate code.
 It is used by the compiler to achieve compile-time efficiency.
 It is used by various phases of the compiler as follows:-
1) Lexical Analysis: Creates new table entries in the table, for example like entries
about tokens.
2) Syntax Analysis: Adds information regarding attribute type, scope, dimension, line
of reference, use, etc. in the table.
3) Semantic Analysis: Uses available information in the table to check for semantics
i.e. to verify that expressions and assignments are semantically correct (type
checking) and update it accordingly.
4) Intermediate Code generation: Refers symbol table for knowing how much and
what type of run-time is allocated and table helps in adding temporary variable
information.
5) Code Optimization: Uses information present in the symbol table for machine-
dependent optimization.
6) Target Code generation: Generates code by using address information of identifier
present in the table.
► A symbol table may serve the following purposes depending upon the language in hand:
 To store the names of all entities in a structured form at one place.
 To verify if a variable has been declared.
 To implement type checking, by verifying assignments and expressions in the source
code are semantically correct.
 To determine the scope of a name (scope resolution).
► The symbol table is defined as the set of Name and Value pairs.
► A compiler uses a symbol table to keep track of scope and binding information about names.
The symbol table is searched every time a name is encountered in the source text. Changes to
the table occur if a new name or new information about an existing name is discovered.
► The two most important functions of the symbol table in a compiler.
► First, they store useful information about various symbols from the source code program for
later use during code generation
111 | P a g e
► Second, they provide the type checking mechanism that determines the semantic correctness
of a program.
► A symbol-table mechanism must allow us to add new entries and find existing entries
efficiently. The two symbol-table mechanism presented in this section are linear lists and
hash tables.
► A linear list is the simplest to implement. But its performance is poor when the number of
entries is large.
► Hashing schemes provide better performance for somewhat greater programming effort and
space overhead.

7.2.1. Symbol Table Entries

► Each entry in the symbol table is associated with attributes that support the compiler in
different phases.
► Each entry in the symbol table is for the declaration of a name; the format of entries does
not have to be uniform, because the information saved about a name depends on the
usage of the name.
► Each entry can be implemented as a record consisting of a sequence of consecutive words
of memory. To keep symbol-table records uniform; it may be convenient for some of the
information about a name to be kept outside the table entry, with only a pointer to this
information stored in the record.
Use of Symbol Table
 The symbol tables are typically used in compilers. Basically compiler is a program
which scans the application program (for instance: your C program) and produces
machine code.
 During this scan compiler stores the identifiers of that application program in the
symbol table. These identifiers are stored in the form of name, value address, type.
 Here the name represents the name of identifier, value represents the value stored in an
identifier, the address represents memory location of that identifier and type represents
the data type of identifier.
 Thus compiler can keep track of all the identifiers with all the necessary information.
Items stored in Symbol Table:

112 | P a g e
  Variable names and constants
 Procedure and function names
 Literal constants and strings
 Compiler generated temporaries
 Labels in source languages
Information used by the compiler from Symbol Table:

 Data type and name

 Declaring procedures
 Offset in storage
 If structure or record then, a pointer to structure table.
 For parameters, whether parameter passing by value or by reference
 Number and type of arguments passed to function
 Base Address
7.2.2. Operations of Symbol Table
The symbol table provides the following operations can be performed on symbol table-

1) Insertion of an item in the symbol table.

2) Deletion of any item from the symbol table.
3) Searching of desired item from symbol table.
Insert ()
 Insert () operation is more frequently used in the analysis phase when the tokens are
identified and names are stored in the table.
 The insert () operation is used to insert the information in the symbol table like the unique
name occurring in the source code.
 In the source code, the attribute for a symbol is the information associated with that
symbol. The information contains the state, value, type and scope about the symbol.
 The insert () function takes the symbol and its value in the form of argument.
For example:
int x;
Should be processed by the compiler as:
insert (x, int)
113 | P a g e
 lookup ()
In the symbol table, lookup () operation is used to search a name used to determine:
 The existence of symbol in the table.
 The declaration of the symbol before it is used.
 Check whether the name is used in the scope.
 Initialization of the symbol.
 Checking whether the name is declared multiple times.
The format of lookup () function varies according to the programming language. The basic
format should match the following:
lookup (symbol)
This method returns 0 (zero) if the symbol does not exist in the symbol table. If the symbol exists
in the symbol table, it returns its attributes stored in the table.
7.2.3. Implementation of Symbol Table

► If a compiler is to handle a small amount of data, then the symbol table can be implemented
as an unordered list, which is easy to code, but it is only suitable for small tables only.
► Among all, symbol tables are mostly implemented as hash tables, where the source code
symbol itself is treated as a key for the hash function and the return value is the information
about the symbol.
► The symbol table can be implemented in the unordered list if the compiler is used to handle
the small amount of data. Following are commonly used data structures for implementing
symbol table:-
List
We use a single array or equivalently several arrays, to store names and their associated
information; new names are added to the list in the order in which they are encountered. The
position of the end of the array is marked by the pointer available, pointing to where the next
symbol table entry will go. The search for a name proceeds backwards from the end of the array
to the beginning. When the name is located the associated information can be found in the words
following next.

id1 info1 id2 info2 …….. id_n info_n

 In this method, an array is used to store names and associated information.
114 | P a g e
 A pointer “available” is maintained at end of all stored records and new names are added in
the order as they arrive
 To search for a name we start from the beginning of the list till available pointer and if not
found we get an error “use of the undeclared name”
 While inserting a new name we must ensure that it is not already present otherwise an error
occurs i.e. “Multiple defined names”
 Insertion is fast O(1), but lookup is slow for large tables O(n) on average
 The advantage is that it takes a minimum amount of space.
Linear list

► The simplest and easiest to implement data structure for a symbol table is a linear list of
records. New names are added to the list in the order in which they are encountered.
► The position of the end of the array is marked by the pointer available.
► The search for a name proceeds backwards from the end of the array to the beginning. When
the name is located, the associated information can be found in the words following next.
► If we reach the beginning of the array without finding the name, a fault occurs - an expected
name is not in the table.

The average search for the name in the symbol table is N/2 comparisons.
Advantage
It takes less space.
Insertion to the table is simple.

115 | P a g e
Linked List
 This implementation is using a linked list. A link field is added to each record.
 Searching of names is done in order pointed by the link of the link field.
 A pointer “First” is maintained to point to the first record of the symbol table.
 Insertion is fast O(1), but lookup is slow for large tables – O(n) on average
7.3. Hash Table
 In hashing scheme, two tables are maintained – a hash table and symbol table and are the
most commonly used method to implement symbol tables.
 A hash table is an array with an index range: 0 to table size – 1. These entries are pointers
pointing to the names of the symbol table.
 To search for a name we use a hash function that will result in an integer between 0 to table
size – 1.
 Insertion and lookup can be made very fast – O(1).
 The advantage is quick to search is possible and the disadvantage is that hashing is
complicated to implement.
The basic hashing scheme consists of two parts

 A hash table consisting of a fixed array of m pointers to table entries.

 Table entries organized into m separate linked lists, called buckets. Each record in the
symbol table appears on exactly one of these lists.
0
1
.
Name Info Name Info
.
.
m
Name Info
Hash Table
To enter a name into symbol table, we find out the hash value of the name by applying suitable
hash function, which maps the name into an integer between 0 to m-1, and using the value
generated by a hash function as index in a hash table, we search the list of the symbol table

116 | P a g e
records built on that hash index, if the name is not present in that list we create a record for name
and insert it at the head of the list built on that hash index.

The retrieval of the information associated with the name is done as follows.

 First, the hash value of the name is obtained and the list button on this hash value is searched
for getting the information about the name.
Binary Search Tree
 Another approach to implementing a symbol table is to use a binary search tree i.e. we add
two link fields i.e. left and right child.
 All names are created as child of the root node that always follows the property of the binary
search tree.
 Insertion and lookup are O(log2 n) on average.
Advantages of Symbol Table
1) The efficiency of a program can be increased by using symbol tables, which give quick and
simple access to crucial data such as variable and function names, data kinds, and memory
locations.
2) Better coding structure Symbol tables can be used to organize and simplify code, making it
simpler to comprehend, discover, and correct problems.
3) Faster code execution: By offering quick access to information like memory addresses,
symbol tables can be utilized to optimize code execution by lowering the number of memory
accesses required during execution.
4) Symbol tables can be used to increase the portability of code by offering a standardized
method of storing and retrieving data, which can make it simpler to migrate code between
other systems or programming languages.
5) Improved code reuse: By offering a standardized method of storing and accessing
information, symbol tables can be utilized to increase the reuse of code across multiple
projects.
6) Symbol tables can be used to facilitate easy access to and examination of a program‟s state
during execution, enhancing debugging by making it simpler to identify and correct mistakes.
Disadvantages of Symbol Table

117 | P a g e
1) Increased memory consumption: Systems with low memory resources may suffer from
symbol tables‟ high memory requirements.
2) Increased processing time: The creation and processing of symbol tables can take a long
time, which can be problematic in systems with constrained processing power.
3) Complexity: Developers who are not familiar with compiler design may find symbol tables
difficult to construct and maintain.
4) Limited scalability: Symbol tables may not be appropriate for large-scale projects or
applications that require o the management of enormous amounts of data due to their limited
scalability.
5) Upkeep: Maintaining and updating symbol tables on a regular basis can be time and resource
consuming.
6) Limited functionality: It‟s possible that symbol tables don‟t offer all the features a
developer needs, and therefore more tools or libraries will be needed to round out their
capabilities.
Applications of Symbol Table
1) Resolution of variable and function names: Symbol tables are used to identify the data
types and memory locations of variables and functions as well as to resolve their names.
2) Resolution of scope issues: To resolve naming conflicts and ascertain the range of variables
and functions, symbol tables are utilized.
3) Symbol tables, which offer quick access to information such as memory locations, are used
to optimize code execution.
4) Code generation: By giving details like memory locations and data kinds, symbol tables are
utilized to create machine code from source code.
5) Error checking and code debugging: By supplying details about the status of a program
during execution, symbol tables are used to check for faults and debug code.
6) Code organization and documentation: By supplying details about a program‟s structure,
symbol tables can be used to organize code and make it simpler to understand.
7.4. Representing Scope Information
► In the source program, every name possesses a region of validity, called the scope of that
name.
The rules in a block-structured language are as follows:
118 | P a g e
1) If a name declared within block B then it will be valid only within B.
2) If B1 block is nested within B2 then the name that is valid for block B2 is also valid for B1
unless the name's identifier is re-declared in B1.
 These scope rules need a more complicated organization of symbol table than a list of
associations between names and attributes.
 Tables are organized into stack and each table contains the list of names and their
associated attributes.
 Whenever a new block is entered then a new table is entered onto the stack. The new
table holds the name that is declared as local to this block.
 When the declaration is compiled then the table is searched for a name.
 If the name is not found in the table then the new name is inserted.
 When the name's reference is translated then each table is searched, starting from the
each table on the stack.
For example:

int x;
void f (int m) {
float x, y;
{
int i, j;
int u, v;
}
}
int g (int n)
{
bool t;
}

119 | P a g e
 Figure 7. 1: Representing scope information

120 | P a g e
 CHAPTER EIGHT
CODE GENERATION AND OPTIMIZATION

Introduction
In this chapter, Overview of Code Generation and Optimization have been studied , how to
represent DAG , understanding of flow blocks and loops, and peephole optimization Techniques
and characteristics are also well studied

After completing this chapter, the students will be able to:

 understand the concept of Code Generation and Optimization

 Develop and design DAG
 Understand the flow blocks and loops, and peephole optimization Techniques and
characteristics

8.1. Introduction to Code Generation and Optimization

► The final phase in compiler model is the code generator.
► It takes as input an intermediate representation of the source program and produces as
output an equivalent target program.
► The code generation techniques presented below can be used whether or not an optimizing
phase occurs before code generation.

Figure 8. 1: Position of code generator

8.1.1. Issues in the Design of a Code Generator

► The following issues arise during the code generation phase:
1) Input to code generator
2) Target program
121 | P a g e
 3) Memory management
4) Instruction selection
5) Register allocation
6) Evaluation order
Input to the Code Generator

► The input to the code generation consists of the intermediate representation of the source
program produced by front end, together with information in the symbol table to
determine run-time addresses of the data objects denoted by the names in the
intermediate representation.
► There are several choices for the Intermediate language representation that can be:-
♦ Linear representation such as postfix notation
♦ Three address representation such as quadruples
♦ Virtual machine representation such as stack machine code
♦ Graphical representations such as syntax trees and DAGs.
► Prior to code generation, the front end must be scanned, parsed and translated into
intermediate representation along with necessary type checking.
► Therefore, input to code generation is assumed to be error-free.
► The code generation phase can therefore proceed on the assumption that its input is free
of errors.
► In some compilers, this kind of semantic checking is done together with code generation.
Target Programs

► The output of the code generator is the target program, like the intermediate code, this
output may be take on a variety of forms:-

a) Absolute machine language:- It can be placed in a fixed memory location and can be
executed immediately.

b) Relocatable machine language:- It allows subprograms to be compiled separately. A

set of relocatable object modules can be linked together and loaded for execution by a
linking loader.

122 | P a g e
 c) Assembly language:- Code generation is made easier. Producing an AL program as
output makes the process of code generation somewhat easier. We use assembly code
as the target language for readability.

Memory management

► Names in the source program are mapped to addresses of data objects in run-time
memory by the front end and code generator.

► It makes use of symbol table, that is, a name in a three-address statement refers to a
symbol-table entry for the name.

► Labels in three-address statements have to be converted to addresses of instructions.

Instruction Selection

► The instructions of target machine should be complete and uniform.

► The uniformity and completeness of the instruction set are important factors.

► If the target machine does not support each data type in a uniform manner, then each
exception to the general rule requires special handling.

► Instruction speeds and machine idioms are other important factors when efficiency of
target program is considered. That means; if we do not care about the efficiency of the
target program, instruction selection is straightforward.

► The quality of the generated code is determined by its speed and size.

► For example, every three-address statement of the form x: =y+z where x, y, and z are
statically allocated, can be translated into the code sequence

 MOV y, RO /* Load y into register RO */

 ADD z, RO /* add z to RO */

 MOV RO, x /* store RO into x */

123 | P a g e
 ► Unfortunately, this kind of statement-by-statement code generation often produces poor
code. For example, the sequence of statements

► Here fourth statement is redundant.

► So, it can be eliminated.

Register Allocation

► Instructions involving register operands are usually shorter and faster than those
involving operands in memory.
► Therefore, efficient utilization of registers is particularly important in generating good
code.
► The use of registers is often subdivided into two sub problems:
♦ During register allocation, we select the set of variables that will reside in
registers at a point in the program is selected.
♦ During a subsequent register assignment phase, we pick the specific register that
a variable will reside in.
Evaluation Order

► The order in which computations are performed can affect the efficiency of the target
code.
► Some computation orders require fewer registers to hold intermediate results than others.

► But, Picking up a best order is another difficult problem.

124 | P a g e
 ► Initially, we shall avoid the problem by generating code for the three-address statements
in the order in which they have been produced-by the intermediate code generator.
8.2. The Target Machine
► Familiarity with the target machine and its instruction set is a prerequisite for designing a
good code generator. The target computer is a byte-addressable machine with 4 bytes to a
word.
► It has n general-purpose registers, R0, R1, . . . , Rn-1.
► It has two-address instructions of the form: op source, destination where, op is an op-
code, source & destination are data fields.
► It has the following op-codes:-

 MOV (move source to destination)

 ADD (add source to destination)
 SUB (subtract source from destination)
8.3. Run-time Storage Management
► Information needed during an execution of a procedure is kept in a block of storage
called an activation record, which includes storage for names local to the procedure.
► The two standard storage allocation strategies are:-
1) Static allocation: - the position of an activation record in memory is fixed at
compile time.
2) Stack allocation:- a new activation record is pushed onto the stack for each
execution of a procedure. The record is popped when the activation ends.
8.4. Basic Blocks and Flow Graphs
8.4.1. Basic Blocks
► A basic block is a sequence of consecutive statements in which flow of control enters at
the beginning and leaves at the end without halt or possibility of branching except at the
end.
► It is a sequence of the intermediate code with a single entry and single exit.
► The following sequence of three-address statements forms a basic block.

125 | P a g e
 t1: a * a
t 2 : a * b
t 3 : 2 * t 2
t 4 : t1  t 3
t 5 : b * b
t 6 : t 4  t 5

► A name in a basic block is said to be live at a given point if its value is used after that
point in the program or in basic block.

Basic Block Construction:

Algorithm: Partition basic blocks

Input: A sequence of three-address statements

Output: A list of basic blocks with each three-address statement in exactly one block

Method:

1. We first determine the set of leaders, the first statements of basic blocks.
the rules use are of the following:
a. The first statement is a leader.
b. Any statement that is the target of a conditional or unconditional
goto is a leader.
c. Any statement that immediately follows a goto or conditional goto
statement is a leader.
2. For each leader, its basic block consists of the leader and all statements up
to but not including the next leader or the end of the program.

Transformations on Basic Blocks

► A basic block computes a set of expressions. These expressions are the values of the
names live on exit from the block.

126 | P a g e
 ► Two basic blocks are said to be equivalent if they compute the same set of expressions.

► A number of transformations can be applied to a basic block without changing the set of
expressions computed by the block. This is for optimizing the code.

► There are two important classes of transformations that can be applied to basic blocks;

1) Structure Preserving Transformations and

2) Algebraic Transformations

3. Structure Preserving Transformations

► The primary structure-preserving transformations on basic blocks are:

1) Common subexpression elimination

2) Dead code elimination

3) Renaming of temporary variables

4) Interchange of two independent adjacent statements

► Assumption: basic blocks have no arrays, pointers, or procedure calls

Common subexpression elimination

a : b  c 
 a:=b+c
b : a  d b:=a-d
c : b  c c:=b+c
d :ad d:=b

► Since the second and fourth expressions compute the same expression, namely, b + c – d,
and hence this basic block may be transformed into the equivalent block.

► Note that although the first and third statements in the above appear to have the same
expression on the right, the second statement redefines b. therefore, the value of b in the
third statement is different from the value of b in the first, and the first and third
statements do not compute the same expression.
127 | P a g e
Dead-code elimination

 Suppose x is dead, that is, never subsequently used, at the point where the statement x : =
y + z appears in a basic block.

 Then this statement may be safely removed without changing the value of the basic
block.

Renaming temporary variable

 Suppose we have a statement t: = b + c (t is a temporary) can be changed to u: = b + c (u

is a new temporary) and all uses of this instance of t can be changed to u without
changing the value of the basic block.

 Such a block is called a normal-form block.

Interchange of statements

► Suppose a block has the following two adjacent statements:

t1: b  c
t 2 : x  y

► Then we can interchange the two statements in the basic block when the value of t1 does
not affect the value of t2.

4. Algebraic Transformations

► Algebraic transformations can be used to change the set of expressions computed by a

basic block into an algebraically equivalent set.

► This includes simplify expressions or replace expensive operations by cheaper ones.

Examples:

► The exponential operator in the statement x: = y * * 2 usually requires a function call to

implement.
128 | P a g e
 ► This statement can be replaced by the cheaper, but equivalent statement x: = y * y.

8.4.2. Flow Graphs

► Flow graph is a directed graph containing the flow-of-control information for the set of
basic blocks making up a program.

► A graph representation of three-address statements is called a flow graph.

► The nodes of the flow graph are basic blocks. It has a distinguished initial; it is the block
whose leader is the first statement.

► There is a directed edge from block B1 to block B2 if B2 can immediately follow B1 in

some execution sequence;

 There is a conditional or unconditional jump from the last statement of B1 to the

first statement of B2, or

 B2 immediately follows B1 in the natural order of the program, and B1 does not
end in an unconditional jump.

► We say that B1 is a predecessor of B2, and B2 is a successor of B1.

► E.g.; Flow graph for the vector dot product is given as follows:

129 | P a g e
 Figure 8. 2:Flow graph for the vector dot product

 B1 is the initial node.

 B2 immediately follows B1, so there is an edge from B1 to B2.

 The target of jump from last statement of B1 is the first statement B2, so there is
an edge from B1 (last statement) to B2 (first statement).

 B1is the predecessor of B2, and B2 is a successor of B1

8.4.3. Loops
► For example, in the above Figure 8.2 there is one loop, consisting of block B2.

► A loop is a collection of nodes in a flow graph such that

1) All nodes in the collection are strongly connected; that is, from any node in the
loop to any other, there is a path of length one or more, wholly within the loop,
and

130 | P a g e
 2) The collection of nodes has a unique entry, that is, a node in the loop such that the
only way to reach a node of the loop from a node outside the loop is to first go
through the entry.

► A loop that contains no other loops is called an inner loop.

8.5. A Simple Code Generator

 The code generation strategy in this section generates target code for a sequence of three
address statement and effectively uses registers to store operands of the statements.
 For example: consider the three-address statement a: = b+c
 It can have the following sequence of codes:
ADD Rj, Ri Cost=1 // if Ri contains b and Rj contains c
(or)
ADD c, Ri Cost=2 // if c is in a memory location
(or)
MOV c, Rj Cost=3 //move c from memory to Rj and add
ADD Rj, Ri

8.6. Register and Address Descriptors

► The code-generation algorithm uses descriptors to keep track of register contents and
addresses for names.
1) A register descriptor is used to keep track of what is currently in each register. It is
consulted whenever a new register is needed.
 We assume that register descriptors show that initially all the registers are empty.
2) An address descriptor is used to keeps track of the location (or locations) where the
current value of the name can be found at run time.
 The location might be a register, a stack location, a memory address, or some set
of these.
8.7. The DAG Representation of Basic Blocks
► Directed acyclic graphs (DAGs) are useful data structures for implementing
transformations on basic blocks.

131 | P a g e
 ► It gives a picture of how the value computed by a statement is used in subsequent
statements.
► It provides a good way of determining common sub- expressions.
 A DAG for a basic block is a directed acyclic graph with the following labels on nodes:
1) Leaves are labeled by unique identifiers, either variable names or constants.
2) Interior nodes are labeled by an operator symbol.
3) Nodes are also optionally given a sequence of identifiers for labels to store the
computed values.
8.8. The Principal Sources of Optimization
► A transformation of a program is called local if it can be performed by looking only at the
statements in a basic block; otherwise, it is called global.

► Many transformations can be performed at both the local and global level.

► Local transformations are usually performed first.

Function Preserving Transformations

► A Compiler can improve a program without changing the function it computes.
1) Common Sub Expression Elimination,
2) Copy Propagation
3) Dead Code Elimination
4) Constant Folding
Common Sub expressions
 An occurrence of an expression E is called a common sub expression if E was previously
computed, and the values of variables in E have not changed since the previous
computation, we can avoid re-computing the expression if we can use the previously
computed value.

132 | P a g e
 t 6 : 4 * i
x : a[t 6]
t 6 : 4 * i
t 7 : 4 * i x : a[t 6]
t 8 : 4 * j t 8 : 4 * j
t 9 : a[t 8] t 9 : a[t 8]
a[t 7] : t 9 a[t 6] : t 9
t10 : 4 * j a[t 8] : x
a[t10] : x
goto B2
goto B2

A) Before B) After

Copy Propagation

 Copy-propagation means use of one variable instead of another.

For example;

x=PI;
…
a=x*r*r;
► The optimization using copy propagation can be done as follows
a=PI * r * r
► Here the variable x is eliminated.

Dead Code Elimination

► A variable is live at a pint in a program if its value can be used subsequently; otherwise,
it is dead at that point.
► A related idea is dead or useless code, statements that compute values that never get
used.
133 | P a g e
 Example:
i:=0;
if (i==1) {
a=b+5;
}
 Here if statement is a dead code because this condition will never get satisfied.
 Hence if statement can be eliminated.
Constant folding

► The substitution of values for names whose values are constant

 A=3.14157/2 can be replaced by

 A=1.570 there by eliminate the division operation.

Loop Optimization

► The running time of a program may be improved if we decrease the number of

instructions in an inner loop, even if we increase the amount of code outside that loop.
► Three techniques for loop optimization are
1) Code Motion
2) induction-variable elimination
3) reduction in strength
Code Motion
► An important modification that decreases the amount of code in a loop is code motion.
► This transformation takes an expression that yields the same result independent of the
number of times a loop is executed and places the expression before the loop.
For Example,
While (i<=n-2) {
------
}
► Evaluation of n-2 is a loop invariant computation in the above while statements. So this
can be placed outside the loop.

134 | P a g e
 ► Code motion will result in the equivalent of
 t=n-2
 While (i<=t)

Reduction in Strength

► Reduction in strength replaces expensive operations by equivalent cheaper ones on the

target machine.
► Certain machine instructions are considerably cheaper than others and can often be used
as special cases of more expensive operators.
► For example; x² is invariably cheaper to implement as x*x than as a call to an
exponentiation routine.
► Fixed point multiplication or division by a power of two is cheaper to implement as a
shift.
► Floating point division by a constant can be implemented as multiplication by a constant,
which may be cheaper.
8.9. Peephole Optimization
► A statement-by-statement code-generation strategy often produces target code that
contains redundant instructions and sub optional constructs.
► The quality of such target code can be improved by applying "optimizing"
transformations to the target program.
► A simple but effective technique for locally improving the target code is peephole
optimization.
► A method for trying to improve the performance of the target program by examining a
short sequence of target instructions (called the peephole) and replacing these
instructions by a shorter or faster sequence, whenever possible.
Characteristic of Peephole Optimizations
 Redundant-instruction elimination
 Flow-of-control optimizations
 Algebraic simplifications
 Use of machine idioms
135 | P a g e
 References
1. Alfred Aho, Ravi Sethi, [Link] Ullman D. “COMPILERS PRINCIPLES,
TECHINQUES AND TOOLS “, Addison- Wesley, 1988.
2. Allen Holub l. “Compiler Design in C”, Prentice Hall of India. 1990.
3. Modern Compiler implementation in C , - Andrew [Link] Cambridge University
Press.
4. Compilers, Principle, Techniques, and Tools. – Alfred.V Aho, Monica [Link], Ravi
Sethi, Jeffrey D. Ullman ; 2nd Edition, Pearson Education.

136 | P a g e