4 ms·

Often you want to capture something, not just check if a match exists. But the theory of capture groups in DFAs is relatively obscure - for example tagged DFAs

Often you want to capture something, not just check if a match exists. But the theory of capture groups in DFAs is relatively obscure - for example tagged DFAs in the Laurikari paper, which is a difficult read. Does anyone know of an accessible writeup of these techniques? Interestingly neither re2 nor Rust regex perform capturing in DFAs. Rather, a DFA is used to locate the end of a match, the DFA is used again to determine the beginning of the match, and then an NDFA is used to match a third time, to extract the capture groups.

burntsushi 4y ago
The "Papers" section on re2c's web site continues Laurikari's work: http://re2c.org/ http://re2c.org/ ... but I haven't found them particularly accessible. And it's not clear it's a viable strategy in a general purpose regex engine. Namely, I'm not sure how much bigger it makes the DFA. Also, AFAIK, these aren't DFAs. They are different theoretical structures with explicitly more power. > and then an NDFA is used to match a third time, to extract the capture groups. That's the PikeVM. It's an NFA simulation. Although it uses additional storage and is otherwise more computationally powerful than just a plain NFA.
- ridiculous_fish 4y ago
  Thanks! I hadn't encountered that top paper "A closer look at TDFA." That paper claims to be "the first practical submatch extraction and parsing algorithm based on DFA" and it came out only last year! It shows how new this theory is.
yarg 4y ago
I don't know about sound theory, but pulling something out of bullshit: Firstly, the nice part about DFAs is that they're really simple to implement - in terms of capture groups bare in mind that the generation mechanism means that the nodes are probably super-positions, and the extracts across aspects of your language can intersect if you're not careful. You can get into messy places really quickly - so I'd suggest not fucking with the machine directly. However, there's one thing that you can do without compromising machine generation: add a processing mode that returns the trace of machine states for the matching string. And then process that state trace. Now bare in mind that some of the states that you went through might have been super-positions, so you don't quite know what they are. But (now that you have a match) you can run the reverse of the match through the reverse of the network and intersect the reverse of its trace. (I haven't actually done that, but it will clean up some trace ambiguity - where earlier branches were only later found not to have been taken.)

burntsushi 4y ago

The "Papers" section on re2c's web site continues Laurikari's work: http://re2c.org/ http://re2c.org/ ... but I haven't found them particularly accessible. And it's not clear it's a viable strategy in a general purpose regex engine. Namely, I'm not sure how much bigger it makes the DFA. Also, AFAIK, these aren't DFAs. They are different theoretical structures with explicitly more power. > and then an NDFA is used to match a third time, to extract the capture groups. That's the PikeVM. It's an NFA simulation. Although it uses additional storage and is otherwise more computationally powerful than just a plain NFA.

ridiculous_fish 4y ago
Thanks! I hadn't encountered that top paper "A closer look at TDFA." That paper claims to be "the first practical submatch extraction and parsing algorithm based on DFA" and it came out only last year! It shows how new this theory is.

yarg 4y ago

I don't know about sound theory, but pulling something out of bullshit: Firstly, the nice part about DFAs is that they're really simple to implement - in terms of capture groups bare in mind that the generation mechanism means that the nodes are probably super-positions, and the extracts across aspects of your language can intersect if you're not careful. You can get into messy places really quickly - so I'd suggest not fucking with the machine directly. However, there's one thing that you can do without compromising machine generation: add a processing mode that returns the trace of machine states for the matching string. And then process that state trace. Now bare in mind that some of the states that you went through might have been super-positions, so you don't quite know what they are. But (now that you have a match) you can run the reverse of the match through the reverse of the network and intersect the reverse of its trace. (I haven't actually done that, but it will clean up some trace ambiguity - where earlier branches were only later found not to have been taken.)