Regular expression matching can be simple and fast (2007)
1–10 of 44 posts
Re: Regular expression matching can be simple and fast (2007)
#2This and the associated series of regex posts from Russ Cox are probably the best content on practical regular expression engine internals you can get. If you have a cursory understanding of NFAs and DFAs, it's some of the best technical writing I've ever had the pleasure to read.
These posts are responsible for my love of regular expressions :)
Re: Regular expression matching can be simple and fast (2007)
#3Some discussion from 5 years ago:
Re: Regular expression matching can be simple and fast (2007)
#4Some discussion from 5 years ago: https://news.ycombinator.com/item?id=20310669
Thanks! Macroexpanded:
Regular Expression Matching Can Be Simple and Fast (2007) - https://news.ycombinator.com/item?id=20310669 - June 2019 (33 comments)
Regular Expression Matching Can Be Simple and Fast (2007) - https://news.ycombinator.com/item?id=16341519 - Feb 2018 (20 comments)
Regular Expression Matching Can Be Simple and Fast (2007) - https://news.ycombinator.com/item?id=9374858 - April 2015 (16 comments)
Regular Expression Matching Can Be Simple And Fast [2007] - https://news.ycombinator.com/item?id=6593331 - Oct 2013 (1 comment)
Regular Expression Matching Can Be Simple And Fast - https://news.ycombinator.com/item?id=820201 - Sept 2009 (15 comments)
Regular Expression Matching Can Be Simple And Fast - https://news.ycombinator.com/item?id=466845 - Feb 2009 (17 comments)
Re: Regular expression matching can be simple and fast (2007)
#5This and the associated series of regex posts from Russ Cox are probably the best content on practical regular expression engine internals you can get. If you have a cursory understanding of NFAs and DFAs, it's some of the best technical writing I've ever had the pleasure to read. These posts are responsible for my love of regular expressions :)
And if you don't have a cursory understanding of NFAs and DFAs, they're still great for getting that cursory understanding.
These articles were my introduction to finite automata (and almost the only place I've learned about them aside from practical use) and my intuition for them seem to often be better than my peers'.
Re: Regular expression matching can be simple and fast (2007)
#6This and the associated series of regex posts from Russ Cox are probably the best content on practical regular expression engine internals you can get. If you have a cursory understanding of NFAs and DFAs, it's some of the best technical writing I've ever had the pleasure to read. These posts are responsible for my love of regular expressions :)
And if you don't have a cursory understanding of NFAs and DFAs, they're still great for getting that cursory understanding. These articles were my introduction to finite automata (and almost the only place I've learned about them aside from practical use) and my intuition for them seem to often be better than my peers'.
NFAs are apparently undecidable since the same input can go to multiple states. DFA states can only go to one state when given a particular input sequence.
The Dragon book contains an NFA to DFA algorithm (powerset) which explodes states with multiple exiting token transitions.
PS: All your DAGs are belong to us.
Re: Regular expression matching can be simple and fast (2007)
#7Perl needed a couple of years to catchup. At first they had no idea what Russ was talking about
Re: Regular expression matching can be simple and fast (2007)
#8Regexes can be fast and simple, but sometimes it’s faster and simpler to use normal string search. I recently replaced a regex with two finds for 10x speedup.
Re: Regular expression matching can be simple and fast (2007)
#9Earlier quoted context omitted.
And if you don't have a cursory understanding of NFAs and DFAs, they're still great for getting that cursory understanding. These articles were my introduction to finite automata (and almost the only place I've learned about them aside from practical use) and my intuition for them seem to often be better than my peers'.
NFAs are apparently undecidable since the same input can go to multiple states. DFA states can only go to one state when given a particular input sequence. The Dragon book contains an NFA to DFA algorithm (powerset) which explodes states with multiple exiting token transitions. PS: All your DAGs are belong to us.
NFAs are decidable. As you said, a NFA can be converted to a DFA which is decidable. Maybe you mean they are non-deterministic (that's in the name)?
Re: Regular expression matching can be simple and fast (2007)
#10Regexes can be fast and simple, but sometimes it’s faster and simpler to use normal string search. I recently replaced a regex with two finds for 10x speedup.
Well if people spend time learning arcane regex syntax it'd be a shame to not use them!
But yes, you're right. Sometimes simple finds are sufficient.