Re: Regular expressions speedup

Tony Finch <dot@dotat.at>
10 Aug 2005 11:53:24 -0400

          From comp.compilers
Related articles
Regular expressions speedup cleos@nb.sympatico-dot-ca.remove (Cleo Saulnier) (2005-08-05)
Re: Regular expressions speedup haberg@math.su.se (2005-08-07)
Re: Regular expressions speedup cleos@nb.sympatico.ca (Cleo Saulnier) (2005-08-07)
Re: Regular expressions speedup haberg@math.su.se (2005-08-10)
Re: Regular expressions speedup bonzini@gnu.org (Paolo Bonzini) (2005-08-10)
Re: Regular expressions speedup dot@dotat.at (Tony Finch) (2005-08-10)
Re: Regular expressions speedup kszabo@bcml120x.ca.nortel.com (2005-08-10)
Re: Regular expressions speedup jburgy@gmail.com (2005-08-10)
Re: Regular expressions speedup torbenm@diku.dk (2005-08-13)
Re: Regular expressions speedup cleos@nb.sympatico-dot-ca.remove (Cleo Saulnier) (2005-08-13)
| List of all articles for this month |
From: Tony Finch <dot@dotat.at>
Newsgroups: comp.compilers
Date: 10 Aug 2005 11:53:24 -0400
Organization: dotat labs
References: 05-08-023 05-08-029
Keywords: lex, DFA
Posted-Date: 10 Aug 2005 11:53:24 EDT

Cleo Saulnier <cleos@nb.sympatico.ca> wrote:
>
>> [If you really care about speed, why not turn the NFA into a DFA so
>> you don't have to do multiple states and backtracking? -John]
>
>Well, I've looked at DFA and it's great if you don't have
>backreferences.


The way Gnu Grep handles this problem is by using a DFA to find
matches, then post-processing them to check for the consistency
of backrefs.


Tony.
--
f.a.n.finch <dot@dotat.at> http://dotat.at/
ARDNAMURCHAN POINT TO CAPE WRATH INCLUDING THE OUTER HEBRIDES: VARIABLE
BECOMING SOUTH OR SOUTHWEST 3 OR 4. DRIZZLE AT TIMES. MODERATE OR GOOD,
OCCASIONALLY POOR LATER. SLIGHT OR MODERATE.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.