Template regexes, version 2

[David Medlock]

pragma wrote:
> Don, I love this rendition.
> 
> In article <dtjv60$1tc9$1 at digitaldaemon.com>, Don Clugston says...
> 
>>I should mention that the code I posted doesn't do real regexps, because 
>>it has no backtracking. It doesn't do *, +, ? properly, they are always 
>>greedy. It can never match ".*a", for example.
>>I was too focused on getting access to variables.
> 
> 
> I'm scratching my head as to how to fix the greedy-matching problem.  (my
> apologies if you've already mulled this over)
> <snip> 
> Hehe.. so the optimal solution is also the most complete? ;)
> 
> - Eric Anderton at yahoo


One option is something like the following:
(Assuming Regex is a linked list of atomic regular expressions, and it 
knows if it is nullable)

bool match( string txt, Regex reg, bool delegate() backtrack )
{
   string tail ;
   // attempt to match the regex against the text
   bool success = reg.match( txt, tail );

   // this function skips the current regex and tries the txt on the 
successor
   bool inner_skip()
   {
     bool result = match( txt, reg.next, backtrack );
     if ( result==false ) return backtrack();
     else return result;
   }

   if ( success )
   {
     if ( reg.nullable ) return match( tail, reg.next, &inner_skip );
     else return match( tail, reg.next, backtrack );
   }
   else return ( backtrack is null ? false : backtrack() );
}

//call with :

match( text, regex, null )

A nice addition would be a callback delegate for matches.

-DavidM