Ambiguity - Programming Languages, Computer Science & Engineering Video Lecture - Computer Science Engineering (CSE) | Best Video for Computer Science Engineering (CSE)

today we will talk about ambiguity but
before that we will go through some
simple definition of a simple
programming language then look at how
ambiguity comes about naturally and let
us see so let us get back to our
favorite grammar our favorite
context-free grammar which you have seen
several times is this and let us look at
let us look at the sentence that we
generated using this grammar so now if
you take a look at this let us take a
look at this sentence generation
carefully if your ultimate aim is to
generate this sentence of this crime
then let us look at how we have applied
the productions of fired the productions
so initially there was no alternative we
took we chose one out of three
possibilities right there are three
possibilities for s s goes rest replaces
replaced by a s replaced by V s replaced
by C s replaced by an identifier so
there are four possibilities of which we
chose one in fact if you have to if you
are to generate this sentence then there
is really no other possibility you
should take any other possibility will
not give you this sentence okay so out
of the four possible choices we have to
choose this and then there was only one
possibility for C and we have chosen
that this here again unless you chose
this possibility a you cannot generate
this alternate sentence
okay and for a there is only one
possibility namely this now you actually
have two possibilities okay we have
chosen to fire this with s goes to be
one okay which is essentially I mean
which is essential in the sense that if
you had to somehow produce this b1 in
the end you would have been forced to
apply this s goes to b1
okay however there was another
possibility that is that we could
instead we could have ignored this and
instead fired this okay so if we had
chosen this s then what would have
happened is we would have chosen we
could have got this this step V first so
these two steps would have been commuted
okay so what we would have got is that
if we have chosen this chosen to apply a
production on this s always keeping in
mind that this is the ultimate sentence
that we have to generate what we would
have got is not open bracket open
bracket V and s and then again we have
the possibility of either firing this V
or this s okay and we could have chosen
anyone
you could either replace this s by this
b1 here or we could have gone ahead with
this V and replaced it by s or s okay
and then here again now you would have
here the supposing you have chosen this
V you would have s or s and you would
this s would still be there then you
have three possibilities with
replacement and you could choose any of
them okay so what I what I am so if you
look at the derivation of a sentence
this particular order is not sacrosanct
out of the various non terminals in the
in an intermediate sentence generation
you could have chosen any one and
applied an appropriate production okay
so there would be many such derivations
of the same sentence okay depending upon
the order in which you have chosen to
apply productions in a sentence in other
words what we are saying is whether you
choose this this it really does not
matter so the so the the various
derivations that you have just give you
various orders whether you for example
here we have not chosen any particular
order we could have chosen for example
to always fire a production of the
leftmost non-terminal symbol in a in an
intermediate string so here for example
we have violated that we have not chosen
the leftmost okay so here you might
consider this derivation as one of
several possible derivations of this
sentence okay so since we are talking
about a context-free grammar and the
replacement of non terminals by the
right hand sides in the production rule
the we are talking of something that is
independent of context so if there are
several non terminals it really does not
matter which non-terminal is chosen
first for replacement provided you you
can so you provided you choose the right
one which will ultimately give you the
sentence so if you were to justify each
of these steps in this derivation by by
which production you have applied okay
so you could number these productions as
one two three four five six seven and
you could write a just if
which just tells you which production
number you apply then even though you
then what you could do is essentially
you could permute the order of
applications of these productions so so
for example in here you do not have my
choice for it here as I said you have
two possible choices either an
application of production for which is
this or an application of production two
which is this right so you could have
just per muted the order in which you
apply these productions but your
intermediate sentences your intermediate
strings will not be the same okay but
you could have per muted the order of
application of these productions and you
could have derived the same sentence so
what it means is that the application of
productions for the derivation of
sentences in a context-free grammar can
often be need not be totally ordered so
they could because of the context
freeness of the grammar there is an
independence in at an intermediate stage
between the various non terminals that
you can choose to replace right so so
what it means is that this there is
nothing sacrosanct about this or this
derivation we could have got another
derivation by just applying the same
productions in a different order so so
what it means is that these productions
because of their independence what we
can however there is a certain amount of
order for example you could never have
applied any of these productions let us
say before applying this production okay
you would never have any of these
possibilities before applying this
production C goes to not s
if you are interested in generating this
sentence so given this sentence you
would have to apply this before any of
the others but here you have a choice
whether you want to replace this s or
this s but the actual production that
you have to apply is still place
specific if you have to generate this B
2 or B 1 you have no alternative but to
replace this s eventually but whether
you replace this as before you replace
this s or after it does not matter ok so
the in any derivation this independence
between the two between two or several
other possible replacements that might
be there gives you a partial ordering on
the application of the production's so
this partial ordering is really what is
sacrosanct so what is this partial
ordering specify this partial ordering
specifies that if that there are certain
productions which have to be applied in
a certain order but other productions
need not be applied in the same order
they could be applied independent of
each other so if you were to look at the
various derivations possible for this
sentence we could take all those
derivations and collapse them to give us
the partial order coalesce them to
actually see independence look for
independence independence in fact what
we can do is we can draw draw three of
exact dependencies ok so that three is
what is known as a parse tree yep
so if you were to take this tick this is
the same same sentence that we have
generated okay and what this tree tells
us is what are the dependencies in the
applications of the various productions
so the root of a parse tree is always
the stock symbol okay now in the
generation of this sentence the first
production that was applied was s goes
to C which I have not written here but
you could you could for example write s
goes to C as a production yeah then the
next production was C C goes to not s
okay so that C goes to not s is what is
here so the various terminal symbols I
mean I am looking upon the whole of not
as a single symbol okay open parenthesis
is a single symbol
I remember our convention that black
denotes terminal symbols the eventual
strings that you generate will all be
strings in black strings of the language
the other colors denote denote certain
abstractions yeah right so the first
production was s goes to C C goes to not
open parenthesis s closed parenthesis
then they were then there was the
production then there was an application
of s which yielded a and that is this
this is an application of the production
su is a and then you have this a yields
open parenthesis s and s closed
parenthesis and now we are here at this
point we are at the same position that
we are here
in the original centers okay and now the
fact that you can choose this s first or
this s does not really matter
eventually in whatever order you apply
the production's for them if you are
interested in generating the sentence
that you have generated then the right
right hand s should go to a b-1 and the
left hand has should be expanded into a
V this V should be expanded into open
parentheses s or s close parentheses and
it does not matter in which order you
perform these two productions the first
one if you are interested in generating
this sentence the first s should produce
a b2 and the second is to produce a B
yeah so that's all that is also the
reason why I have used a a brown color
for the productions so we obtained a
tree which we which we can call the
parse tree and the branches of so that
the leaves of that of this tree are all
terminal symbols notice that all the
leaves of this tree are all black so if
you read if you read the tree if you
read the leaves from left to right you
get the sentence that you generated so
you have not open parentheses open
parentheses open parentheses B 2 or B 1
close parenthesis and b1 close
parentheses close parentheses which is
what the sentences right
so so what we are most interested in is
enough is in the parse tree rather than
in the actual derivation okay so for any
sentence we have a corresponding parse
tree for generating any sentence we do
not necessarily have a unique derivation
okay so in this grammar that we have
defined for every sentence there is
actually a unique parse tree yeah
so let's let's and parse trees are very
important from the point of view of
compiling language implementation the
point of view of specifying semantics
and it's the only thing that is really
sacrosanct and the fact that there are
many orders of derivation for the forest
there are many ways of traversing this
path parse tree gives you several
possible derivations yeah so so let's
just summarize that briefly so we can
look upon a parse tree as presenting a
partial order in the firing of
productions yeah and we can look upon a
derivation of a sentence as just one of
many possible traversals of the parse
tree of the sentence so for each
sentence what we would like to have is a
unique parse tree not necessarily a
unique derivation what we want is a
unique parse tree okay so the traversal
of the tree depending on which how you
decide to traverse the tree you have
various possible derivation so you can
look upon a derivation as just a
linearization of a partial order yeah I
think most of you are familiar with
topological sorting
so for example a topological sort
just takes a partial order and
linearizes it you sort it so that you
you you you provide a linear order a
total order of all the elements such
that the dependence is specified by the
partial order are maintained but where
dependencies do not exist you might
place them in any order you like
okay so then a linearization of a tree
always gives you a total order okay and
you can have and in fact for partial
orders it's also true that a partial
order is completely defined by the set
of all possible linearizations of the
partial order so essentially a parse
tree is also completely specified since
it's a partial order by the set of all
possible derivations or traversals you
can make of the parse tree yeah so this
is a fundamental property on in the
theory of partial orders which is that
you can look upon every partial order as
actually a set consisting of all total
orders of that set yeah so as being
completely defined by the set of all
total orders okay so now what actually
if the the parse tree that we have
presented is somewhat syntactically yeah
so it is in tactical in the sense that
from the point of view of compiling or
language deaf or language implementation
it is all fine in the sense that well
from the point of view of all of a
language implementation it does not
really matter what what is the nature of
each of these terminal symbols as far as
it is concerned it's some
stream of symbols that are coming and it
just looks upon them as a stream of
symbols but any kind of language also
has an implicit type of terminal symbols
which is clearly distinguished for
example we make we make a clear
distinction always between an identifier
and an operator yeah so for example so
up to so this we might call a concrete
parse tree where we make no distinctions
at all between identifiers and operators
if they are terminal symbols they are
leaves of the parse tree that's it okay
so what we are more often interested in
is what might be called an abstract
parse tree where the same sentence you
actually make a distinction between what
are the operators and what are the
operands so if you look at this sentence
that we have previously generated if you
look at this sentence it is clear that
our intention was to define a language
of boolean expressions where the
operators are not and and are and the
operands are all those boolean variables
like b1 b2 and so right so this clear
distinction between operands and
operators is what leads us to what we
might call an abstract syntax tree yeah
so this syntax tree actually elevates
replaces the non terminals we have been
I mean I have been for we have designed
the language in such a way that we could
easily elevate the operators to the
intermediate nodes of this tree we could
talk we can talk of a root operator
which is not we can talk of intermediate
operators and
or okay so in an abstract syntax tree
the operators are always the
intermediate nodes okay
and the leaves the leaves are all the
identifiers of the operands right and
this is of course not something that's
this is of course not something that's
absolutely foolproof or anything but we
are when we talk about the distinction
between operands and operators we are
saying that we are making a distinction
between the various kinds of terminal
symbols that are there in the parse tree
and we are we are elevating some of them
see if you look at the ultimate language
the ultimate programming language that
we interested in we are really not too
interested in the non terminal symbols
the concrete parts of the language the
real down-to-earth asphalt of the road
if you like are whatever is are all the
terminal symbols but those terminal
symbols in any programming language have
some meaning there are some distinctions
between what is an identifier what is an
operator okay if you want to bring about
this distinction well then what you are
not interested is not in this concrete
syntax tree but you are interested in
what order should I apply the operators
on the operands in fact if you look at
this sentence the reason why we included
parentheses why we have parentheses in
all our mathematical language or
anything is to specify an order of
application of operators on operands
okay
right so and this is especially true for
what what might be called in fixed
operators it is not absolutely essential
to have parentheses but you can see that
otherwise we would have to have a
uniform postfix notation or a uniform
prefix notation if we have to avoid
operators okay so in fact every language
construct can be regarded as an operator
yeah so so so essentially if you are
interest so if you are interested in
giving meanings to languages you are not
interested in the concrete parse tree
but you are interested in the abstract
syntax tree okay if you look at the way
you have done arithmetical calculations
in school you will see that you have
actually I mean so remember that in an
abstract syntax tree there are no
brackets okay given an arbitrary
expression there are various ways of
evaluating that expression you can
choose to evaluate one operand rather
than the other rather than another
unless there is an explicit dependency
that you cannot evaluate one operand
before the other so for example if you
have if you have let us say let us say
an arithmetic expression like 3 x 5 plus
4 x 6 yeah in in our normal arithmetic
there is an implicit order this is the
order so the abstract syntax tree of
this is just it's just the following I
mean it's just this you first apply
multiplication
you cannot do this addition before doing
both multiplications but it does not
matter in which order you do these two
multiplications and then you do the
addition right so all our evaluation
mechanisms actually refer more to a
syntax to an abstract syntax tree than
to the concrete parse tree of the
expression yeah so we have to keep keep
this in mind so we I will often be using
these abstract syntax trees once we go
once we cross syntax I will be using
only these abstract syntax trees yeah so
let us keep that in mind
so now keeping these things in mind let
us define a small programming language
yeah it is very simple it is really
amazingly simple that it is actually
completely useless if you like yeah so
what does this programming language
contain it contains no declarations it
contains only boolean variables and
expressions it contains the following
commands assignment sequencing a
conditional and a simple looping command
yeah
and what I would like to do is to
specify the syntax of this programming
language so that it clearly gives me all
the possible syntactically valid
programs in the language I can generate
so that I can generate from the grammar
all possible syntactically valid
programs of the language for anybody who
has done some programming it is clear
that I mean but it's it's clear that you
know what what kinds of programs you are
talking about you know in the sense that
you know what would be syntactically
valid what would not be syntactically
valid but now there is a question of
formalizing it and giving rules
production rules for the syntax in such
a way that for example if you had to
build a compiler or a translator for
this language you should be able to do
it without any problems
yeah so it's so so in fact if it were a
course on programming what I what I
could do since all of you know some
programming or the other is that I could
just specify this much and then we could
start writing programs yeah but but for
the purposes of translation and
compilation you require to specify
things in a grid in some more detail so
let me just summarize the construction
the summarize my my coding of various
constructs so the this-this-this Brown
is part of the context-free grammar
notation I mean the notation for
productions as I said this this this
Brown looks very much like the bark of a
tree so branches of parse trees and so
on are coded in this color the actual
terminal symbols are of course in black
yeah in this since we have two different
kinds of entities commands and boolean
expressions I have I am I've used this
dark brown for boolean X
patience and what might be called atomic
commands the assignment is an atomic
command for which I have used light
green all other compound commands I use
this light blue and actual program or a
sentence of the language if you like is
in dark brown yeah so this is whenever I
change then change my color coding I'll
inform you but this is how I have to
find a grammar so what we will do is we
will define the grammar in a top-down
fashion I mean the best way to do
anything is top-down so let us let us
look at it problem so so let us look at
this grammar so I have the start symbol
so as far as I am concerned I mean we I
am only interested in sentences of the
language and the sentences of this
language are all programs okay
unlike say a language like Pascal or
something there are no there are no
there is no program heading and there
are no let us say declarations so on so
what is this what is a program in this
language so this rule specifies that a
program is any command so given a so any
command is a full program of this
language yeah so and what is the command
of this language well a command could be
an atomic command or it could be a
sequence of two commands yeah
it could be a conditional command or it
could be a looping command okay
so here I have used this these brown
bars to indicate that this actually is
for productions cro a see arrow c
semicolon c c arrow if B then C LC fee C
arrow while we do see on that so this
bar actually specifies the various
alternatives that you have for each
non-terminal symbol right so so so at
the command level or what in most of
these imperative languages are called
statement level this is the thing this
is these are the various productions we
can look upon the definition of this
programming language in terms of several
levels and this so this this s gives you
the production level gives you the
program level and how the program level
goes into the command level okay
this command level essentially tells you
how it is I have so far not specified
what this atomic command a is okay but
at this point it tells you how to form
compound commands from simpler commands
so it just says that any simple command
is a command and the sequence of two
sequencing of two twelve simple or
compound commands that is why it's in
blue this semicolon is a reserved word
of the language so it is in black so the
sequence of two commands is a command in
itself and if B is a boolean expression
then and then this conditional comma
this conditional compound command might
contain might contain some compound
commands inside it and this while
do command contains a boolean expression
and a possibly a compound command inside
it yeah right so so what it means is
that as far as the grammar of commands
is concerned this B and this a are also
terminal symbols of this this level of
the grammar specification yeah so but
but what we should do is in order to get
a complete definition we should also
look into these atomic commands and the
boolean expressions so let us look at
the atomic command as well as so since I
specify that there is only assignment
statement there is only one one atomic
command yeah so the grammar or atomic
commands is just of this form let us
assume that V is a boolean variable and
B is a boolean expression when we assign
B is the set of a comma so then let me
look at the boolean so the language of
boolean expressions I am defining a
different grammar just for variation
okay I could have used the grammar that
I have previously defined but that
grammar is a sort of a hodgepodge
grammar this is okay so let me look at
this so for one thing in that grammar
there were the constants true and false
were not there okay so that the terminal
true is a boolean expression the
terminal falls is a boolean expression
any boolean variable is a boolean
expression okay so these are the so if
you take the language of boolean
expressions alone as a separate entity
these are the terminal symbols of the
language okay and the next level
specifies how do you make compound
boolean expressions from simpler boolean
expression
so if B is a boolean expression then not
B is also boolean
and given two boolean expressions this
is a boolean expression and and this is
also a billion expression and this is so
what I have used here I have changed the
grammar in the sense that here I have
defined a fully parenthesized notation
so i am i am for all boolean expressions
which are not atomic these are the
atomic these are the atoms of the
boolean expression language for all
boolean expressions that are not atomic
I have enclosed them in parentheses yeah
right
so so now supposing we did not do that
okay supposing instead if we define this
grammar consider so I have gotten rid of
true and false now just consider this
grammar supposing we did get such we
define such a grammar without
parentheses okay then consider this
sentence this sentence is generated by
this grammar it is very easy to give a
derivation for that but not just that
this sentence can actually be derived in
two different ways yeah so look at this
sentence v1 or v2 and v3 and this is my
grammar so what I could do is I could
apply the B or B rule and there are this
I could choose to expand this and get
since my first symbol has to be v1 I do
not really have any other alternative
maybe so I I got v1 or B then I can
choose to expand this replace this by b
and b
and v1 or v2 and B I can choose to
expand this and replace it by v2 then I
can choose to expand this and get this
yeah all right now I could also make a
different derivation so for example I
can decide to apply this B&B here yeah
and I can choose to expand this in give
me v1 or what what did I do
ah I chose to expand this and replace it
by B or B then I chose to expand this
and replace it by v1 then I chose to
expand this replace it by v2 then I
choose to expand this and replaced by v3
yeah and I get the same sentence right
but yeah there are no brackets in the
language right so that is the point so
that is what ambiguity is all about so
so the point is that if you were to look
at the way in which this these
productions have been done then and the
way in which these productions have been
done here and is a root operator so if
you were to look at the abstract syntax
tree then and is a root operator and
below that is an R and this is the
abstract syntax tree that you get yeah
I have chosen to just give you the
abstract syntax tree but you could for
example take the concrete parse tree
also of this derivation okay now if you
were to look at the abstract syntax tree
of the other derivation there R is the
root operator and an comes inside and if
you look at these tools in these two
trees you can see that they are both
actually different
okay there are not just two different
derivations of the same sentence there
are two different derivations with
different syntax trees yeah and this the
two different syntax trees actually
affect how you can specify the meaning
of this language so for example if v1
had the value true and we a v1 and v2
have the values true and v3 were false
then the evaluation of this syntax tree
would give you a value of true and
evaluation of this syntax tree would
give you a value of false okay so if you
look upon syntax as ultimately having to
specify a meaning then what you would
like is a unique meaning to be specified
in that sense this grammar for example
falls short of being an adequate
representation of a unique expression
line an expression language with unique
means yeah so we call such a we call
such a grammar ambiguous
it's called syntactically ambiguous but
the syntax is really a wire media in
which you are going to specify semantics
it is only a an initial handle for the
specification of semantics so so let's
look at this grammar a grammar is
ambiguous if there exists a sentence in
the language with more than one parse
tree
right so so ambiguity is an important
constraint in the sense that it it's not
just that there are just two different
derivations it is that there are two
different parse trees those parse trees
are important both from the point of
view of translating which means running
programs if you if you are looking at
the problem of compiling then you are
really looking at the problem of
executing programs in order to get
meanings so it is necessary for a
program to be interpreted in exactly one
way I mean and actually the the compiler
for that program and the user of that
programming language should both come to
an agreement on how that program is to
be interpreted right so ambiguity has
very serious consequences and specifying
the meaning which means the execution
behavior of programs right and actually
a lot of our programming languages for
example I have a lot of our programming
languages actually do have ambiguity so
the programming language that we have
defined is totally unambiguous if this
grammar specifies a language in which
there is absolutely no earlier
there is exactly one parse tree for
every sentence
now if you were to look at languages are
strange so what one reason why so in the
expression language there is always
ambiguity in most languages but that is
because that's because the expression
language uses allows you to use normal
mathematical notation okay so for
example it allows you to specify various
things with an implicit order of
evaluation so if you look at if you look
at our if you look at our these
expressions for example it allows you
are my normal mathematical notation
allows you to specify this expression
without any parentheses where it is
implicitly assumed that the syntax tree
for this expression if you remove the
parentheses is still going to be this
and nothing else for example it does if
you if you remove the parentheses there
is absolutely no reason except normal
mathematical convention why you cannot
have a syntax tree of this form
there is absolutely no reason why except
for normal mathematical convention there
is absolutely no reason why you should
not construct such a syntax tree
supposing I remove these parentheses
okay but it is just that our
mathematical convention says that well
there is a precedence of operations
which ensures that multiplication is
done first an addition is done later
so if there is ambiguity if there is
syntactic inequity then the order of
evaluation should be that multiplication
should precede addition otherwise the
order of evaluation is as specified by
the parentheses okay so since this is
our normal mathematical notation most
programming languages actually implement
this okay there are this there are also
in the at the command level two there
are syntactic ambiguities for example in
languages like Pascal one is what is
known as that dangling else problem yeah
so that if you look at the difference
between our conditional the conditional
that we have defined and Pascal is that
first if you do not have both an if-then
and an if then else construct we have a
perfect bracket in between between this
for example our if our conditional
construct has a perfect bracketing there
is an if with a fee and a while do with
an odd okay so there is no possibility
of ambiguity except in the case of one
construct what is that
No there is ambiguity
BMA even estate is an instruction this
grammar does not provide ambiguity for
that
it's totally unambiguous for that but it
is still one place where there's handy
the sequencing is ambiguous so think
about it we'll come back to it later