--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/uprogs/grep.c	Sun Oct 22 18:25:39 2017 +0900
@@ -0,0 +1,106 @@
+// Simple grep.  Only supports ^ . * $ operators.
+
+#include "types.h"
+#include "stat.h"
+#include "user.h"
+
+char buf[1024];
+int match(char*, char*);
+
+void
+grep(char *pattern, int fd)
+{
+  int n, m;
+  char *p, *q;
+  
+  m = 0;
+  while((n = read(fd, buf+m, sizeof(buf)-m)) > 0){
+    m += n;
+    p = buf;
+    while((q = strchr(p, '\n')) != 0){
+      *q = 0;
+      if(match(pattern, p)){
+        *q = '\n';
+        write(1, p, q+1 - p);
+      }
+      p = q+1;
+    }
+    if(p == buf)
+      m = 0;
+    if(m > 0){
+      m -= p - buf;
+      memmove(buf, p, m);
+    }
+  }
+}
+
+int
+main(int argc, char *argv[])
+{
+  int fd, i;
+  char *pattern;
+  
+  if(argc <= 1){
+    printf(2, "usage: grep pattern [file ...]\n");
+    exit();
+  }
+  pattern = argv[1];
+  
+  if(argc <= 2){
+    grep(pattern, 0);
+    exit();
+  }
+
+  for(i = 2; i < argc; i++){
+    if((fd = open(argv[i], 0)) < 0){
+      printf(1, "grep: cannot open %s\n", argv[i]);
+      exit();
+    }
+    grep(pattern, fd);
+    close(fd);
+  }
+  exit();
+}
+
+// Regexp matcher from Kernighan & Pike,
+// The Practice of Programming, Chapter 9.
+
+int matchhere(char*, char*);
+int matchstar(int, char*, char*);
+
+int
+match(char *re, char *text)
+{
+  if(re[0] == '^')
+    return matchhere(re+1, text);
+  do{  // must look at empty string
+    if(matchhere(re, text))
+      return 1;
+  }while(*text++ != '\0');
+  return 0;
+}
+
+// matchhere: search for re at beginning of text
+int matchhere(char *re, char *text)
+{
+  if(re[0] == '\0')
+    return 1;
+  if(re[1] == '*')
+    return matchstar(re[0], re+2, text);
+  if(re[0] == '$' && re[1] == '\0')
+    return *text == '\0';
+  if(*text!='\0' && (re[0]=='.' || re[0]==*text))
+    return matchhere(re+1, text+1);
+  return 0;
+}
+
+// matchstar: search for c*re at beginning of text
+int matchstar(int c, char *re, char *text)
+{
+  do{  // a * matches zero or more instances
+    if(matchhere(re, text))
+      return 1;
+  }while(*text!='\0' && (*text++==c || c=='.'));
+  return 0;
+}
+