Regular Expressions - Computerphile

Professor Brailsford on one of our most requested topics.

This video was filmed and edited by Sean Riley.

[ketv]

'Some people, when confronted with a problem, think, “I know, I'll use regular expressions.” Now they have two problems.' - J. Zawinski

[ChrisSeltzer]

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."

[giotsas]

A wise man once said: "The plural of regex is regrets"

[samipah]

More info in:
Mastering Regular Expressions, 3rd Edition
By Jeffrey Friedl

Pages: 544

[josko]

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.

[davidgillies]

It is hard to overstate the enlightenment that comes from realising that a regular expression is a state machine.

[realandar]

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.

[hahahatall]

It's terribly difficult to explain regex to people who don't use it!

[sejinmajnaric]

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.

[swagatochatterjee]

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.

[BeCurieUs]

As far as pedagogy goes, Professor Brailsford is unrivaled. Def reignited my computer science flame

[tedchirvasiu]

0:43 Professor Brailsford is a real-life Yoda

[fouzaialaa]

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

[BTHobbies]

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!

[asaadb]

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!

[chaoslab]

Quite happy to regularly express that I think Prof Brailsford is a nice chap!

[banderfargoyl]

Love the history. Ken and Dennis certainly deserve the recognition for their accomplishments.

[davidwise]

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.

[thattimestampguy]

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.

[lawrencedoliveiro]

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.