regexp.cpp

一个类似STL的自动机的源代码库

#include <astl.h>
#include <regexp.h>
#include <stream.h>
#include <ccopy.h>
#include <string>
#include <iostream>
#include <tools.h>
#include <match.h>
#include <ctime>
#include <set_operation.h>

#define TEMPLATE_TEMPLATE_IMPLEMENTATION
#include <lazy.h>

using namespace std;
#if !defined(__GNUG__) || __GNUG__ >= 3
using namespace rel_ops;
#endif

const string USAGE = "[-v] [-c] [-nl] [-g] [-dfa] expression file";

void usage(const char* exe)
{
  cerr << "Usage: " << exe << " " << USAGE << endl;
  cerr << "       -v\tverbose mode" << endl;
  cerr << "       -c\tmatch count" << endl;
  cerr << "       -nl\tno lazy-construction optimization" << endl;
  cerr << "       -g\tgrep style (line mode)" << endl;
  cerr << "       -dfa\tdump dfa" << endl;
  exit(1);
}

int main(int argc, char** argv)
{
  if (argc < 3 || argc > 6) usage(argv[0]);
  bool verbose = false, no_lazy = false;
  bool grep = false, dump_dfa = false;
  bool match_count = false;
  string tag = "";
  int i;
  int c = argc; 

  for(i = 1; c > 3; --c, ++i)
    if (string("-v") == argv[i]) verbose = true;
    else
      if (string("-nl") == argv[i]) no_lazy = true;
      else
	if (string("-g") == argv[i]) grep = true;
	else
	  if (string("-dfa") == argv[i]) dump_dfa = true;
	  else
	    if (string("-c") == argv[i]) match_count = true;
	    else
	      usage(argv[0]);
    
  if (verbose) {
    char buffer[1024];
    FILE *f = popen("date", "r");
    buffer[max((int) fread(buffer, sizeof(char), 1023, f) - 1, 0)] = '\0';
    pclose(f);
    cerr << buffer << " \"";
    copy(argv, argv + argc, ostream_iterator<char*>(cerr, " "));
    cerr << "\"" << endl;
  }

  FILE *f = fopen(argv[i + 1], "rb");
  if (f == NULL) {
    string msg = string(argv[0]) + ": " + argv[i + 1];
    perror(msg.c_str());
    exit(2);
  }
  frandom_iterator<> first(f), last, input;
  ostream_iterator<char> out(cout);

  if (no_lazy) {
    regexp_cursor rc(argv[i], false, verbose);
    if (rc.errpos != -1) {
      cerr << argv[0] << ": error in expression at char " << rc.errpos << endl;
      cerr << argv[i] << endl;
      for(int k = 0; k++ < rc.errpos; cerr << " ");
      cerr << "^" << endl;
      exit(3);
    }
    regexp_cursor::state_type initial = rc.src();
    int count = 0;

    while (first != last) {
      input = first_match(first, last, rc);
      if (input == first) ++input;
      else
      if (match_count) ++count;
      else {
	cout << tag;
	copy(first, input, out);
	cout << tag << endl;
      }
      first = input;
      rc = initial;
    }

    if (match_count)
      cout << count << endl;
  }
  else
    if (grep) {
      regexp_cursor rg(argv[i], true, verbose);   // KMP FA recognizing Sigma*expression
      lazy_cursor<regexp_cursor> rc(rg);
      lazy_cursor<regexp_cursor>::state_type initial = rc.src();
      int count = 0;

      for(input = first; first != last; )
	if (*first == '\n') { 
	  input = ++first;
	  rc = initial;
	}
	else {
	  rc.forward(*first);
	  if (rc.src_final())
	    if (match_count) ++count;
	    else {
	      copy(input, ++first, out);
	      for(; first != last; ++first)
		if (*first == '\n') {
		  cout << endl;
		  input = ++first;
		  rc = initial;
		  break;
		}
		else cout << *first;
	    }
	  else ++first;
	}

      if (match_count)
	cout << count << endl;

      if (dump_dfa) {
	DFA_stream out(cerr);
	clone(out, dfirst_markc(rc.cache()));
      }

      if (verbose) 
	cerr << "DFA has " << rc.cache().state_count() << " states and " 
	     << rc.cache().trans_count() << " transitions" << endl;
    }
    else
    {
      regexp_cursor rg(argv[i], false, verbose);
      lazy_cursor<regexp_cursor> rc(rg);
      lazy_cursor<regexp_cursor>::state_type initial = rc.src();
      int count = 0;

      while (first != last) {
	input = longest_match(first, last, rc);
	if (input == first) ++input;
	else
	  if (match_count) ++count;
	  else {
	    cout << tag;
	    copy(first, input, out);
	    cout << tag << endl;
	  }
	first = input;
	rc = initial;
      }
      //       while (first != last) {
      // 	input = first;
      // 	for(rc = initial; input != last && rc.forward(*input)
      
      //       for(; first != last;) {
      // 	match_length = 0;
      // 	input = first;
      // 	for(rc = initial; input != last && rc.forward(*input); ) {
      // 	  ++input;
      // 	  if (rc.src_final()) match_length = input - first;
      // 	}
      
// 	if (match_length > 0) {
// 	  for(input -= match_length; match_length > 0; ++input, --match_length)
// 	    cout << *input;
// 	  cout << endl;
// 	  first = input;
// 	}
// 	else ++first;
//       }

      if (match_count)
	cout << count << endl;

      if (dump_dfa) {
	DFA_stream out(cerr);
	clone(out, dfirst_markc(rc.cache()));
      }

      if (verbose) 
	cerr << "DFA has " << rc.cache().state_count() << " states and " 
	     << rc.cache().trans_count() << " transitions" << endl;
    }
      
  if (verbose)
    cerr << argv[0] << ": " << clock() / (double) CLOCKS_PER_SEC << " s CPU time" << endl;

  fclose(f);
  exit(0);
}