From: Hans Fugal <fugalh@...>
Date: 2007-05-25T23:25:09+09:00
Subject: Re: Partial Regular Expression Matching

Rick DeNatale wrote:
> On 5/22/07, Hans Fugal <fugalh@zianet.com> wrote:
> 
>> Well that works for \w+ an \s+, but what if you want to match /01+0/?
>> You'd get a syntax error on 0111 even though it's a valid partial match.
> 
> Han's I'm not sure I understand your use case. Perhaps you could
> provide some code as you would write it IF Ruby provided a
> match_partial method for Regexp.

It's a thought excercise. I've been fiddling with parser generators, and 
had an idea for a simple recursive-descent parser that includes the 
lexer by defining terminals as regexes. Example:


     # productions
     expr: term              {. expr0  = term  .}
         (   '+'  term       {. expr0 += term3 .}
           | '-'  term       {. expr0 -= term4 .}
         )*
         ;

     term: fact              {. term0  = fact1 .}
         (   '*' fact        {. term0 *= fact2 .}
           | '/' fact        {. term0 /= fact3 .}
         )*
         ;

     fact: ['+'] const       {. fact0 =  const1.to_f .}
         |  '-'  const       {. fact0 = -const2.to_f .}
         |  '(' expr ')'     {. fact0 =  expr1 .}
         ;

     # terminals
     const: /\d+[\.\d+]/ = '0';

Whether a parser generator or a generic lexer, in order to do the lexing 
generically from a set of regexes, you need to be able to say "doesn't 
match" in order to catch syntax errors in a timely manner. It's easy 
enough if you have all of the input, or "a lot" which is reasonably 
expected to be longer than any token, or if you can count on tokens not 
crossing a guard (such as a newline), but in general you need to do 
partial matching.

So the code might look like:

r = /\A#{terminals.inject {|u,r| Regexp.union(u,r)}}/
until input.eof?
   if r =~ input
     # figure out which token and consume/return it
   elsif r.partial_match(input)
     # wait for more input
   end
end

That may not be the most efficient way, but it gives a good idea.

The problem is also applicable for input verification, i.e. in a field 
on a form, as has been mentioned.