Phases of Compiler – Compiler Design

The structure of compiler consists of two parts:

Analysis part

• Analysis part breaks the source program into constituent pieces and imposes a grammatical structure on them which further uses this structure to create an intermediate representation of the source program.

• It is also termed as front end of compiler.

• Information about the source program is collected and stored in a data structure called symbol table.

Synthesis part

• Synthesis part takes the intermediate representation as input and transforms it to the target program.

• It is also termed as back end of compiler.

The design of compiler can be decomposed into several phases, each of which converts one form of source program into another.

The different phases of compiler are as follows:

1. Lexical analysis

2. Syntax analysis

3. Semantic analysis

4. Intermediate code generation

5. Code optimization

6. Code generation

All of the aforementioned phases involve the following tasks:

• Symbol table management.

• Error handling.

Lexical Analysis

• Lexical analysis is the first phase of compiler which is also termed as scanning.

• Source program is scanned to read the stream of characters and those characters are grouped to form a sequence called lexemes which produces token as output.

• Token: Token is a sequence of characters that represent lexical unit, which matches with the pattern, such as keywords, operators, identifiers etc.

• Lexeme: Lexeme is instance of a token i.e., group of characters forming a token. ,

• Pattern: Pattern describes the rule that the lexemes of a token takes. It is the structure that must be matched by strings.

• Once a token is generated the corresponding entry is made in the symbol table.

Input: stream of characters

Output: Token

Token Template: <token-name, attribute-value>

(eg.) c=a+b*5;

                                                 Lexemes and tokens

Hence, <id, 1><=>< id, 2>< +><id, 3 >< * >< 5>

Syntax Analysis

• Syntax analysis is the second phase of compiler which is also called as parsing.

• Parser converts the tokens produced by lexical analyzer into a tree like representation called parse tree.

• A parse tree describes the syntactic structure of the input.

• Syntax tree is a compressed representation of the parse tree in which the operators appear as interior nodes and the operands of the operator are the children of the node for that operator.

Input: Tokens

Output: Syntax tree

Semantic Analysis

• Semantic analysis is the third phase of compiler.

• It checks for the semantic consistency.

• Type information is gathered and stored in symbol table or in syntax tree.

• Performs type checking.

Intermediate Code Generation

• Intermediate code generation produces intermediate representations for the source program which are of the following forms:

     o Postfix notation

     o Three address code

     o Syntax tree

Most commonly used form is the three address code.

        t₁ = inttofloat (5)

        t₂ = id₃* tl

        t₃ = id₂ + t₂

        id₁ = t₃

Properties of intermediate code

• It should be easy to produce.

• It should be easy to translate into target program.

Code Optimization

• Code optimization phase gets the intermediate code as input and produces optimized intermediate code as output.

• It results in faster running machine code.

• It can be done by reducing the number of lines of code for a program.

• This phase reduces the redundant code and attempts to improve the intermediate code so that faster-running machine code will result.

• During the code optimization, the result of the program is not affected.

• To improve the code generation, the optimization involves

       o Deduction and removal of dead code (unreachable code).

       o Calculation of constants in expressions and terms.

       o Collapsing of repeated expression into temporary string.

       o Loop unrolling.

       o Moving code outside the loop.

       o Removal of unwanted temporary variables.

                   t₁ = id₃* 5.0

                   id₁ = id₂ + t₁

Code Generation

• Code generation is the final phase of a compiler.

• It gets input from code optimization phase and produces the target code or object code as result.

• Intermediate instructions are translated into a sequence of machine instructions that perform the same task.

• The code generation involves

     o Allocation of register.php and memory.

     o Generation of correct references.

     o Generation of correct data types.

     o Generation of missing code.

                LDF R₂, id₃

                MULF R₂, # 5.0

                LDF R₁, id₂

                ADDF R₁, R₂

                STF id₁, R₁

Symbol Table Management

• Symbol table is used to store all the information about identifiers used in the program.

• It is a data structure containing a record for each identifier, with fields for the attributes of the identifier.

• It allows finding the record for each identifier quickly and to store or retrieve data from that record.

• Whenever an identifier is detected in any of the phases, it is stored in the symbol table.

Example

int a, b; float c; char z;

Example

extern double test (double x);
double sample (int count) {
 double sum= 0.0;
 for (int i = 1; i < = count; i++)
 sum+= test((double) i);
 return sum;
 }

Error Handling

• Each phase can encounter errors. After detecting an error, a phase must handle the error so that compilation can proceed.

• In lexical analysis, errors occur in separation of tokens.

• In syntax analysis, errors occur during construction of syntax tree.

• In semantic analysis, errors may occur at the following cases:

(i) When the compiler detects constructs that have right syntactic structure but no meaning

(ii) During type conversion.

• In code optimization, errors occur when the result is affected by the optimization. In code generation, it shows error when code is missing etc.

Figure illustrates the translation of source code through each phase, considering the statement

    c =a+ b * 5.

Error Encountered in Different Phases

Each phase can encounter errors. After detecting an error, a phase must some how deal with the error, so that compilation can proceed.
A program may have the following kinds of errors at various stages:

Lexical Errors

It includes incorrect or misspelled name of some identifier i.e., identifiers typed incorrectly.

Syntactical Errors

It includes missing semicolon or unbalanced parenthesis. Syntactic errors are handled by syntax analyzer (parser).
When an error is detected, it must be handled by parser to enable the parsing of the rest of the input. In general, errors may be expected at various stages of compilation but most of the errors are syntactic errors and hence the parser should be able to detect and report those errors in the program.

The goals of error handler in parser are:

• Report the presence of errors clearly and accurately.
• Recover from each error quickly enough to detect subsequent errors.
• Add minimal overhead to the processing of correcting programs.

There are four common error-recovery strategies that can be implemented in the parser to deal with errors in the code.

o Panic mode.
o Statement level.
o Error productions.
o Global correction.

Semantical Errors

These errors are a result of incompatible value assignment. The semantic errors that the semantic analyzer is expected to recognize are:

• Type mismatch.
• Undeclared variable.
• Reserved identifier misuse.
• Multiple declaration of variable in a scope.
• Accessing an out of scope variable.
• Actual and formal parameter mismatch.

Logical errors

These errors occur due to not reachable code-infinite loop.