>> Sean: We've looked at Chomsky and we've looked at Finite State Automata,
>> Sean: We've looked at Chomsky and we've looked at Finite State Automata,

and you've given me a sneak preview about what might be next,
and you've given me a sneak preview about what might be next,

and my first thought was
and my first thought was

"What do all these notation marks mean, and where do they come from?"
"What do all these notation marks mean, and where do they come from?"

>> DFB: Chomsky instinctively went for a notation that appeals to
>> DFB: Chomsky instinctively went for a notation that appeals to

mathematical logicians or theoretical computer scientists nowadays -- very tight, very compact.
mathematical logicians or theoretical computer scientists nowadays -- very tight, very compact.

What he would basically say about a programming language identifier,
What he would basically say about a programming language identifier,

which we're trying to define, is that everything in Chomsky's world is a sentence.
which we're trying to define, is that everything in Chomsky's world is a sentence.

We've covered this already in the car park:
We've covered this already in the car park:

"A legal sentence in this language is five-five-five-five-five."
"A legal sentence in this language is five-five-five-five-five."

So everything's an 'S' in Chomsky notation.
So everything's an 'S' in Chomsky notation.

What he would say about the identifiers problem ..., In sensible languages,
What he would say about the identifiers problem ..., In sensible languages,

we've got to start off with a letter. I'll call that L.
we've got to start off with a letter. I'll call that L.

And then, the tail piece of the identifier.
And then, the tail piece of the identifier.

Well, it could be nothing at all because a single letter is an identifier in pretty well every language.
Well, it could be nothing at all because a single letter is an identifier in pretty well every language.

But the tailpiece could be more letters, more digits, in any combination. Fine.
But the tailpiece could be more letters, more digits, in any combination. Fine.

Now, round about the time late '50s turning into 1960, there was a whole bunch of them
Now, round about the time late '50s turning into 1960, there was a whole bunch of them

defining the language ALGOL, which was the first language to be designed by a committee
defining the language ALGOL, which was the first language to be designed by a committee

and ran into all the usual committee problems, but when you think back to that era,
and ran into all the usual committee problems, but when you think back to that era,

FORTRAN was there, COBOL was there, they never, until later on, had a formal definition.
FORTRAN was there, COBOL was there, they never, until later on, had a formal definition.

The ALGOL people said we are going to use something like Chomsky notation
The ALGOL people said we are going to use something like Chomsky notation

to define what's a legal program.
to define what's a legal program.

John Backus and Peter Naur, who were on the ALGOL 60 defining committee --
John Backus and Peter Naur, who were on the ALGOL 60 defining committee --

Backus was famous as one of the big inventors of FORTRAN;
Backus was famous as one of the big inventors of FORTRAN;

Peter Naur, a very famous European computer scientist --
Peter Naur, a very famous European computer scientist --

they said we need something that is more self-explanatory.
they said we need something that is more self-explanatory.

And they invented a notation that looks like this: pointy brackets!
And they invented a notation that looks like this: pointy brackets!

Yes, this early on! And we are going to say, an identifier - not a sentence, it's an identifier we're trying to define.
Yes, this early on! And we are going to say, an identifier - not a sentence, it's an identifier we're trying to define.

And rather than using Chomsky's arrow, which they felt might occur in the middle of a program and cause confusion,
And rather than using Chomsky's arrow, which they felt might occur in the middle of a program and cause confusion,

they wanted a "is defined as" operation here which wouldn't ever occur inside a program.
they wanted a "is defined as" operation here which wouldn't ever occur inside a program.

But they wanted it to be clear it was part of the definition.
But they wanted it to be clear it was part of the definition.

And they said, "Easy, we're not going to call it L, we're going to say ".
And they said, "Easy, we're not going to call it L, we're going to say ".

And you see the advantage straight away: That you can then say, ahh!, it's a letter followed by
And you see the advantage straight away: That you can then say, ahh!, it's a letter followed by

a tailpiece, which we'll call .
a tailpiece, which we'll call .

By putting things in the pointy brackets, we're saying: We don't literally mean that you must look for
By putting things in the pointy brackets, we're saying: We don't literally mean that you must look for

the characters l-e-t-t-e-r on your input, no, we mean "anything that can be a legal letter".
the characters l-e-t-t-e-r on your input, no, we mean "anything that can be a legal letter".

So further down here there'd be another definition saying a letter is an 'A', a 'B', a 'C' (...) all the way up to 'Z', and all that.
So further down here there'd be another definition saying a letter is an 'A', a 'B', a 'C' (...) all the way up to 'Z', and all that.

The tailpiece is far more complicated because it's any mix of further letters or further digits,
The tailpiece is far more complicated because it's any mix of further letters or further digits,

but there could be a definition for digits.
but there could be a definition for digits.

But the point is, they're readable things here, they're readable notions as they're sometimes called.
But the point is, they're readable things here, they're readable notions as they're sometimes called.

And they are pretty well self-explanatory, far more appealing to be setting out a definition of a programming language,
And they are pretty well self-explanatory, far more appealing to be setting out a definition of a programming language,

than you forever having to remember, "Oh, a letter capital 'D', is that a digit or is it a denominator?" You know.
than you forever having to remember, "Oh, a letter capital 'D', is that a digit or is it a denominator?" You know.

Of course the theoreticians say, "Oh, it's far too verbose, but yes, I expect I do understand.
Of course the theoreticians say, "Oh, it's far too verbose, but yes, I expect I do understand.

You've got to make it clear to people who have got no brain, exactly what's going on."
You've got to make it clear to people who have got no brain, exactly what's going on."

So this was very popular for defining languages.
So this was very popular for defining languages.

>> Sean: So this is a bit like having a how-to guide, is it? Like saying "This is not programming; this is how the programming works."
>> Sean: So this is a bit like having a how-to guide, is it? Like saying "This is not programming; this is how the programming works."

Yeah, exactly, it's a blueprint for legal programs -- all of them -- they've got to fit into this template basically;
Yeah, exactly, it's a blueprint for legal programs -- all of them -- they've got to fit into this template basically;

that's what the formal definition did.
that's what the formal definition did.

And the interesting thing, as many of you are yelling at me now is, "This is XML, isn't it?"
And the interesting thing, as many of you are yelling at me now is, "This is XML, isn't it?"

It is the forerunner of XML. XML, as some of you know, started of with a thing called SGML,
It is the forerunner of XML. XML, as some of you know, started of with a thing called SGML,

which was its earlier form, but it was refined into being XML.
which was its earlier form, but it was refined into being XML.

And right back from the early SGML days, somebody saw Backus-Naur Form notation and said
And right back from the early SGML days, somebody saw Backus-Naur Form notation and said

"That is going to be fantastically useful for what we want to do."
"That is going to be fantastically useful for what we want to do."

The characteristic of this [BNF] stuff is that you never ever see it in the actual language itself,
The characteristic of this [BNF] stuff is that you never ever see it in the actual language itself,

and we can see advantages in actually making these appear in documents.
and we can see advantages in actually making these appear in documents.

Now, we all know this, don't we?! We all accidentally see a listing of our Web pages that went wrong and you see
Now, we all know this, don't we?! We all accidentally see a listing of our Web pages that went wrong and you see

things like . So this is XML, be clear.
things like . So this is XML, be clear.

You see things like .
You see things like .

>> Sean: And actually, if anyone right-clicks on the YouTube webpage and selects 'View Source',
>> Sean: And actually, if anyone right-clicks on the YouTube webpage and selects 'View Source',

they're going to see all this (...) >> DFB: Yes, they're going to see this, all of that.
they're going to see all this (...) >> DFB: Yes, they're going to see this, all of that.

But what the XML people realized was that so long as you introduce the "end-of" slash --
But what the XML people realized was that so long as you introduce the "end-of" slash --

just elaborate the notation a bit -- you really could use it in an actual document.
just elaborate the notation a bit -- you really could use it in an actual document.

Say: "the paragraph starts here" and "the paragraph ends here".
Say: "the paragraph starts here" and "the paragraph ends here".

The break-line here, it starts and finishes, it's just a marker, and most browsers are tolerant if you miss the slash out,
The break-line here, it starts and finishes, it's just a marker, and most browsers are tolerant if you miss the slash out,

but, you know, theoretically that should be there.
but, you know, theoretically that should be there.

So, they gave it some new lease of life, really, by saying, well, we're not going to just keep it in the abstract,
So, they gave it some new lease of life, really, by saying, well, we're not going to just keep it in the abstract,

we're actually going to use it, within documents, to clearly delineate where things start and where things finish.
we're actually going to use it, within documents, to clearly delineate where things start and where things finish.