Generating a Computing Language….unfinished from undergrad days!!!

It is now an established fact that in the revolutionary globe of computer industry spanning the terrestrial nook and corner, Indians have emerged as one of the leading proponents of software profession and are now being looked up with respect almost in the sense of getting the technological deification. But most of this apotheosis is confined to the software tools that are heavily in use. But the question arises as to why can’t we churn out research scholars working towards the generation of languages and making a mark in this stream also. Is it that the resources are inadequate/ or there is a twist in the story altogether. Majority of the technical students in the sophomore year decide that there has to be a career which would secure their cause financially and to an extent psychologically ( a different picture and hence leave it untouched ). Research in software isn’t expedient as compared with how a person uses it otherwise. Idiosyncrasies turn up and people think that working towards a new development is onerous. ‘ipso facto’, we have resources which are sine qua non in nature, but at face value the two factors which have emerged as dissuading ones are lack of influx of funds, which in turn don’t pay heavily to a scholar endeavoring this line of action and secondly the brain drain that this country is suffering from is sucking the nutrition from the vast pool of talent in our motherland.

I won’t astray anymore but now acculturate to a very language of what is really happening at the very foundation of the software tool that one is using. Let us take the view that the tool is general and anybody using any software language or package is open to this grammar.

Whatever follows here is very succinct in nature :

The basic characteristic or eligibility is accepting the power of discrete mathematics as the new mother tongue.

A Programming language is notational in existence and gives a precise description of computer programs and algorithms. They form an artificial set which are defining the semantics and syntaxes in a strict manner as compared with the natural languages.

SET : It forms a collection of distinct objects of any sort and the objects being called the elements and these can occur at most once, order of appearance merely irrelevant.

If x is an element of Set S, then notationally:

x Є S and

x ≠ S ( read as x doesn’t belong to S )

The set theory forms the basis of functions, relations and algebraic structures.

LOGIC : A common term but badly misunderstood by many. It’s the science of reasoning, inference and ratiocinating. Two common systems are:


                                                      Propositional      Predicate

                                                      Calculus             Calculus

Propositional calculus forms the system of symbolic logic, the study being called Propositional Logic. It has only two admissible terms/symbols in T and F, together with logical propositions that are denoted by small letters; those symbols being indivisible and hence are called atomic formulae. Propositional calculus is based on study of well formed formulae or ‘wwf’, e.g.

( ~ A ) , ( A Λ B ) , ( if A then B ) etc.

Predicate calculus : What is a Predicate ?

06cd070e1f95efae9890306b920a4d9cA function from some domain to a truth value is a predicate.

If a domain has x variables , where x Є 0,1,2,3,…, then the function is called a x place predicate.

Predicate is a statement iff x = 0.

Statement is the unit from which high level language program is constructed i.e. a program is a sequence of statements.

Predicate calculus forms the system of inference that is the generalization of the extended propositional calculus.

DECLARATION : An element in a conventional program. It tells the program its scope and defines the static properties, e.g. declaration of variables, procedures etc.

Before exploring any further, lets take a look at what is BNF…

BNF: Backus normal/naur form. The first widely used notation for describing the syntax of  programming language, invented by John Backus. BNF is capable of describing any context free language.

< digit > :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

< signed number > :: = < number > | + < number > | – < number >

:: = { is defined to }| { as }

angled brackets contain syntactic categories.

  • Context free language: A language generated by context free grammar.

Declarative Languages: Within its scope, the programs explicitly sate what properties the desired result is required to exhibit but not how to obtain them. Ideally it would contain an unordered set of equations sufficient to tell the desired result.

Functional languages: Subclass of declarative languages adhering to the rules of Lambda calculus. Their unordered sets of equations tell of functions and values.

Lambda calculus: Ways about functions and combining them. Formalized in nature. e.g.

λx . x, denotes the identity function, simply returning its argument.

λx . c,  denotes the constant function, returning c regardless of the argument applied.

λx . f ( f (x) )  composites function f with itself. For any argument x, f(x) is returned.


Lambda calculus comprises also of rules for transforming λ – expressions into equivalent ones. For e.g. the rule of β reduction, by which for e.g.

( λx . e1 ) ( e2 ) can be simplified.

λ ( x . f ( x,x ) ) ( a ) → β reduces to f (a,a )

In computer science, Lambda calculus has influenced the design of languages like LISP ( list processing ).

Formal languages: A finite or infinite subset of the set ∑ of all ∑ – words for some finite set of symbols ∑.

∑ is the alphabet of the language.


A principal way for specifying an infinite formal language by finite means. Grammar consists of a set of productions/rules that derive one string from substring replacement. An alphabet is divided into a set of terminal symbols T and a set of non-terminal symbols N. The specified language consists of strings of terminals only.

G is defined as two sets of symbols T and N, a system of T U N and an esoteric member S of N. Language generated by G is the set of all strings over T that can be derived from S, S being the start symbol. e.g.

Let T be { b , c }, N be { S , A } and let the productions be

  1. S → SA
  2. S → A
  3. A → b

Starting from S, we can derive bcbcbc via

SA − by production 1)

SAA − by 2)

AAA − by 3)

bcAA − by 3)

bcbcA − by 3)

bcbcbc − by 3)

the language generated is

{ bc, bcbc, bcbcbc, …, etc.}

strings of bs and cs are derivable from S.

The syntax of programming languages is designed by context free grammar (above example is an illustration).

Context Free Grammar: has the left hand side of each production a single non-terminal. They have the form

A → α ; α is a string belonging to T or N.

A → α1 | α 2        


| αn-1| αn

In contrast, we have the context-sensitive grammar, where the production has the form

α A β → α γ β ; A is a non terminal

α, β, γ are arbitrary words with γ being non-empty.

More importantly to derive an empty word,

S → Λ must be included……


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s