[COFF] Re: Requesting thoughts on extended regular expressions in grep.

On Thu, Mar 2, 2023 at 1:55 PM Grant Taylor via COFF <coff(a)tuhs.org> wrote: Well, obviously the former matches any sequence 3 of alpha-numerics/underscores at the beginning of a string, while the latter only matches abbreviations of months in the western calendar; that is, the two REs are matching very different things (the latter is a strict subset of the former). But I suspect you mean in a more general sense. ...do you really want to match a space, a colon and a single digit 11 times in a single string? Using character classes would greatly simplify what you're trying to do. It seems like this could be simplified to (untested) snippet: ( [1-9]|[12][[0-9]]|3[01]) [0-2][0-9]:[0-5][0-9]:[0-5][0-9] For this, I'd probably eschew `[:digit:]`. Named character classes are for handy locale support, or in lieu of typing every character in the alphabet (though we can use ranges to abbreviate that), but it kind of seems like that's not coming into play here and, IMHO, `[0-9]` is clearer in context. It's not clear to me that dates, in their generality, can be matched with regular expressions. Consider leap years; you'd almost necessarily have to use backtracking for that, but I admit I haven't thought it through. `\w` is a GNU extension; I'd probably avoid it on portability grounds (though `\b` is very handy). The thing about regular expressions is that they describe regular languages, and regular languages are those for which there exists a finite automaton that can recognize the language. An important class of finite automata are deterministic finite automata; by definition, recognition by such automata are linear in the length of the input. However, construction of a DFA for any given regular expression can be superlinear (in fact, it can be exponential) so practically speaking, we usually construct non-deterministic finite automata (NDFAs) and "simulate" their execution for matching. NDFAs generalize DFAs (DFAs are a subset of NDFAs, incidentally) in that, in any non-terminal state, there can be multiple subsequent states that the machine can transition to given an input symbol. When executed, for any state, the simulator will transition to every permissible subsequent state simultaneously, discarding impossible states as they become evident. This implies that NDFA execution is superlinear, but it is bounded, and is O(n*m*e), where n is the length of the input, m is the number of nodes in the state transition graph corresponding to the NDFA, and e is the maximum number of edges leaving any node in that graph (for a fully connected graph, that would m, so this can be up to O(n*m^2)). Construction of an NDFA is O(m), so while it's slower to execute, it's actually possible to construct in a reasonable amount of time. Russ's excellent series of articles that Clem linked to gives details and algorithms. In practical terms? Basically, don't worry about it too much. Egrep will generate an NDFA simulation that's going to be acceptably fast for all but the weirdest cases. - Dan C.