[HN Gopher] Programming Techniques: Regular expression search al...
       ___________________________________________________________________
        
       Programming Techniques: Regular expression search algorithm (1968)
        
       Author : userbinator
       Score  : 15 points
       Date   : 2023-08-12 08:36 UTC (14 hours ago)
        
 (HTM) web link (dl.acm.org)
 (TXT) w3m dump (dl.acm.org)
        
       | mikhailfranco wrote:
       | This is _Thompson 's Construction._
       | 
       | There is a nice description given by Russ Cox:
       | 
       | https://swtch.com/~rsc/regexp/regexp1.html
       | 
       | The following project has an interesting implementation in
       | Elixir, which converts the NFA directy into a process network:
       | 
       | https://github.com/mike-french/myrex
       | 
       | The network runs all possible traversals concurrently without
       | back-tracking. It automatically scales to use all cores (Erlang
       | BEAM runtime). Multiple input strings can be processed
       | concurrenty. It can also generate matching strings concurrently
       | (Monte Carlo). It implements captures and Unicode character sets.
       | 
       | While it is designed for concurrency, it is not meant to be the
       | fastest regex implementation. There is an example of a highly
       | ambiguous match that launches 900k traversals and reports all
       | capture results in about 10s.
       | 
       | There is a short proof sketch for the formula to calculate the
       | number of possible matches in this case as _a dot product of
       | vectors sliced from Pascal 's Triangle._
        
       ___________________________________________________________________
       (page generated 2023-08-12 23:01 UTC)