aim, in the end, is to unite these all into one, at the top, so that you're all

totally happy - or completely unhappy - as the case may be. We have done Regular

Expressions and the last one I did was really very simple and straightforward,

and showed you absolutely nothing about what can go wrong. And some of you out

there, coming up with the usual old jokes, quite right, about: "Oh! you're implementing

using Regular Expressions. Now you've got two problems", Yeah! We'll look on in glee

as we now take the story a bit further and see what can go right and how

powerful Regular Expressions are. But also a little bit of what can go wrong

and why you've got to be careful in your use. So what can it be this marvellous new

example that consumes Life the Universe and Everything and exhibits a whole load

of new features? And you're going to be quite convinced I'm off my head.

It's Roman Numbers. Way way back when we first, here at Nottingham, got Lex and Yacc, in

UNIX Version 7 - it was in the late 70s. So, believe me, I have been ... or, back in

those days I was setting Roman Numbers as an example of what Lex - remember the

Regular-Expression-based front-end to your compiler. Does tour identifiers and

all that. I thought, all right, as an exercise, just write a Regular Expression

that will accept Roman Numbers - all of the good ones and reject all the bad ones.

Now, I can't emphasize too strongly: that rider is important! It is very easy, in a

Regular Rxpression, quite easy, to get it to recognize what you want, but will it [also]

reject all the stuff that's bad? And it is sometimes so easy to overlook [things].

I say with shame because, when I'd set that question, I scratched down a quick and

easy answer - which I now see is full of holes .... Because if you input, into my

regular expression MMII - again, looking ahead, Roman Numbers

MMII [is] 2002. Fine. But then I thought ... well I thought now, I didn't think then:

"What happens if I do MIIM? [winces at the thought]?" [Answer = ] 2002. [It] shouldn't be. There's a strict hierarchy

in the way these work. So, at this stage we don't know how much, if anything, you

remember about Roman Numerals. So, as an Extra Bits we've put out a simple

tutorial on Roman Numerals based around this example, But for those of you that

are totally happy with Roman numerals, we can just carry on with the main video now.

So, just to locate ourselves then, and do a few examples to make everybody

comfortable I'm going to write down MCDXCII. Start at the left. We've got a

thousand [M] Then we see CD and, remember, this is one of these subtraction things

CD is "a hundred less than 500" which is 400. MCD. So we're up to 1400 so far. XC?

>> Sean: OK That's 90 >> DFB: 90. II? >> Sean: 2 >> DFB: 1492. What happens in 1492 Sean, in Western European folklore?

"Columbus discovered horizons new in America (1492) >> Sean: I should have known that one

>> DFB: Yeah! right. And, of course, the year we're in at the moment, as we film all of this,

is - that's simple MMXX, 2020. And one which is dear to me, I'm sure you'll

work out why. Yes, it's got a lot of these prepended abbreviation things in there look,

MCM; 1900, XL: 10 less than 50 (40) IV: one less than 5 (4) -- 1944. 244 let's focus

Let's focus ourselves now on how would we do a Regular Expression for all of this?

In fact, let's make things very very simple and say: "All I'm gonna do at the moment

is concentrate on getting a Regular

Expression pattern that will either generate me one or two, or three, or four, or five -

[writes on paper] forgive me I'll carry on down here. Or six, seven, eight, or nine. And I won't go

any further than that. Because tens is a new adventure

further to the left. So, those numbers then, from one to nine, which I've written

know like that now. I hope you can see that if you're completely simple-minded

about this and don't want to do complex Regular Expressions you really could

write yourself a great long 'alternation' as it's called. In other words a great

big sequence of ORs. And you could do everything from one up to thousands and

just have this walloping great OR clause, that your Regular Expression parser will

probably go bananas and say: "too many alternations", or something like this.

So, no, that's not the way to do it. What one wants to do is to generalize and use,

as it were, elegant Regular Expression capabilities to shorten this a bit.

So, there we are the Roman numbers from I to IX,

All written out. First of all let's try and separate

these things into classes, and groups, that make sense. There are two weird

things which involved the subtraction rule, you know, like IV (1 less than 5)

IX (one less than 10). I think we will do those together, because they're weird in the

same way, if you like. The other things are much more regular like you go from 1

2 and 3, which is with III. And similarly, here, you get the same pattern but coming

after a V - a V on its own, or VI, VII, VIII, and so on. So, we've got three

groupings: things involving Is with or without a V in front of them;

and the two special cases IV and IX. So I would conjecture there's a wonderful

piece of Regular Expression covering so far what we've done, but something new

coming up - so do pay attention - would be this: my RE is going to be I

- now this is square 'choice' brackets [], We have seen these before.

But whereas, before, I put ranges inside them - you know like [A-Za-z]

[0-9], any one of those digits.

These aren't ranges; these are just explicit possibilities inside square

brackets. It's called a 'choice' so I've got to have an 'I', if I'm on this side of the

expression. But then it could be followed by either an X or a V, but it must be one

or other of them, and only once. There's no repetition outside; there's no

star there's no plus; no nothing. So those are the special cases taken care of,

the IV and the IX. Now we put a walloping great big OR bar down the middle. Or if

it's not a special case it's a regular straightforward case. But we've been

clever with our REs now. Oh yes! look at this. Now, again, I think this is

something we may have mentioned but probably not another piece of regular

expression notation is: " ... if you put a question mark after something it means

0 or 1 of". So, what I'm saying here is I can either have a V, or I don't need

a V. How can you not need a V? Well, what's following on here is going to be

something that really is new. This is a counted repetition in curly braces zero

- [should be 0,3]. Look at that! Bound to win an award! Let's just run through it.

The two special cases are off on that left-hand side of the OR bar. But if you choose not

to go down that route you go to here and it says: "Oh well if it's not one of

the two special cases then it's like the following: anything between 0 and 3 Is.

I mean you may not have Is at all - you can just have V on its own if you want -

preceded by an optional V, nought or one these, >> Sean: Tthat's giving you the choice of

either 1 2 3, or 5, or 6 7 8, right? >> DFB: Yeah, yeah, that's right.

But it's all to do with sometimes having zero of something. Now, hereby

hangs a tale about Regular Expressions. And those of you that keep on posting

these notices about " ... you've got multiple problems with Regular Expressions !". Well. here's

another one. It's the strange case of the 'empty

alternative', which really can gang up to get you. Because what you're saying here,

in this expression, is: " ... Is it possible for it to match nothing at all and yet

that's a valid match?" Yes it is! Because if you choose to ignore what's on the

left of the OR bar here - which you can do, it's either/or - we come here, and we say: " V,

oh! I can have 0 or 1 of those. So, let's have 0 of them". The I ? I can have

anything between 0 to 3 of those. So let's choose 0 of them. So, in other words

choosing nothing at followed by nothing is a valid match for a Roman number [according to this RE].

And if you think about it it's true. Nothing in Roman Numbers is compulsory. You can have

M's, or no M. Yyou can have C's or no C's. You know all of them.

It's all optional. But as you start getting down to the units digits you think: "I've got

to have something !" The paradox, then, about Roman Numbers

done as a Regular Expression, is: you've got all sorts of cases that yield you

nothing at all and yet you're going to be very disappointed if you don't have something!

But saying "... overall you must have something" That's not a context-free

assertion. That's a context-sensitive assertion. So we'll live with that for the

moment. And I think also what I'd like to just show you now, if I can get the

screen fired up ... and I'm using 'awk' here to demonstrate this, I'm going to add yet

another little piece of notation to all of this. I'm going to say that you can, if

you want to, insist that what you're matching must just be a valid Roman

Number, on a line on its own, with no writing or messing about on either side

of it. Just the number. Start of the number (^), end of the number ($). Finish. Right?

And you denote that by saying start of string anchor, ^ End of string anchor, $.

You're basically saying whatever pattern there is must fit between

the start of the string, on a line on its own, and the end of the string - the

newline right at the end. Now, this is the key thing about this. Those things [^$ markers]

if you put them in, are not options. You can't have zero of them. If you say

you must match the beginning of the line, you must match the beginning of the line. If you

say you must match the end of the line, you cannot ignore it. You can't have zero

of them. So, in a way, this is a kind of reality check and it's generally the

case that if you use these correctly you won't end up with null strings being a

pseudo-match. Because this thing is saying: "Well, whatever the finite [non-zero] length

string is, it's got to fit between beginning of line end of line. Here's the

'awk' script that I hacked together, to try out a few alternatives. And I decided to

go for this simple little piece first. Can I do everything from 1 to 9 in a

single piece of Regular Expression. And you'll see here this is classic 'awk'.

You, give a Regular Expression pattern, then you give an action. It's a C-like syntax,

even in 'awk'. Basically what I'm saying is; "If I match that then I print out 'Pattern

p1 matched' and so on". Now, if you look down here four of these things - because

this is just a test-bed - four of them are commented out, they will not be executed.

The one that will be executed is the one I've just been discussing with you, here,

which says: "I must match start of string then here's my Regular Expression

pattern - which I think will work from I to IX inclusive, and then it must match

end of string". So, I'm hoping that by uncommenting this that this will work.

And I'll type some good and bad Roman Numbers at it. And for every one it's happy

with, it will say 'Pattern P0 matched is' And it will echo back what it your Roman

Number [was] that you put in. So, what I want to do, now, is actually run that script, that

we've been looking at. 'awk - f ' take your instructions from a file called 'test-roman.awk'

OK, so when that runs now it should just hang there waiting for its

input of a Roman number. And remember it is going

to match that beginning of string, piece of regular expression, end of string.

>> DFB: So. which one do you want me to try first Sean? >> Sean: OK, let's go really simply and just go

for a number 5 [V]. >> DFB: V all on its own [waits] Look at that! That's a 'P0 matched is V

>> Sean: All right - a bit trickier 4 [IV] because it's got that 'minus one' sort of idea. Let's put one in that shouldn't work.

>> DFB: Go on that what do you want ? OK just put in C for Computerphile.

>> DFB: C for Computerphile? Now you might say that's a valid Roman number.

Yes, but it's it's not being covered by the bit of Regular Expression I've done, I've done a

piece of Regular Expression that literally, I hope, does I to IX and

nothing else. Let's see what happens there [with C] It echoes it back but it doesn't

do anything with it. So let's now try IX, looking good.

All right how about the ultimate test [which] is type in something utterly idiotic like HELLO

No, doesn't do anything with it, doesn't recognize it. So, we're back

showing the 'awk' script again and let me just remind you that what we've shown is

that as long as we put the anchors in at the beginning and the end of this

pattern then our minimal testing, but I think we've tried all the options, it's

recognized V it's recognized IX. IV all this stuff. That one is absolutely

fine and it rejects rubbish. I've actually put in, as a comment,

StackOverflow's assertion that this [points at screen] is the thing that's the answer to life the

universe and everything. Let's move right across to the right and the first thing

you'll see here is the piece we've just done for the units as it were, I through to IX.

But as you go leftwards can you see that the beauty of this is ...

that has handled the units part of the Roman Numbers. It's dead easy to see, therefore,

that it's like a repetition of the same idea, but with different symbols? When you

come to the tens range What are the exceptions there XC (ten less than a hundred)

XL (ten less than fifty). I's just like the I's and the X's and V's were before, look.

Similar. X[CL]. Or it is is an optional L, for 50, followed by a tens digit, zero

{0,3} of them. You can't say just {1,3} because L on its own is

perfectly valid as a Roman Number Number. So, you see that piece of pattern - similar to

the far-right one but just with a relabeling almost of the digits you're

using- that copes with the tens. Up here [points to left of screen] it's coping with the hundreds, going on to