A lexer returns tokens, and tokens are rather simple. So simple that parsing them requires no backtracking. This makes it very easy to not use regexps.

But it also your task possible (but not simple) with regexps too. Take Perl single-quoted strings:

sub squote {
   my $s_pos = pos;

   my $match = /
      \G
      '       
      (?>
         (?:
            \\.
         |
            [^\\']
         )*
      )
      '
   /xsgc;

   my $e_pos = pos;

   if ($match) {
      $_[0] = substr($_, $s_pos, $e_pos-$s_pos);
      return 1;
   } else {
      pos = $s_pos;
      return 0;
   }
}
[download]

sub squote {
   my $s_pos = pos;

   RETRY: {
      local our $at_eof = ...;
      local our $need_more = 0;
      my $match = /
         \G
         (?: \z (?{ $need_more = !$at_eof }) )? '
         (?>
            (?:
               \\
               (?: \z (?{ $need_more = !$at_eof }) )? .
            |
               [^\\']
            )*
         )
         (?: \z (?{ $need_more = !$at_eof }) )? '
      /xsgc;

      if ($need_more) {
         ...
         pos = $s_pos;
         redo RETRY;
      }

      my $e_pos = pos;

      if ($match) {
         $_[0] = substr($_, $s_pos, $e_pos-$s_pos);
         return 1;
      } else {
         pos = $s_pos;
         return 0;
      }
   }
}
[download]

By the way, you asked
"How can I tell if a regular expression is matching but fails merely because it ran out of data?"
but you should also be asking
"How can I tell if a regular expression succeeded merely because it ran out of data?"

Take an identifier, for example. If $_ contains 'abc', it'll return a match, but it'll return the wrong match if the next character is 'd'.

sub ident {
   my $s_pos = pos;

   my $match = /
      \G
      [a-zA-Z_]
      [a-zA-Z0-9_]*
   /xsgc;

   my $e_pos = pos;

   if ($match) {
      $_[0] = substr($_, $s_pos, $e_pos-$s_pos);
      return 1;
   } else {
      pos = $s_pos;
      return 0;
   }
}
[download]

becomes

sub ident {
   my $s_pos = pos;

   RETRY: {
      local our $at_eof = ...;
      local our $need_more = 0;
      my $match = /
         \G
         (?: \z (?{ $need_more = !$at_eof }) )? [a-zA-Z_]
         (?> [a-zA-Z0-9_]* )
         (?: (?= . ) | (?{ $need_more = !$at_eof }) )
      /xsgc;

      if ($need_more) {
         ...
         pos = $s_pos;
         redo RETRY;
      }

      my $e_pos = pos;

      if ($match) {
         $_[0] = substr($_, $s_pos, $e_pos-$s_pos);
         return 1;
      } else {
         pos = $s_pos;
         return 0;
      }
   }
}
[download]

Update: Simple optimization.

See File::Stream for an implementation of the idea.

You may want to look at Matching in huge files, which uses a sliding window technique to match in large files.

A sliding window is useless, since a lexer needs to match at the end of the last found token. However, the linked snippet could be modified to *expand* it's window instead of sliding it.

I look at that and do not see that it differentiates between regex failure modes. That is, I think I see in the code that if a regex fails, it simply gets more data for the window and trys again. I would only want this to happen if the regex failed only by reaching the end of the window. Otherwise, a lexer should try a different token pattern to match.

Or am I missing something?

The first thing that comes to mind is to have a bunch of optional captures.

while (1) {
   $foo .= <HANDLE>
   $foo =~ /(bar(baz(buz)?)?)/;

   print "bar found\n" if defined $1;
   print "baz found\n" if defined $2;
   print "buz found\n" if defined $3;

   last if defined $3;
}
[download]

Of course this could get really ugly if you have big, complex regexes to work with. I'm willing to bet that there are other caveats as well, but I'm not sure what they might be.

Cheers,

JohnGG