2 ms·
Oh, I understand what you're saying. No they weren't using native .net regexes. As an aside, I'm not sure the specifics of the .net regex engine at the time, b
by keepamovin 3y ago
Oh, I understand what you're saying. No they weren't using native .net regexes.
As an aside, I'm not sure the specifics of the .net regex engine at the time, but you seem to be suggesting that it used an NFA. I suspect it might not have but I don't know. Certainly a few languages didn't use NFAs, yet others did indeed! :)
To your point: it was many years ago so perhaps I will get some details wrong in what follows. I apologize in advance for the fuzziness! The most clear thing in my memory was the beauty of Thompson's work and how much using it sped things up.
Anyway, their system had a custom pattern matching algorithm specific to a couple NLP domains and conceptual models they were working in, that was like regex but extended. It was an academic invention, sophisticated and ambitious, and IIRC, they hadn't fully implemented all their ideas. Turned out their implementation just wasn't particularly efficient.
IIRC, it was a recursive implementation, but it's so many years I can't recall really, especially as I was mainly focused on making it faster. This necessitated replacing much of their code, but luckily the implementation and ideas were clean enough that the replacement was almost as if a clean interface had been planned all along, IIRC.
Turns out it could be sped up mightily by replacing a lot of their implementation with Thompson NFA and then adding their custom weird stuff on top of that. I tried to push the NFA as far as it could to utilize its own concepts to implement their ideas, but some things simply couldn't fit, so had to be bolted on. Still, it was far more efficient.
That's what it was.
As another aside: I think it was Russ Cox's article online about Thompson NFA that I found and which led me down that path. IIRC, he has this super simple HTML page with maybe a powder blue background telling all about it. His article was also a great help in clearly understanding the concept. It was fun to go back and forth between article, paper and code to get it to work!
- vidarh 3y agoNo powder blue background so maybe it's a different page or has been redesigned, but Cox has a page linking to several articles on regexps here [1]. [1] https://swtch.com/~rsc/regexp/ https://swtch.com/~rsc/regexp/
- keepamovin 3y agoThat's the page! Man it was 12 years, could be my memory :) https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html It might have had a more "retro geocities" type design in the past, tho haha
- burntsushi 3y agoThis is exactly what was linked and discussed in my OP. ;-)
- keepamovin 3y agoYeah, very good overview, no?