Mercurial > hg > Members > shinya > pyrect

changeset 91:19a88707bd29

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add cbc code.
author Ryoma SHINYA <shinya@firefly.cr.ie.u-ryukyu.ac.jp>
date Fri, 03 Dec 2010 18:36:23 +0900
parents 8cfa81638130
children 87cd1db7ec3f
files code/c/jitgrep_dfa.c code/cbc/jitgrep_dfa.cbc.c pyrect/regexp/fa.py pyrect/regexp/nfa.py
diffstat 4 files changed, 797 insertions(+), 1 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/code/c/jitgrep_dfa.c	Fri Dec 03 18:36:23 2010 +0900
@@ -0,0 +1,379 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/mman.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <string.h>
+
+typedef unsigned char   UCHAR;
+typedef unsigned char *UCHARP;
+
+void reject(UCHARP beg, UCHARP buf, UCHARP end);
+void matcher(UCHARP beg, UCHARP buf, UCHARP end);
+void accept(UCHARP beg, UCHARP buf, UCHARP end);
+
+void state_11(UCHARP beg, UCHARP buf, UCHARP end);
+void state_10(UCHARP beg, UCHARP buf, UCHARP end);
+void state_12(UCHARP beg, UCHARP buf, UCHARP end);
+void state_1(UCHARP beg, UCHARP buf, UCHARP end);
+void state_0(UCHARP beg, UCHARP buf, UCHARP end);
+void state_3(UCHARP beg, UCHARP buf, UCHARP end);
+void state_2(UCHARP beg, UCHARP buf, UCHARP end);
+void state_5(UCHARP beg, UCHARP buf, UCHARP end);
+void state_4(UCHARP beg, UCHARP buf, UCHARP end);
+void state_7(UCHARP beg, UCHARP buf, UCHARP end);
+void state_6(UCHARP beg, UCHARP buf, UCHARP end);
+void state_9(UCHARP beg, UCHARP buf, UCHARP end);
+void state_8(UCHARP beg, UCHARP buf, UCHARP end);
+
+void booster(UCHARP beg, UCHARP buf, UCHARP end) {
+  UCHARP end_ = end - 2;
+  if (buf > end_) return;
+  do {
+    switch (buf[2]) {
+      case 98: /* 'b' */
+      case 99: /* 'c' */
+      case 100: /* 'd' */
+      case 101: /* 'e' */
+      case 102: /* 'f' */
+      case 103: /* 'g' */
+      case 105: /* 'i' */
+      case 108: /* 'l' */
+      case 110: /* 'n' */
+      case 117: /* 'u' */
+      goto ret;
+      }
+    } while((buf += 3) <= end_);
+  ret: return state_4(beg, buf, end);
+  }
+
+UCHARP get_line_beg(UCHARP p, UCHARP beg) {
+  while(p > beg) {
+    if ((*--p) == '\n') return p+1;
+  }
+  return beg;
+}
+
+void print_line(UCHARP beg, UCHARP end) {
+  fwrite(beg, sizeof(char), (end - beg + 1), stdout);
+}
+
+void grep(char *regexp, int fd, char *name) {
+  caddr_t file_mmap;
+  UCHARP buf, end, beg;
+  off_t size;
+  struct stat sb;
+
+  if (fstat(fd, &sb)) {
+    fprintf(stderr, "can't fstat %s\n", name);
+    exit(0);
+  }
+
+  size = sb.st_size;
+  file_mmap = mmap(NULL, size, PROT_READ, MAP_SHARED, fd, (off_t)0);
+
+  if (file_mmap == (caddr_t)-1) {
+    fprintf(stderr, "can't mmap %s\n", name);
+    exit(0);
+  }
+
+  beg = buf = (UCHARP) file_mmap;
+  end = beg + size - 1;
+
+  matcher(beg, beg, end);
+
+  munmap(file_mmap, size);
+  return;
+}
+
+int main(int argc, char* argv[]) {
+  int i, fd;
+
+  if (argc < 2) {
+    fprintf(stderr, "usage: grep regexp [file ...]");
+    exit(0);
+  }
+  if (argc == 2) {
+    return 0;
+  } else {
+    for (i = 2; i < argc; i++) {
+      fd = open(argv[i], O_RDONLY, 0666);
+      if (fd == 0) {
+        fprintf(stderr, "can't open %s:", argv[i]);
+        continue;
+      }
+      grep(argv[1], fd, argc > 3 ? argv[i] : NULL);
+      close(fd);
+    }
+  }
+
+  return 0;
+}
+
+void matcher(UCHARP beg, UCHARP buf, UCHARP end) {
+  state_4(beg, buf, end);
+  return;
+  }
+
+void state_11(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      return reject(beg, buf, end);
+    case 98: /* 'b' */
+      return state_12(beg, buf, end);
+    case 100: /* 'd' */
+      return state_7(beg, buf, end);
+    case 102: /* 'f' */
+      return state_10(beg, buf, end);
+    case 103: /* 'g' */
+      return state_1(beg, buf, end);
+    case 10: /* LF */
+      return reject(beg, buf, end);
+    case 13: /* CR */
+      return reject(beg, buf, end);
+    default: return booster(beg, buf, end);
+    }
+  }
+
+void state_10(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      return reject(beg, buf, end);
+    case 98: /* 'b' */
+      return state_12(beg, buf, end);
+    case 102: /* 'f' */
+      return state_10(beg, buf, end);
+    case 103: /* 'g' */
+      return state_1(beg, buf, end);
+    case 10: /* LF */
+      return reject(beg, buf, end);
+    case 13: /* CR */
+      return reject(beg, buf, end);
+    case 110: /* 'n' */
+      return state_11(beg, buf, end);
+    default: return booster(beg, buf, end);
+    }
+  }
+
+void state_12(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      return reject(beg, buf, end);
+    case 98: /* 'b' */
+      return state_12(beg, buf, end);
+    case 102: /* 'f' */
+      return state_10(beg, buf, end);
+    case 103: /* 'g' */
+      return state_1(beg, buf, end);
+    case 10: /* LF */
+      return reject(beg, buf, end);
+    case 13: /* CR */
+      return reject(beg, buf, end);
+    case 117: /* 'u' */
+      return state_5(beg, buf, end);
+    default: return booster(beg, buf, end);
+    }
+  }
+
+void state_1(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      return reject(beg, buf, end);
+    case 98: /* 'b' */
+      return state_12(beg, buf, end);
+    case 99: /* 'c' */
+      return state_8(beg, buf, end);
+    case 102: /* 'f' */
+      return state_10(beg, buf, end);
+    case 103: /* 'g' */
+      return state_1(beg, buf, end);
+    case 10: /* LF */
+      return reject(beg, buf, end);
+    case 13: /* CR */
+      return reject(beg, buf, end);
+    default: return booster(beg, buf, end);
+    }
+  }
+
+void state_0(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      return reject(beg, buf, end);
+    case 98: /* 'b' */
+      return state_12(beg, buf, end);
+    case 100: /* 'd' */
+      return state_3(beg, buf, end);
+    case 102: /* 'f' */
+      return state_10(beg, buf, end);
+    case 103: /* 'g' */
+      return state_1(beg, buf, end);
+    case 10: /* LF */
+      return reject(beg, buf, end);
+    case 13: /* CR */
+      return reject(beg, buf, end);
+    default: return booster(beg, buf, end);
+    }
+  }
+
+void state_3(UCHARP beg, UCHARP buf, UCHARP end) {
+  return accept(beg, buf-1, end);
+  }
+
+void state_2(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      return reject(beg, buf, end);
+    case 98: /* 'b' */
+      return state_12(beg, buf, end);
+    case 102: /* 'f' */
+      return state_10(beg, buf, end);
+    case 103: /* 'g' */
+      return state_1(beg, buf, end);
+    case 10: /* LF */
+      return reject(beg, buf, end);
+    case 108: /* 'l' */
+      return state_3(beg, buf, end);
+    case 13: /* CR */
+      return reject(beg, buf, end);
+    default: return booster(beg, buf, end);
+    }
+  }
+
+void state_5(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      return reject(beg, buf, end);
+    case 98: /* 'b' */
+      return state_12(beg, buf, end);
+    case 102: /* 'f' */
+      return state_10(beg, buf, end);
+    case 103: /* 'g' */
+      return state_1(beg, buf, end);
+    case 105: /* 'i' */
+      return state_6(beg, buf, end);
+    case 10: /* LF */
+      return reject(beg, buf, end);
+    case 13: /* CR */
+      return reject(beg, buf, end);
+    default: return booster(beg, buf, end);
+    }
+  }
+
+void state_4(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      return reject(beg, buf, end);
+    case 98: /* 'b' */
+      return state_12(beg, buf, end);
+    case 102: /* 'f' */
+      return state_10(beg, buf, end);
+    case 103: /* 'g' */
+      return state_1(beg, buf, end);
+    case 10: /* LF */
+      return reject(beg, buf, end);
+    case 13: /* CR */
+      return reject(beg, buf, end);
+    default: return booster(beg, buf, end);
+    }
+  }
+
+void state_7(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      return reject(beg, buf, end);
+    case 98: /* 'b' */
+      return state_12(beg, buf, end);
+    case 101: /* 'e' */
+      return state_9(beg, buf, end);
+    case 102: /* 'f' */
+      return state_10(beg, buf, end);
+    case 103: /* 'g' */
+      return state_1(beg, buf, end);
+    case 10: /* LF */
+      return reject(beg, buf, end);
+    case 13: /* CR */
+      return reject(beg, buf, end);
+    default: return booster(beg, buf, end);
+    }
+  }
+
+void state_6(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      return reject(beg, buf, end);
+    case 98: /* 'b' */
+      return state_12(beg, buf, end);
+    case 102: /* 'f' */
+      return state_10(beg, buf, end);
+    case 103: /* 'g' */
+      return state_1(beg, buf, end);
+    case 10: /* LF */
+      return reject(beg, buf, end);
+    case 108: /* 'l' */
+      return state_0(beg, buf, end);
+    case 13: /* CR */
+      return reject(beg, buf, end);
+    default: return booster(beg, buf, end);
+    }
+  }
+
+void state_9(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      return reject(beg, buf, end);
+    case 98: /* 'b' */
+      return state_12(beg, buf, end);
+    case 99: /* 'c' */
+      return state_2(beg, buf, end);
+    case 102: /* 'f' */
+      return state_10(beg, buf, end);
+    case 103: /* 'g' */
+      return state_1(beg, buf, end);
+    case 10: /* LF */
+      return reject(beg, buf, end);
+    case 13: /* CR */
+      return reject(beg, buf, end);
+    default: return booster(beg, buf, end);
+    }
+  }
+
+void state_8(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      return reject(beg, buf, end);
+    case 98: /* 'b' */
+      return state_12(beg, buf, end);
+    case 99: /* 'c' */
+      return state_3(beg, buf, end);
+    case 102: /* 'f' */
+      return state_10(beg, buf, end);
+    case 103: /* 'g' */
+      return state_1(beg, buf, end);
+    case 10: /* LF */
+      return reject(beg, buf, end);
+    case 13: /* CR */
+      return reject(beg, buf, end);
+    default: return booster(beg, buf, end);
+    }
+  }
+
+void accept(UCHARP beg, UCHARP buf, UCHARP end) {
+  UCHARP ret = (UCHARP)memchr(buf, '\n', (buf - end));
+  beg = get_line_beg(buf, beg);
+  if (ret == NULL) {
+    print_line(beg, end);
+    return;
+    }
+  print_line(beg, ret);
+  beg = buf = ret + 1;
+  matcher(beg, buf, end);
+  }
+
+void reject(UCHARP beg, UCHARP buf, UCHARP end) {
+  if (buf >= end) return;
+  beg = buf;
+  return matcher(beg, buf, end);
+  }
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/code/cbc/jitgrep_dfa.cbc.c	Fri Dec 03 18:36:23 2010 +0900
@@ -0,0 +1,382 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/mman.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <string.h>
+
+typedef unsigned char   UCHAR;
+typedef unsigned char *UCHARP;
+
+__code reject(UCHARP beg, UCHARP buf, UCHARP end);
+void matcher(UCHARP beg, UCHARP buf, UCHARP end);
+__code accept(UCHARP beg, UCHARP buf, UCHARP end);
+
+__code state_11(UCHARP beg, UCHARP buf, UCHARP end);
+__code state_10(UCHARP beg, UCHARP buf, UCHARP end);
+__code state_12(UCHARP beg, UCHARP buf, UCHARP end);
+__code state_1(UCHARP beg, UCHARP buf, UCHARP end);
+__code state_0(UCHARP beg, UCHARP buf, UCHARP end);
+__code state_3(UCHARP beg, UCHARP buf, UCHARP end);
+__code state_2(UCHARP beg, UCHARP buf, UCHARP end);
+__code state_5(UCHARP beg, UCHARP buf, UCHARP end);
+__code state_4(UCHARP beg, UCHARP buf, UCHARP end);
+__code state_7(UCHARP beg, UCHARP buf, UCHARP end);
+__code state_6(UCHARP beg, UCHARP buf, UCHARP end);
+__code state_9(UCHARP beg, UCHARP buf, UCHARP end);
+__code state_8(UCHARP beg, UCHARP buf, UCHARP end);
+
+__code booster(UCHARP beg, UCHARP buf, UCHARP end) {
+  UCHARP end_ = end - 2;
+  if (buf > end_) return;
+  do {
+    switch (buf[2]) {
+      case 98: /* 'b' */
+      case 99: /* 'c' */
+      case 100: /* 'd' */
+      case 101: /* 'e' */
+      case 102: /* 'f' */
+      case 103: /* 'g' */
+      case 105: /* 'i' */
+      case 108: /* 'l' */
+      case 110: /* 'n' */
+      case 117: /* 'u' */
+      goto ret;
+      }
+    } while((buf += 3) <= end_);
+  ret: goto state_4(beg, buf, end);
+}
+
+UCHARP get_line_beg(UCHARP p, UCHARP beg) {
+  while(p > beg) {
+    if ((*--p) == '\n') return p+1;
+  }
+  return beg;
+}
+
+void print_line(UCHARP beg, UCHARP end) {
+  fwrite(beg, sizeof(char), (end - beg + 1), stdout);
+}
+
+void grep(char *regexp, int fd, char *name) {
+  caddr_t file_mmap;
+  UCHARP buf, end, beg;
+  off_t size;
+  struct stat sb;
+
+  if (fstat(fd, &sb)) {
+    fprintf(stderr, "can't fstat %s\n", name);
+    exit(0);
+  }
+
+  size = sb.st_size;
+  file_mmap = mmap(NULL, size, PROT_READ, MAP_SHARED, fd, (off_t)0);
+
+  if (file_mmap == (caddr_t)-1) {
+    fprintf(stderr, "can't mmap %s\n", name);
+    exit(0);
+  }
+
+  beg = buf = (UCHARP) file_mmap;
+  end = beg + size - 1;
+
+  matcher(beg, beg, end);
+
+  munmap(file_mmap, size);
+  return;
+}
+
+int main(int argc, char* argv[]) {
+  int i, fd;
+
+  if (argc < 2) {
+    fprintf(stderr, "usage: grep regexp [file ...]");
+    exit(0);
+  }
+  if (argc == 2) {
+    return 0;
+  } else {
+    for (i = 2; i < argc; i++) {
+      fd = open(argv[i], O_RDONLY, 0666);
+      if (fd == 0) {
+        fprintf(stderr, "can't open %s:", argv[i]);
+        continue;
+      }
+      grep(argv[1], fd, argc > 3 ? argv[i] : NULL);
+      close(fd);
+    }
+  }
+
+  return 0;
+}
+
+void driver(UCHARP beg, UCHARP buf, UCHARP end) {
+  goto state_4(beg, buf, end);
+}
+
+void matcher(UCHARP beg, UCHARP buf, UCHARP end) {
+  return driver(beg, buf, end);
+}
+
+__code state_11(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      goto reject(beg, buf, end);
+    case 98: /* 'b' */
+      goto state_12(beg, buf, end);
+    case 100: /* 'd' */
+      goto state_7(beg, buf, end);
+    case 102: /* 'f' */
+      goto state_10(beg, buf, end);
+    case 103: /* 'g' */
+      goto state_1(beg, buf, end);
+    case 10: /* LF */
+      goto reject(beg, buf, end);
+    case 13: /* CR */
+      goto reject(beg, buf, end);
+    default: goto booster(beg, buf, end);
+    }
+  }
+
+__code state_10(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      goto reject(beg, buf, end);
+    case 98: /* 'b' */
+      goto state_12(beg, buf, end);
+    case 102: /* 'f' */
+      goto state_10(beg, buf, end);
+    case 103: /* 'g' */
+      goto state_1(beg, buf, end);
+    case 10: /* LF */
+      goto reject(beg, buf, end);
+    case 13: /* CR */
+      goto reject(beg, buf, end);
+    case 110: /* 'n' */
+      goto state_11(beg, buf, end);
+    default: goto booster(beg, buf, end);
+    }
+  }
+
+__code state_12(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      goto reject(beg, buf, end);
+    case 98: /* 'b' */
+      goto state_12(beg, buf, end);
+    case 102: /* 'f' */
+      goto state_10(beg, buf, end);
+    case 103: /* 'g' */
+      goto state_1(beg, buf, end);
+    case 10: /* LF */
+      goto reject(beg, buf, end);
+    case 13: /* CR */
+      goto reject(beg, buf, end);
+    case 117: /* 'u' */
+      goto state_5(beg, buf, end);
+    default: goto booster(beg, buf, end);
+    }
+  }
+
+__code state_1(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      goto reject(beg, buf, end);
+    case 98: /* 'b' */
+      goto state_12(beg, buf, end);
+    case 99: /* 'c' */
+      goto state_8(beg, buf, end);
+    case 102: /* 'f' */
+      goto state_10(beg, buf, end);
+    case 103: /* 'g' */
+      goto state_1(beg, buf, end);
+    case 10: /* LF */
+      goto reject(beg, buf, end);
+    case 13: /* CR */
+      goto reject(beg, buf, end);
+    default: goto booster(beg, buf, end);
+    }
+  }
+
+__code state_0(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      goto reject(beg, buf, end);
+    case 98: /* 'b' */
+      goto state_12(beg, buf, end);
+    case 100: /* 'd' */
+      goto state_3(beg, buf, end);
+    case 102: /* 'f' */
+      goto state_10(beg, buf, end);
+    case 103: /* 'g' */
+      goto state_1(beg, buf, end);
+    case 10: /* LF */
+      goto reject(beg, buf, end);
+    case 13: /* CR */
+      goto reject(beg, buf, end);
+    default: goto booster(beg, buf, end);
+    }
+  }
+
+__code state_3(UCHARP beg, UCHARP buf, UCHARP end) {
+  goto accept(beg, buf-1, end);
+  }
+
+__code state_2(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      goto reject(beg, buf, end);
+    case 98: /* 'b' */
+      goto state_12(beg, buf, end);
+    case 102: /* 'f' */
+      goto state_10(beg, buf, end);
+    case 103: /* 'g' */
+      goto state_1(beg, buf, end);
+    case 10: /* LF */
+      goto reject(beg, buf, end);
+    case 108: /* 'l' */
+      goto state_3(beg, buf, end);
+    case 13: /* CR */
+      goto reject(beg, buf, end);
+    default: goto booster(beg, buf, end);
+    }
+  }
+
+__code state_5(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      goto reject(beg, buf, end);
+    case 98: /* 'b' */
+      goto state_12(beg, buf, end);
+    case 102: /* 'f' */
+      goto state_10(beg, buf, end);
+    case 103: /* 'g' */
+      goto state_1(beg, buf, end);
+    case 105: /* 'i' */
+      goto state_6(beg, buf, end);
+    case 10: /* LF */
+      goto reject(beg, buf, end);
+    case 13: /* CR */
+      goto reject(beg, buf, end);
+    default: goto booster(beg, buf, end);
+    }
+  }
+
+__code state_4(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      goto reject(beg, buf, end);
+    case 98: /* 'b' */
+      goto state_12(beg, buf, end);
+    case 102: /* 'f' */
+      goto state_10(beg, buf, end);
+    case 103: /* 'g' */
+      goto state_1(beg, buf, end);
+    case 10: /* LF */
+      goto reject(beg, buf, end);
+    case 13: /* CR */
+      goto reject(beg, buf, end);
+    default: goto booster(beg, buf, end);
+    }
+  }
+
+__code state_7(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      goto reject(beg, buf, end);
+    case 98: /* 'b' */
+      goto state_12(beg, buf, end);
+    case 101: /* 'e' */
+      goto state_9(beg, buf, end);
+    case 102: /* 'f' */
+      goto state_10(beg, buf, end);
+    case 103: /* 'g' */
+      goto state_1(beg, buf, end);
+    case 10: /* LF */
+      goto reject(beg, buf, end);
+    case 13: /* CR */
+      goto reject(beg, buf, end);
+    default: goto booster(beg, buf, end);
+    }
+  }
+
+__code state_6(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      goto reject(beg, buf, end);
+    case 98: /* 'b' */
+      goto state_12(beg, buf, end);
+    case 102: /* 'f' */
+      goto state_10(beg, buf, end);
+    case 103: /* 'g' */
+      goto state_1(beg, buf, end);
+    case 10: /* LF */
+      goto reject(beg, buf, end);
+    case 108: /* 'l' */
+      goto state_0(beg, buf, end);
+    case 13: /* CR */
+      goto reject(beg, buf, end);
+    default: goto booster(beg, buf, end);
+    }
+  }
+
+__code state_9(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      goto reject(beg, buf, end);
+    case 98: /* 'b' */
+      goto state_12(beg, buf, end);
+    case 99: /* 'c' */
+      goto state_2(beg, buf, end);
+    case 102: /* 'f' */
+      goto state_10(beg, buf, end);
+    case 103: /* 'g' */
+      goto state_1(beg, buf, end);
+    case 10: /* LF */
+      goto reject(beg, buf, end);
+    case 13: /* CR */
+      goto reject(beg, buf, end);
+    default: goto booster(beg, buf, end);
+    }
+  }
+
+__code state_8(UCHARP beg, UCHARP buf, UCHARP end) {
+  switch(*buf++) {
+    case 0: /* NUL */
+      goto reject(beg, buf, end);
+    case 98: /* 'b' */
+      goto state_12(beg, buf, end);
+    case 99: /* 'c' */
+      goto state_3(beg, buf, end);
+    case 102: /* 'f' */
+      goto state_10(beg, buf, end);
+    case 103: /* 'g' */
+      goto state_1(beg, buf, end);
+    case 10: /* LF */
+      goto reject(beg, buf, end);
+    case 13: /* CR */
+      goto reject(beg, buf, end);
+    default: goto booster(beg, buf, end);
+    }
+  }
+
+__code accept(UCHARP beg, UCHARP buf, UCHARP end) {
+  UCHARP ret = (UCHARP)memchr(buf, '\n', (buf - end));
+  beg = get_line_beg(buf, beg);
+  if (ret == NULL) {
+    print_line(beg, end);
+    return;
+    }
+  print_line(beg, ret);
+  beg = buf = ret + 1;
+  goto matcher(beg, buf, end);
+  }
+
+__code reject(UCHARP beg, UCHARP buf, UCHARP end) {
+  if (buf >= end) return;
+  beg = buf;
+  goto matcher(beg, buf, end);
+  }
+
--- a/pyrect/regexp/fa.py	Tue Nov 16 06:06:25 2010 +0900
+++ b/pyrect/regexp/fa.py	Fri Dec 03 18:36:23 2010 +0900
@@ -11,3 +11,39 @@
     def accept(self, laungage):
         return False
 
+class Transition(dict):
+    def __setitem__(self, key, value):
+        if type(key) == tuple:
+            (state, input) = key
+            if self.has_key(state):
+                self[state][input] = value
+            else:
+                self[state] = {input: value}
+        else:
+            if not isinstance(value, dict):
+                raise "Transition.__setitem__: invalid item!"
+            dict.__setitem__(self, key, value)
+
+    def __getitem__(self, key):
+        if type(key) == tuple:
+            (state, input) = key
+            if self.has_key(state) and self[state].has_key(input):
+                return self[state][input]
+            else:
+                return None
+        else:
+            if self.has_key(key):
+                return dict.__getitem__(self, key)
+            else:
+                return None
+
+    def __str__(self):
+        string = "Transition:"
+        for (s, i), ns in self.iterallitems():
+            string += " %s x %s -> %s," % (s, i, ns)
+        return string
+
+    def iterallitems(self):
+        for s, v in self.iteritems():
+            for i, n in v.iteritems():
+                yield (s, i), n
--- a/pyrect/regexp/nfa.py	Tue Nov 16 06:06:25 2010 +0900
+++ b/pyrect/regexp/nfa.py	Fri Dec 03 18:36:23 2010 +0900
@@ -91,7 +91,6 @@
     def transition(self, state, char):
         return frozenset(self.map.get((state, char), []))
 
-#TODO: bug-fix
 class SuffixTrieNFA(NFA):
     def __init__(self, dfa):
         self.start = dfa.start