[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Tom Lord
Subject: Re: [Gnu-arch-users] Preventing matches in regular expressions
Date: Wed, 11 Aug 2004 01:13:30 -0700 (PDT)

    > 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

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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]