Post #2493639
2023-02-14 19:06 UTC
Converting a regular expression to a DFA is standard CS material. Does the theory expand to handle capture groups? (Not including back references)
Replies (2)
-
@pervognsen@mastodon.social 2023-02-14 20:38
@stoklund@oldbytes.space The left factorization that's inherent to determinization doesn't play well with capture groups. AFAIK, everyone switches to a non-DFA method once a match has been confirmed and the match boundaries found, e.g. https://swtch.com/~rsc/regexp/regexp2.html
-
@zwarich@hachyderm.io 2023-02-14 23:16
@stoklund@oldbytes.space Laurikari's master's thesis is the classic work on the subject: https://laurikari.net/ville/regex-submatch.pdf You can find more references by looking for citations of the paper version of Laurikari's work.