Transcript compiler construction

COMPILER
CONSTRUCTION
WEEK-1
THE ROLE OF PROGRAMMING
LANGUAGE
An Overview
• The widespread use of the computer programming
languages began in 1957, after the introduction of
FORTRAN.
• FORTRAN allows Engineers and Scientists to write
formulas using traditional symbols of mathematics.
• For example + for addition, * for multiplication etc.
• Such notations were actually the starting point for the
design of programming languages
• The formula e.g. B2 – 4AC was written in Fortran as the
following expression:
• B**2 – 4.0 * A * C
• Fortran takes its name from Formula Translation; readable
formulas were translated into machine instructions for the
IBM-704 (i.e. in the form of zeros and ones)
• Besides describing a result, a formula or expression
X+Y*Z can be treated as an algorithm for computing the
result.
An Overview
• The algorithm is to multiply Y with Z and add the result to
X.
• An expression can be therefore be translated into machine
instructions for evaluating the expression.
• Since then hundreds of programming languages have
been designed and implemented.
• Related programming languages are grouped into
families.
• Members of a family differ in taste more than substance.
• Having learned one member, it is easier to learn another,
since the concepts from one member carry over to other
member of the same family.
An Introduction
• Programming languages are notations.
• They are used for specifying, organizing, and reasoning
about computations.
• Programming languages have evolved far beyond their
origins in machines.
• Languages can help not only by improving the readability
of individual program fragments, but also by providing
ways of organizing and managing large programs.
• A readable program in any programming language cannot
be run directly on a machine.
• It required adopting two approaches to running or
implementing a program: it can be run by compiling it or by
interpreting it.
Higher-Level Languages:
• Programming languages are invented to make machines
easier to use.
• Also they make problems easier to solve.
• The informal term “level” is useful for gross distinction
between languages.
• Levels of readability for programs are analogous to levels
of readability for English text.
• Consider English text: Are the individual words readable?
Do the sentences make sense? What are the main ideas?
Words, sentences, paragraphs, sections, chapters are
levels of structure in English.
• Machine computations are low level, full of details that
have more to do with the inner workings of the machine
than with what the computation is for.
• A typical machine-level operation might add numbers or
compare characters.
Higher-Level Languages:
• Machine Language is the native language of a computer; it
is the notation to which the computer responds directly.
• The term code originally referred to machine language,
although code is now used more broadly to refer to any
programming text.
• A language is higher level if it is independent of the
underlying machine.
• A language is general purpose if it can be applied to a
wide range of problems.
• For example, Fortran was initially created for numerical
computing, LISP for artificial intelligence, Simula for
simulation, Prolog for natural language processing.
• Yet, these languages are general enough to have been
applied to wide range of problems.
Machine Language:
• Programs in machine language are usually unintelligible
(meaningless) at the lowest level, the most detailed level,
since they consist only of 0’s and 1’s.
• Machine language is unsuitable for programming.
• Machine language is unintelligible to a human, while it is
exactly what the machine understands.
• Then there was a need to develop new language, which
can be represented more easily than machine language.
Assembly Language:
• Assembly language is a variant of machine language, in
which names and symbols take the place of the actual
codes for machine operations, values and storage
locations, making individual instruction more readable.
• Individual instructions in assembly language are readable,
but limitations of the underlying machine can lead to make
program complicated.
• A readable relative of this program has four main
components.
–
–
–
–
A memory
A program
An input file
An output file
Assembly Language:
• The memory consists of a sequence of locations, 0,1,….,
each capable of holding single integer value at a time.
• A machine address is the number of a location in memory.
• The integer held in a location will be referred to as the
contents of the location.
• A program consists of a sequence of instructions.
• An input file consists of a sequence of values consumed
one at a time by read instructions.
• An output file consists of the sequence of values produced
one at a time by write instructions.
Benefits of Higher-Level Languages
• Higher-level languages have replaced machine and assembly
language in virtually all areas of programming, because they provide
benefits like the following:
–
–
–
–
Readable familiar notations.
Machine independence.
Availability of program libraries.
Consistency checks during implementation that can detect errors.
• Portability is another term for machine independence; a language is
portable if programs in the language can be run on different machines
with little or no change.
• Such benefits led to Fortran’s immediate acceptance as the language
of choice for scientific programming.
• For example, originally written in assembly language, the UNIX
operating system kernel was rewritten in the programming language C
in 1973, by Denis Ritchie.
Problems of Scale:
• The problems of programming are ones of scale.
• Any one-change to a program is easy to make.
• Any isolated program fragment can be understood and
checked in its entirety.
• With large programs, the effect of a change can ripple
trough the program, perhaps introducing errors or bugs
into some forgotten corner.
• Programming languages can help in two ways.
• First, readable and compact notations reduce the
likelihood of errors.
• Small programs are easier to get right than large ones.
• With large programs, programming languages can help by
providing way of organizing computations so that they can
be understood one piece at a time.
Factor of Human Error:
• Due to programming error, the rocket-carrying Mariner I,
an unmanned probe to the planet Venus, had to be
destroyed 290 seconds after launch on July 22, 1962.
• The program in the ground computer was supposed to
behave as follows:
• If not in radar contact with the rocket then
•
Do not correct its flight path
• But, in error, the initial “not” was missing.
• As a result, the ground computer continued to blindly
guide the rocket even after radar contact was lost.
• The program had previously been used without fault in
four lunar launches.
Factor of Human Error:
• After the loss it was the questions that how to detect
errors?
• And the answer was to adopt two techniques “Code
inspection” and “Program Testing”.
• Code inspection: in this technique one or more people
read someone else’s program, line by line.
• Program testing: consists of running the program on
sample input data.
• Both techniques are standard practice in software
engineering.
• They can be used with any programming language.
• Both are incomplete; they rely on the imagination and
foresight of the inspectors and testers, and are subject to
human limitations.
Role for Programming
Languages:
• It is hopeless to establish the correctness of a program by
testing, unless the internal structure of the program is
taken into account.
• Our only hope is to carefully design a program so that its
correctness can be understood in terms of its structure.
• The art of programming is the art of organizing complexity.
• We must organize the computations in such a way that our
limited powers are sufficient to guarantee that the
computation will establish the desired effect.
Programming Paradigms:
• New languages are not introduced lightly.
• A language takes on a life of its own as people invest in it
by learning it and building up collection of programs in it.
• The effect needed to introduce a new language is
substantial, not only in designing it and implementing it,
but in teaching it and supporting it.
• Following are the categories of languages.
Imperative Programming:
• Imperative languages are action oriented, i.e. a
computation is viewed as a sequence of actions.
• The imperative family began with Fortran; Pascal and C,
are general-purpose imperative languages.
• Other examples are Algol60, CPL,BCPL and Algol68.
• Pascal and C embody key ideas of imperative
programming.
• The term “imperative” comes from command or action; the
computation model is that of a sequence of action on an
underlying machine.
Functional Programming:
• Functional programming is worth studying as a
programming style in its own right; as a setting for studying
concepts such as types; and as a technique for language
description.
• The basic concepts of functional languages originated with
LISP (LISt Processor), a language designed in 1958 for
applications in artificial intelligence.
• The LISP language is designed primarily for symbolic data
processing.
• It has been used for symbolic calculations in differential
and integral calculus, electrical circuit theory, mathematical
logic, game playing, and other fields of artificial
intelligence.
• Other examples are ISWIM, SASL, SCHEME, ML etc.
Object-Oriented Programming:
• As programs get larger, the natural unit of programming is
a grouping of data and operations.
• The progression of concepts for such grouping can be
described in terms of modules, user-defined types (for
example, stacks), and classes (as in object-oriented
programming).
• Object-oriented programming owes much to Simula’s
origins in simulation.
• The language was designed as both a description
language and a programming language by Kristen
Nygaard and Ole-Johan Dahl between 1961 and 1967.
• Simula changed the way people think about programming.
• C++ and Smalltalk are popular for object-oriented
programming. (JAVA too)
• Although both got notion of objects and classes form
Simula.
Logic Programming:
• Logic programming deals with relations rather than
function.
• Where it fits, programs are concise, consisting of facts and
rules.
• The language uses the fact and rules to deduce
responses to queries.
• Prolog is the best example of this category.
• Prolog comes from PROgrammation en LOGique).
• Prolog was developed in 1972 for natural language
processing in French by Alain Colmerauer and Philipee
Roussel.
• Prolog has since been used for a range of applications
from database to expert systems.
• Prolog programs have the brevity and expressiveness of
logic.
Choice of Language:
• The choice of programming language depends in part on
the programming to be done, and in part on external
factors, such as availability, support, and training.
• For example, the initial prototype of the UNIX system
spelling checker, was written in by combining existing
utility programs (tools) in the UNIX environment.
• Several years later, once the spelling checker became
sufficiently popular, an improved version was implemented
in C to speed up checking.
• Different goals led to the two versions being implemented
in different languages.