Re: [Gnu-arch-users] Preventing matches in regular expressions

[Tom Lord]

    > From: Jan Hudec <address@hidden>

    > Lookahead/lookback assertions are perfectly regular. 

For the most part, yes.

    > They definitely can be expressed as a NFA. And negative
    > lookahead assertion is all you need.

Hence as a dfa, yes.

There's the rub.

In an NFA, you can express boolean regexp logic in a very compact
amount of space, but at the cost of backtracking (or parallel
execution).  In a DFA (or quasi-DFA, like Rx), you get boolean logic
at the cost of a lot of space.

Historically, the tagging method regexps use a very limited form of
boolean logic.  Fortunately, they use a kind that can be optimized by
`cut'.  The reason they use boolean logic historically is because
`inventory' was originally a call to `find(1)' (and I was assuming GNU
find); that was the easy way to write it.  The reason `inventory'
happens to be optimizable using cut is, alas, shear luck: I wasn't
thinking about that at the time; in fact, I was underestimating the
importance of the performance of `inventory' for overall arch
performance.

What I've learned is that `inventory' performance is crtiical.  I have
seriously considered, from time to time, arranging to have
=tagging-method piped through `lex(1)' or something similar!   Thus,
fully general boolean regexp logic is not likely to be supported, at
least until you and I are close to or past retirement.

-t