Name: Parsing Explained - Computerphile
Uploaded: 2020-03-27T16:57:13.000Z
Duration: 14 min 58 s
Description: Thousands of YouTube videos with English-Chinese subtitles! Now you can learn to understand native speakers, expand your vocabulary, and improve your pronunciation...

Adverbs of manner

I actually think that if we're going to do parsing it might be easiest not to

Modal verbs - B1

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

Adverbs of degree

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

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

Subtitles ListPlay Video

Parsing Explained - Computerphile

approach

phrase

expression

panic