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

Oh, for sure; to be clear, it was obvious that in the earlier discussion the original was just part of something larger.

FWIW, this RE seems ok to me; the additional context makes it unlikely to match something else accidentally.

It needn't be special. The point is simply that there's some external knowledge that can be brought to bear to guide the shape of the REs.

In this case, you know that log lines won't begin with `___ 123 456:789` or other similar junk.

Kinda. The "machine" in this case is actually an abstraction, like a Turing machine. The salient point here is that REs map to finite state machines, and in particular, one need not keep (say) a stack of prior states when simulating them. Note that even in an NDFA simulation, where one keeps track of what states one may be in, one doesn't need to keep track of how one got into those states.

Obviously in a real implementation you've got the program counter, register contents, local variables, etc, all of which consume "memory" in the conventional sense. But the point is that you don't need additional memory proportional to anything other than the size of the RE. DFA implementation could be implemented entirely with `switch` and `goto` if one wanted, as opposed to a bunch of mutually recursive function calls, NDFA simulation similarly except that you need some (bounded) additional memory to hold the active set of states. Contrast this with a pushdown automata, which can parse a context-free language, in which a stack is maintained that can store additional information relative to the input (for example, an already seen character). Pushdown automata can, for example, recognize matched parenthesis while regular languages cannot.

Anyway, sorry, this is all rather more theoretical than is perhaps interesting or useful.

Bottom line is, I think your REs are probably fine. `egrep` will complain at you if they are not, and I wouldn't worry too much about optimizing them: I'd "stop" whenever you're happy that you've got something understandable that matches what you want it to match.