[HN Gopher] How Regexes Work
       ___________________________________________________________________
        
       How Regexes Work
        
       Author : aleyan
       Score  : 65 points
       Date   : 2022-11-12 01:04 UTC (21 hours ago)
        
 (HTM) web link (perl.plover.com)
 (TXT) w3m dump (perl.plover.com)
        
       | macintux wrote:
       | Probably taken from yesterday's discussion: Ken Thompson's NFA
       | regex patent
       | 
       | https://news.ycombinator.com/item?id=33566557
        
       | [deleted]
        
       | kqr wrote:
       | Always a worthy, related mention:
       | https://swtch.com/~rsc/regexp/regexp1.html
       | 
       | Another fun idea is the opposite of the regex: the regex
       | constructs a state machine of the needle and is then quickly able
       | to run many haystacks through it. Sometimes you need the other
       | optimisation: compile the entire haystack down to a state
       | machine, and you can run many needles through it! It becomes a
       | very primitive search index.
        
         | zwkrt wrote:
         | That link is a very high quality write up.
         | 
         | I'm having a hard time understanding how your "haystack
         | compilation" would work. I get the desire to be able to
         | efficiently run many regexes on the same large file, but how
         | could you optimize the file for arbitrary regex matching?
        
         | jstrieb wrote:
         | The haystack idea reminds me of this wonderful post from the
         | creator of both the Rust regex crate and the ripgrep command
         | line utility (among other awesome things).
         | 
         | https://blog.burntsushi.net/transducers/
        
           | metadat wrote:
           | Interesting read.
           | 
           | Also discussed only 1 year ago:
           | 
           | https://news.ycombinator.com/item?id=28243636 (174 points, 10
           | comments)
        
         | lagt_t wrote:
         | January 2007
         | 
         | No thanks
        
           | Cu3PO42 wrote:
           | How is the age relevant here? The article doesn't deal with
           | current events or the newest hottest framework. It explains
           | algorithms and abstract ideas which haven't changed in the
           | last 15 years.
        
       | ttul wrote:
       | I worked briefly with Mark-Jason Dominus in 2000. He added
       | instrumentation to the Perl regex engine so that we could develop
       | a regex debugger for the forthcoming Komodo editor. Each time the
       | engine advanced to process the next step, we would get a callback
       | that included vital information such as the location in the regex
       | string and the target string.
       | 
       | Today, there are numerous excellent tools like this on the web.
       | Back in 2000, it was dark magic and so much fun to work on.
        
         | nerdponx wrote:
         | There are websites that can step through a regex execution
         | (e.g. Regex101), but I still don't have a regex debugger with
         | arbitrary callbacks! When do I get one in Python?
        
       | [deleted]
        
       | mNovak wrote:
       | Curious if this exponentially slow regex is the reason Notepad++
       | crashes on loading modestly sized (10 MB) JSON?
        
       ___________________________________________________________________
       (page generated 2022-11-12 23:02 UTC)