Just an anecdote about regular expressions from working as a software engineer. I once worked in a codebase that made lots of use of regular expressions. I suggested that for maintainability we should have a rule that above the regular expression you add a comment stating what it was intended to match. The pushback I received was that "the regular expression, by definition, says what it's intended to match."
My attitude to comments is that they shouldn’t say just what the code does (the code itself does that), but _why_ the code is doing what it’s doing. Perhaps a comment on the regular expression could be expressed on the same basis.
It's funny because regular expressions regularly make my life easier because I use them constantly. A rare use of them is worse than using them often and now using them.
The famous book by the man who disregard and direspect the underlying math. This book will mostly teach you how to best use regular expressions given the current widespread implementations. Not what they are nor how regex engine actually work. It's targeted at casual programmers and not at computer scientists. (Gosh, I don't even remember this book talking about algorithmic complexity.) And most of everything he says about regex engines is at best incomplete and misuse the terminology, at worst it's wrong and misleading. I would recommend the blog of Russ Cox to dive into how regex are actually executed. I honestly loved every word.
Ceelvain I am in the middle of reading Larry Wall’s book on Perl. In it he says Friedl’s book is the place to go to for more information about regular expressions. Are you saying that this is not so and Friedl’s book is rubbish? I looked it up on Amazon but haven’t decided to go ahead and buy it.
12:40 not only Ken Thompson. This problem was also solved on the other side of the Iron Curtain by Vladimir Glushkov. Unfortunately we are not taught much about Glushkov's construction algorithm.
I'm a huge fan of Prof Brailsford. I was extremely fortunate to start my computing career, while in secondary school in about 1975, learning on a pdp/8E. I learned so much, including TECO a text editor that used regexp. Those were the days that truly grounded my understanding of computers, hardware, firmware, and software. Watching this series brings back great memories. Thank you.
All of the contributors on this channel are great, but every Professor Brailsford video always has my undivided attention. I appreciate his particular style of making these complex concepts unfold like a story.
I faced a really pesky regex problem the other day, took me 2 days to solve it (had to trace back data to a reduced set), i never knew you could use a diagram for regex - i just scribbled it down in like 20 mins, got the same solution. genius!
i was taught this stuff without explanation never thought it could be used to solve a problem ..... i genuinely believe this channel is better that teachers i pay to teach me stuff
I am retired now, but for decades of my software engineering career I have used C switch statements to implement state machines. No programming book that I have ever read has ever described such a method, but I learned it on-the-job (OTJ, a very common military acronymn since that is how you learn almost everything). In the last two decades of my software engineering career, I was repeatedly tasked with communicating with GPS receivers over their serial communications. We were never taught those skills in school, but we learned them immediately in the real world.
This video was the first time the link between regular expressions and finite state automata clicked in my brain. I've been comfortable with both for years, and knew they were equivalent, but they just never came together for me before now. Thanks!
2 года назад+1
The NFA-to-GNFA-to-Regex algorithm is really helpful in making that connection too
If you get deep into regex, it helps to understand FSA. But for basic stuff you don't need to understand the mechanics, just the syntax.
4 года назад+12
I think there should have been a real-life example like matching a telephone number or zip code or something. I had a course on formal languages so I understood the video in full and enjoyed the context provided, but there is no way this is digestible by common folk, which is a shame because this might end up showing up in the youtube search for regular expressions…
I loved how this video tied together regex, automata and formal languages. Watching this I felt the formal definition for regex is really simple, but in real world use things can get messy. Would've liked some mention of the extended symbols like the Kleene plus, or use of subexpressions etc. Anyway great job.
The wealth of knowledge contained within this man is mind blowing. To me, all this is trivial information that I'd never remember. These days, I can't remember what I did five minutes ago. But it's all so fascinating.
The way people mostly use regular expression in programming or at least me is to use it as a language that describes search patterns. One example would be an expression that looks for a date in a specific format like 2020-01-09 in a given text. For example you would write an expression that states: A four digit number, starting with a 1 or 2 followed by a "-" then a number between 01 and 12 one more "-" and then a number between 01 and 31. But you have to write it in that language in a compact form. And then your expression will only find that specific format and you can extend it to other formats, like allowing 2020-1-9 as a first step or 2020/01/09 and so on and then formats from other countries, with names of months in different languages and totally go nuts until your regular expression fills multiple pages. But its and incredibly powerful tool and very hard to master. If you have to make one yourself for a more complicated case you will find yourself always tweaking it a bit to include more matches and have less mismatches.
For those interested on how to convert a non-deterministic regex (& hence equally a non-deterministic finite automata or non-deterministic left-regular grammar) into a deterministic ones, what you'll have to do is a closure of each (initial state + input state tuple) with each possible subsequent states which in the worst case will mathematically end up being a full power set construction of the initial non-deterministic automata which is why a given non-deterministic regex of length ~n may end up being as big as O(k*2^n) for a positive non-vanishing constant k in the worst case. So yes, succinctness as well as computational complexity of deterministic vs non-deterministic regexes differ exponentially! Another thing: all this video talks about is about regexes, finite automata & grammars without much output besides a singular boolean accepting or non accepting, that is, pure acceptors - while in practice regexes, finite automata & grammars often specify a corresponding output which is why they are called a transducers - & there's an entire zoo of different kinds of transducers - even for just regexes - different forms of output, multiple outputs... you name it!
It still boggles my mind that people know what regular expressions are but don’t understand them, and are so proud of that fact that they’ll brag about it in RUclips comments. If you thought you had one problem before someone used a regex, and then had two problems, well now you have three. You’re unemployable.
I've known it for ten years and his explanation greatly overcomplicates it and never really gives you an idea of how it works, it was more a history lesson. He does this a lot.
@@idjles I was replying to Colin as he thought this was an explanation when it wasn't. The closest he got was explaining *b** was matching b 0 times-infinity.
@@NoNameAtAll2 It can’t work, because opening/closing tags can be nested inside other opening/closing tags, to arbitrary levels. Regexes cannot handle that.
@@NoNameAtAll2 It can’t work, because opening/closing tags can be nested inside other opening/closing tags, to arbitrary levels. Regexes cannot handle that.
Regular expressions are awesome, and in my own experience everyone who's spoken ill of them has implicitly announced their own lack of skill with them rather than establishing anything compellingly negative about them.
You should see what he did with it in Raku (née Perl 6). Allows for full parsing of something like JSON in a crazy small amount of code (and READABLE code at that). Take a look at the JSON::Tiny module's code. It's actually kinda beautiful
The guy who designed APL was deeply inspired by the obfuscation of Regex. If you can express a program in 4 lines, then squeeze it into one! The incredible amount of disk space a few extra lines requires can not be understated!
I love regular expressions and I include them in all coding projects. It saves me from having to write hundreds of lines of code to capture the same data with a single regular expression.
Regex is incredibly useful for searching for and filtering text. It's a feature of pretty much every MUD client for that reason. One long sentence worth of Regex can do with 40 lines of code for a plugin can do. I've used them to the extent that my client's memory allocation for that system seems to have run out and they don't always fire now, lol.
Useful as long as you don't let it become Zed's hair code. > These yellow pets > are called Zeds. > They have one hair > up on their heads. > Their hair grows fast... > so fast, they say, > they need a hair cut > every day. > - Dr. Seuss, One Fish Two Fish Red Fish Blue Fish When code is crunched into a single complex line when many simple lines would be clearer, I call that Zed's hair. Eg, if you're trying capturing all email addresses and phone numbers from a string. Split it into two separate searches, one for emails, one for numbers. Don't crunch it into one line by creating a single RegEx that matches both email addresses and phone numbers. Also, as you mentioned, regex can be inefficient. Crunching down line numbers when it sacrifices both clarity and efficiency is incredibly dumb. That said, simple regular expressions can be much clearer than the equivalent multiple lines of code.
Finally a subject I know! There's a lot to be said about Automata and Regex, and personally I think it's a great debt of this channel. One thing is about the Sakoda Sipser problem, which asks about the amount of states involved in the change from non deterministic to deterministic automata of basic operations of (regular) languages like union, intersection, complement and so. Other is the Černy problem, but this is more abstract. Automata are a very interesting subject hidden from the general public.
Yeah they could have explained why the not so regular expressions are called regular and in fact knowing why its called that and understanding what regular means also tells you when you should and should not use regex.
I agree also It would be great to do something about push-down automata, deterministic and non-deterministic and say something about relation between automatas and languages in chomsky's hierarchy
7:04 Notice the only kind of recursion allowed is tail recursion-there is nothing after the B that occurs in the substitution for B itself. This can be implemented with simple iteration, without a stack. Otherwise, it would no longer be a Type 3 grammar.
I have often wondered how the name Kleene should be pronounced since I had only seen it written. This pronunciation is at least something I’ve learned from this video.
His hierarchy of languages has come up in a couple of past videos. I suspect that among this channel's audience, there's a decently large percentage who only know of him for that.
Thank you, for the explanation , but especially for the historical perspective on things that are used. I was intrigued by describing graphic diagrams over the phone , that I admit you can't really do that if you only have a microphone and a speaker. The older I get the more I try to learn and use things with a histiorical background and not just use them mindlessly.
I thought regex was just a syntax for searching for patterns in strings, but this video makes it seem like it's at the heart of programming and computer science... what am I missing?
This is one of the topics we have covered in discrete maths on my computer science degree, could have done with this video a couple of weeks ago lmao, great video though
If you can master Regex, you can add tremendous power to app for little effort. Seriously, if you need to do text parsing and validation, you are cheating yourself if you don't look into using them.
Of course, the grammar way of doing things allows you to specify things that cannot be specified with a finite automata or a regular expression (namely nested constructs like parenthesis). :-) Just, the particular set of grammar statements he chose express exactly what's being expressed in the other two forms.
I was about to comment the same thing. A formal grammar allows recursive structures, but most regex implementations don't have a way to do that. Thankfully there are some now coming out that do, and man does it make creating parsers so much easier.
@@MSStuckwisch - But, it will make the regex handling slower. There's a reason for the very restrictive nature of regexes. It enables a very simple model for the computation. There is, in fact, a C++ library that will generate the C++ code to match a DFA at compile time for super-fast regex handling. Making it as fast as it is if you had to do full LALR or recursive descent parsing would be impossible I think. Regexes definitely have their place. And parsers have their place too. That's one of the reasons that a lot of compilers are written with a 'lexing' phase that uses a regex to tokenize the input, then uses a parser to parse the code.
@@Omnifarious0 True, though the speed will really depend on the nature of the grammar. A fully unambiguous CFG (to eliminate any type of backingtracking) should be able to optimize to virtually the same speed. Of course, virtually no real-world grammars are written like that, and most of the time we'd want to do more than just a yay/nay match. To me it comes down to ease of writing / maintaining. Most of the time the slower parsing using regex grammars is worth it, but if something starts to become truly speed critical, then I'd look to coding it manually for speed. (An interesting speed test for optimizations can be the JSON::Tiny (regex) and JSON::Fast (imperative) modules in Raku. Overtime the Tiny has been catching up a little bit, although the Fast still runs in about 25% Tiny's time
Grammers and regular expressions are not equivalent! You cannot write a regular expression for lets say a^n b^n (all strings that have n a symbols followed by n b symbols) but you can do it with a grammer: S -> aSb | ab
@@lawrencedoliveiro9104 of course it''s not, regular expressions are a sub set of context free grammar. Regular grammars are defined as all grammars that can be written as a regular expression. edit: I think that in the video what he meant is that all 3 examples are equivalent, that is true. What I'm saying is that that could be misleading and someone would start to think that all grammars can be written as a regular expression, which is false.
what is a regular expression? What is it good? Suppose you want to look for the word "he" in a book a simple search will also give you noisy results "they, she, here, etc". Well to fix that you include spaces " he " though you'll still miss things like typos such as he being right on the end of a sentence ".He said". Regular expression [^a-zA-Z]he[^a-zA-Z] let's you look for "he" with no excess letters on either end.
There are a fantastic collection of articles on regexes and implementing them efficiently on Russ Cox's website. They're a bit more in depth than this, but still pretty accessible, though they come with the assumption that you can read C.
at 6:42 it seems you place more emphasis on regular expressions (type 3) than the more powerful context free grammar (type 2), regular expressions are only limited in recognizing strings in text (pattern matching), and for lexers, or tools like grep (only 2000/3000 lines of code), awk etc..., but they can't do that much, I see you have the dragon book on your desk, and you value regular expressions more than cfg, the real geniuses were Chomsky and then McClure with his TMG, that Ken Tompson was so impressed that he used his principles also in the B language which later became C, same principles but greatly improved by Donald Knuth's inventing the most powerful LR parser followed by Stephen C. Johnson inventing Bison, I'm a parser fanatic, worked on a preprocessor C, contributed to add improvements in binutils and gcc source (bfd for the section elf and coff and dwarf for symbol debugger) and make version 4.x for variable expansions
In languages that permit it, parser combinators allow more verbose, but still highly readable regular expression syntax: myParser = do char 'a' many (char 'b') char 'c'
An instance of (char x) is of type (Parser Char). When sequenced, the whole function effectively becomes type (Parser [Char]) which is equal to (Parser String).
^\(?([0-9]{3})\)?[-. ]?([0-9]{3})[-. ]?([0-9]{4})$ I feel like part of the purpose of regex is lost in its short handedness. If the above looks like an alien language then you should either get really familiar with regex or use an expanded notation thats intuitive. Long English notation: ^ = From start \X = literal X ? = zero or one time ( = capture ) = end capture [X] = any of X X - Y = from X to Y {X} = X (range) times $ = to end From start, literal (, zero or one time, capture (, any of, from 0 to 9, 3 times, literal ), zero or one time, ) end capture, any of - or ., zero or one time, capture (, any of, from 0 to 9, 3 times, ) end capture, any of - or ., zero or one time, capture (, any of, from 0 to 9, 4 times, ) end capture, to end.
No they didn't get it wrong! Research shows that Kleene himself wanted it to be pronounced "Claney" but I suspect it's a Germanic surname and should be "Clay - nuh" (see Wikipedia entry for S.C. Kleene). I did devote a few mins to this in the filming session but Sean clearly had to omit it because the video is already very long at 17 mins.
What the heck is determinate (deterministic) vs non? I comes up too often and in too many ways for me to infer and I don't understand the somewhat philosophical references that I find.
Probably 2/3rds of my SQL or PL/SQL coding nowadays involves using the regexp_????? functions (regexp_replace and regexp_like in particular). They are so useful.
I just tried to search a not completly readable serial code with google today, but regex seems not to be supported. So thank you for substituting my missed oportunity to revise/remember regular expressions!
I was under the impression that the grammar was more expressive than the regular expression. For example, a grammar can balance parentheses. Unless there is some restriction on the grammar you describe here.
My question is, do you still have use for that green bar paper or are you using it as note pad paper because you have it left over from back in the day? As a kid, I had reams of green bar paper from my uncle that was a software engineer at Rockwell International, programming avionics in C and who knows what other language before that. That green bar paper was, literally, an unending joy to draw on as a kid. P.S. - I think RegEx is one of the most brilliant, yet least mastered languages in computer science.
I'm watching a series on computation theory on another channel and funnily enough he just covered some of this stuff. But I'm not a computer scientist and I still need someone tell me how this actually relates to real programming or machine design. Unless I truly wanted to build a machine that accept or reject strings of characters. But it does feel like that when I code.
Just an anecdote about regular expressions from working as a software engineer. I once worked in a codebase that made lots of use of regular expressions. I suggested that for maintainability we should have a rule that above the regular expression you add a comment stating what it was intended to match. The pushback I received was that "the regular expression, by definition, says what it's intended to match."
How dare you not instantly know how to read regex 😂
[groans] A prime example of being correct on the wrong level.
My attitude to comments is that they shouldn’t say just what the code does (the code itself does that), but _why_ the code is doing what it’s doing. Perhaps a comment on the regular expression could be expressed on the same basis.
It's all fun and games until \b\w+\b\s*(?=(\[.*\]\w*)?([\(]|([ ](?![,+\-*/=!^&<>|?]|and|as|div|in|is|isnot|mod|notin|of|or|shl|shr|xor))))
Evan Grove please could you add a comment describing what that regex is intended to match?.....
'Some people, when confronted with a problem, think, “I know, I'll use regular expressions.” Now they have two problems.' - J. Zawinski
Kevin Kenny Oh I know! I will just use regex. wait, what was the token for that thing again?
Put RegEx into APL for ultimate confusion (and compactness)
booo "bad Regexp meme is bad". #Regexp4life
You just earned your 69th like my man. Regex is the most confusing thing for me lol.
It's funny because regular expressions regularly make my life easier because I use them constantly. A rare use of them is worse than using them often and now using them.
A wise man once said: "The plural of regex is regrets"
I have no regrets using regex in programming...
wise words!
Pure gold.
@Poppy Smoria xD
It is hard to overstate the enlightenment that comes from realising that a regular expression is a state machine.
Yes !
Which you know if you study computer science.
Regular language -> deterministic, finite state machine -> regular expression
More info in:
Mastering Regular Expressions, 3rd Edition
By Jeffrey Friedl
Pages: 544
The famous book by the man who disregard and direspect the underlying math.
This book will mostly teach you how to best use regular expressions given the current widespread implementations. Not what they are nor how regex engine actually work. It's targeted at casual programmers and not at computer scientists. (Gosh, I don't even remember this book talking about algorithmic complexity.)
And most of everything he says about regex engines is at best incomplete and misuse the terminology, at worst it's wrong and misleading.
I would recommend the blog of Russ Cox to dive into how regex are actually executed. I honestly loved every word.
Ceelvain I am in the middle of reading Larry Wall’s book on Perl. In it he says Friedl’s book is the place to go to for more information about regular expressions. Are you saying that this is not so and Friedl’s book is rubbish?
I looked it up on Amazon but haven’t decided to go ahead and buy it.
12:40 not only Ken Thompson. This problem was also solved on the other side of the Iron Curtain by Vladimir Glushkov. Unfortunately we are not taught much about Glushkov's construction algorithm.
I'm a huge fan of Prof Brailsford. I was extremely fortunate to start my computing career, while in secondary school in about 1975, learning on a pdp/8E. I learned so much, including TECO a text editor that used regexp. Those were the days that truly grounded my understanding of computers, hardware, firmware, and software. Watching this series brings back great memories. Thank you.
All of the contributors on this channel are great, but every Professor Brailsford video always has my undivided attention. I appreciate his particular style of making these complex concepts unfold like a story.
"To all of you who think I am personal friends with all these people"
Bless this man, he puts up with a lot 🙏
His voice is so nice to hear...
Finally someone speaks about the important things. I would have visited his lectures just for relaxation 😌
I faced a really pesky regex problem the other day, took me 2 days to solve it (had to trace back data to a reduced set), i never knew you could use a diagram for regex - i just scribbled it down in like 20 mins, got the same solution. genius!
Thank you so much, Professor Brailsford! Hope you are well and healthy! I absolutely love listening to your explanation, it's so soothing to my ears.
It's terribly difficult to explain regex to people who don't use it!
I use it from time to time. I understood nothing from the video.
And thats the first time on computerphile videos.
It's terribly difficult to explain regex to people who don't use it ;-)
@@pdrg you can use it -like this- you know
@@FireWyvern870 how
@@a.yashwanth As he said, -like this- (precede and follow it by a dash).
1:32 012 ac string
3:15 abc
3:57 Ab*c
B* = 0 or more B’s
5:03 Quite complicated but locally simple
5:34 Chomsky Grammer approach
7:27 complete equivalence
Automaton
Regular expression
Chomsky Expression
Start, Automation, Finish
8:29 Snag in equivalence
9:46 2 alternatives, 2 completely different directions.
11:03 What are you gonna do?
11:28 Nondeterminist -> Determinist
13:03 Ken Thompson said
13:57 Regular Expression recognizer.
i was taught this stuff without explanation never thought it could be used to solve a problem ..... i genuinely believe this channel is better that teachers i pay to teach me stuff
Lol I was the opposite... I got taught how to solve problems using it but not really any of the theory behind it.
You can’t lie he is the best professor to explain regular expressions
I am retired now, but for decades of my software engineering career I have used C switch statements to implement state machines. No programming book that I have ever read has ever described such a method, but I learned it on-the-job (OTJ, a very common military acronymn since that is how you learn almost everything). In the last two decades of my software engineering career, I was repeatedly tasked with communicating with GPS receivers over their serial communications. We were never taught those skills in school, but we learned them immediately in the real world.
Yup, hand-coding state machines to handle parsing various kinds of data is an extremely common thing. Done it lots myself.
Yup, hand-coding state machines to handle parsing various kinds of data is an extremely common thing. Done it lots myself.
This video was the first time the link between regular expressions and finite state automata clicked in my brain. I've been comfortable with both for years, and knew they were equivalent, but they just never came together for me before now. Thanks!
The NFA-to-GNFA-to-Regex algorithm is really helpful in making that connection too
As far as pedagogy goes, Professor Brailsford is unrivaled. Def reignited my computer science flame
Love the history. Ken and Dennis certainly deserve the recognition for their accomplishments.
💯 agree! True GENIUS.
This was a very "computer science" explanation. I'm not sure how well anyone who hasn't worked with regexes will understand it.
If you get deep into regex, it helps to understand FSA. But for basic stuff you don't need to understand the mechanics, just the syntax.
I think there should have been a real-life example like matching a telephone number or zip code or something. I had a course on formal languages so I understood the video in full and enjoyed the context provided, but there is no way this is digestible by common folk, which is a shame because this might end up showing up in the youtube search for regular expressions…
yes i understood some of those words
I loved how this video tied together regex, automata and formal languages. Watching this I felt the formal definition for regex is really simple, but in real world use things can get messy. Would've liked some mention of the extended symbols like the Kleene plus, or use of subexpressions etc. Anyway great job.
Hope to do more actual regex examples and more extended regex constructs in a follow-up video
The wealth of knowledge contained within this man is mind blowing. To me, all this is trivial information that I'd never remember. These days, I can't remember what I did five minutes ago. But it's all so fascinating.
The way people mostly use regular expression in programming or at least me is to use it as a language that describes search patterns. One example would be an expression that looks for a date in a specific format like 2020-01-09 in a given text. For example you would write an expression that states: A four digit number, starting with a 1 or 2 followed by a "-" then a number between 01 and 12 one more "-" and then a number between 01 and 31. But you have to write it in that language in a compact form. And then your expression will only find that specific format and you can extend it to other formats, like allowing 2020-1-9 as a first step or 2020/01/09 and so on and then formats from other countries, with names of months in different languages and totally go nuts until your regular expression fills multiple pages. But its and incredibly powerful tool and very hard to master. If you have to make one yourself for a more complicated case you will find yourself always tweaking it a bit to include more matches and have less mismatches.
Quite happy to regularly express that I think Prof Brailsford is a nice chap!
If I didn't already know what regular expressions are, I still wouldn't.
For those interested on how to convert a non-deterministic regex (& hence equally a non-deterministic finite automata or non-deterministic left-regular grammar) into a deterministic ones, what you'll have to do is a closure of each (initial state + input state tuple) with each possible subsequent states which in the worst case will mathematically end up being a full power set construction of the initial non-deterministic automata which is why a given non-deterministic regex of length ~n may end up being as big as O(k*2^n) for a positive non-vanishing constant k in the worst case.
So yes, succinctness as well as computational complexity of deterministic vs non-deterministic regexes differ exponentially!
Another thing: all this video talks about is about regexes, finite automata & grammars without much output besides a singular boolean accepting or non accepting, that is, pure acceptors - while in practice regexes, finite automata & grammars often specify a corresponding output which is why they are called a transducers - & there's an entire zoo of different kinds of transducers - even for just regexes - different forms of output, multiple outputs... you name it!
0:43 Professor Brailsford is a real-life Yoda
/Lol/i
Aka Coda
I'm part of a minority, should I be worried?
It still boggles my mind that people know what regular expressions are but don’t understand them, and are so proud of that fact that they’ll brag about it in RUclips comments. If you thought you had one problem before someone used a regex, and then had two problems, well now you have three. You’re unemployable.
Having watched this I feel like I learned absolutely nothing about regular expressions.
Same, lol
I've known it for ten years and his explanation greatly overcomplicates it and never really gives you an idea of how it works, it was more a history lesson. He does this a lot.
@@SteS i came for the history - i know the rest.
@@idjles I was replying to Colin as he thought this was an explanation when it wasn't. The closest he got was explaining *b** was matching b 0 times-infinity.
Well, it is about the idea of regex
There's the Compiler Dragon book in the background there which explains & uses the principles mentioned in this video
Light bulb lit up @ 7:25. Used regex extensively in early 2000's writing real-time flat file parsers for AIG. Very challenging and enjoyable.
The story telling is amazing.
Regular expressions are the sole reason we have websites like stackoverflow etc, so you can ask somebody else to write your regex :P
Please allow the automatic captions
subs have been sent to Sean so shouldn't be too long now ...
Definitely the best video about regular expression I've ever seen!
I never knew it was Kleene(Cleany) I always called him Kleene(Clean). Yes I called the operator a "clean star".
Me too. >w
That epic 'how to parse HTML with regexps'-question on stack overflow.
Worst answers on all that website
Thats an awful use case for regex.
@@Furiends
Why?
StOve question was about finding closing tags in simplest html files
Seems alright place for regex
@@NoNameAtAll2 It can’t work, because opening/closing tags can be nested inside other opening/closing tags, to arbitrary levels. Regexes cannot handle that.
@@NoNameAtAll2
It can’t work, because opening/closing tags can be nested inside other
opening/closing tags, to arbitrary levels. Regexes cannot handle that.
this man is one of my favorite youtubers
Regular expressions are awesome, and in my own experience everyone who's spoken ill of them has implicitly announced their own lack of skill with them rather than establishing anything compellingly negative about them.
A history lesson is fine and all, but I was hoping for a more practical video
Hope to do a couple of case studies in detail in the next video
@@profdaveb6384 it was a great video but must admit I expected a practical video too.
If you think this isnt practical then you should see my professor explain this stuff
And then Larry Wall put regexes into Perl and the world was saved!
Perl is the best programming language ever.
You should see what he did with it in Raku (née Perl 6). Allows for full parsing of something like JSON in a crazy small amount of code (and READABLE code at that). Take a look at the JSON::Tiny module's code. It's actually kinda beautiful
Ken Thompson's `grep` was also a pretty important in-between step.
Glad to see there are a few of us, still.
And you appreciate Perl regexes even more when you see the weird regex implementations in other languages (I'm looking at you, Java).
The guy who designed APL was deeply inspired by the obfuscation of Regex. If you can express a program in 4 lines, then squeeze it into one! The incredible amount of disk space a few extra lines requires can not be understated!
I love regular expressions and I include them in all coding projects. It saves me from having to write hundreds of lines of code to capture the same data with a single regular expression.
Regex is incredibly useful for searching for and filtering text. It's a feature of pretty much every MUD client for that reason. One long sentence worth of Regex can do with 40 lines of code for a plugin can do. I've used them to the extent that my client's memory allocation for that system seems to have run out and they don't always fire now, lol.
Useful as long as you don't let it become Zed's hair code.
> These yellow pets
> are called Zeds.
> They have one hair
> up on their heads.
> Their hair grows fast...
> so fast, they say,
> they need a hair cut
> every day.
> - Dr. Seuss, One Fish Two Fish Red Fish Blue Fish
When code is crunched into a single complex line when many simple lines would be clearer, I call that Zed's hair.
Eg, if you're trying capturing all email addresses and phone numbers from a string. Split it into two separate searches, one for emails, one for numbers. Don't crunch it into one line by creating a single RegEx that matches both email addresses and phone numbers.
Also, as you mentioned, regex can be inefficient. Crunching down line numbers when it sacrifices both clarity and efficiency is incredibly dumb.
That said, simple regular expressions can be much clearer than the equivalent multiple lines of code.
@@JNCressey Haha that's a great expression. I'm stealing it.
Finally a subject I know! There's a lot to be said about Automata and Regex, and personally I think it's a great debt of this channel.
One thing is about the Sakoda Sipser problem, which asks about the amount of states involved in the change from non deterministic to deterministic automata of basic operations of (regular) languages like union, intersection, complement and so.
Other is the Černy problem, but this is more abstract.
Automata are a very interesting subject hidden from the general public.
Yeah they could have explained why the not so regular expressions are called regular and in fact knowing why its called that and understanding what regular means also tells you when you should and should not use regex.
I agree also It would be great to do something about push-down automata, deterministic and non-deterministic and say something about relation between automatas and languages in chomsky's hierarchy
The idea that I can describe state machines with regex is somehow mindblowing.
7:04 Notice the only kind of recursion allowed is tail recursion-there is nothing after the B that occurs in the substitution for B itself. This can be implemented with simple iteration, without a stack. Otherwise, it would no longer be a Type 3 grammar.
I have often wondered how the name Kleene should be pronounced since I had only seen it written. This pronunciation is at least something I’ve learned from this video.
Was not expecting Noam Chomsky to come up in a Computerphile video!
His hierarchy of languages has come up in a couple of past videos. I suspect that among this channel's audience, there's a decently large percentage who only know of him for that.
While this explains the history and background of Regex very well, it's not a video for regex beginners who want to use them.
Thank you, for the explanation , but especially for the historical perspective on things that are used.
I was intrigued by describing graphic diagrams over the phone , that I admit you can't really do that if you only have a microphone and a speaker.
The older I get the more I try to learn and use things with a histiorical background and not just use them mindlessly.
I thought regex was just a syntax for searching for patterns in strings, but this video makes it seem like it's at the heart of programming and computer science... what am I missing?
ab(a|b)b
or for a single line
^ab(a|b)b$
I bet there's other approaches that would work just fine too.
1:14 it’s not a good idea to write zero inside a circle, professor Brailsford.
Only if you forget to put a stroke through it.
I can't imagine a person sounding more British than this gentleman
This is one of the topics we have covered in discrete maths on my computer science degree, could have done with this video a couple of weeks ago lmao, great video though
If you can master Regex, you can add tremendous power to app for little effort. Seriously, if you need to do text parsing and validation, you are cheating yourself if you don't look into using them.
Of course, the grammar way of doing things allows you to specify things that cannot be specified with a finite automata or a regular expression (namely nested constructs like parenthesis). :-) Just, the particular set of grammar statements he chose express exactly what's being expressed in the other two forms.
I was about to comment the same thing. A formal grammar allows recursive structures, but most regex implementations don't have a way to do that. Thankfully there are some now coming out that do, and man does it make creating parsers so much easier.
@@MSStuckwisch - But, it will make the regex handling slower. There's a reason for the very restrictive nature of regexes. It enables a very simple model for the computation. There is, in fact, a C++ library that will generate the C++ code to match a DFA at compile time for super-fast regex handling. Making it as fast as it is if you had to do full LALR or recursive descent parsing would be impossible I think.
Regexes definitely have their place. And parsers have their place too. That's one of the reasons that a lot of compilers are written with a 'lexing' phase that uses a regex to tokenize the input, then uses a parser to parse the code.
@@Omnifarious0 True, though the speed will really depend on the nature of the grammar. A fully unambiguous CFG (to eliminate any type of backingtracking) should be able to optimize to virtually the same speed. Of course, virtually no real-world grammars are written like that, and most of the time we'd want to do more than just a yay/nay match.
To me it comes down to ease of writing / maintaining. Most of the time the slower parsing using regex grammars is worth it, but if something starts to become truly speed critical, then I'd look to coding it manually for speed. (An interesting speed test for optimizations can be the JSON::Tiny (regex) and JSON::Fast (imperative) modules in Raku. Overtime the Tiny has been catching up a little bit, although the Fast still runs in about 25% Tiny's time
People wanting a more practical video do not get that this channel is more focused on the mathematical aspects of computer science.
Grammers and regular expressions are not equivalent! You cannot write a regular expression for lets say a^n b^n (all strings that have n a symbols followed by n b symbols) but you can do it with a grammer: S -> aSb | ab
That’s not a regular grammar.
@@lawrencedoliveiro9104 of course it''s not, regular expressions are a sub set of context free grammar. Regular grammars are defined as all grammars that can be written as a regular expression.
edit: I think that in the video what he meant is that all 3 examples are equivalent, that is true. What I'm saying is that that could be misleading and someone would start to think that all grammars can be written as a regular expression, which is false.
@@ItsN1key Trying to equate regular expressions with non-regular grammars is, shall we say, mathematically disingenuous, is it not?
I could'nt comprehend a single word in this entire video, let alone understand regular expressions.
Sir. These explanations are crystal clear. You're a legend. Thank you so much :)
ill never get what people dont get about regular expressions
Pattern recognition is the essence of intelligence.
Some people get regex, some don't.
Therein lies the rub.
If you write the expression "abab|abbb" as "ab(a|b)b" or "ab[ab]b" it is much easier to see the way to create the state machine.
Go on professor B, nail it!
what is a regular expression? What is it good? Suppose you want to look for the word "he" in a book a simple search will also give you noisy results "they, she, here, etc". Well to fix that you include spaces " he " though you'll still miss things like typos such as he being right on the end of a sentence ".He said". Regular expression [^a-zA-Z]he[^a-zA-Z] let's you look for "he" with no excess letters on either end.
Actually you should be able to use \b (word boundary) instead /\bhe\b/ .
I wish this video was up when I was studying towards my theory exam! Great video
There are a fantastic collection of articles on regexes and implementing them efficiently on Russ Cox's website. They're a bit more in depth than this, but still pretty accessible, though they come with the assumption that you can read C.
You need to understand C ... Yeah very accessible ;-)
@Steven Tsakiris
:-)
C seperates the man from the quiche
eaters.
at 6:42 it seems you place more emphasis on regular expressions (type 3) than the more powerful context free grammar (type 2), regular expressions are only limited in recognizing strings in text (pattern matching), and for lexers, or tools like grep (only 2000/3000 lines of code), awk etc..., but they can't do that much, I see you have the dragon book on your desk, and you value regular expressions more than cfg, the real geniuses were Chomsky and then McClure with his TMG, that Ken Tompson was so impressed that he used his principles also in the B language which later became C, same principles but greatly improved by Donald Knuth's inventing the most powerful LR parser followed by Stephen C. Johnson inventing Bison, I'm a parser fanatic, worked on a preprocessor C, contributed to add improvements in binutils and gcc source (bfd for the section elf and coff and dwarf for symbol debugger) and make version 4.x for variable expansions
In languages that permit it, parser combinators allow more verbose, but still highly readable regular expression syntax:
myParser = do
char 'a'
many (char 'b')
char 'c'
An instance of (char x) is of type (Parser Char). When sequenced, the whole function effectively becomes type (Parser [Char]) which is equal to (Parser String).
Regex is my bane. Anything but the most simple expressions are like writing minified code outright!
But they’re so good!
^\(?([0-9]{3})\)?[-. ]?([0-9]{3})[-. ]?([0-9]{4})$
I feel like part of the purpose of regex is lost in its short handedness. If the above looks like an alien language then you should either get really familiar with regex or use an expanded notation thats intuitive.
Long English notation:
^ = From start
\X = literal X
? = zero or one time
( = capture
) = end capture
[X] = any of X
X - Y = from X to Y
{X} = X (range) times
$ = to end
From start, literal (, zero or one time, capture (, any of, from 0 to 9, 3 times, literal ), zero or one time, ) end capture, any of - or ., zero or one time,
capture (, any of, from 0 to 9, 3 times, ) end capture, any of - or ., zero or one time,
capture (, any of, from 0 to 9, 4 times, ) end capture, to end.
I've always pronounced kleene the same way as clean
No they didn't get it wrong! Research shows that Kleene himself wanted it to be pronounced "Claney" but I suspect it's a Germanic surname and should be "Clay - nuh" (see Wikipedia entry for S.C. Kleene). I did devote a few mins to this in the filming session but Sean clearly had to omit it because the video is already very long at 17 mins.
Once this finished uploading have a watch: ruclips.net/video/-U_ggjfLc1g/видео.html -Sean
@@profdaveb6384 wow thanks for the clarification :) that's really interesting
@@profdaveb6384
U are
L= (knowledge)*
❤❤
so this is where kleen*ex got its name from?
Asking for a friend... ;)
On my lunch break and here I am watching a video on Regex...But it's by Professor Brailsford so it'll be interesting!
What the heck is determinate (deterministic) vs non? I comes up too often and in too many ways for me to infer and I don't understand the somewhat philosophical references that I find.
PEG is a better solution for complex parsing, but regex is fantastic for simpler cases. All about using the right tool for the job
Should have shown the official regexp for an email address. It's enormous
Probably 2/3rds of my SQL or PL/SQL coding nowadays involves using the regexp_????? functions (regexp_replace and regexp_like in particular). They are so useful.
Regexp is the shortest way(often the worst) to define state transitions.
I used to struggle with regex until I took a formal language class :P
I recognise the ‘Dragon’ book in the background, but couldn’t find my copy. But I did find Bornat’s book on compiler writing.
Awesome video! RegEx are super useful!
I have the same mouse. excellent taste professor brailsford
I'm doing a lunch and learn on RegEx at work in the coming weeks...this is conveniently timed.
I just tried to search a not completly readable serial code with google today, but regex seems not to be supported.
So thank you for substituting my missed oportunity to revise/remember regular expressions!
I was under the impression that the grammar was more expressive than the regular expression. For example, a grammar can balance parentheses. Unless there is some restriction on the grammar you describe here.
It’s a regular (Type 3) grammar.
If you want to explain to people not knowing what regexp is, you may want to start by explaining what it is used for !!
My question is, do you still have use for that green bar paper or are you using it as note pad paper because you have it left over from back in the day? As a kid, I had reams of green bar paper from my uncle that was a software engineer at Rockwell International, programming avionics in C and who knows what other language before that. That green bar paper was, literally, an unending joy to draw on as a kid.
P.S. - I think RegEx is one of the most brilliant, yet least mastered languages in computer science.
If this was the no-previous-experience-needed version I'd hate to see the one requiring it.
Professor Brailsford, I loveeee you!!!!
Regular expressions are hard to read but on *unix you can't live without.
Few more videos and we will have Prof. Brailsford's Computerphile course on compilers.
How about getting the Perl and Vim people to agree on what should be escaped?
Omg finally I asked for this 2 years ago
But the most important question here is of course "Can you use regular expressions to parse HTML?"
pattern matched:
print('wow, i have the same exact shirt as professor's.)
Would these all be equivalent to BNF notation as well? Or am I misunderstanding slightly?
I know you should never put people on a pedestal, but I have to make an exception for Professor Brailsford!
What happens if b* is zero, wouldn't it be like (B-> bB | lambda) and (S-> aBc)
I'm watching a series on computation theory on another channel and funnily enough he just covered some of this stuff. But I'm not a computer scientist and I still need someone tell me how this actually relates to real programming or machine design. Unless I truly wanted to build a machine that accept or reject strings of characters. But it does feel like that when I code.