4 ms·
> operator in regex. regex is not regular expressions - if using NFA to match then you're matching all alternates simultaneously. Russ Cox has good pictures e
by bear8642 5y ago
> operator in regex.
regex is not regular expressions - if using NFA to match then you're matching all alternates simultaneously.
Russ Cox has good pictures explaining idea in 'Regular Expression Search Algorithms' section of <https://swtch.com/~rsc/regexp/regexp1.html https://swtch.com/~rsc/regexp/regexp1.html>
- recursive 5y agoI'm talking about regex. Regex libraries in practical use do not use NFA. I'm talking about actual code that's written using normal languages. I'm familiar with the difference between "regular expressions" as in "regular languages".
- deleted 5y ago[deleted]
- burntsushi 5y agoGo's regexp package, Rust's regex crate and RE2 are examples of regex engines that are very much in practical use that use NFAs (among other things).
- ivegotnoaccount 5y agoLex/Flex, wich I think we can agree is used by "actual code that's written using normal languages" use DFAs, both inside rules and between rules, and they do not try '|' cases left to right (They probably could have if they wanted since there is a REJECT action that already force them to store the list of all the rules/texts that were matched): a|ab {cout << "matched ab" << std::endl; } b { cout << "matched b" << std::endl; } if provided with "ab", will match the first rule with "ab", and not the first with "a" then the second with "b".
- burntsushi 5y agoAll POSIX compatible regex engines do the same. It's somewhat linked to why POSIX regexes don't have non-greedy operators. But DFAs can implement the preference-order semantics found in backtracking regex engines too. Russ Cox's articles show how to do that. (Just adding some additional info to your point.)