Remix.run Logo
Remix clone Hacker News
new | show | ask | jobsGithub
▲ ogogmad a day ago

I don't know if you're aware that there's a formal analogy between matrix operations and regex operations:

  Matrix vs Regex
  --------------

  A+B with A|B
  
  A*B with AB
  
  (1 - A)^{-1} with M*
To make the analogy between array programming and regex even more precise: I think you might even be able to make a regex engine that uses one boolean matrix for each character. For example, if you use the ASCII character set, you'd use 127 of these boolean matrices. The matrices should encode transitions between NFA states. The set of entry states should be indicated by an additional boolean vector; and the accepting states should be indicated by one more boolean vector. The regex operations would take 1 or 2 NFAs as input, and output a new NFA.
▲BiteCode_dev 17 hours ago | parent [-]

Didn't know that but I assume you can share most of the engine's logic anyway. Those kind of generalisations tend to break down once you get pratical implementations.