Re: Regular expression search algorithm

"Peter S Tillier" <peter.tillier@btinternet.com>
24 Jul 2002 02:24:20 -0400

          From comp.compilers

Related articles
Regular expression search algorithm harvinder.singh@patni.com (Harry) (2002-07-15)
Re: Regular expression search algorithm joachim_d@gmx.de (Joachim Durchholz) (2002-07-21)
Re: Regular expression search algorithm ralph@inputplus.co.uk (Ralph Corderoy) (2002-07-21)
Re: Regular expression search algorithm peter.tillier@btinternet.com (Peter S Tillier) (2002-07-24)
Re: Regular expression search algorithm arnold@skeeve.com (Aharon Robbins) (2002-09-03)
regular expression search algorithm forsyth@minster.york.ac.uk (1993-03-18)
Re: regular expression search algorithm pardo@cs.washington.edu (1993-03-19)
| List of all articles for this month |

From: "Peter S Tillier" <peter.tillier@btinternet.com>
Newsgroups: comp.compilers
Date: 24 Jul 2002 02:24:20 -0400
Organization: Compilers Central
References: 02-07-036 02-07-069
Keywords: lex
Posted-Date: 24 Jul 2002 02:24:20 EDT

"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?"


Post a followup to this message

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