I suggest using the term "regular language" in contrast to "regex" or "regular expression".
https://news.ycombinator.com/item?id=23598078
"Regular language" is an accurate mathematical term that's not "corrupted" by programming. I think you could also use "automata-based" but it's probably less clear and refers more to the implementation [1]
If you scroll down about 3 pages here, there is table explaining regexes vs. regular languages:
https://www.oilshell.org/share/05-31-pres.html
It's the same stuff that's in RSC's articles but those are too dense for a general programming audience (they're more for regex engine implementers). And the existence of the OP's article shows that people haven't gotten it :)
You could also use the terms:
- regex engine (Perl/Python/PCRE/Java/etc.)
- regular language engine (libc, RE2, rust/regex)
Or "hybrid engine" may be more accurate for some of those. That is, they may use either automata-based techniques or backtracking depending on the situation.
-----
BTW, the Oil shell has a new syntax Eggex for both regular languages and regexes that makes the difference clear. In other words, you should be able to see from the syntax if a construct may cause exponential backtracking.
https://www.oilshell.org/release/0.8.pre6/doc/eggex.html
In other words, it's a static property that's easily detected (if you have a parser for the regex language itself, which is not hard at all in theory, but maybe it is a little in practice :) )
-----
[1] Aside: The terms NFA and DFA were also corrupted by Friedl in a popular O'Reilly book. I have this book and remember being super confused by it, since I read it long after I learned what a DFA and NFA were.
https://swtch.com/~rsc/regexp/regexp1.html
What little text it devotes to implementation issues perpetuates the widespread belief that recursive backtracking is the only way to simulate an NFA. Friedl makes it clear that he neither understands nor respects the underlying theory.
http://regex.info/blog/2006-09-15/248
https://news.ycombinator.com/item?id=23598078
"Regular language" is an accurate mathematical term that's not "corrupted" by programming. I think you could also use "automata-based" but it's probably less clear and refers more to the implementation [1]
If you scroll down about 3 pages here, there is table explaining regexes vs. regular languages:
https://www.oilshell.org/share/05-31-pres.html
It's the same stuff that's in RSC's articles but those are too dense for a general programming audience (they're more for regex engine implementers). And the existence of the OP's article shows that people haven't gotten it :)
You could also use the terms:
- regex engine (Perl/Python/PCRE/Java/etc.)
- regular language engine (libc, RE2, rust/regex)
Or "hybrid engine" may be more accurate for some of those. That is, they may use either automata-based techniques or backtracking depending on the situation.
-----
BTW, the Oil shell has a new syntax Eggex for both regular languages and regexes that makes the difference clear. In other words, you should be able to see from the syntax if a construct may cause exponential backtracking.
https://www.oilshell.org/release/0.8.pre6/doc/eggex.html
In other words, it's a static property that's easily detected (if you have a parser for the regex language itself, which is not hard at all in theory, but maybe it is a little in practice :) )
-----
[1] Aside: The terms NFA and DFA were also corrupted by Friedl in a popular O'Reilly book. I have this book and remember being super confused by it, since I read it long after I learned what a DFA and NFA were.
https://swtch.com/~rsc/regexp/regexp1.html
What little text it devotes to implementation issues perpetuates the widespread belief that recursive backtracking is the only way to simulate an NFA. Friedl makes it clear that he neither understands nor respects the underlying theory.
http://regex.info/blog/2006-09-15/248