Category: Compiler Design

Global data flow analysis

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

Loop optimization

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

Code optimization

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

Boolean expression

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

Type checking

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

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

Parameter passing

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

Storage organization

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 expression in type checking

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

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 and operator overloading

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

Recursive descent parser

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

Analysis of syntax directed definition

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

Operator precedence parsing

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 definition

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 CFGs

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

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,

Register allocation and assignment

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

Data structure in CD

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

Analysis synthesis model of compilation

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

LEX

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

Specification & Recognition of Tokens

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

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 include. Some […]

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. 1. Static Allocation The size of […]

Lexical Analyzer: Input Buffering

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 and Porting

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

Analysis and synthesis model of compilation

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

Introduction to Compiler

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