Phases of a Compiler
the compiler is divided into two major phases-
1. Analysis phase- language dependent but machine independent
2. Synthesis phase-language independent but machine dependent
1. Lexical Analyzer –
It is also called a scanner. It takes the output of the preprocessor as the
input which is in a pure high-level language. It reads the characters from
the source program and groups them into lexemes (sequence of
characters that “go together”). Each lexeme corresponds to a token.
Tokens are defined by regular expressions which are understood by the
lexical analyzer. It also removes lexical errors (e.g., erroneous
characters), comments, and white space.
2. It is the first phase of a compiler is known as Scanner (It’s scan the
program).
3. Lexical Analyzer will divide the program into some meaningful strings
which are known as a token.
In the first phase, the compiler doesn’t check the syntax. So, here this
program as input to the lexical analyzer and convert it into the tokens. So,
tokenization is one of the important functioning of lexical analyzer. The
total number of token for this program is 26.
Types of token as following –
1. Identifier
2. Keyword
3. Operator
4. Constants
5. Special symbol(@, $, #)
2. Syntax Analyzer – It is sometimes called a parser. It constructs the parse
tree. It takes all the tokens one by one and uses Context-Free Grammar
to construct the parse tree.
Syntax Analysis or Parsing is the second phase, i.e. after lexical analysis.
It checks the syntactical structure of the given input, i.e. whether the given
input is in the correct syntax (of the language in which the input has been
written) or not. It does so by building a data structure, called a Parse tree
or Syntax tree. The parse tree is constructed by using the context free
Grammar of the language and the input string. If the given input string can
be produced with the help of the syntax tree (in the derivation process),
the input string is found to be in the correct syntax. if not, the error is
reported by the syntax analyzer.
The main goal of syntax analysis is to create a parse tree or abstract
syntax tree (AST) of the source code, which is a hierarchical
representation of the source code that reflects the grammatical structure
of the program.
[Link] Analyzer – It verifies the parse tree, whether it’s meaningful or
not. It furthermore produces a verified parse tree. It also does type checking,
Label checking, and Flow control checking.
The third phase of a compiler is semantic analysis. This phase checks
whether the code is semantically correct.
The compiler performs type checking, which ensures that variables are used
correctly and that operations are performed on compatible data types. The
compiler also checks for other semantic errors, such as undeclared variables
and incorrect function calls.
4. Intermediate Code Generator – It generates intermediate code,
which is a form that can be readily executed by a machine We have
many popular intermediate codes. Example – Three address codes
etc. Intermediate code is converted to machine language using the last
two phases which are platform dependent. To build a new compiler
we don’t need to build it from scratch. We can take the intermediate
code from the already existing compiler and build the last two parts.
5. Code Optimizer – It transforms the code so that it consumes fewer
resources and produces more speed. The meaning of the code being
transformed is not altered. Optimization can be categorized into two
types: machine-dependent and machine-independent. 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. Target Code Generator – The main purpose of the Target Code
generator is to write a code that the machine can understand and also
register allocation, instruction selection, etc. The output is dependent
on the type of assembler. This is the final stage of compilation. The
optimized code is converted into relocatable machine code which then
forms the input to the linker and loader.
Symbol Table – It is a data structure being used and maintained by the
compiler, consisting of all the identifier’s names along with their types. It
helps the compiler to function smoothly by finding the identifiers quickly.
The analysis of a source program is divided into mainly three phases. They
are:
1. Linear Analysis-
This involves a scanning phase where the stream of characters is read
from left to right. It is then grouped into various tokens having a collective
meaning.
2. Hierarchical Analysis-
In this analysis phase, based on a collective meaning, the tokens are
categorized hierarchically into nested groups.
3. Semantic Analysis-
This phase is used to check whether the components of the source
program are meaningful or not.
Derivation Tree
Derivation tree is a graphical representation for the derivation of the given production rules
for a given CFG. It is the simple way to show how the derivation can be done to obtain some
string from a given set of production rules. The derivation tree is also called a parse tree.
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.
A parse tree contains the following properties:
1. The root node is always a node indicating start symbols.
2. The derivation is read from left to right.
3. The leaf node is always terminal nodes.
4. The interior nodes are always the non-terminal nodes.
1. E = E + E
2. E = E * E
3. E = a | b | c
Input
1. a * b + c
Step 1: