Chapter 2
Program Language Translation
Language Processing System
• We have learnt that any computer system is made of hardware and software.
• The hardware understands a language, which humans cannot understand.
• So we write programs in high-level language, which is easier for us to understand and remember.
• These programs are then fed into a series of tools and OS components to get the desired code that can
be used by the machine.
• This is known as Language Processing System.
Cont.
Language Processing System
Cont.
• The high-level language is converted into binary language in various phases.
• A compiler is a program that converts high-level language to assembly language.
• Similarly, an assembler is a program that converts the assembly language to machine-level
language.
• Let us first understand how a program, using C compiler, is executed on a host machine.
User writes a program in C language (high-level language).
The C compiler compiles the program and translates it to assembly program (low-level
language).
An assembler then translates the assembly program into machine code (object).
A linker tool is used to link all the parts of the program together for execution
(executable machine code).
A loader loads all of them into memory and then the program is executed.
Cont.
• Before diving straight into the concepts of compilers, we should understand a few other tools
that work closely with compilers.
Preprocessor
Interpreter
Assembler
Linker
Loader
Cross-compiler
Source-to-source Compiler
Cont.
Preprocessor: A preprocessor, generally considered as a part of compiler, is a tool that produces
input for compilers.
• It may perform the following functions.
1) Macro processing: A preprocessor may allow a user to define macros that are short hands for
longer constructs.
2) File inclusion: A preprocessor may include header files into the program text.
3) Rational preprocessor(augmentation): These preprocessors augment older languages with more
modern flow-of control and data structuring facilities.
4) Language Extensions: These preprocessor attempts to add capabilities to the language by certain
amounts to build-in macro
Cont.
Interpreter: An interpreter, like a compiler, translates high-level language into low-level machine
language.
• The difference lies in the way they read the source code or input.
• A compiler reads the whole source code at once, creates tokens, checks semantics, generates
intermediate code, executes the whole program and may involve many passes.
• In contrast, an interpreter reads a statement from the input, converts it to an intermediate code,
executes it, then takes the next statement in sequence.
• If an error occurs, an interpreter stops execution and reports it; whereas a compiler reads the whole
program even if it encounters several errors.
• Languages such as BASIC, JAVA, LISP and etc. can be translated using interpreters.
Cont.
Assembler: An assembler translates assembly language programs into machine code.
• The output of an assembler is called an object file, which contains a combination of machine
instructions as well as the data required to place these instructions in memory.
Linker: Linker is a computer program that links and merges various object files together in order
to make an executable file.
• All these files might have been compiled by separate assemblers.
• The major task of a linker is to search and locate referenced module/routines in a program and to
determine the memory location where these codes will be loaded, making the program instruction
to have absolute references.
Cont.
Loader: is a part of operating system and is responsible for loading executable files into memory
and executes them.
• It calculates the size of a program (instructions and data) and creates memory space for it.
• It initializes various registers to initiate execution.
Cross-compiler: A compiler that runs on platform (A) and is capable of generating executable
code for platform (B) is called a cross-compiler.
Source-to-source Compiler: A compiler that takes the source code of one programming language
and translates it into the source code of another programming language is called a source-to-source
compiler.
Compiler Architecture/The Grouping of Phases
A compiler can broadly be divided into two phases based on the way they compile.
I. Analysis Phase
• Known as the front-end of the compiler, the analysis phase of the compiler reads the source
program, divides it into core parts, and then checks for lexical, grammar, and syntax errors.
• The analysis phase generates an intermediate representation of the source program and symbol
table, which should be fed to the Synthesis phase as input.
• Machine Independent/Language Dependent
Cont.
II. Synthesis Phase
• Known as the back-end of the compiler, the synthesis phase generates the target program with the
help of intermediate source code representation and symbol table.
• Machine Dependent/Language independent
• A compiler can have many phases and passes.
Pass : A pass refers to the traversal of a compiler through the entire program.
Phase : A phase of a compiler is a distinguishable stage, which takes input from the previous
stage, processes and yields output that can be used as input for the next stage. A pass can have
more than one phase
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.
• Let us understand the phases of a compiler.
Phases of Compiler 12
Cont.
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: <token-name, attribute-value>
2. Syntax Analysis
• The next phase is called the syntax analysis or parsing.
• It takes the token produced by lexical analysis as input and generates a parse tree (or syntax tree).
• In this phase, token arrangements are checked against the source code grammar, i.e., the parser
checks if the expression made by the tokens is syntactically correct.
3. Semantic Analysis
• Semantic analysis checks whether the parse tree constructed follows the rules of language.
• For example, assignment of values is between compatible data types, and adding string to an integer.
• Also, the semantic analyzer keeps track of identifiers, their types and expressions; whether
identifiers are declared before use or not, etc.
• The semantic analyzer produces an annotated syntax tree as an output.
Cont.
4. Intermediate Code Generation
• After semantic analysis, the compiler generates an intermediate code of the source code for the
target machine.
• It represents a program for some abstract machine.
• It is in between the high-level language and the machine language.
• This intermediate code should be generated in such a way that it makes it easier to be translated
into the target machine code.
5. Code Optimization
• The next phase does code optimization of the intermediate code.
• Optimization can be assumed as something that removes unnecessary code lines, and arranges the
sequence of statements in order to speed up the program execution without wasting resources
(CPU, memory).
Cont.
6. Code Generation
• In this phase, the code generator takes the optimized representation of the intermediate code and
maps it to the target machine language.
• The code generator translates the intermediate code into a sequence of (generally) re-locatable
machine code.
• Sequence of instructions of machine code performs the task as the intermediate code would do.
7. Symbol Table (Book-keeping)
• It is a data-structure maintained throughout all the phases of a compiler.
• All the identifiers’ 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.
Cont.
8. Error Handlers
• It is invoked when a flaw error in the source program is detected.
• The output of LA is a stream of tokens, which is passed to the next phase, the syntax analyzer or
parser.
• The SA groups the tokens together into syntactic structure called as expression.
• Expression may further be combined to form statements.
• The syntactic structure can be regarded as a tree whose leaves are the token called as parse trees.
Compiler Construction Tools
• For the construction of a compiler, the compiler writer uses different types of software tools that
are known as compiler construction tools.
• Compiler-construction tools are,
I. Parser generators
II. Scanner generators
III. Syntax-directed translation engines
IV. Automatic code generators
V. Data-flow engines
Cont.
I. Parser generators: It takes the grammatical description of a programming language and
produces a syntax analyzers or parsers.
II. Scanner generators: It automatically produce lexical analyzers or scanners from a regular
expression description of the tokens of a language.
III. Syntax-directed translation engines: It produce a collection of routines, which traverses the
parse tree as input and generates the intermediate code.
IV. Automatic Code generators: It produce a code generator from a set of rules that translates the
intermediate language instructions into the equivalent machine language instructions for the
target machine. It generates the machine language for a target machine.
V. Data-flow analysis engines: It gather the information about how the data is transmitted from
one part of the program to another. For code optimization, data-flow analysis is a key part.
Cont.
• Compiler-construction toolkits: It provide an integrated set of routines for construction of
the different phases of a compiler.
• These compiler construction kits, parser generators, lexical analyzer / analyser (lexers) generators,
code optimizers (optimizer generators), provide the facility where you define your language and
allow the compiler creation tools to generate the source code for your software.
