In structure flow graph condition and control statements like, if else, do while comes. An useful property of structured flow graph such as for do-while statements is: There is a single beginning point at which control enters and a single endpoint that control leaves from when execution of the statement is over. To do data […]

Introduction to Global data flow analysis Data-flow analysis Data-flow analysis is a process in which optimizing compiler collects the data-flow information. Here,Data-flow information means status information during computation times like transformations performed in a basic block. Collection of data-flow information about the program as whole and to distribute this information to each block in the […]

Invariant code: The code which reside in a loop and computes same value at each iteration is known as invariant code. This code can be moved out of the loop to compute once, other than at each iteration, to reduce the computation time. Induction analysis: A variable is called an induction variable if its value […]

Basic blocks of codes are the number of instructions exist in a source code, which are executed sequentially. Basic blocks are sequence of codes. Some of the statements which ends sequence of codes and give born to basic blocks are, If Else Switch Case Do While, etc. For example: Take source code as shown below. […]

A compiler can be divided into two phases based on the way they compile: Analysis phase, also known as front end as shown in diagram below. Synthesis phase, also known as back end as shown in diagram below. The code optimization in the synthesis phase is a program transformation technique, which tries to improve the […]

Instruction involve: Create Variables Get user input from the keyboard Investigate memory addresses of variables Choose the best data type for the job Create and work with arrays Create and use functions Perform Binary Arithmetic / Logic operations Construct Expressions with a variety of operators Statements can be broken into a number of categories: Declarations: […]

A boolean expression is an expression in a programming language that produce a boolean value when evaluated i.e. one of true or false. A boolean expression may be composed of a combination of boolean constats true or false, boolean-typed variables, boolean value operators and boolean valued functions. Most programming languages have the boolean operators OR […]

Introduction Code generation can be considered as the final phase of compilation. Through post code generation, optimization process can be applied on the code, but that can be seen as a part of code generation phase itself. The code generated by the compiler is an object code of some lower-level programming language. For example, Assembly […]

TYPE CHECKING Introduction: The compiler must perform static checking (checking done at compiler time).This ensures that certain types of programming errors will be detected and reported. A compiler must check that the source program follows both the syntactic and semantic conversions of the source language. This checking is called static checking example of static checks […]

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 […]

PARAMETER PASSING There are two types of parameters: Formal parameters Actual parameters Based on these parameters there are various parameter passing methods.  The most common methods are: 1. Call by value: This is the simplest method of parameter passing.  The actual parameters are evaluated and their r-values are passed to called procedure.  The operations on […]

During the execution of a program, the same name in the source can denote different data objects in the computer. The allocation and deallocation of data objects is managed by the run-time support package. Terminologies Name storage space: The mapping of a name to a storage space is Called environment Storage space value: The current […]

EQUIVALENCE OF EXPRESSIONS IN TYPE CHECKING Type checker find whether two type expressions are equivalent or not.  This type equivalence is of two categories: Structural equivalence  Name equivalence. In type checking if two type expressions are equal then return a certain type else return type-error. Structural equivalence: Replace the named types by their definitions and […]

STORAGE ALLOCATION STRATEGIES Static Allocation: It is for all the data objects at compile time. Stack Allocation: In this a stack is used to manage the run time storage. For example recursive calls make use of this area.  Heap Allocation: In this a heap is used to manage the dynamic memory allocation. Static Allocation The […]

Function Overloading If any class have multiple functions with same names but different parameters then they are said to be overloaded.  Function overloading allows you to use the same name for different functions, to perform, either same or different functions in the same class.  Ways to overload a function: By changing number of Arguments. By […]

A parser that uses collection of recursive procedures for parsing the given input string is called Recursive descent (RD) parser. Basic steps for construction of RD parser: The R.H.S. of the rule is directly converted into program code symbol by symbol. If the input is non-terminal then a call to the procedure corresponding to the […]

Syntax directed definations: Are a generalizations of context-free grammars in which Grammar symbols have an associated set of Attributes. Productions are associated with Semantic Rules for computing the values of attributes. The value of an attribute of a grammar symbol at a given parse-tree node is defined by a semantic rule associated with the production […]

A grammar G is said to be operator precedence if it possess following properties: No production on the right side is Ɛ. There should not be any production rule possessing 2 adjacent non terminals at the right hand side. Consider the grammar for arithmetic expression This grammar is not an operator precedent grammar as in […]

L-Attribute class of Syntax Directed Definition (SDD) is called L-Attributed definitions. The idea behind this class is that, between the attributes associated with a production body, dependency-graph edges can go from left to right, but not from right to left hence L-attribute. L-Attribute grammars are a special type of attribute grammars. They allow the attributes […]

Syntax analysis or parsing is the second phase of a compiler. First we should know why CFG needed ? The main task of the lexical analyzer is to read the input characters of the source program group them into lexemes and produce as output a sequence of tokens.. A lexical analyzer can identify tokens with […]

Dead code elimination removes unneeded instructions from the program. Dead code is a section in the source code of a program, which is executed but whose result is never used in any other computation. Dead code execution prevents from wastes of computation time and memory. For example, After dead code elimination above program become,

Take source code as shown below, Basic blocks in above source code are (1) (2) (3) (4) a = 0;b = b+c;c = 0;If (a>d) c = b;b++; c = d;d++; a= b+d; Flow graph for above Basic blocks

Introduction In many programming languages, the programmer has the illusion of allocating arbitrarily many variables. However, during compilation, the compiler must decide how to allocate these variables to a small, finite set of registers. Not all variables are in use (or “live”) at the same time, so some registers may be assigned to more than […]

Symbol table Symbol table is an important data structure created and maintained by compilers in order to store information about the occurrence of various entities such as variable names, function names, objects, classes, interfaces, etc. Symbol table is used by both the analysis and the synthesis parts of a compiler. A symbol table may serve […]

The analysis and synthesis phases of a compiler are: Analysis Phase Breaks the source program into constituent pieces and creates intermediate representation. The analysis part can be divided along the following phases: 1. Lexical Analysis The program is considered as a unique sequence of characters. The Lexical Analyzer reads the program from left-to-right and sequence […]

Introduction Lexical analyzer generator scans the input stream and converts sequences of characters into tokens. The main job of lexical analyzer (scanner) is used to break up an input stream into more usable element(tokens) Lex is not a complete language, but rather a generator representing a new language feature which can be added to different […]

Front end and back end of the compiler Front end and back end is the collection of phases of compiler. Front End :  1. Lexical Analysis,  2. Syntax Analysis, 3. Semantic Analysis,  4. Intermediate Code,  5. Some amount of Code Optimization. Back End:  1. Code Optimization,  2. Code Generation 1. Lexical Analysis: It takes source […]

First know about Lexical Analysis: The lexical analyzer breaks 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. It reads character streams from the source code, checks for legal tokens, and passes the data to the syntax analyzer […]

Introduction The compiler must perform static checking (checking done at compiler time).This ensures that certain types of programming errors will be detected and reported. A compiler must check that the source program follows both the syntactic and semantic conversions of the source language. This checking is called static checking example of static checks include. Some […]

Static Allocation: It is for all the data objects at compile time. Stack Allocation: In this a stack is used to manage the run time storage. For example recursive calls make use of this area.  Heap Allocation: In this a heap is used to manage the dynamic memory allocation. 1. Static Allocation The size of […]

First we should know what is Lexical Analyzer? The main task of the lexical analyzer is to read the input characters of the source program group them into lexemes and produce as output a sequence of tokens for each lexeme in the source program. When the lexical analyzer discovers a lexeme constituting an identifier, it […]

Bootstrapping Bootstrapping is used to create compilers and to move them from one machine to another by modifying the back end. A compiler is characterized by three languages Source Language (S) Target Language  (T) Implementation Language (I)  Porting Porting the compiler to the new host computer now only requires that the back end of the source code be […]

Compilation is a process by Compiler.Compilation having mainly 2 parts: Analysis Synthesis 1. Analysis: Divide source code in to components. Create an intermediate representation of source code. 2. Synthesis: It generates desired target code from above intermediate representation. Software tools: Structure editors Pretty Printers Static checkers Interpreters Structure editors : Analyze program text, creates text, methods. It […]

Compiler is a software. Compiler is a large program. Compiler converts high level language in to machine language. Compiler do error reporting present in the source program. Classification of Compiler: Single Pass Compiler Multi Pass Compiler Debugging Compiler Optimizing Compiler Incremental Compiler Silicon Compiler What is Pass in Classification of Compiler ? Ans. Pass is […]