Compiler Construction

Outline

History of Compiler
Why Learn Compiler Design?
Stages of Compiler Design
Types of Compiler
Single Pass Compiler
Two Pass Compiler
Single Pass Compiler
Language Processing Systems
Features of Compilers
Compiler Construction Tools
Summary

History of Compiler

The history of compilers dates back to the mid-20th century. The first compiler,
developed by Grace Hopper in 1952, was the A-0 system, translating mathematical
code into machine-readable code. Subsequently, the development of the first high-
level programming languages like FORTRAN (1957) and LISP (1958) led to the
creation of compilers to convert these languages into machine code.

The 1960s and 1970s saw significant advancements in compiler theory and design,
marked by the creation of compilers for languages like COBOL, ALGOL, and BASIC.
This period also witnessed research in formal language theory, parsing algorithms,
and optimization techniques, which laid the foundation for modern compiler
construction.

Tools like Lex and Yacc (developed in the 1970s) streamlined the process of lexical
analysis and parsing, making compiler construction more efficient. The development
and standardization of the C programming language and its associated compiler,
along with the emergence of the GNU Compiler Collection (GCC), significantly
influenced compiler design and optimization techniques.

The 21st century brought about the LLVM project in the early 2000s, offering a set of
reusable compiler and toolchain components. LLVM became the backbone for various
programming language compilers, enhancing the performance and capabilities of
modern compilers.

Why Learn Compiler Design?

Computers are a balanced combination of software and hardware. Hardware is just a

piece of mechanical device and its functions are being controlled by a corresponding
software. Hardware interprets instructions as an electronic charge, the binary
language counterpart in software programming. A binary language has only two
alphabets, 0 and 1. In order to carry instructions, hardware codes must be written in
binary format, which is simply a series of 1s and 0s. Writing such code would be a
difficult and burdensome task for computer programmers, which is why we have
compilers to write such codes.
Compiler construction is the process of designing and building a compiler, which is a
computer program that translates source code written in one programming language
into another programming language. The target language is often a lower-level
language, such as assembly language or machine code, that can be executed directly
by a computer.

Compilers are essential for developing software, as they allow programmers to write
code in a high-level language that is easier to read and write than machine code.
High-level languages are also more portable, meaning that code written in one
language can be compiled to run on different types of computers.

Compiler construction is a complex task, as compilers must be able to parse and

understand the source code, generate equivalent code in the target language, and
optimize the generated code for performance. Compilers also need to be able to
detect and report errors in the source code.

Stages of Compiler Design

The process of compiler designing can be divided into several phases:

o Lexical analysis: The lexical analyzer breaks the source code into a stream of
tokens, which are the basic building blocks of the language.
 o Syntax analysis: The syntax analyzer parses the stream of tokens to determine the
structure of the program.
o Semantic analysis: The semantic analyzer checks the program for semantic
errors, such as type mismatches and undeclared variables.
o Intermediate code generation: The intermediate code generator generates an
intermediate representation of the program, which is a more abstract representation
than the source code but more concrete than the target language.
o Code generation: The code generator generates code in the target language from
the intermediate representation.
o Code optimization: The code optimizer improves the performance of the generated
code by applying various techniques, such as dead code elimination and loop
optimization.

Compiler construction is a challenging but rewarding field of computer science.

Compilers are essential for developing software, and compiler construction
researchers are constantly developing new techniques to improve the performance
and reliability of compilers.

Types of Compiler

There are three types of compilers:

o Single Pass Compilers

o Two Pass Compilers
o Multipass Compilers

Single Pass Compiler

When all stages of a compiler are contained within a single module, it is simply called
a single-pass compiler. It performs the task of converting source code into machine
code.

Two Pass Compiler

A two-pass compiler is a compiler in which the program is translated twice, once from
the front-end and once from the back-end.
Single Pass Compiler

When a program generates several intermediate codes and processes a syntax tree
multiple times, it is called a multipass compiler. It breaks the code into

Language Processing Systems

The process of converting high-level language into machine code involves several key
stages handled by language processing systems:

1. High-Level Language: Programs written in high-level languages, such as C, C++,

etc., are easier for humans to understand but need translation for machines.
2. Pre-Processor: This component handles pre-processor directives (e.g., #include,
#define) by expanding macros and including necessary files as directed.
3. Assembly Language: Acts as an intermediate form between high-level and machine
code. It consists of partially converted machine instructions and other required data for
execution.
4. Assembler: Platform-specific, it translates assembly language into machine code,
generating object files for the given hardware and operating system.
5. Interpreter and Compiler: Both convert high-level language to machine code, but
they differ in how they handle input. The interpreter translates code line by line, while
a compiler processes the entire program at once. Compiled programs tend to run
faster than interpreted ones.

6. Linker and Loader: The linker merges object files (generated by compiler, assembler,
etc.) into a single executable file. The loader then loads this file into memory and
executes it. Additionally, they ensure that the code is appropriately located in memory
for smooth execution.
7. Relocatable Machine Code: Code that can be loaded at any memory point and
executed, as its internal addresses are adaptable for program movement.

The entire process involves a sequence of transformations, beginning from human-

readable high-level code and culminating in machine-executable code, allowing
computers to understand and run the software efficiently.

Features of Compilers

o Correctness
o Speed of compilation
o Preserve the correct the meaning of the code
o The speed of the target code
o Recognize legal and illegal program constructs
o Good error reporting/handling
o Code debugging help

Compiler Construction Tools

Compiler construction tools are instrumental in creating the various components of a

compiler. They aid in the process of designing, implementing, and optimizing
compilers by providing specific functionalities. Here are some examples of compiler
construction tools:
 1. Scanner Generators: Tools like LEX for Unix Operating System take regular
expressions as input and generate scanners. These scanners analyze the source code,
breaking it into tokens for further processing.
2. Syntax-Directed Translation Engines: These tools produce intermediate code by
utilizing the parse tree. They associate translations with each node of the parse tree to
generate intermediate code.

3. Parser Generators: Tools that take a grammar as input and automatically generate
source code. This generated code is capable of parsing streams of characters based on
the provided grammar, facilitating syntax analysis.
4. Automatic Code Generators: These tools take intermediate code and convert it into
machine language or the target code that can be directly executed by the machine.
5. Data-Flow Engines for Code Optimization: These tools aid in code optimization by
analyzing the data flow within the program. Users provide information, and the engine
compares and analyzes intermediate code to understand relationships and how values
are transmitted throughout different parts of the program. This helps in optimizing the
code by identifying and improving data flow within the program.

Compiler construction tools provide essential functionality and automation for various
phases of compiler construction, contributing significantly to the efficiency and
performance of the resultant compilers and the programs they produce.

Summary

o A compiler is a computer program that helps you convert source code written in a
high-level language into a low-level machine language.
o Accuracy, compilation speed, preserving the correct meaning of the code are some of
the important features of compiler design.
o Compilers are divided into three categories 1) single pass compilers 2) two pass
compilers, and 3) multi pass compilers.
o The word “composite” was first used by Grace Murray Hooper in the early 1950s.
o The steps of a language processing system are: preprocessor, interpreter, assembler,
linker/loader.
o The main tools of compiler construction are 1) scanner generators, 2) syntax-
directed translation engines, 4) parser generators, 5) automatic code
generators.
o The primary function of the compiler is to verify the entire program, so there are no
syntax or semantic errors.