Good morning, good afternoon, good evening or good whatever or whenever, you are
actually listening to this. Today we're going to start a completely new tack,
where we learn about a second important class of languages other than the regular
languages. This class is the context-free languages. They include all the regular
languages and more. The most common description of these languages is a
context-free grammar. We'll see the definition of these grammars and the way
these grammars define languages, which is through derivations. We're also going to
introduce a related notation called Bacchusnouer four. The two most important
applications of context free grammars are probably a processing natural languages
and computer languages. I am going to focus on computer languages Where almost
every language today has its syntax defined by a context free grammar in the
Bacchusnouer notation. Grammars are also essential when designing a parser for the
language. That part of the compiler that puts together the tokens of the language
into the proper structure. For example, the parser discovers the order in which
arithmetic operators in an arithmetic expression and group statements properly
so their execution sequence is as intended by the programmer. A context free grammar
defines a language by a mechanism we will soon learn. Every regular language has a
context free grammar describing it but there are also languages that can be
described by a grammar but that are not regular. On the other hand, the context
free grammar is still a relatively weak formalism. There are some languages that
are simple to describe yet have to context free grammar. Many of the languages in the
context free class that are outside the regular languages are languages that
involve nested structures such as the patterns of left and right parenthesis
that we called balanced. The central elements of the grammar are variables.
These are symbols that generate particular sets of strings. One of these symbols
called the start symbol will generate the entire language. But we can add many
others to help us in that definition. The variables or rather the sets of strings
they generate, are defined recursively in terms of one another. The rules that
define the languages of the variables are called productions. Each production has a
variable on the left, say A, an arrow And zero or more symbols on the right will
draw say x or y on the right, that serve as the definition. A rule like this says
that the concatenation of the languages represented by x and y is a subset of the
language represented by a. A variable may have several productions and its languages
thus defined to be the union of the languages described by the right side of
each of its productions, but remember, all of this may be recursive so grammars are
in fact far more powerful than the regular expressions we can build from unions and
concatenations. For our first example, let's consider the language that we showed
not to be a regular language. The set of strings of the form of N, zero followed by
the same number of 1s. Here is a grammar for this language, Two productions or
rules and only one variable s. The first production, this one is a basis rule. It
says that the string zero one is in the language of s. The second, this, is an
inductive rule. It says that if w is a string in the language of s, then zero w
one is also in the language. That rule lets us build longer and longer strings at
each step adding one zero to the beginning and one, one to the end. So we always have
the same numbers of zeros and ones with the zeros preceding the ones. Now lets
make precise our informal introduction to what context free grammars look like. The
terminals of the grammar are analogous to the input symbols of an atomaton. They
form the alphabet for the language being defined. The variables or non-terminals
are something like states of automaton but they are more powerful. One variable is
called the start symbol. It is the language of this variable that the grammar
defines. And the other variables are used as auxiliaries but we can think of them as
internal to the grammar and their languages are not visible outside. The
productions of the grammar which are akin to the transition function of an atomaton
have the form of the variable on the left, sometimes called the head, an arrow and a
string of zero or more symbols which can terminals of variables. These are
sometimes called the body of the production. We have the convention about
the letters used for certain symbols and strings. These conventions are more
complex than the convention we use to distinguish input symbols, little a,
little b and so on from strings w, x and so on. But they're really important as a
reminder of the roles different components play and it is something worth committing
to memory early on. First, we use capital letters at the beginning of the alphabet
as variables. However S is also normally a variable. In fact it will be the start
symbol in many grammars. On the other hand, lower case letters at the beginning
of the alphabet are terminals. This convention agrees with an earlier
convention that made these letters stand for input symbols. Since there is a good
analogy between the inputs of an atomaton and the terminals of a grammar. Capital
letters near the end of the alphabet are used for symbols that can be either
terminals or variables, we typically don't know which. Lower case letters at the end
of the alphabet stand for strings of terminals only. Again, this matches our
earlier convention. And we use Greek letters at the beginning of the Greek
alphabet for strings that may consist of both terminals and variables mixed. We'll
design a grammar for the language of strings with the form zero to the n, one
to the n. The terminal alphabet is zero and one of course. We need only one
variable in this case, we'll call it S. S will be the start symbol. There's no other
option since it is the only variable. And here are the productions which we
explained earlier in our informal discussion. The first production generates
only the string zero one and the second production puts a zero and one at the
beginning and end respectively of a shorter string in the language. A
derivation consists of a sequence of strings that typically have both terminals
and variables, although they can have only one kind of symbol or even be empty. We
start with the string consisting of just the start symbol. At each step, we find a
variable to replace, say A. The productions for A, or the A productions,
are those that have A on the left side, that is the head of production. We replace
this A by the right side or the body of the production. We can then repeat the
process as many times as we like until we are left with only terminals at which
point no replacement is possible and we have in fact generated a string that is in
the language of the grammar. Here's what the replacement looks like. You take any
string that has an occurrence of some variable A and anything to the left and
right. Terminals and or variables, which is what the alpha and beta we have here,
suggest you take an A production who's body is gamma and you replace the A by
gamma. Here is an example derivation. We always start with the string that has Just
the start symbol s. We choose the second production so S replaced by zero, S, one.
Now, we replace the s, again using the second production. And again we replace
the s, but this time we use the first production whose body is just zero one. We
are now left with a string that has only terminals and this string cannot be
subjected to further replacements. You should be aware that in more complicated
grammars, variables can be replaced by strings that contain two or more
variables, and when that happens we have lots of choices of what variable to
replace at each step. And derivations can be much more complicated. The double arrow
symbol represents single steps of a derivation and just as we extend the delta
the many steps for atomaton, we need to have a notation that means any number of
steps for a derivation. This is the arrow star symbol, and we define it inductively.
The basis is that in zero steps the string can't change, so any string goes to star
itself. The inductive step lets us get from alpha to beta using any number of
steps using any numbers of steps including zero steps. That's that. And then with one
more step, get from beta to gamma. The conclusion is then that alpha goes on some
number of steps to gamma. Here's an example using the same grammar as before
and the same derivation sequence we just discussed. We can conclude that s goes to
itself in zero steps, that is we just start here, don't go anywhere. So we can
conclude that s goes to star itself. Then inductively, S goes to 0,1, zero, S, one
rather 00, S1 and 000111. Notice also that we don't have to start with the start
symbol. It is also true for example, that 0S1 goes to star Zero, zero, zero, one,
one, one. That is anything along the derivation sequence goes to any later,
goes to itself and any later position along the sequence. A sentential form for
a grammar is any string derivable from the start symbol. That is, s arrow star the
sentential form. The [inaudible] form can consist of any mix of terminals and non
terminals. The language of the grammar G is the set of terminal strings W such as
the start symbol G derives W. Here's an example grammar that's just a little
different from the previous one. Here the basis rule is that S goes to Epsilon
rather than S goes to 01. Note that Epsilon is a perfectly legitimate body for
production and is effective to make the variable on the left disappear. As a
result, this grammar can derive the empty string along with all the other strings
that have some numbers of 0s followed by the same number of 1s. That is, the
language of this grammar is this set of zero to the n, one to the n, such that n
is at least zero while the previous grammar had at least one as the condition
on n. The class of language is called context-free languages consists of all
those languages that are defined by some context-free grammar. We now see that
there are context-free languages that are not regular languages, such as the zero to
the n, one to the n example just given. However there are languages that are not
context free and the intuition is that context free grammars can count two things
but not three. Thus an example of a language that is not context free is zero
to the N, One to the n, two to the n, say, such that n is equal to a greater than
one. That is, you cannot match both the zeroes against the ones and the ones
against the two at the same time. I want to introduce a notation called BNF or
Bacchusnaur Form, which you may have seen in manuals for programming languages, and
which is closely related to context-free grammars. Bnf has a number of extensions
of the grammar notation we use, and these extensions are useful in manuals but don't
add any power. B and F style notations were used for two of the original
programming languages. John Bacchus used it in the original description of Fortran
and Peter Nouer used it in the original description of [inaudible]. In B and F you
usually use a word to describe a variable for example, statement for the intent is
that this variable will generate all the strings that valid statements of
programming language. Conventionally these words are put in triangular brackets that
tell us they are variables rather than terminals. Some terminals for programming
language are single characters just like in our formal context free grammars. For
example, the plus sign or semi-colon are commonly terminals in the grammar for a
programming language. However other terminals are really reserve words like if
or while. And we see these shown either in bold or underline depending on the style
used to remind us that they are single symbols. In B and F we often colon, colon
equals used in productions rather than arrow. We also find a vertical bar used to
list several production bodies that have the same head. That is a useful convention
that we should use in formal conventions as well. For example, our original grammar
can be written with s ones on the left side and the bodies of the two s
productions listed with the bar connecting them. We follow a symbol or bracketed
expression by dot, dot, dot. So here's an example. We have one variable digit with
the obvious ten productions all grouped together with the bars. Then we have one
production for the variable unsigned integer. With the right side digit, ... ,
that is one or more digits. In general, we can replace alpha ... By two productions.
Let A be a new variable that generates all sequences of one or more alphas. A has two
productions with bodies a alpha and just alpha. They are. You should be able to see
how a can be replaced of n alphas. Just use the first production n minus one times
and then the second production once. For example, here is a grammar for unsigned
integers, where the BNF d dot, dot, dot has been replaced by the these two
productions. These generate any sequence of one or more D's. Then D generates each
of the ten strings consisting of a single digit. That's, of course, that. We can
make part of a production body be optional if we surround it by square brackets. For
example, many programming languages have both an if then and an if then construct
for statements. We can see this as an if then statement with an optional else
clause. In B and F we put brackets around the else clause to make it optional.
That's essentially this stuff there. We can replace an optional alpha by a new
variable a. This variable has two productions, one with a body alpha and the
other with the empty string for a body. Thus the alpha can be either there or not,
when we expand the new variable a. Here we're using I for IF, T for then E for
else and the semicolon is another terminal standing for itself. S is the start symbol
standing for statement. And C is another variable representing conditions. We
really need to add production for conditions but I haven't done so in this
fragment of a real grammar. Notice the a is a variable standing for an optional
else clause. Okay. It can be replaced by a semi colon and else and another statement
if we want to have the else clause there. Or by epsilon if we just want an if/then
statement with no else clause. Curly braces are used in B and F for grouping
several different elements. You need this for example if you want to have a
repeating group of elements and a ... Or one or more construct. For example, it is
common if programming languages to allow a statement list to be one or more
statements. The statements are separated by semicolons so there is one fewer
semicolon than statements. That is a statement list consists of one statement,
that's this. Followed optionally by one or more groups consisting of a semi-colon and
a statement There. The Brackets form a group and then finally the ... Applying to
the group says one or more of these groups. Finally you have the braces And
those braces say that the whole thing is optional. To translate groups to our
original notation, just create a new variable a for the group. A has one
production whose body is the group. Here's an example of a production that uses all
three BNF features, one or more optional and grouping. It says a list of statements
L is a single statement S optionally followed by one or more groups each group
consisting of a semi-colon and a statement. The first thing we'll do is
replace the group semicolon S by a new variable A. A has one production in which
it is replaced by thing it stands for, that's this guy right here. And next we'll
introduce a new variable B which stands for the optional A ., ., ., . B has two
productions, it is replaced either by the A... , that would be choice, or, it is
replaced by the empty string. Finally, we replace the A... And the B productions by
the new variable C. The productions for C, which are here, allow C to be replaced by
any sequence by one or more As. When a sentential form has a number of variables,
we can replace any one of them at any step. But what string of terminals a
variable ultimately gets replaces by is independent of what else is in the
sentential form. That's actually where the term context free comes from. As a result,
we have many different derivations of the same string of terminals. We can restore
some order to the world by requiring that a particular variable be replaced at each
step. Although we cannot demand that any particular production be used for the
replacement. One reasonable rule is to require that the leftmost variable be the
one replaced at each step. This rule restricts us to what are called leftmost
derivations. Similarly we could require that the rightmost variable be replaced at
each step, and that gives us the rightmost derivations. The double arrow with an LM
subscript That's this, represents one step of a left most derivation. That is, on the
left of the arrow LM we must have a string in the form WA Alpha. Here you see one.
That is since W by our convention has terminals only, A must be the left most
variable in this string. On the right is the same string with the body, say Beta,
is that, of some A production replacing it, A. The symbol consisting of the double
arrow with the subscript LM and the star. That's this, means becomes by a sequence
of zero or more leftmost derivation steps. Let's introduce another very simple
grammar that generates a language that is not a regular language. This grammar has
only one variable but unlike the zero to the n one to the n grammar there are
productions with more than one variable in the body. This grammar generates strings
of balanced parentheses. Those strings that are legal and arithmetic expressions.
The last production, here's it's body. Says that a pair of matching parentheses
is balanced. Of course the left parenthesis must come first. The middle
production, this, says that if we put matching parentheses around a balanced
string it is still balanced. And the first production, this, says that the
concatenation of two balanced strings is balanced. We need to prove that every
string of balanced parentheses can be generated by this grammar. The proof is
not too hard but we're not going to do it here. Here's an example of a leftmost
derivation. We start with just S, so that is the leftmost variable. We replace it by
two S's at the first step. There we go. Next, the first of these S's must be
replaced in a leftmost derivation. We choose the second production for the
replacement. There we are. At the third step, the first of the S's must be
replaced and here we choose the last production in the replacement, that's
giving us that. [sound] At the last step, we have only one S and that naturally is
the one we replace. We've chosen to replace Using the last of the three
productions so now we have a terminal string and are done. The arrow star
leftmost notation can be used to express zero or more leftmost derivation steps. So
for example, S is related to the terminal string by this relationship. It is also
related to itself and all the other steps in the derivation by the same relationship
and in fact each step is related to itself and all the following steps. Here is an
example of a derivation that is not left most. The problem is that if the second
step, the second S, rather than the first, was replaced. Rightmost derivations are
defined quite analogously to leftmost derivations. The arrow with an RM
subscript, this. Means that the rightmost variable is replaced at the step. Notice
that the string on the left which is this, has W which must be a string of only
terminals following the variable A that it's replaced. Thus A is surely the
rightmost variable. And the arrow with the RM and a star means zero or more steps in
the rightmost derivation. Here's a balanced parenthesis grammar again. Now we
have a rightmost derivation of the same string as before. Notice that at the
second step, okay, the second S got replaced rather than the first. S is
related to the terminal string by the arrow star rightmost operator. And as the
leftmost derivations each step in the rightmost derivation is related by the
operator to itself and all the steps that follow. Here's an example of a derivation
that is neither a leftmost nor a rightmost. See how at the third step The
middle S is replaced. Also notice that the second step is correct but the ambiguous
in a concerning way. One of the [sound], here, one of the these got replaced by two
[sound] but we don't know which.