Hacker News Reader

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

View on HN

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

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

Reply on news.ycombinator.com