10 ms·

Learn Regex The Hard Way

191 points by karlzt 15y ago

deleted 15y ago
[deleted]
jdthomas 15y ago
Not to sound like a pretensions CS guy ... but how can you have a book on regular expressions without even mentioning DFA/NFA? Maybe its just me, but (back in my day) I found learning about finite automata made regex just click. Edit: ahh, I see now mentioned in intro that "I'm going to be very practical and straight forward about it. No NFA to DFA conversion. No crazy explanations of push down finite state automata." :) I still argue that thinking of regex as state machines is a very useful tool.
- mekoka 15y ago
  I'm not a CS graduate. I first learned of state machine from an article posted here on HN a few months ago. I learned regular expression from the regular-expression.info site and from the first 4 chapters of Jeffrey Friedl's book over 5 years ago. I don't recall an introduction to NFA/DFA from them either. I'm pretty comfortable with regex and use them regularly (no pun intended) and so far, I don't feel that I've missed much. I'm not disagreeing with your view, but I think it's worth pointing out from someone having developed an understanding of regex from a different perspective, that NFA/DFA might not be such a strong prerequisite and people should not feel like they're going in at a disadvantage.
  - bad_user 15y ago
    An understanding of finite-state machines is useful, because that way you'll understand the limitations you have when using regular expressions, which have been grossly misused. It also helps you write optimal regular expressions - for instance if your regular expression clearly describes a DFA, then it will probably perform well. Otherwise in many cases you can optimize it - just as you can turn any NFA into a DFA. It isn't so clear and cut these days however, as the regexp capabilities provided by modern libraries exceed the capabilities of finite state machines - for instance the engine in Perl 5.10 has support for recursion, which means a regular expression in Perl 5.10 can describe a Pushdown Automaton (PDA) instead, so things get way more complicated. Either way, I suggest you do some reading on Automata Theory, because it's fun and not that hard.
  - spp 15y ago
    Chapter 4 of Jeffrey Friedl's "Mastering Regular Expressions" goes in depth about NFA/POSIX NFA/DFA. It even has car analogies!
    - mekoka 15y ago
      It must have been the 3 first chapters then. At the time, they were enough for me to understand and "get going" with regex. Various other online resources have filled little gaps here and there over time. This thread makes me want to revisit the book and resume my reading of the next 3 chapters, a long overdue promise to myself. I'm glad that the book will cover the topic of FA then.
- burke 15y ago
  I'm a CS graduate, and I read the Friedl book on regular expressions in high school. I don't seem to remember learning anything about automata from it, and I know for certain that my automata course in university didn't make me any more competent at understanding or applying regular expressions.
- dfc 15y ago
  Do not worry, in order to sound "pretensions" you need to be able to spell pretentious correctly;)
- leeoniya 15y ago
  i learned regex inside-out before ever learning or implementing any sort of FSM - just sayin'.
- zedshaw 15y ago
  Yep, I'm going at it from another direction where I teach the symbols like a language, and then it makes it easier to explain how they work later. I agree that state machines are a great way to understand them, but I don't think they're practical for using them and they just complicate getting capable in it.
  - furyg3 15y ago
    Just wanted to chime in, thanks a lot for making the guide with this approach. Sysadmins, specifically, will find this to be a great resource. Many people start out tweaking config files, editing other's scripts, manipulating logs and output data, and then eventually sit down and say "Damn, it's about time I learned how to really write good [bash/perl/python/regex]". I find the theory behind it interesting, but it's a bit of a distraction for many.
- kd0amg 15y ago
  I imagine that sort of implementation issue is only relevant to the typical user if that user comes across a case where the potential inefficiency of NFA->DFA conversion (or NFA simulation) actually does happen. I'm not sure how common it is to encounter this. I'd be more concerned about making sure there is some discussion of nonregular languages; this appears to be in the works (I'm curious to see what exactly it turns out to be).
- irahul 15y ago
  Personally I don't find NFA/DFA helpful with learning regular expressions. To a newcomer, even a naive implementation of NFA/DFA doesn't make sense. Consider this small gist https://gist.github.com/1414061 https://gist.github.com/1414061 I have a feeling a newcomer will come out none the wiser even if he were shown this. And this is just a naive implementation - no nfa to dfa conversions, inefficient implementation etc. I would root for state diagrams though. Generally diagrams help people see patterns mere text doesn't.
- marchdown 15y ago
  I know the theory pretty well, but writing actual regexes always felt so slow and frustrating that I really welcome this kind of rote hand-holding tutorial. I might finally learn the arbitrary DSL that everyone seems to have settled on.
suivix 15y ago
The (?i) is a confusing part of that example expression, and I don't see why it's necessary.
- walrus 15y ago
  The (? ... ) syntax is for "extended patterns". In this case, it makes the rest of the regular expression case insensitive. Read through http://perldoc.perl.org/perlre.html#Extended-Patterns http://perldoc.perl.org/perlre.html#Extended-Patterns for more information on extended patterns.
- zedshaw 15y ago
  Which one? That might be an error.
  - rcthompson 15y ago
    I think it's the one on the "cover page" (the one linked to from HN.
- irahul 15y ago
  It's good to know about it. Earlier at an employer we had a system where a processor in the pipeline took regular expressions as input - you can pass regular expressions but not the flags. (?i) is the only way you can indicate case-insensitive in these cases.
delwin 15y ago
What do you guys think of Zed Shaw's teaching style? As I'm not a beginner programmer, I can't really evaluate correctly — to me it seems like a odd approach to programming pedagogy, but perhaps it works. Any non-programmers want to shed light on why his style works?
- KevinEldon 15y ago
  My brother is working through Learn Ruby The Hard Way, which is not written by Zed, but is based on his Python book. He has no programming experience and seems to be enjoying the work and learning Ruby pretty quickly.
- nikcub 15y ago
  as a Python dev I scanned the python book and I thought it dwelled too much on string formatting, focused on teaching syntax and not programming, and the language was a bit terse. but then a friend of mine told me that he and a few other people he knew learnt python from that book, so either later revisions got better or my opinion is shit.
  - zedshaw 15y ago
    I don't think your opinion is shit, I just think your perspective has changed because you actually can code. The hardest thing for a beginner is just the syntax. If you've never written code before then the symbols in programming are alien as hell. By focusing on seemingly repetitive syntax drills I get them skilled progressively until syntax isn't a problem. Another thing you might be missing is under each exercise is a real piece of programming they're learning. For example, with string formatting I'm actually teaching the concept of named variables. Later on I use the fact they've actually been using named variables to then teach the concept explicitly and then they get it quicker.
    - YuriNiyazov 15y ago
      I agree that syntax is the hardest thing. Based on my experience tutoring, I would add the following (which was surprising to discover at first): the second hardest thing is the order of evaluation. I've seen students write down a = do_something1(do_something2()) and be unable to explain that do_something2() actually happens before do_something1(), and to see that the code is loosely equivalent to b = do_something2() a = do_something1(b)
leeoniya 15y ago
just decided to randomly click a chapter. in 12.1 wouldn't ^[0-9]+|[A-Z]+$ in fact need to be written as ^([0-9]+|[A-Z]+)$ or non-capturing ^(?:[0-9]+|[A-Z]+)$ i doubt the intent was to alternate NL/EOL assertion. seems like a novice oversight and does not instill confidence in the rest of the material. or am i missing something?
- mekoka 15y ago
  The point is not to have the best or most efficient regex expression, but rather to do the exercises and to highlight by this process misconceptions you may have about how the regex engine operates. You enter what is given, you run it, see what the console returns, ponder about the implications for a few minutes and then scream "aha!" What do you expect ^[0-9]+|[A-Z]+$ to return when matched against the various lines? What does it actually return? What conclusions do you draw from that little experiment?
  - leeoniya 15y ago
    unfortunately this is not an efficiency optimization. the intent appears to be to match EITHER all-alpha OR all-numeric strings. the regex, as given, would match both "&()ABC" and "5673%$^#" and "123ABC" but NOT "ABC123" what should be a simple concept is defeated and confusion ensues. the correct formulation should have been ^[0-9]+$|^[A-Z]+$ or (judging from the example input and output samples) [0-9]+|[A-Z]+
    - zedshaw 15y ago
      Uh, no, the intent is not to match all-alpha or all-numeric strings. It's to search for all alpha or all numeric. As I mentioned above, you're confusing search with match semantics.
- zedshaw 15y ago
  Hmm, well the book is being written so there's potential for some errors, but I believe you are wrong here. You're confusing match with search semantics. Your above works because by default Regetron searches. If you turn on match it doesn't match your proposed test below. Try this: http://codepad.org/uPpwKPJS http://codepad.org/uPpwKPJS Notice when you turn on !match it doesn't find your test. Also, keep in mind that this is just introducing the concept of alternating. Captures are covered later.
mturmon 15y ago
The regex shell is a neat idea. In many situations I'd like to generate strings accepted by the regex, to check that my regex is tight enough. I know this is hard in general (for lots of reasons, basically all reducing to "there are a lot of strings and no easy way to iterate through them in a satisfying way"). But, has anyone made any progress on this for the "easy" cases?
- zedshaw 15y ago
  I thought about trying but it's hard to dip into the regex data structure (if there is one) and also display it in some sort of meaningful way. Other than that, Regetron is kind of just enough of a tool to get you through the book and have no friction. I think for more advanced regex exploration there's http://kodos.sourceforge.net/ http://kodos.sourceforge.net/ and I believe there's a few javascript ones in the browser and even a few very advanced ones in Java.
  - tbrooks 15y ago
    I'm sure this has made the rounds before: http://rubular.com/ http://rubular.com/
- scorpion032 15y ago
  Your wish has been granted: http://txt2re.com/ http://txt2re.com/ I use this all the time. No wonder I don't know to hand write a Regex.
  - haraball 15y ago
    Here's another tool I use when testing my regex: http://regexpal.com/ http://regexpal.com/ Nice tool for testing the regex on a given data set.
  - mturmon 15y ago
    That's a neat page, which does help construction of regex's. But, it does not address the question I posed. The regex R generates a language L of strings accepted by R. I want a facility for generating example elements of L. Given that L often is infinite or has immense cardinality, this is hard to do. I think I want a breadth-first descent of the tokens in the regex, but it's not always that simple.
scrame 15y ago
Thats pretty awesome. Regex's the tool (vs. the concept of "regular expressions" that comes up in interpreters/compilers) is a supremely useful utility when used sparingly, and surprisingly portable between languages. Regex's are in a (not-)sweet spot of practical languages that aren't taught in school. For all the hype of ruby, et al. being able to make "DSL's", its surprising how mystical an _actual_ DSL, that is portable between languages (through PCRE) is held. Unfortunately, like many other tools, can be used sparingly after a lot of practice writing crappy regex's, and having to eat your own dogfood (so you learn its not an "ultra-fast parser", or that you shouldn't chain substitutions on user-generated input). A rote tutorial -- in the style of LPTHW -- is excellent.
- itmag 15y ago
  What are some other examples of DSL's that are useful in the same way as regexes? I am thinking LINQ might qualify. Also, JQuery is strictly not a DSL, but it kinda feels DSLy.
  - lmkg 15y ago
    Personally, I classify any sort of sequence comprehension as a DSL, including LINQ and python's list and generator comprehensions. JQuery is basically as close to a LINQ-like DSL as you can get in a language like JavaScript that doesn't have metaprogramming support. Related to sequence comprehensions, there is Common Lisp's controversial LOOP macro, which is basically an iteration comprehension DSL. I'm somewhat on the fence about whether format control strings qualify as DSL's. They don't as much, but they tend to have very complicated and specialized syntax. I feel that Monads are a DSL in Haskell, but whenever I see "Monads in Blub!" I don't feel the same way about them. Part of it is probably that Haskell provides not only infix operators, but do-notation for supporting monads. Part of it is also that monads don't do as much in other languages, because their type systems aren't rich enough to fully express them, nor restrictive enough that their capabilities are useful.
    - itmag 15y ago
      A DSL doesn't have to be Turing-complete IIRC so format strings could probably qualify.

191 points by karlzt 15y ago

deleted 15y ago

[deleted]

Not to sound like a pretensions CS guy ... but how can you have a book on regular expressions without even mentioning DFA/NFA? Maybe its just me, but (back in my day) I found learning about finite automata made regex just click. Edit: ahh, I see now mentioned in intro that "I'm going to be very practical and straight forward about it. No NFA to DFA conversion. No crazy explanations of push down finite state automata." :) I still argue that thinking of regex as state machines is a very useful tool.

mekoka 15y ago
I'm not a CS graduate. I first learned of state machine from an article posted here on HN a few months ago. I learned regular expression from the regular-expression.info site and from the first 4 chapters of Jeffrey Friedl's book over 5 years ago. I don't recall an introduction to NFA/DFA from them either. I'm pretty comfortable with regex and use them regularly (no pun intended) and so far, I don't feel that I've missed much. I'm not disagreeing with your view, but I think it's worth pointing out from someone having developed an understanding of regex from a different perspective, that NFA/DFA might not be such a strong prerequisite and people should not feel like they're going in at a disadvantage.
- bad_user 15y ago
  An understanding of finite-state machines is useful, because that way you'll understand the limitations you have when using regular expressions, which have been grossly misused. It also helps you write optimal regular expressions - for instance if your regular expression clearly describes a DFA, then it will probably perform well. Otherwise in many cases you can optimize it - just as you can turn any NFA into a DFA. It isn't so clear and cut these days however, as the regexp capabilities provided by modern libraries exceed the capabilities of finite state machines - for instance the engine in Perl 5.10 has support for recursion, which means a regular expression in Perl 5.10 can describe a Pushdown Automaton (PDA) instead, so things get way more complicated. Either way, I suggest you do some reading on Automata Theory, because it's fun and not that hard.
- spp 15y ago
  Chapter 4 of Jeffrey Friedl's "Mastering Regular Expressions" goes in depth about NFA/POSIX NFA/DFA. It even has car analogies!
  - mekoka 15y ago
    It must have been the 3 first chapters then. At the time, they were enough for me to understand and "get going" with regex. Various other online resources have filled little gaps here and there over time. This thread makes me want to revisit the book and resume my reading of the next 3 chapters, a long overdue promise to myself. I'm glad that the book will cover the topic of FA then.
burke 15y ago
I'm a CS graduate, and I read the Friedl book on regular expressions in high school. I don't seem to remember learning anything about automata from it, and I know for certain that my automata course in university didn't make me any more competent at understanding or applying regular expressions.
dfc 15y ago
Do not worry, in order to sound "pretensions" you need to be able to spell pretentious correctly;)
leeoniya 15y ago
i learned regex inside-out before ever learning or implementing any sort of FSM - just sayin'.
zedshaw 15y ago
Yep, I'm going at it from another direction where I teach the symbols like a language, and then it makes it easier to explain how they work later. I agree that state machines are a great way to understand them, but I don't think they're practical for using them and they just complicate getting capable in it.
- furyg3 15y ago
  Just wanted to chime in, thanks a lot for making the guide with this approach. Sysadmins, specifically, will find this to be a great resource. Many people start out tweaking config files, editing other's scripts, manipulating logs and output data, and then eventually sit down and say "Damn, it's about time I learned how to really write good [bash/perl/python/regex]". I find the theory behind it interesting, but it's a bit of a distraction for many.
kd0amg 15y ago
I imagine that sort of implementation issue is only relevant to the typical user if that user comes across a case where the potential inefficiency of NFA->DFA conversion (or NFA simulation) actually does happen. I'm not sure how common it is to encounter this. I'd be more concerned about making sure there is some discussion of nonregular languages; this appears to be in the works (I'm curious to see what exactly it turns out to be).
irahul 15y ago
Personally I don't find NFA/DFA helpful with learning regular expressions. To a newcomer, even a naive implementation of NFA/DFA doesn't make sense. Consider this small gist https://gist.github.com/1414061 https://gist.github.com/1414061 I have a feeling a newcomer will come out none the wiser even if he were shown this. And this is just a naive implementation - no nfa to dfa conversions, inefficient implementation etc. I would root for state diagrams though. Generally diagrams help people see patterns mere text doesn't.
marchdown 15y ago
I know the theory pretty well, but writing actual regexes always felt so slow and frustrating that I really welcome this kind of rote hand-holding tutorial. I might finally learn the arbitrary DSL that everyone seems to have settled on.

suivix 15y ago

The (?i) is a confusing part of that example expression, and I don't see why it's necessary.

walrus 15y ago
The (? ... ) syntax is for "extended patterns". In this case, it makes the rest of the regular expression case insensitive. Read through http://perldoc.perl.org/perlre.html#Extended-Patterns http://perldoc.perl.org/perlre.html#Extended-Patterns for more information on extended patterns.
zedshaw 15y ago
Which one? That might be an error.
- rcthompson 15y ago
  I think it's the one on the "cover page" (the one linked to from HN.
irahul 15y ago
It's good to know about it. Earlier at an employer we had a system where a processor in the pipeline took regular expressions as input - you can pass regular expressions but not the flags. (?i) is the only way you can indicate case-insensitive in these cases.

delwin 15y ago

What do you guys think of Zed Shaw's teaching style? As I'm not a beginner programmer, I can't really evaluate correctly — to me it seems like a odd approach to programming pedagogy, but perhaps it works. Any non-programmers want to shed light on why his style works?

KevinEldon 15y ago
My brother is working through Learn Ruby The Hard Way, which is not written by Zed, but is based on his Python book. He has no programming experience and seems to be enjoying the work and learning Ruby pretty quickly.
nikcub 15y ago
as a Python dev I scanned the python book and I thought it dwelled too much on string formatting, focused on teaching syntax and not programming, and the language was a bit terse. but then a friend of mine told me that he and a few other people he knew learnt python from that book, so either later revisions got better or my opinion is shit.
- zedshaw 15y ago
  I don't think your opinion is shit, I just think your perspective has changed because you actually can code. The hardest thing for a beginner is just the syntax. If you've never written code before then the symbols in programming are alien as hell. By focusing on seemingly repetitive syntax drills I get them skilled progressively until syntax isn't a problem. Another thing you might be missing is under each exercise is a real piece of programming they're learning. For example, with string formatting I'm actually teaching the concept of named variables. Later on I use the fact they've actually been using named variables to then teach the concept explicitly and then they get it quicker.
  - YuriNiyazov 15y ago
    I agree that syntax is the hardest thing. Based on my experience tutoring, I would add the following (which was surprising to discover at first): the second hardest thing is the order of evaluation. I've seen students write down a = do_something1(do_something2()) and be unable to explain that do_something2() actually happens before do_something1(), and to see that the code is loosely equivalent to b = do_something2() a = do_something1(b)

leeoniya 15y ago

just decided to randomly click a chapter. in 12.1 wouldn't ^[0-9]+|[A-Z]+$ in fact need to be written as ^([0-9]+|[A-Z]+)$ or non-capturing ^(?:[0-9]+|[A-Z]+)$ i doubt the intent was to alternate NL/EOL assertion. seems like a novice oversight and does not instill confidence in the rest of the material. or am i missing something?

mekoka 15y ago
The point is not to have the best or most efficient regex expression, but rather to do the exercises and to highlight by this process misconceptions you may have about how the regex engine operates. You enter what is given, you run it, see what the console returns, ponder about the implications for a few minutes and then scream "aha!" What do you expect ^[0-9]+|[A-Z]+$ to return when matched against the various lines? What does it actually return? What conclusions do you draw from that little experiment?
- leeoniya 15y ago
  unfortunately this is not an efficiency optimization. the intent appears to be to match EITHER all-alpha OR all-numeric strings. the regex, as given, would match both "&()ABC" and "5673%$^#" and "123ABC" but NOT "ABC123" what should be a simple concept is defeated and confusion ensues. the correct formulation should have been ^[0-9]+$|^[A-Z]+$ or (judging from the example input and output samples) [0-9]+|[A-Z]+
  - zedshaw 15y ago
    Uh, no, the intent is not to match all-alpha or all-numeric strings. It's to search for all alpha or all numeric. As I mentioned above, you're confusing search with match semantics.
zedshaw 15y ago
Hmm, well the book is being written so there's potential for some errors, but I believe you are wrong here. You're confusing match with search semantics. Your above works because by default Regetron searches. If you turn on match it doesn't match your proposed test below. Try this: http://codepad.org/uPpwKPJS http://codepad.org/uPpwKPJS Notice when you turn on !match it doesn't find your test. Also, keep in mind that this is just introducing the concept of alternating. Captures are covered later.

mturmon 15y ago

The regex shell is a neat idea. In many situations I'd like to generate strings accepted by the regex, to check that my regex is tight enough. I know this is hard in general (for lots of reasons, basically all reducing to "there are a lot of strings and no easy way to iterate through them in a satisfying way"). But, has anyone made any progress on this for the "easy" cases?

zedshaw 15y ago
I thought about trying but it's hard to dip into the regex data structure (if there is one) and also display it in some sort of meaningful way. Other than that, Regetron is kind of just enough of a tool to get you through the book and have no friction. I think for more advanced regex exploration there's http://kodos.sourceforge.net/ http://kodos.sourceforge.net/ and I believe there's a few javascript ones in the browser and even a few very advanced ones in Java.
- tbrooks 15y ago
  I'm sure this has made the rounds before: http://rubular.com/ http://rubular.com/
scorpion032 15y ago
Your wish has been granted: http://txt2re.com/ http://txt2re.com/ I use this all the time. No wonder I don't know to hand write a Regex.
- haraball 15y ago
  Here's another tool I use when testing my regex: http://regexpal.com/ http://regexpal.com/ Nice tool for testing the regex on a given data set.
- mturmon 15y ago
  That's a neat page, which does help construction of regex's. But, it does not address the question I posed. The regex R generates a language L of strings accepted by R. I want a facility for generating example elements of L. Given that L often is infinite or has immense cardinality, this is hard to do. I think I want a breadth-first descent of the tokens in the regex, but it's not always that simple.

scrame 15y ago

Thats pretty awesome. Regex's the tool (vs. the concept of "regular expressions" that comes up in interpreters/compilers) is a supremely useful utility when used sparingly, and surprisingly portable between languages. Regex's are in a (not-)sweet spot of practical languages that aren't taught in school. For all the hype of ruby, et al. being able to make "DSL's", its surprising how mystical an _actual_ DSL, that is portable between languages (through PCRE) is held. Unfortunately, like many other tools, can be used sparingly after a lot of practice writing crappy regex's, and having to eat your own dogfood (so you learn its not an "ultra-fast parser", or that you shouldn't chain substitutions on user-generated input). A rote tutorial -- in the style of LPTHW -- is excellent.

itmag 15y ago
What are some other examples of DSL's that are useful in the same way as regexes? I am thinking LINQ might qualify. Also, JQuery is strictly not a DSL, but it kinda feels DSLy.
- lmkg 15y ago
  Personally, I classify any sort of sequence comprehension as a DSL, including LINQ and python's list and generator comprehensions. JQuery is basically as close to a LINQ-like DSL as you can get in a language like JavaScript that doesn't have metaprogramming support. Related to sequence comprehensions, there is Common Lisp's controversial LOOP macro, which is basically an iteration comprehension DSL. I'm somewhat on the fence about whether format control strings qualify as DSL's. They don't as much, but they tend to have very complicated and specialized syntax. I feel that Monads are a DSL in Haskell, but whenever I see "Monads in Blub!" I don't feel the same way about them. Part of it is probably that Haskell provides not only infix operators, but do-notation for supporting monads. Part of it is also that monads don't do as much in other languages, because their type systems aren't rich enough to fully express them, nor restrictive enough that their capabilities are useful.
  - itmag 15y ago
    A DSL doesn't have to be Turing-complete IIRC so format strings could probably qualify.