Re: Regular expression search algorithm

"Joachim Durchholz" <joachim_d@gmx.de> wrote in message
> Harry wrote:
> >
> > 1. I have read the boyer moore algo in the intro to algo by
> > corman, rivest, leiserson.... however they taked about only
> > the simple patterns ...
> > How to acomodate the regular expression in the pattern ?
>
> Regex searches work very differently than Boyer-Moore. The effect that
> makes the Boyer-Moore algorithm fast is implicitly part of the regex
> algorithms though.
>
> Regex searching is usually done by compiling the regex into a
> deterministic finite automaton, then feeding the input to the regex.


This is not correct. Many regex search algorithms are implemented
using NFAs rather than DFAs. For example perl, sed, grep and others
use NFAs so that back references are readily available. awk, egrep
and others usually use DFAs, which tend to be slower to compile and
faster to execute than NFAs, but don't support back references. gawk
uses both - DFA most of the time, but NFA when back references are
needed.


[...]


HTH
--
Peter S Tillier
"Who needs perl when you can write dc and sokoban in sed?"

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