Compiler Design Compiler
• A compiler is a translator that converts the high-level language into the
machine language.
Chapter 1: Introduction to Compiler
• High-level language is written by a developer and machine language can be
understood by the processor.
• Compiler is used to show errors to the programmer.
Instructor: Fikru T.
Email: fikrutafesse08@[Link] • The main purpose of compiler is to change the code written in one
[Link]@[Link] language without changing the meaning of the program.
1 2
Compiler … Compiler …
• When you execute a program which is written in HLL programming language
then it executes into two parts.
• In the first part, the source program compiled and translated into the object
program (low level language).
• In the second part, object program translated into the target program through
the assembler.
• The compiling process includes basic translation mechanisms and error detection.
• Compiler process goes through lexical, syntax, and semantic analysis at the front
end, and code generation and optimization at a back-end.
3 4
Page 1
Features of Compiler History of Compiler
• Important Landmark of Compiler’s history is as follows:
– Correctness – The “compiler” word was first used in the early 1950s by Grace Murray Hopper.
– Speed of compilation – The first compiler was build by John Backum and his group between 1954 and 1957
– Preserve the correct the meaning of the code at IBM.
– The speed of the target code – COBOL was the first programming language which was compiled on multiple
platforms in 1960.
– Recognize legal and illegal program constructs
– The study of the scanning and parsing issues were pursued in the 1960s and 1970s to
– Good error reporting/handling
provide a complete solution.
– Code debugging help
5 6
Compiler vs Interpreter Types of Compiler
1. Native code compiler
Compiler Interpreter
– A compiler may produce binary output to run /execute on the same
1. It translates the whole program at a 1. It translate statement by statement.
time computer and operating system.
2. Compiler is faster 2. Interpreter is slower. – This type of compiler is called as native code compiler.
3. Debugging is not easy. 3. Debugging is easy. 2. Cross Compiler
4. Compilers are not portable 4. Interpreter are portable. – A cross compiler is a compiler that runs on one machine and produce object
code for another machine.
3. Bootstrap compiler
7
– If a compiler has been implemented in its own language, self-hosting compiler. 8
Page 2
Types of Compiler Cont.…. Types of Compiler Cont.….
4. One pass compiler
6. JIT Compiler
– The compilation is done in one pass over the source program, hence the
compilation is completed very quickly. – This compiler is used for JAVA programming language and Microsoft
– This is used for the programming language PASCAL, COBOL, FORTAN. .NET
5. Multi-pass compiler(2 or 3 pass compiler) 7. Source to source compiler
– In this compiler , the compilation is done step by step . – It is a type of compiler that takes a high level language as a input and
– Each step uses the result of the previous step and it creates another
its output as high level language.
intermediate result.
– Example Open MP
– Example:- gcc , Turboo C++
9 10
List of Compiler Overview Of Language Processing System
Some of the list of compliers are :
» Ada compiler
» ALGOL compiler
» BASIC compiler
» C# compiler
» C compiler
» C++ compiler
» COBOL compiler
» Smalltalk compiler
» Java compiler 11 12
Page 3
Overview Of Language Processing System …. Overview Of Language Processing System ….
– A source program may be divided into modules stored in separate files. Language Extensions: These preprocessor attempts to add capabilities to
Preprocessor – collects all the separate files to the source program. the language by certain amounts to build-in macro.
– A preprocessor produce input to compilers. Assembler
– They may perform the following functions. – Programmers found it difficult to write or read programs in machine language.
Macro processing: A preprocessor may allow a user to define macros that are – They begin to use a mnemonic (symbols) for each machine instruction, which
short hands for longer constructs. they would subsequently translate into machine language.
File inclusion: A preprocessor may include header files into the program text. – Such a mnemonic machine language is now called an assembly language.
Rational preprocessor: These preprocessors augment older languages with – Programs known as assembler were written to automate the translation of
more modern flow-of-control and data structuring facilities.
assembly language in to machine language.
13 14
Overview Of Language Processing System …. Overview Of Language Processing System ….
– The input to an assembler program is called source program, the output is – Languages such as BASIC, SNOBOL, LISP can be translated using
a machine language translation (object program). interpreters.
Interpreter – JAVA also uses interpreter.
– An interpreter is a program that appears to execute a source program as – The process of interpretation can be carried out in following phases.
if it were machine language. » Lexical analysis
» Syntax analysis
» Semantic analysis
» Direct Execution
15 16
Page 4
Overview Of Language Processing System …. Overview Of Language Processing System ….
Advantages
Linker
– Modification of user program can be easily made and implemented as execution
– Linker is a computer program that links and merges various object files
proceeds.
together in order to make an executable file.
– Type of object that denotes a various may change dynamically.
– Debugging a program and finding errors is simplified task for a program used for – All these files might have been compiled by separate assemblers.
interpretation. – The major task of a linker is to search and locate referenced
– The interpreter for the language makes it machine independent. module/routines in a program and to determine the memory location where
Disadvantages these codes will be loaded, making the program instruction to have absolute
– The execution of the program is slower. references.
– Memory consumption is more.
17 18
Computer Language Representation … Major Parts of a Compiler
– There are two major parts of a compiler: Analysis and Synthesis
Loader
1. Analysis Phase
– Loader is a part of operating system and is responsible for loading
– An intermediate representation is created from the given source program.
executable files into memory and execute them. » Lexical Analyzer, Syntax Analyzer and Semantic Analyzer are the phases in this part.
– It calculates the size of a program (instructions and data) and 2. Synthesis phase
creates memory space for it. » In synthesis phase, the equivalent target program is created from this
– It initializes various registers to initiate execution. intermediate representation.
» Intermediate Code Generator, Code Generator, and Code Optimizer are the phases
in this part.
19 20
Page 5
Phases of Compiler …
Phases of Compiler
– The compilation process is a sequence of various phases.
– Each phase takes input from its previous stage, has its own representation of source
program, and feeds its output to the next phase of the compiler.
– They communicate with error handlers and the symbol table.
– Let us understand the phases of a compiler.
1. Lexical Analysis
» The first phase of scanner works as a text scanner.
» This phase scans the source code as a stream of characters and converts it into
meaningful lexemes.
» Lexical analyzer represents these lexemes in the form of tokens as: 21 22
Phases of Compiler … Phases of Compiler …
2. Syntax Analysis » For example, assignment of values is between compatible data types, and
» The next phase is called the syntax analysis or parsing. adding string to an integer.
» It takes the token produced by lexical analysis as input and generates a parse » Also, the semantic analyzer keeps track of identifiers, their types and
tree (or syntax tree) as output.
expressions; whether identifiers are declared before use or not etc.
» In this phase, token arrangements are checked against the source code grammar,
» The semantic analyzer produces an annotated syntax tree as an output.
i.e. the parser checks if the expression made by the tokens is syntactically
4. Intermediate Code Generation
correct.
» After semantic analysis the compiler generates an intermediate code of
3. Semantic Analysis
the source code for the target machine.
» Semantic analysis checks whether the parse tree constructed follows the rules of
language. » It represents a program for some abstract machine.
23 24
Page 6
Phases of Compiler … Phases of Compiler …
» It is in between the high-level language and the machine language.
6. Code Generation
» This intermediate code should be generated in such a way that it makes it
» In this phase, the code generator takes the optimized representation
easier to be translated into the target machine code.
of the intermediate code and maps it to the target machine language.
5. Code Optimization
» The next phase does code optimization of the intermediate code. » The code generator translates the intermediate code into a sequence
» It optional phase of compiler. of (generally) re-locatable machine code.
» Optimization can be assumed as something that removes unnecessary » Sequence of instructions of machine code performs the task as the
code lines, and arranges the sequence of statements in order to speed up intermediate code would do.
the program execution without wasting resources (CPU, memory).
25 26
Phases of Compiler …
Phases of Compiler …
Symbol Table
» It is a data-structure maintained throughout all the phases of a compiler.
» All the identifier's names along with their types are stored here.
» The symbol table makes it easier for the compiler to quickly search the
identifier record and retrieve it.
» The symbol table is also used for scope management.
Error Handler
» It is invoked when an error in the source program is detected.
27 28
Page 7
Grouping of Phases Compiler Construction Tools
1. Front end : machine independent phases – Writing a compiler is tedious and time consuming.
– Lexical analysis – There are some specialized tools for helping in implementation of various
– Syntax analysis phases of compilers.
– Semantic analysis – These tools are called compiler construction tools.
– Intermediate code generation – These tools are also called as compiler-compiler, compiler-generators,
2. Back end : machine dependent phases or translator writing systems.
– Code Optimization – Various compiler construction tools are given below:
– Final code generation 1. Scanner generator: generate lexical analyzer
29 30
Compiler Construction Tools … Compiler Construction Tools …
– The specifications given to these generators are in the form of regular 3. Syntax-directed Translation Engines: generate intermediate code.
expressions. – Translation is done for each node of the tree.
– LEX is scanner generator tool 4. Automatic Code Generator: generate machine code from
2. Parser Generator: generate syntax tree. intermediate code.
– The specification to given to these generators is given in the form of
5. Data Flow Engines: required to perform good code optimization.
context free grammars. – Basically useful in code optimization.
– YACC(Yet Another Compiler Compiler) is atypical parser
End!!!
generator tool. Thank You!!!
31 32
Page 8
