Hacker News Reader

Comment by bear8642 | Hacker News Reader

> 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>

View on HN

I'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".

Go'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).

Lex/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".

All 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.)

Reply on news.ycombinator.com