Page 200 - DCAP507_SYSTEM_SOFTWARE

System Software

Notes 13. ............................. is a method of specifying programming languages by means of formal
grammars and production rules with a particular form of notation.
14. .......................... is a grammar symbol that can be substituted/expanded to a sequence of symbols.

15. Formal grammars are a tool for syntax, not .............................



Case Study Programming Language: ALGOL
lgol is of interest to us because it was the first programming language to be
defined using a grammar. It grew out of an international effort in the late 1950's
Ato create a “universal programming language” that would run on all machines.
At that time, FORTRAN and COBOL were the prominent languages, with new languages
sprouting up all around. Programmers became increasingly concerned about portability
of programs and being able to communicate with one another on programming topics.
Consequently the ACM and GAMM (Gesellschaft für angewandte Mathematik und
Mechanik) decided to come up with a single programming language that all could use on
their computers, and in whose terms programs could be communicated between the users
of all machines. Their first decision was not to use FORTRAN as their universal language.
This may seem surprising to us today, since it was the most commonly used language
back then. However, as Alan J. Perlis, one of the original committee members, puts it:
"Today, FORTRAN is the property of the computing world, but in 1957, it was an IBM
creation and closely tied to IBM hardware. For these reasons, FORTRAN was unacceptable
as a universal language."
ALGOL-58 was the first version of the language, followed up very soon after by ALGOL-
60, which is the version that had the most impact. As a language, it introduced the following
features:
(i) block structure and nested structures, (ii) strong typing, (iii) scoping, (iv) procedures
and functions, (v) call by value, call by reference, (vi) side effects (is this good or bad?),
(vii) recursion.
It may seem surprising that recursion was not present in the original FORTRAN or COBOL.
You probably know that to implement recursion we need a runtime stack to store the
activation records as functions are called. In FORTRAN and COBOL, activation records
were created at compile time, not runtime. Thus, only one activation record per subroutine
was created. No stack was used. The parameters for the subroutine were copied into the
activation record and that data area was used for subroutine processing. The ALGOL
report was the first time we see BNF to describe a programming language. Both John
Backus and Peter Naur were on the ALGOL committees. They derived this description
technique from an earlier paper written by Backus. The technique was adopted because
they needed a machine-independent method of description. If one looks at the early
definitions of FORTRAN, one can see the links to the IBM hardware. With ALGOL, the
machine was not relevant. BNF had a huge impact on programming language design and
compiler construction. First, it stimulated a large number of studies on the formal structure
of programming languages laying the groundwork for a theoretical approach to language
design. Second, a formal syntactic description could be used to drive a compiler directly
(as we shall see). ALGOL had a tremendous impact on programming language design,
compiler construction, and language theory, but the language itself was a commercial
failure. Partly this was due to design decisions (overly complex features, no IO) along
with the politics of the time (popularity of Fortran, lack of support from the all-powerful
IBM, resistance to BNF).

194 LOVELY PROFESSIONAL UNIVERSITY