Using Regular Expressions - Computerphile
ฝัง
- เผยแพร่เมื่อ 27 ม.ค. 2020
- Professor Brailsford takes the theory of RegEx and puts it into practice.
EXTRA BITS: • EXTRA BITS - History o...
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. More at www.bradyharan.com
![[TH] VCT Masters Shanghai Playoffs DAY 4 // 100T vs GEN | G2 vs TH](http://i.ytimg.com/vi/UkTGSxdCUQw/mqdefault.jpg)
I wish I could have a long and deep conversation with Professor Brailsford over an afternoon tea. He's so Jolly.
Ashish Acharya yeah, I’d be happy just being on the next table in that pub and listening in.
At least listen to him at lecture
...Wait, is it going right now?
If I could afford to take a trip to the UK, I would come out there just to have a chance to meet Professor Brailsford!
He is jolly but I have a tendency to falling asleep in the middle of his explainations
@@WillYouVid You must be a Millennial.
Obligatory xkcd:
"I have a problem. I know, I'll write a regexp for it! Now I have two problems."
The xkcd is a different version of that saying, but same idea.
I dont get it, somebody pls explain.
@@BangBang-te3mi The new problem is he needs to figure out the regex syntax
@@Krissam2k ah haha thanks
@@BangBang-te3mi Or that the RegEx written is *almost* correct.
I’m really enjoying these videos; My knowledge of RegEx is entirely practical, and limited to contemporary uses for string validation, matching, and parsing. I had presumed some ultimate shared origin with lexical grammar theory, but I had no idea it was so diverse and fundamental.
Wait until you see the diversity of regex engines out there and the performance implication thereof. Backtracking, backtracking with cache, multistate-NFA, lazy-DFA, DFA, DFA with filtering check for non-regular features, DFA filtering + backtracking. There's a lot if techniques out there.
please a more in-depth regex part 2 video!! Vote up if agree!
4:21 The video-editor is clearly less experienced with regex, leaving out the essential asterisk...
Aaaagh!!! Well spotted!! As you can imagine,that trailing asterisk *is* there in the actual program (otherwise VARNAMES wouldn't get recognised) but it's somehow fallen off during the highlighting of the regex .... Apologies.
@@profdaveb6384 clearly visible on the paper printout at 4:15 :D
@@profdaveb6384 Might be worth enabling program as downloadable file
OK!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Professor Brailsford always brightens my day. Thank you so much!
Here's a little unexpected connection. My favourite little function that I wrote is to convert any number into its Roman numerals. And I used both recursion AND regexes to do it! It's nice that these are both areas Prof. Brailsford is the Numberphile expert on, because I'm such a huge fan.
How did you do it?
To get close and personal with regular expressions, I would recommend the command line tools egrep (for searching text) and sed (to search and replace text). Both deliver immediate results and are very useful and versatile tools in their own right.
I just finished building a lexer and a parser in C for a new programming language. I'm here to listen to the professor more than anything else.
Some people, faced with the problem of comprehending a presentation on regular expressions, like to distract themselves with a well-known and overused Jamie Zawinski quote. Now they have two problems ...
I love that your comment was right above said Jamie Zawinski quote for me.
@@miguelpaz1579 Yes!
Am actually doing this in this semester and the prof is really teaching superbly.
Next video should be about RFC5322 and how insane regex can become (to a point where its actually quite terrible for what most people use it for)
When I worked at Yahoo! years ago my Boss used to quip, "regular expressions are anything but regular."
I would to be enrolled in one of his classes, or to help with his research. A truly inspiring and engaging professor, I am sure.
The best part of the video is this expert with decades of experience still gets visibly disturbed by the sheer scope of what Regular Expressions are. Makes me not feel so bad when even after decades of using them myself I still get that sinking feeling in my stomach any time i have to figure out a non trivial Regular Expression I might not have looked at in 6 months or more
Best is to avoid such situations, by keeping your REs simple.
@@lawrencedoliveiro9104 Yeah because a validation regex for things like a valid email address defined in the RFC document is SUPER simple...
@@TofuBug24 That’s the kind of (mis)use of regexes Jamie Zawinski had in mind when he made his famous quote.
I still use TSE (The Semware Editor) which lets me use regular expressions in its script language. Works for me.
What a lovely guest!
Some people, when confronted with a problem, think "I know, I'll use regular expressions."
Now they have two problems.
I use it a bounch for Powershell scripts and it is insanely useful, but yes sometimes you do get stuck :D
regex101 website help ALOT, usually fixes the expression in seconds.
@@magnusschollin9583 Yeah that site is really useful. Even if you understand RegEx it works, it saves a lot of time. Sad thing is that they won't let you use it on code tests.
Professor Brailsford! Yay!!
I use regex mostly to search existing strings. It will allow me to capture portions of data, replace data, or simply tell me if the string is okay.
And it works just fine for this both in userscript and when searching a document.
I actually don't know why else you would use it, nor why it would be bad in this context.
Oh my goodness, that's Principles of Compiler Design next to his monitor. Wow, that was one of my Computer Science textbooks, last century.
I love that cover design
Much better than the previous regex video
Regex can't cope? Thats AWKward.
Or as Professor Brailsford would say, Orcward.
Honestly I feel like windows 7 is better, at least I don't get pestered with update notices every 15 minutes, and the UI is just so much clearner and intuative, not to mention that windows 10 comes with half the drive filled with adware, a lot of it is near impossible to uninstall. If security is of concern, use Linux.
Just get w10 pro. Easy to remove every single app and chose not to install anything else than stable updates.
@@Chriva Honestly if I have to fork out an extra $90 just to install it without crapware, whilst having virtually nothing different except worse UI, updates shoved down my throat constantly, and having to deal with a bunch of compatibility issues with programs intended for older versions of Windows, I think I'll just stick with 7.
@@deidara_8598 You can uninstall the "crapware" you know
@@archiemisc Have you ever tried uninstalling candy crush on windows 10? You can't do it by the convetional methods, it won't allow you to delete the files, even with administrator, and if you try to use control panel it'll just flip you off. No, if you want to uninstall candy crush and the other junk they obnoxiously bloat your drive with what you have to do is to go into powershell as administrator, find the ID of the app you want to uninstall, then copy that id, then remove the app using the Remove-AppxPackage command, and that's just one of the bastards, imagine doing that 50 times over, and you'll realize that maybe it's just easier to stay of Windows 10 all together.
@@deidara_8598 deidara _ imagine doing get-appxpackage and piping that to remove-appxpackage! :O
You're welcome!
Does lex (or flex) compile a full blown determinitstic automaton with the union of all the regexes? Or does it try them all in sequence?
Both approaches have their pros and cons.
When I was in college in the mid-80s I was using unix boxes and learning regex's was really important, but there were little difference between lex and awk and file globbing and others.
> 3:30 AM PST
> New Prof. B video
> About regex
I'll tell you one regex I wouldn't write, but I'll stay for Dave :^)
I actually implemented the IRC protocol as a regex about 20 years ago :)
You... WHAT?
Github or it didn't happen.
@@fitzroyfastnet Well not just Github
you mean the parsing part of the commands? Possible, considering their syntax not being too complicated - or do I miss something?
@@FrankHarwald I wrote a single regular expression (using the C PCRE library) to parse incoming lines of text from the IRC server, then branching logic looking at what subpatterns had matched
Professor Brailsford! Many thanks 😃👍
"Some of you know way more than I do"
(x) - Doubt
He is so cute explaining 😆 and the topics are always the best
I'd love a regular expression video on catastrophic backtracking!
And then a video on how the solution is known since 1968.
@@Ceelvain Do tell us
yes, but these sort of things would probably better go to computerphile 2 because they tend to be beyond what beginners can easily comprehend.
@@deoxal7947 Well, don't implement regular expressions with backtracking. Ken Thompson (the one that made C and Unix) published a 4 pages paper in 1968 titled "Regular expression search algorithm". In it he describe an algorithm to compile a regular expression into machine code for the IBM 7094.
The generated code perform a breadth-first search on the non-deterministic automaton. The algorithm still has exponential cases, but an easy fix is noted at the end of the paper. Which he implemented in this text editor QED.
Anyway, the idea of the algorithm is that you read each character of the input string only once. And at each step, you activate all the states of the non-deterministic automaton that are reachable with that character. If you're careful to not activate the same state twice, then you have a linear-time algorithm.
The reason it's rarely implemented like this is that it's harder to implement all the bells and whistles people want in their regex today. It's possible to implement counted repetitions, but it migh take a lot of memory. And backreferences are proven to be NP-Hard to match so there will always be cases that take an exponential amount of time if you support them. In fact backreferences bring new matching power to the regexes. They're no longer "regular" and thus should not be called "regular expressions". There seem to be an implicit agreement to call them "regex" and keep "regular expression" when it' s the mathematically correct term.
Frank Harwald there’s a second Computerphile channel? Also I don’t think that’s beyond comprehension for most computerphile viewers. It’s basically just another video on why RegEx works the way it does. Once you understand that a RegEx isn’t magic, and that it actually works as well as it does because it basically brute forces its search algorithm, then you begin to think about why and when it does so and how to prevent it.
I'm now going to call all my integers Bob the Builder
Bob the expression builder.
8:34 So lex was written by a guy named Lesk. So near, and yet so far ...
Guess it's like Linux & Linus.
@@FrankHarwald That one was no coincidence.
@@lawrencedoliveiro9104 I guess both were not coincidences
@@FrankHarwald No, the one I mentioned was indeed a (near) coincidence.
Regexes are definitely my favorite write-only language.
You clearly haven't written any Perl.
Only time I've used RegEx was when I set up a forum at uni and needed to filter out non uni emails from the sign up section.
being handy with regex is vital with processing anything with text. And seriously speaking it can be very complicated ;)
Got an exam on this tomorrow... couldn't have come at a better time
The first thing I noticed when I started the video was Windows 7... Thanks for the heads up! :D
Is that a first edition of the dragon book?
Now I'm off to read the lex man page
Please include CC transcript for the hearing {or spelling} impaired
when i discovered $1, it saved me a lot of time and it's fun to use
Capturing groups are most likely one of the most essential tools for regular expressions
Don’t spend it all at once.
$NF in awk is my go-to for obscure clever things. Super handy.
Do you mean extracting content of the parentheses in the host program? Or reusing it in the regex like /(doc|cat)\1/ would match "dogdog" or "catcat" only?
The first one is a core tool that makes regex useful. The second one (called backreferences) makes the language non-regular. Actually, we shouldn't call these "regular expressions". They are also pretty difficult to match (proven NP-complete).
I was very happy to discover the multi-line flag.
when you need to fix a customer support request and all you have is a rough date and time, a user id and (metric)tonnes of logs.
I love to work it regex ❤
I'd expect someone like prof. Brailsford to be more comfortable with one of the *Nixes on his pc.
Grandpas like this should be the one on senate asking tech CEO's.
If David Attenborough taught computer science!
Now i'd like to see what happens if you feed it, let's say "trampoline" or "archery"
lex is greedy, which means it takes as many characters as possible before matching. For that reason alone, it would rather match "trampoline" as a variable than "trampo" as variable and "line" as reserved.
3:12 By “letter” do you include everything in Unicode classes Ll and Lu? Because, you know, we don’t live in an ASCII-centric world any more...
As evident by the regex, only A-Za-z so no, not a single non-english letter.
@@RealCadde But even English uses diacritics. For example, “resumé” versus “resume”.
That's easily fixed. Just use [:alpha:].
@@JanBruunAndersen Be careful, though. Those sorts of things can be localization-dependent, which is not what we want here.
It depends on the regex flavor really. If I am not mistaken PCRE flavors do include non ASCII characters in character ranges. Even within PCRE there are many slight differences within engines though.
25 years ago I made a meta search engine which stole the search results from another website in real time and presenting it to my visitors using regex.
Just use vim, you’ll be a regexpert in no time!
Why though or Emacs for that matter
@@deoxal7947 Why use vi? Because it's so FAST to edit in.
I wish you'd use conventional Regex, like the PHP and Java/JavaScript versions - compared to the fabulous first video, this was hard to follow.
4:20: The [A-Za-z][A-Za-z0-9] expression as enlarged here is wrong. It's actually supposed to be [A-Za-z][A-Za-z0-9]*, as in with the asterisk.
Awk, Sed, bash and grep walked into a bar... It was just Perl. 🤣😉
Leaving the machine on Windows 7 to the very last minute 🧐
Far better to have forward planning so you have time to put in a solution if there were problems.
I LOVE Regex!
but I hate it so much...
My thoughts exactly. Doesn't help that there's different versions out there. (Ex: The version that Visual Studio uses is not quite PCRE)
@@FnordOok YES!! regex are screwed up enough as-is, it really doesn't help that different languages have different spinoffs to make our lives even worse
I love it when I've been absorbed into them for a little bit. The problem is that I only use them on rare occasions and have to get used to it again whenever I do...
Wat about re with AI and deep Learning?
I
Regular expressions or regular headaches? amirite?
I use them all the time... used two today
I wanted to see what would happen with something like "1a".
wow does the camera wobble
i think it was handheld and stabilized
Windows 7 is perfectly safe to use and will be for some considerable time. All the scaremongering originates from security software companies with vested interests in selling their products.
Try "circue circls circuit circ".
I just had a lecture today about regex in java coincidentally
How many classes does it take to implement a regex in Java?
@@lawrencedoliveiro9104 2 classes/labs
Just a little warning: Upgrading windows 7 era hardware to windows 10 is like upgrading a win 3.1 486 to win 95. Chances are the PC will be much more sluggish afterwards and you can expect windows update to completely brick your computer now and then. If you're going to use windows 10, it's really best in my experience to only run it on hardware newer than the OS. Just my opinion.
I had no idea that Regex was meant for compilers.
I now want to go fire up lex and yacc .
Keep it on windows 7, you don't need the spyware upgrade.
guardians unite the
I always thought it would be cool if CPUs could have some special bus to process regex
@@Ceelvain, maybe if you had a dedicated regex processor you decide if something matches in 1 cpu cycle.
Perhaps it could even use a "reconfigurable computing" architecture. You could load your regex pattern into it, then use it as of it were a bespoke hardware checking for that specific pattern, for as many times as you wish until you reconfigure it again to a new pattern.
@@JNCressey You cannot match them in one CPU cycle. Regexes with backreferences are known to be NP-hard to match. So if you could match them with a number of CPU cycles less than exponential in the size of the regex, you'd have proven that P=NP and would win a million dollar.
Even without backreferences, you still have to examine the whole regex and every character of your input string at least once. Therefore, matching a regex in a constant amount of time is just not possible.
I mean, sure in some cases we could probably benefit from dedicated hardware, like a FPGA or just using GPUs. But these always come with a setup cost and a cost on each call. Basically you'd have to compile or otherwise prepare your regex for the device, then you'd have to send each input string to the device. So, in the end, you have to have a lot of input text to make it worth.
@@Ceelvain, I mean if the dedicated processor had a much faster clock it could bring back the answer quicker than 1 cycle of the cpu.
It wouldn't need to be constant time or processed below some number of cycles, it could just be a very very fast processor.
@@JNCressey You'd still have to pay the cost of the setup time, and even with a fast co-processor you can't escape the algorithmic complexity. Even if the coprocessor is 100 times faster than your CPU, any string longer than 100 characters would be slower to parse than one CPU cycle.
And I don't think higher clock frequency would be the way to go. The power consumption grows with the square of the frequency. And the thermal dissipation grows with the power consumption. There's a reason we reached a max CPU frequency of 5GHz 15 years ago.
Besides, think about it. We already have algorithms that match regular expressions (without backreferences) in a time that's linear in the size of the input string. Meaning that each character is processed only once, and for each one, there's a constant amount of work to perform. In addition to that, the CPU will have to process every character at its own speed anyway. Should it be just to write the string in memory the first time. Therefore, the speedup you might get is fairly limited.
@@Ceelvain, ok, cool.
Why does the professor not use Linux?
Moving to Windows 10 is not an upgrade...
Yeah I feel sorry for him. I'm surprised he's not a Linux man to be honest.
Most of the regex I've created has been write-only.
Well, I guess the circus is officially a drawing primitive now...
He's like the David Attenborough of computers.
I'll be quite disappointed if at no time during the video are the splines reticulated.
I was trying to do something with regex and... I was completely lost
Did you try the multi-line option?
Up until now I never thought about which operating sytem he is using because his talk is so interesting. But now that he brought it up I am kinda surprised he is using Windows. From what I have seen from him a unix like operating system would be what I expect him to use. Maybe he has work that can be done on Windows or just prefers to use Windows :)
Maybe the university supports windows, and won't let him access particular services without it. :-/
@@llearch I’m not sure I would put up with working at such a place.
I saw (open?)SUSE in at least one video with him ('The Most Difficult Program to Compute?') , but it could be because he needed to run a program for a month without interruptions..
@@lawrencedoliveiro9104 same but I'm afraid for his time in academia it wasn't possible because of how ubiquitous windows was. It's much more agnostic now but even when I was in college 7 years ago using a linux laptop required quite a few workarounds to access the internet and other silly and simple things like printing.
Luckily the ACM at my school set up many things to help hack our way around this redtape like a facebook chat bot that printed files we sent to it haha
Can't believe it. Nobody mentions Jeffrey Friedl.
Today I failed my fundamentals of computer science exam because of regular expressions
Now I have to wait another year to retake it
In my defence I joined Uni only only a month ago and was unable to go to any of the lectures
Regex, where rewriting is easier than editing...
Mostly true - unless you're having a) determined anchors everywhere & b) consistently use variables, parameters or constants to reuse (external) subexpressions - which is unfortunately not what most users of regexes do - nor do even all tools that use regexes allow for such things. Bother, said Pooh :|
I had a problem, so I decided to use Regex. Now I have 2 problems.
Windows 7 is EOL, Prof. Brailsford :)
Still better than windows 10. So much bad design in win 10 :(
@@scragar Geezus people have a hard time adapting. Ten is superior if you only take the time to LEARN it :)
@@Chriva lol
@@kestrel8838 It happens with every single release. People have complained about every new release since windows 98. Yes, people even hated xp in the beginning. Same goes for seven :p
If C1 then D1.
If D1 then C1 or C2.
If C2 then D1 and C1 or D2...
Or I didn't understand what the Professor was talking about. :)
Next video should be on "sed."
I wouldn't call win7→win10 an upgrade, personally...
MachiToons - Machimations having a supported OS with patches is generally considered an upgrade. 🙂
I used Lex/Flex to tokenize a programming language I've created at school, it was the best class ever. Creating a compiler for a custom programming language was fun, Now I'm developing boring websites :/
4:3 gang
I use regex for everything that I hate hehe
😍 I love regex; I want to have its babies. (CSS is great too, but don't let regex find out about my mistress.)
Imagine calling updating your computer to windows 10 from 7 an 'upgrade' lol. USE LINUX
I will just pretend I'm smart.
Bob
❤️ awk ❤️
The Windows 7/10 bit...*Other operating systems are available. :-)
Yeah, I moved to Linux rather than use Windows 10.
& if you can't or don't want to switch to Linux/GNU, there's also React OS for most things.
@@FrankHarwald It's been a while since I last tried ReactOS in a VM. What's the compatibility like these days?
You should upgrade to Linux.
Totally off topic: Is it just me or does the professor's skin color look a bit odd? Hopefully it's just me, or wonky color correction, because the first thing going through my mind while watching this video was: "I really hope that's not a liver condition".
I thought he looked a bit I'll too.
@@ChrisLee-yr7tz I hope it's just a wonky white balance or color profile/grading gone off track. I know we all have our time, but I hate the thought of professor Brailsford being ill. Let's just hope for the best: being scared by failing tech.
Yea something's up with your auto stabilizer lately... Get a new one as they've never been quite this bad...
It looks like someone's purposely jittering the camera back and forth... Yea it's that bad...
Or like Professor Brailsford is holding the Camera! LOL but obviously not in this one since he's in the frame, not behind the camera! :P
I think we need to talk about the elephant in the room ...