dive into compilers straight away, as some of you might want me to do, but to

actually just take a simple, very simple, subset of the English language and see

how we would parse that. And if you look up in a dictionary "what does `parsing' mean"

it says, essentially, one of the definitions is: " ... breaking up sentence

structure into its component parts under the direction of a grammar." so the

So the grammar is the rules of your language. Well, I have drawn up here a language

involving furry dice and robots and people, men and women, and cats and dogs

and they can 'bite' they can 'stroke' they can ... whatever. And I thought: that little

grammar, which I'll walk you through, is capable of generating between 200 and

300 sentences and they are all valid English. But there's no way it

captures the spirit of English. The idea that your sentences have

subject-verb-object is pretty universal, I think, among what's called the

Indo-European languages. However, sometimes it's not always in the order

of subject-verb-object, although that's common. Sometimes they get twisted up

particularly in German, where there's a definite option to have the verb last.

In this example I'm pointing to here, I'm using a notation that we did cover about

three or four years ago now. We'll put out a link.

I think the episode was called Angle Brackets. And they invented a notation

that looks like this: pointy brackets. Yes, back in the very late 50s and early 60s

people who wanted to write compilers realized they had to write

down a formal specification of what were the rules in their language. And two

computer scientists actually won the Turing award - [the] ACM Turing Award - for their

notation and their development of a grammar

for the language Algol 60. And it uses angle brackets all over the place.

So, that was so-called Backus-Naur form. Those are the two computer scntists

who developed it. People really liked it. And I've used it here because it's

verbose enough to make some sense. I'll read it out to you. What I'm saying, up at

the top of the grammar - using the angle brackets for what's going to become

parts of a so-called parse tree. A is defined as then a

then an . That's the most common form of English sentence the

subject is the person, or thing, doing the action. The verb says what the action is:

'kicked' 'bit', 'stroked' ... whatever. The object says what it is doing it to. [e.g.] 'the man

kicked the robot' And it's such a powerful language! You can have either

'the' or 'a' [as] definite or indefinite article. You can have 'the robot' or

'a robot'. You can have a choice of verbs either 'bit', 'kicked' or 'stroked' - you're

going to be very expressive in this language (!) Your subject of the sentence

can either be 'dog', 'cat', 'man', 'woman' or 'robot'. And finally the tailpiece. The object

i've decided could either be any followed by a again, like 'a dog',

'the robot bites a dog' [is] perfectly possible. But just to show that you can put in

shortcuts, if you like, and put bits of structure in there that aren't parsed -

they're just globbets you can put in - I have defined the phrase: 'two furry dice'

as being a valid 'object'. Just the string "two furry dice". So the target

sentence, that ultimately we're going to try and construct from all of this, is

the [in lower case] robot stroked [writes on paper] ... running out of space here, carry on on the line below ...

"the robot stroked two furry dice" We all agree it makes sense [but] is it parsable

against that set of rules? And how would you go about showing that it was?

>> Sean: So by 'parsable' you mean "can we decode it"? >> DFB: [Yes] can we decode it? Can we assign everything to

be the right flavour of structural component according to those [grammar] rules.

You can either start with a string, which we've got here, and start trying to group

things together and work upwards. Now we all know about trees - the root is at the

top. We're computer scientists, the root is at the top; the leaves are at the bottom.

They're always upside down. Do we start with and leaves and say:"Ooh! the

robot stroked ... The robot stroked ... Looking sideways at the grammar I can

see there's a shortcut for "the robot". So I'm gonna start coming from the string

upwards and see if I end up back at the root of the tree, or shall I start at the

root of the tree and say: "I must have a subject then a verb then an object". Can I

see anything that could likely be the start of a ? That's called coming

top-down. So it's been there in computer science ever since the dawn of computer

science: the top-down approach versus the bottom-up approach.

There's no prizes for guessing that functional languages like Haskell tend,

by their very structure, to favour the top-down approach. It's messier, is the

bottom-up approach. I shall try to indicate both, OK, but let's

just this once, let's go top down rather than bottom-up.

If we're coming top-down it is telling me, is this grammar, that I must have a

then a then an . Now, for those

of you who are concerned with a mechanistics -- you can actually think

of these things, if you're coming top down, as being pushed as targets, that

you've got to satisfy, on a stack which .... We all know about stacks! This one is not

building upwards and downwards it's building from right to left. So, at the

top of my stack currently, because I'm coming top down, I say my target my

sub-target is . I must find a . But I must keep half an eye on the target

string to say: "does it really match?" If we cross-refer now, to this grammar,

for inspiration, we're trying to match a If I look at the grammar over

there it tells me that a can either be an article and a noun like

"the" and "a" , with a like 'cat', 'dog', 'robot' or you can take a shortcut. Because it

tells you here that the just could be the phrase "the robot". So let's

go for broke. I'm looking at the input string and I see

"the robot". So let's take the shortcut just to be devils, right?! I can say

straight away then, taking the shortcut, that can be the string

"the robot". That's good! Now, having satisfied , I pop it

off the top of my stack. I've done that. Next thing, to match this sentence,

you've got to be able to match the . Well, we're going along the string we've coped

with "the robot". Next word - next valid leaf word - that has to match up with being a

. I'm looking at 'stroked'. Is 'stroked' a possibility? Look at . What are the

possibilities for ? And I see 'bit' 'kicked' or 'stroked'. Great! I choose 'stroked'.

But, once again, if you can imagine the stack I then pop that off the top of the stack

-- we've done it! The stack is shrinking! all we've got left to identify

is an that matches [in] that sentence. Again, I've pulled a fast one here! In the

rules for I said you can either break it down into an and a ,

just like the , so nice having the action done to it. Or you can take a

whizzy short-cut. An allowed shortcut, for an is what you might call an

and I put it in deliberately, just to make a point: "two furry dice" Wonderful!

Simplest parse going: an can be "two furry dice". We declare success and we say

we have matched "the robot strokes two furry dice" by going .

came down into being shortcut "the robot". developed straight away

into being "stroked". shortcut to It's a very shallow tree, really.

But it's developed the target sentence: "the robot stroked two furry dice".

Now, the only thing you might say: "Well, yes, wonderful, we've parsed it. But would

it have worked if the instead of taking the shortcut. Could you have

done it with the option?" Yes, you could.

I could have basically, come here: let's write out:

and, yes, right at the beginning instead of taking the shortcut phrase

"the robot", I could have said: "Ah! but I'm going to do it as can be an

followed by a ". So, the head of the stack then would be - when we're

looking at the sentence and starting off from the beginning again - it's got to be

an to start with. is 'a' or 'the'. Oh! I'm looking at the string, I see "the".

Bingo! So, article can be "the" - no problem.

Pop that off the stack. What's the next thing I've got to look for? . Can be "robot",

which is the next thing I'm looking at? Yes, "robot" is an option, so I could have done

"robot". Now the is as before. It's got to be "stroked". And "stroked" is

there. And equally the is as before. There's only one way to develop

the string: "two furry dice" and that's to take the declared short-cutk that does it for

you. The reason for doing this rather artificial example is to say: "Oh dear!

Does this matter? We have got a sentence that makes perfect sense to us: "the robot

stroked two furry dice". But you've drawn two slightly different trees. First time

you took a shortcut subject-phrase, just for "the robot". Next time you said: "Ah! but

we could also do it by breaking it down further into a 'the' and 'robot'. Does that

matter? In this particular case, in informal spoken English, no it doesn't.f

If people understand you the fact that your grammar is technically called 'ambiguous'

- so if you say to yourself what does 'ambiguous' mean? It means there's more

than one parse tree that seems to satisfy and give the final target phrase.

Does that matter? In this case 'no'. Does it matter in general? Yes, because you might

get very different effects under certain circumstances. What I think I'll show you

is a favourite one almost. Which is to check your 4-function desk calculator.

When you start typing things into a 4-function (so-called) hand-calculator.

You're basically putting in, shall we say, integer numbers - let's simplify it.

But the burning question is something like this: that if you type in 8 * 4 * 2

You may not think of it in those terms but computer scientists

would say: "Yes ,if you've got the right grammar rules that's an example of a

"sentence". That is a - what might you call it? - a sort

of subsection of a long calculation, that you do on the right-hand side [say] of a C statement.

It's just 8 times 4 times 2. There's no problem is there?. Eight 4s are 32.

Two 32s are 64. But then you say: "Ah! but we're into tree structures now. How would

you parse that sentence, given that multiply can only multiply two things

at a time. So, are you going to arrange it so that your overall expression groups

as 8 * 4, done on the left. Then you do the multiply by 2, which is

that tree structure. So, the question is you've got a little bit of depth on your

tree structure here. It's gone down a level whereas finally you've got one [operand]

up at the top level. Do you want that sub-structure to be on the left or on the right?

Because it would be equally OK, as we've got things at the moment, for

you to draw something that's got 8 here, multiplied by here 4 * 2 with a

multiplier between. So have we got a little bits of tree structure on the

left or on the right? And does it matter? And you say no it doesn't matter. We all

know that you can't complete the expression until it's left operand

is known and that involves forcing you to do the multiply. 8 * 4 is 32.

Fine, 32. What's the other operand here? It's multiply by 2: 32 * 2 = 64.

Equally, over here, 8 x (four twos are 8; eight 8s are 64) So, you're doing it two different ways

but you're getting the same answer. And the reason that's OK

is that multiply is well-behaved [over the integers] Mathematicians will tell you it commutes

a * b is the same as b * a for integers [and * is also associative over the integers]

However, just look at the ambiguity, OK, Two different parse trees and it

didn't matter for multiply. [But] just suppose those multipliers weren't multiplies but

were divides [ / ] . Does it then matter that you do 8 / 4 first in

this one? You get your 2 and the multiply is now replaced by a divide:

2 / 2 is 1. But look at this other possibility and

just mentally substitute divides for multiplies. 8t divided by the result

of 4 / 2 ? Well 4 /2 is 2. 8 / 2 is 4.

Two completely different answers! Is it 1 or is it 4. If you're panicking take

out your calculator now and check the app. Just do 8 / 4 / 2 and

if the answer isn't 1 demand your money back!

Here we see it then. Here is an example of where ambiguity [two differing parse trees] does lead to problems,

because depending which tree you choose you get a different answer. So, there we

are then. We now know what a grammar is. We know that against a grammar you can

try and parse things like sentences but "sentences" [is] used in its widest sense.

It could be a program statement from C and just think of this: 8 * 4 * 2

has been as a part of a phrase on the right-hand side of an arithmetic statement.

And grammar is the guiding principle for the whole thing.