Phases of a Compiler

There are two phases of compilers, namely the Analysis phase and Synthesis
phase. The analysis phase creates an intermediate representation from the
given source code. The synthesis phase creates an equivalent target program
from the intermediate representation.
A compiler is a software program that converts the high-level source code
written in a programming language into low-level machine code that can be
executed by the computer hardware. The process of converting the source code
into machine code involves several phases or stages, which are collectively
known as the phases of a compiler. The typical phases of a compiler are:
1. Lexical Analysis: The first phase of a compiler is lexical analysis, also known
as scanning. This phase reads the source code and breaks it into a stream
of tokens, which are the basic units of the programming language. The
tokens are then passed on to the next phase for further processing.
2. Syntax Analysis: The second phase of a compiler is syntax analysis, also
known as parsing. This phase takes the stream of tokens generated by the
lexical analysis phase and checks whether they conform to the grammar of
the programming language. The output of this phase is usually an Abstract
Syntax Tree (AST).
3. Semantic Analysis: The third phase of a compiler is semantic analysis. This
phase checks whether the code is semantically correct, i.e., whether it
conforms to the language’s type system and other semantic rules.
4. Intermediate Code Generation: The fourth phase of a compiler is
intermediate code generation. This phase generates an intermediate
representation of the source code that can be easily translated into machine
code.
5. Optimization: The fifth phase of a compiler is optimization. This phase
applies various optimization techniques to the intermediate code to improve
the performance of the generated machine code.
6. Code Generation: The final phase of a compiler is code generation. This
phase takes the optimized intermediate code and generates the actual
machine code that can be executed by the target hardware.
In summary, the phases of a compiler are: lexical analysis, syntax analysis,
semantic analysis, intermediate code generation, optimization, and code
generation.
Lexical Analysis:
Lexical analyzer phase is the first phase of compilation process. It takes source code as
input. It reads the source program one character at a time and converts it into meaningful
lexemes. Lexical analyzer represents these lexemes in the form of tokens.

Syntax Analysis
Syntax analysis is the second phase of compilation process. It takes tokens as input and
generates a parse tree as output. In syntax analysis phase, the parser checks that the
expression made by the tokens is syntactically correct or not.
Semantic Analysis
Semantic analysis is the third phase of compilation process. It checks whether the parse
tree follows the rules of language. Semantic analyzer keeps track of identifiers, their types
and expressions. The output of semantic analysis phase is the annotated tree syntax.

Intermediate Code Generation

In the intermediate code generation, compiler generates the source code into the
intermediate code. Intermediate code is generated between the high-level language and
the machine language. The intermediate code should be generated in such a way that
you can easily translate it into the target machine code.

Code Optimization
Code optimization is an optional phase. It is used to improve the intermediate code so
that the output of the program could run faster and take less space. It removes the
unnecessary lines of the code and arranges the sequence of statements in order to speed
up the program execution.

Code Generation
Code generation is the final stage of the compilation process. It takes the optimized
intermediate code as input and maps it to the target machine language. Code generator
translates the intermediate code into the machine code of the specified computer.
Compiler Passes
Pass is a complete traversal of the source program. Compiler has two passes to traverse
the source program.

Multi-pass Compiler
o Multi pass compiler is used to process the source code of a program several times.
o In the first pass, compiler can read the source program, scan it, extract the tokens and
store the result in an output file.
o In the second pass, compiler can read the output file produced by first pass, build the
syntactic tree and perform the syntactical analysis. The output of this phase is a file that
contains the syntactical tree.
o In the third pass, compiler can read the output file produced by second pass and check
that the tree follows the rules of language or not. The output of semantic analysis phase
is the annotated tree syntax.
o This pass is going on, until the target output is produced.

One-pass Compiler
o One-pass compiler is used to traverse the program only once. The one-pass compiler
passes only once through the parts of each compilation unit. It translates each part into
its final machine code.
o In the one pass compiler, when the line source is processed, it is scanned and the token is
extracted.
o Then the syntax of each line is analyzed and the tree structure is build. After the semantic
part, the code is generated.
o The same process is repeated for each line of code until the entire program is compiled.

Bootstrapping
o Bootstrapping is widely used in the compilation development.
o Bootstrapping is used to produce a self-hosting compiler. Self-hosting compiler is
a type of compiler that can compile its own source code.
 o Bootstrap compiler is used to compile the compiler and then you can use this
compiled compiler to compile everything else as well as future versions of itself.

A compiler can be characterized by three languages:

1. Source Language
2. Target Language
3. Implementation Language

The T- diagram shows a compiler SCIT for Source S, Target T, implemented in I.

Follow some steps to produce a new language L for machine A:

1. Create a compiler SCAA for subset, S of the desired language, L using language "A" and
that compiler runs on machine A.

2. Create a compiler LCSA for language L written in a subset of L.

3. Compile LCSA using the compiler SCAA to obtain LCAA. LCAA is a compiler for language L,
which runs on machine A and produces code for machine A.
Finite state machine

o Finite state machine is used to recognize patterns.

o Finite automata machine takes the string of symbol as input and changes its state
accordingly. In the input, when a desired symbol is found then the transition occurs.
o While transition, the automata can either move to the next state or stay in the same
state.
o FA has two states: accept state or reject state. When the input string is successfully
processed and the automata reached its final state then it will accept.

A finite automata consists of following:

Q: finite set of states

∑: finite set of input symbol
q0: initial state
F: final state
δ: Transition function

Transition function can be define as

δ: Q x ∑ →Q
 FA is characterized into two ways:
1. DFA (finite automata)
2. NDFA (non deterministic finite automata)

DFA
DFA stands for Deterministic Finite Automata. Deterministic refers to the uniqueness of
the computation. In DFA, the input character goes to one state only. DFA doesn't accept
the null move that means the DFA cannot change state without any input character.

DFA has five tuples {Q, ∑, q0, F, δ}

Q: set of all states

∑: finite set of input symbol where δ: Q x ∑ →Q
q0: initial state
F: final state
δ: Transition function

Example
See an example of deterministic finite automata:

1. Q = {q0, q1, q2}

2. ∑ = {0, 1}
3. q0 = {q0}
4. F = {q3}
 NDFA
NDFA refer to the Non Deterministic Finite Automata. It is used to transit the any number
of states for a particular input. NDFA accepts the NULL move that means it can change
state without reading the symbols.

NDFA also has five states same as DFA. But NDFA has different transition function.

Transition function of NDFA can be defined as:

δ: Q x ∑ →2Q

1. Q = {q0, q1, q2}

2. ∑ = {0, 1}
3. q0 = {q0}
4. F = {q3}

Regular expression
o Regular expression is a sequence of pattern that defines a string. It is used to denote
regular languages.
o It is also used to match character combinations in strings. String searching algorithm used
this pattern to find the operations on string.
o In regular expression, x* means zero or more occurrence of x. It can generate {e, x, xx, xxx,
xxxx,.....}
 o In regular expression, x+ means one or more occurrence of x. It can generate {x, xx, xxx,
xxxx,.....}

Operations on Regular Language

The various operations on regular language are:

Union: If L and M are two regular languages then their union L U M is also a union.

1. L U M = {s | s is in L or s is in M}

Intersection: If L and M are two regular languages then their intersection is also an
intersection.

1. L ⋂ M = {st | s is in L and t is in M}

Kleene closure: If L is a regular language then its kleene closure L1* will also be a regular
language.

1. L* = Zero or more occurrence of language L.

Example
Write the regular expression for the language:

L = {abn w:n ≥ 3, w ∈ (a,b)+}

Solution:
The string of language L starts with "a" followed by atleast three b's. Itcontains atleast one
"a" or one "b" that is string are like abbba, abbbbbba, abbbbbbbb, abbbb.....a

So regular expression is:

r= ab3b* (a+b)+

Here + is a positive closure i.e. (a+b)+ = (a+b)* - ∈

Optimization of DFA
 To optimize the DFA you have to follow the various steps. These are as follows:

Step 1: Remove all the states that are unreachable from the initial state via any set of the
transition of DFA.

Step 2: Draw the transition table for all pair of states.

Step 3: Now split the transition table into two tables T1 and T2. T1 contains all final states
and T2 contains non-final states.

Step 4: Find the similar rows from T1 such that:

1. δ (q, a) = p
2. δ (r, a) = p

That means, find the two states which have same value of a and b and remove one of
them.

Step 5: Repeat step 3 until there is no similar rows are available in the transition table T1.

Step 6: Repeat step 3 and step 4 for table T2 also.

Step 7: Now combine the reduced T1 and T2 tables. The combined transition table is the
transition table of minimized DFA.
 LEX
o Lex is a program that generates lexical analyzer. It is used with YACC parser generator.
o The lexical analyzer is a program that transforms an input stream into a sequence of
tokens.
o It reads the input stream and produces the source code as output through implementing
the lexical analyzer in the C program.

The function of Lex is as follows:

o Firstly lexical analyzer creates a program lex.1 in the Lex language. Then Lex compiler runs
the lex.1 program and produces a C program [Link].c.
o Finally C compiler runs the [Link].c program and produces an object program [Link].
o [Link] is lexical analyzer that transforms an input stream into a sequence of token

Lex file format

A Lex program is separated into three sections by %% delimiters. The formal of Lex source
is as follows:

1. { definitions }
2. %%
3. { rules }
4. %%
5. { user subroutines }

Definitions include declarations of constant, variable and regular definitions.

Rules define the statement of form p1 {action1} p2 {action2}....pn {action}.

Where pi describes the regular expression and action1 describes the actions what action
the lexical analyzer should take when pattern pi matches a lexeme.

User subroutines are auxiliary procedures needed by the actions. The subroutine can be
loaded with the lexical analyzer and compiled separately.

ACC
o YACC stands for Yet Another Compiler Compiler.
o YACC provides a tool to produce a parser for a given grammar.
o YACC is a program designed to compile a LALR (1) grammar.
o It is used to produce the source code of the syntactic analyzer of the language
produced by LALR (1) grammar.
o The input of YACC is the rule or grammar and the output is a C program.

These are some points about YACC:

Input: A CFG- file.y

Output: A parser [Link].c (yacc)

o The output file "[Link]" contains the parsing tables.

o The file "[Link].h" contains declarations.
o The parser called the yyparse ().
o Parser expects to use a function called yylex () to get tokens.
 Derivation
Derivation is a sequence of production rules. It is used to get the input string through
these production rules. During parsing we have to take two decisions. These are as follows:

o We have to decide the non-terminal which is to be replaced.

o We have to decide the production rule by which the non-terminal will be replaced.

We have two options to decide which non-terminal to be replaced with production rule.

Left-most Derivation
In the left most derivation, the input is scanned and replaced with the production rule
from left to right. So in left most derivatives we read the input string from left to right.

Example:
Production rules:

1. S = S + S
2. S = S - S
3. S = a | b |c

Input:

a - b + c

The left-most derivation is:

1. S = S + S
2. S = S - S + S
3. S = a - S + S
4. S = a - b + S
5. S = a - b + c

Right-most Derivation
In the right most derivation, the input is scanned and replaced with the production rule
from right to left. So in right most derivatives we read the input string from right to left.
 Example:
1. S = S + S
2. S = S - S
3. S = a | b |c

Input:

a - b + c

The right-most derivation is:

1. S = S - S
2. S = S - S + S
3. S = S - S + c
4. S = S - b + c
5. S = a - b + c

Parse tree
o Parse tree is the graphical representation of symbol. The symbol can be terminal or non-
terminal.
o In parsing, the string is derived using the start symbol. The root of the parse tree is that
start symbol.
o It is the graphical representation of symbol that can be terminals or non-terminals.
o Parse tree follows the precedence of operators. The deepest sub-tree traversed first. So,
the operator in the parent node has less precedence over the operator in the sub-tree.

The parse tree follows these points:

o All leaf nodes have to be terminals.
o All interior nodes have to be non-terminals.
o In-order traversal gives original input string.
 Example:
Production rules:

1. T= T + T | T * T
2. T = a|b|c

Input:

a * b + c
Step 1:

Step 2:

Step 3:
 Step 4:

Step 5:

Ambiguity
A grammar is said to be ambiguous if there exists more than one leftmost derivation or
more than one rightmost derivative or more than one parse tree for the given input string.
If the grammar is not ambiguous then it is called unambiguous.

Example:
1. S = aSb | SS
2. S = ∈

For the string aabb, the above grammar generates two parse trees:
If the grammar has ambiguity then it is not good for a compiler construction. No method
can automatically detect and remove the ambiguity but you can remove ambiguity by re-
writing the whole grammar without ambiguity.

Capabilities of CFG
There are the various capabilities of CFG:

o Context free grammar is useful to describe most of the programming languages.

o If the grammar is properly designed then an efficientparser can be constructed
automatically.
o Using the features of associatively & precedence information, suitable grammars
for expressions can be constructed.
o Context free grammar is capable of describing nested structures like: balanced
parentheses, matching begin-end, corresponding if-then-else's & so on.

Unit-I: Introduction to Compiler (Short Question)

Q1. State any two reasons as a why phases of compiler should be grouped.

Ans. Two reasons for phases of compiler to be grouped are:

 1. It helps in the creation of compilers for various source languages.

 2. Several compilers share similar front end phases.
Q2. Discuss the challenges in compiler design.

Ans. Challenges in compiler design are :

 i. There must be no errors in the compiler.

 ii. It must provide accurate machine code that executes quickly.
 iii. The speed of the compiler itself, i.e., the ratio of the compilation time to the
programme size, must be favourable.
 iv. It has to be transportable (i.e., modular, supporting separate compilation).
 v. It ought to display error and diagnostic messages.

Q3. What is translator ?

Ans. A translator transforms a programme written in a source language into a

programme written in a target language.

Q4. Differentiate between compiler and assembler.

Ans.

S. No. Compiler Assembler

1. High level language is transformed into machine language. It transforms machine language from assem

2. Debugging is slow. Debugging is fast.

 3. It is used by C, C++. It is used by assembly language.

Q5. What do you mean by regular expression ?

Ans. Mathematical symbolisms known as regular expressions are used to characterize

a set of strings in a particular language. It offers simple and practical notation for
expressing tokens.

Q6. Differentiate between compilers and interpreters.

Ans.

S.
Compiler Interpreter
No.

It scans through the entire source code and lists each It scans each line individually, and if there are any sy
1.
syntax error as it is found. programme immediately stops running.

The compiler’s output is saved in a file. Hence, the file The machine code that an interpreter generates is no
2.
need not be continuously compiled. As a result, each time, we must interpret the file.

3. It takes less time to execute. It takes more time to execute.

Q7. What is cross compiler ?

Ans. A cross compiler is a compiler that has the ability to generate executable code for
platforms other than the one it is currently executing on.

Q8. How YACC can be used to generate parser ?

Ans. 1. YACC is a tool which will produce a parser for a given grammar.

2. A (LALRO) grammar compilation software called YACC is used to generate source

code. As a result, a parser is created using it.

Q9. Write regular expression to describe a language consist of strings made of

even number a and b.

Ans. Language of DFA which accept even number of a and b is given by:

Regular expression for above DFA:

(aa + bb + (ab + aa aa + bb)* (ab + ba))*

Q10. Write a CF grammar to represent palindrome.

Ans.

Q11. List the features of good compiler.

Ans. Features of good compiler are:

 i. It takes less time to compile the vast amount of code.

 ii. The source language can be translated into another language with decreased
memory usage.
 iii. If the source programme needs to be amended frequently, it can only compile
the modified code segment.
 iv. Effective compilers work closely with the operating system while addressing
hardware interrupts.

Q12. What are the two parts of a compilation ? Explain briefly.

Ans. Two parts of a compilation are:

 1. Analysis part: It separates the source programme into its component parts
and produces a middle representation of the source programme.
 2. Synthesis part: It constructs the desire target program from the intermediate
representation.

Q13. What are the classifications of a compiler ?

Ans. Classification of a compiler:

 1. Single pass compiler

 2. Two pass compiler
 3. Multiple pass compiler

1. What is Compiler? Design the Analysis and Synthesis Model of Compiler.

2. Write down the five properties of compiler.

3. What is translator? Write down the steps to execute a program.

4. Discuss all the phases of compiler with a with a diagram.

5. Write a short note on:

a. YACC

b. Pass

c. Bootstrapping

d. LEX Compiler

e. Tokens, Patterns and Lexemes

6. Write the steps to convert Non-Deterministic Finite Automata (NDFA) into Deterministic Finite

Automata (DFA).