Practice English Speaking&Listening with: Lecture - 2 Syntax

Difficulty: 0

Welcome to the lecture 2. Let us just go briefly through what we did

in the last lecture. We are mainly concerned with what might be called high level programming

languages of which there are three kinds. Imperative and functional programming languages

are the most important. Logic also can be used as a language but our main concern is

with the imperative and functional languages. They are also similar in certain respects.

Imperative languages might be called state-based languages where state updation is the main

action. However, functional languages are really value based languages much closer to

our mathematical languages. The notion of variables in functional languages is very

much like the notion of variables in mathematics whereas the notion of variables in the imperative

languages is more like quantities in physics which can change over time such as acceleration

and velocity. State based languages means that there is a state change along a time

axis. Unlike physics we are not talking of continuous time. We are talking of discrete

time in the case of functional languages. The notion of the variable is really a variable

in mathematics which means that a variable is just a name for a value and it cannot change

in time during the execution of a program.

If we look at the history of languages, most of the work on high level languages is really

concentrated on the imperative languages. There are hundreds and hundreds of programming

languages. So firstly, it is impossible to study all of them. If you look at history,

you will find that a large portion of the time during the fifties and sixties was concentrated

on what might be called the basic features. This means that these represent the basic

control structures in the basic data structures in order to obtain clean readable programs

efficiently. Later once they were fixed in the 70s and

80s, most of the exploration of programming languages was in terms of what might be called

features. If you were to take Modula, which is just

an extension of Pascal, its most important feature is that of a module.

If you were to take Ada, it combines the module features of Modula and adds more features

like concurrency as an important feature like in exception-handling, generics or polymorphism.

Then you have CLU, which is a module based language very much like Modula but with a

different syntax. But they are all extensions of Pascal in the sense that the basic control

structure remains the same and then you extend the language.

The basic control structures in these languages could be different too. They are not very

similar except that these arrow marks denote the decendency in terms of similarity of even

the basic control structures. Even though the Smalltalk-80 control structures

or syntax are different from that of Simula, the basic extensional feature comes from a

new feature of Simula which was extended and that was the notion of class or objects.

Most of the languages in the early 60s were sequential, whether concurrent or modular

distributed or parallel etc.

Nowadays by and large the exploration of most of the languages in the early 60s is mostly

in terms of new features. I have listed the various kinds of features and in the current

state of art, large amount of work is into trying to make them more efficient, more readable,

more comprehendible etc. The basic functional languages also have this feature that the

early functional languages were all an exploration of. They were very basic data structures and

control structures. Languages like ML and CAML actually signify the addition of new


In fact the syntax of ML expressions etc. is much closer to that of Pascal than that

of LISP. But philosophically, it is a more LISP like language because it is an applicative

or functional language. It is not a state based language and it goes far beyond LISP

in the sense that there are new features like the introduction of modules, introduction

of exceptional handling, the introduction of very powerful data abstraction mechanisms

and a type checking. LISP has no type checking at all.

Let us first study the basic features of languages and look at the issues in language design.

Consider the kinds of issues you would really have to study if you were to design a language.

One very major issue that the implementation of the language Pascal has taught us is that

it is a good idea for a language to have a simple, clear and a small set of unified primitives

for expressing all your algorithms and data structures.

One of the most convenient characteristics about Pascal or in general about what are

known as Algol 60 like languages is that most algorithms are written in some crude variations

of the dialect of Pascal or Algol system. So, the Pascal is a small language easily

learnable which is why most people are taught Pascal initially. One issue could be that

you should start with a small language with a small set of primitive operations over which

you can build.

The next issue would be that you should have an absolutely clear syntax. There should be

no ambiguity and you should be able to get highly readable programs.

It is very important to have readability meaning that we have to be able to read the source

code of the program like a book and a very good reason for that is that no piece of software

that you write is ever permanently fixed. Most pieces of software have bugs in them.

Bugs might be detected years and years after their software has been commissioned. Somebody

else should be able to read the source code and modify it. In order to be able to read

the source code, one should be able to understand the algorithms of the source code contained.

In fact consideration of efficiency comes much later. Readability is the most important

aspect because it includes maintainability of the software. Normally, those who have

written this software are not likely to be present to maintain the software. Software

in general has to be maintained by somebody else, which means that the source code must

be readable and that comes first. The second point is that over the years the software

actually has more and more users who feel their need for its extension which is why

you have to be able to extend the software by adding new features or by adding more conveniences

for specific reasons.

Part of the maintainability of a piece of software is not just the detection and correction

of bugs but also the extensibility of the software as years go by and more and more

needs are felt. It is necessary for somebody who is usually not the original programmer

or the original team that wrote the software to be able to extend it. For all that, readability

is most important and secondly the language should provide what is known as a support

for abstraction.

You are already aware of the basic abstractions. Control abstractions are procedures, functions

in Pascal, loop statements etc. There are also data abstractions. The most primitive

kinds of data abstraction that Pascal provides are the record structures and the arrays which

almost all languages including the early languages have.

Arrays are one data abstraction. You think of a whole sequence of elements as a single

logical unit like records and variant records. Over time it was felt that you should have

data abstraction which allows you to not only take sets of data together as a single unit

but also to operate on them as a single unit.

There are combinations of operations and data abstractions on a module basis or further

abstractions for which you might require languages like ML and Ada that provide the notion of

generality or polymorphism where you can use types themselves as variables and change types

and instantiate the same kinds of algorithms. For example; in stacks, it does not matter

whether you are talking of a stack of integers, a stack of characters, a stack of reals or

a stack of some complicated data element. It may be a stack of some record or stacks

of arrays. The basic operation on stacks is like pop

push, checking for emptiness etc. They should all be available in one form and it should

not be necessary for us to repeat the code depending on the type of the element. An abstraction

should be one where the basic element of the stack itself is a variable which can be instantiated

to a different type, each time the same piece of code is carefully written, verified, or

thoroughly tested and the type instantiated. We get different kinds of stacks with the

same kinds of operations which is why the support for abstraction is an important modern

language design issue. The other kinds of issues that have come up are that you should

be able to verify your programs. So, the language should also provide support for verification,

provability of programs (not necessarily machine based provability but possibly hand based

provability) or a mixture or a user interactive provability of programs. Portability was felt

even in the 60s where a lot of time and effort was expended in the case of FORTRAN and COBOL


Nowadays portability means that the language design should be oriented towards an end user.

It is not architecture or machine-specific simply because a certain machine has a certain

kind of assembly instruction. It does not mean that you make that available in the language.

Other machines may not have that. You should be able to provide as far as possible an abstract

form which is not related to the machine that uses only the basic instruction set available

in all machines. If you ensure that your language is really architecture or machine-independent

in the sense that your main concern is one of convenience of the user or the abstractions

required for the user, then they are not specific to particular machine instruction sets of

a particular architecture. You might have register based architectures or stack based

architectures. If you can design the language in such a fashion that it is not architecture-specific

or machine-specific then you can move the entire language to another machine with a

different architecture and with the minimum amount of effort.

There are certain machine specific details which still have to be changed when I move

an entire language implementation from one machine or architecture to another. But the

whole idea of the language design or the design of its implementation should be that the amount

of changes to be made should be minimal. Then there are considerations that include the

ability to easily implement it. You cannot compromise everything for the sake of portability.

Ease of implementation and the availability of ready algorithms for implementing the language

should be considerations. Ease of implementation was perhaps the most important reason for

this and the fact that it used very low level primitives is perhaps the most important reason

for the success of the C language. Efficiency is another important reason. C programs run

very fast and they are very efficient.

If you have a language and you want it to be generally acceptable then it should have

a clear definition of what its constructs do. The reason being that if it has to be

widely acceptable there might be many different implementers trying to implement it on various

machines and only if there is a common clear syntax, common clear semantics or clear specifications

of the effects of each language construct, you can expect to get wide applicability.

We will get to the notion of semantics later. Of course it has to be run time efficient.

By run time efficient I mean that the programs have to run efficiently. This is the efficiency

of the implementation which implies very often compile time efficiency. This means how fast

you can compile programs written in the language. Whereas this runtime efficiency implies that

it should have an excellent runtime support and the program should run as fast as the

programs written in the language. Ease of maintenance is about the maintenance

of programs as well as the maintenance of the language by an implementation of the language.

There might be bugs in the language implementation. Fast compilation translation and support for

extensibility are in fact the most important reasons why Pascal is used as the basic language

from which you add new features to get newer languages. This is one controversial feature,

which is the support for subsets. Most books on programming languages specified this feature.

It is that every language should support subsets of the language in the sense that it should

be necessary for you to use only a smaller set of operations or features of the language

than is actually necessary. It should be possible to divide up the language so that there is

a small kernel and large sorts of extensions. All programs written for the small kernel

run on all machines regardless of the subset supported. However, the language of Ada for

example in the 80s has clearly specified that there should be no support for subsets and

their reason is that it would then affect the portability of programs written in the


Support for subsets is a controversial aspect. It is not at all clear whether it is desirable

especially in the most important language for embedded systems.

They are real time systems that control sensors, various kinds of hardware, ballistic missiles

etc. It could affect their portability because you would have a feature which is used in

a specific implementation and then you move the program to another implementation which

does not support that feature and your programs do not run.

The portability of actually programs written in the language gets affected if you allow

arbitrary subsets. If you look at all these features, there are hundred and hundreds of

programming languages and it is impossible to study all of them and moreover it is not

necessary to do so. Therefore we would like to divide up the study of programming languages

into a few small parts.

What does a theory of programming languages contain? A general theory of programming languages

is based on three aspects. What might be the most important aspect or the most basic aspect

is known as the syntax of the language. A programming language is really like a very

highly simplified natural language; it has a certain syntax which implies that it has

a grammar. Certain elements of a sentence can occur only in certain ways. You cannot

arbitrarily form sentences of the language. As I said, a program written in that language

is the sentence of the language like in a natural language. You take a sentence of a

natural language and you find it has various parts.

For example; in almost all natural languages any full sentence should have a predicate.

A syntactic category called predicate in general may not be words; a predicate could be a clause

or a phrase and so it might have a subject and an object.

Let us take a sentence in natural language. Supposing I say 'run'; that is a complete

sentence because it has a predicate. No complete sentence in the natural language is without

a predicate. So 'run' is a complete sentence because it has a predicate. Optionally, it

might have a subject and may be also an object clause. Subject clauses have to be of a grammatical

form called subject phrases or may be noun phrases which means they might have nouns

qualified by adjectives or an article etc.

You can divide up any grammatically correct sentence in a natural language into firstly

various clauses and each clause into various phrases and all these phrases have certain

grammatical properties in a very much similar manner in a greatly simplified form that might

be called the parts of speech of a program. Every programming language has a certain grammar,

which specifies various parts of speech. It has a certain vocabulary and it is possible

to take a sentence of this programming language and parse it. We will get into the meaning

of these points more clearly later where artificial languages have similarities with natural languages;

(a lot of the theory of the syntax was actually inspired by natural languages) where the construction

of artificial languages did not have a lot of problems in the natural language.

The next aspect is 'semantics', very often called the semantics of a programming language,

which is really specified by its reference manual.

In your study of Pascal programming one of the important references would be the ISO

standard Pascal reference manual by Janson Edward. That reference manual really specifies

for each syntactic entity of the language the effect to be expected by executing that

syntactic entity which is the meaning associated for each language construct.

So, we have to look at the notion of meanings. Unlike natural language the notion of meaning

can be specified mathematically in a machine-independent fashion.

When we are talking about the semantics of this programming language, we are talking

about a pure meaning associated with the language regardless of any machine on which the language

is implemented. In general we are talking about meanings in an abstract setting in the

sense that you assume for practical purposes that you have no restrictions on the word

lengths, no restrictions on memory and you have no restrictions on computational power

except that you can only do a finite number of operations at any instance.

The programming language itself can be thought of as a mathematical entity quite independent

from all its implementations and in general when you think of it that way then you are

thinking of some kind of an ideal machine which has no restrictions except one that

at any instant of time only a finite number of operations can be performed.

You cannot do an infinite number of operations at any instant of time. If you consider such

an ideal machine then you are really looking at the programming language as a mathematical

entity in some ideal environment and the meanings of the constructs of the language in that

ideal environment, form, what might be called the actual reference manual.

If you were to go through the reference manual of Pascal, most of the reference manual is

independent of any machine. There are certain specific machine paragraphs or what are known

as implementation dependent features. But if you look at the language itself, it is

capable of looking at the language as an entity devoid of any machine.

In general the semantics would follow the syntax. The syntax has a certain structure.

The syntax has got some basic elements and some compound forming operations. They are

connectives which allow you to form compound sentences from simpler ones.

The meanings in general should be such that you give the meanings of the basic elements

and then you give the meanings of the connectives in terms of the basic elements.

A programming language is really a finitary object which allows you the construction of

the infinite set of programs.

It is not in general possible to predict the behavior of the language of a program written

in the language unless you have this basic discipline where you express the effects of

connectives in terms of the effects of the basic elements of the language.

It is not in general possible to predict the behavior of the language of a program written

in the language unless you follow this discipline.

The basic feature of any kind of semantics is that it should allow for the derivation

of the meanings of an infinite number of programs which means the only way to derive the meaning

of the program should be from the meanings of its finitary elements.

You have certain basic elements from which complex elements are formed. So, the meaning

of the complex element should be derivable in terms of the meanings of the basic elements

and the meanings associated with the connectives that formed a complex element from the basic

elements. It means that semantics is going to be intimately related to syntax.

The syntax is really a finitary way of specifying an infinite set of allowable objects.

The infinite set of allowable objects are the programs of the language or the sentences

of the language and the syntax gives you a finitary mechanism for specifying all possible

allowable programs very much like a set theory notation, which allows you to give a finitary

specification for an infinite set. What is really analyzable for an arbitrary program

is its structure in terms of its syntax. The meaning of the program has to be derived

from its finitary specification to be expressed in terms of its finitary specification.

Lastly, do not worry about machine constraints or about architecture because the programming

language has to be portable. Do not worry about word lengths or about limits and also

do not worry about memory constraints. Assume infinite amount of memory available

so that you get into what are known as pragmatic considerations. Most of these implementation

dependant features are really pragmatics, for example; the Pascal reference manual does

not tell you how to associate a disc file with a file variable inside the program. That

is one example of an implementation dependant feature which will vary depending upon the

operating system interface you have. Then there are various simple implementations.

The pragmatics firstly involves really all the algorithms that are going to be used for

the implementation of the language and all kinds of machine and architectural constraints

for example the MAXINT. The maximum integer allowable in a Pascal program is a typically

implementation dependant feature because it really depends upon word length or byte length

or on whether it uses two bytes for representing integers etc.

The value of the MAXINT can vary from machine to machine. The amount of memory that is available

for a program can vary whether it is a stack based machine or a register based machine.

All those are implementation dependent features.

Normally, the way to make the language portable even in our implementation is to separate

the basic algorithms of implementation from the architectural specific nature of the implementation.

When we read through a small compiler you will see this happening. So, there are certain

basic algorithms which are really machine-independent and then there are some machine dependant

features and the actual code.

Then you have the OS interface, the nature of the input and output that is file-based,

terminal based, sensor based, signal based, etc. The OS interface also includes the file

server, how the language has to interact with the file server and how the language has to

interact in general with the directory service of the machine etc.

Lastly, what is to be done about errors introduced by users in their programs? Errors could be of a syntactic nature or of

runtime nature and we need to know what to do about them. There is a blanket policy where

you could just abort but you know that does not help anybody in particular. What is the

nature of error reporting? Is there some error correction that can be

done? Is there some way of recovering from errors so that as soon as the first error

comes, you just throw out the program? - No, if you can you should at least be able to

point out all the errors in the program or all possible errors so that the user gets

to know all the errors at one time. It reduces the amount of compilation effort and similarly

you cannot do that at run time but at least there should be some decent error reporting


But error is a very dicey subject and dicey policy. Different languages have taken different

attitudes and different implementations take different attitudes towards it. So, it is

a very pragmatic feature. I will just briefly go through the notion of syntax. There are

three issues and it is better to study all three issues separately. The semantic and

pragmatic issues will closely depend upon the syntax and it is preferable that they

depend upon the syntax. Let us look at what constitutes syntax.

Syntax has to do with a form or a physical representation of possibly an abstract object.

If you look at numbers, they really are not very physical. At least the 20th century attitude

towards numbers is that they are a conception of the mind and are not physical.

They do have a physical representation in the form of numerals. What you write out and

think of as a number is actually a numeral so while you have various ways of representing

the same number let us say the number 126 you can have what is known as the positional

representation which is what we normally use.

In the basic form all these three representations of the number 126 are really the same.

The roman representation differs from the DEVNAGRI representation in the sense that

the characters used are different. What might be called the basic alphabet for the positional

representation of numbers is different in the two.

It is just that the character set is different but that is incidental. It is a positional

representation but in basic forms all these are unified by the fact that they are all positional representations.

You go in units: 16s...64s... Then you have the roman numerals which is non positional.

Firstly, it has a different alphabet. You could represent the same number 126 with different

character sets but there is something unifying about this. There is some fundamental difference

about this representation.

If you disregard the change in character set what makes these two classes different is the grammar

of the numeral of the language used for representing them.

In both these cases the grammar is exactly identical, the character sets are different

and by and large the grammar of all these three is the same except for the character

sets but the grammar is different in the sense the form of representation is fundamentally

different. How you represent compound forms from simpler forms is different between the

roman and Arabic case. What that grammar is, is what we have to study.

Let us look at this in a more general setting of the programming language.

We might think of every programming language as having a vocabulary. A vocabulary is a

complete dictionary of words of the language. A word of a language is formed from a fixed

character set and you identify certain strings of characters as allowable words as part of

the vocabulary of the language. A complete dictionary of the language is what states

that vocabulary. If you take languages, for example natural languages like Konkani or

Sindhi they have different character sets but the same collection of words.

Sindhi for example is written by different people. Some people write in Devanagari, some

people write it in the Urdu script or in the Arabic script.

But the collection of the words is the same, so, a person who knows Devanagari can communicate

with the person who does not know Devanagari but knows the Urdu script by speech because

the words are the same although you cannot communicate by letters.

There is a certain fixed collection of words whose actual form might depend on the character

set. But given the words there are formation rules. Given a vocabulary there are ways of

combining words of the language to form sentences of the language and there is a finite set

of formation rules called productions which allow you to generate all possible sentences

in the language.

Let us quickly go through one example. The character set really depends upon the kind

of codes you use. Nowadays most of the time we use ASCII codes but then we have 8 bit

ASCII's and PC's and 7 bit ASCII's on the main frame.

The character sets are different. There are all these kinds of differences but let us

disregard them and look at what constitutes grammar.

I would say grammar is really a four tuple of objects where there is a set N which is

called the set of non terminals and this set of non terminals really specifies various

kinds of grammatical categories of the language like the parts of speech, noun phrase, verb

phrase, adjectival phrase, noun clause subject clauses, subject phrases, object clauses,

predicates etc. This set N consists of the basic grammatical

categories and all these sets are finite. Then the terminal T is the set of what are

known as terminal symbols or terminal words and T is the complete vocabulary of the language.

P is the collection of formation rules or what are known as productions and S is what

is called as the start symbol but S really represents a grammatical category in N called

as sentence. So, the basic element of the language is what

constitutes a sentence.

Here is a simple grammar specifying Boolean expressions. There is a start symbol S,

(every grammar should have a start symbol S) and some grammatical categories. The grammatical

categories that I have chosen are A, V and C which actually stand for an odd Boolean

expression or a complement expression.

The vocabulary of the language consists of all possible Boolean variables that we might

take including the two left and right parentheses and the three connectors and 'not' and 'or'.

Any Boolean variable is a Boolean expression meaning you take any b belonging to the set

of Boolean variables. The sentences of the language are Boolean expressions that are

more than fully parenthesized Boolean expressions.

Any sentence is either a complement of a Boolean expression or of the 2 Boolean expressions

'and' and 'or'. If an 'and' expression is one form which consists of two Boolean expressions

enclosed in parenthesis and separated by the word 'and', an 'or' Boolean expression similarly

is two Boolean expressions enclosed in parenthesis and separated by an 'or' and it is similarly

the case with 'not'. These productions are really replacement rules

so whenever you find an S you can replace it either by an A, a V or a C or one of the

Boolean variables. Whenever you find an A you have to replace

it by this. There is no other way you can replace A by anything else. Similarly, whenever

you see a C you have to replace it and so here is a simple sentence generation.

You start from S and one of the possibilities is that you can replace S by C. Whatever I

am replacing, I have circled in orange. C has to be replaced and now I am replacing

S leaving everything else intact. I have chosen here to replace S by A and once I have got

an A there, the only possibility is to replace it by this form S. I have chosen to replace

this S rather than this S first and I have chosen to replace it by a Boolean variable.

Let us assume that there are only two variables b1 and b2 and I proceed. Lastly, I get a complete

sentence of the language which consists of only the terminal symbols which is generated

by the grammar.

We talk of a language as being generated from a grammar as a set of all possible sentences

that may be generated from the start symbol S.

Important warnings are that the set of non terminals and the set of terminal symbols

are disjoint and a production is really a replacement. It replaces a non terminal by

a string consisting of terminals or non terminals and a sentence is just a string of terminal

symbols generated from the start symbol.

The Description of Lecture - 2 Syntax