|
「お願いします！！！」についての質問ですか。
「お願いします！！！」を教えて欲しいのですか。
「お願いします！！！」がわからないのですか。
「お願いします！！！」は、題名として不適切です。
「正規表現との照合」とでもすれば十分なのに、残念です。
> 正規表現を分割するというところまではなんとかできたのですが、
> 正規表現をオートマトンに変換するのがどうしても思いつきません。
その出来たところまでを載せてくれたら、私も興味を持って、もっと早くコメントを書いたかも
しれません。
さて、正規表現を木構造にするところまでは、すぐに出来るんですが、オートマトンに変換する
ところは、すぐには思いつきませんでした。昔、egrep のソースを読んで、決定性有限オートマト
ンの状態遷移表を作るコードには感心した覚えはあるのですが、結構複雑だったように思います。
で、今回の場合、かなり制限された正規表現ですから、正規表現のまま、パターンマッチングを
行えば、わりと簡単に済むんじゃないかと考えて、次のようなコードをでっち上げました。
質問者の期待に答えるものではありませんが、まあこんなことでも実現できますよということで
ご容赦ください。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void error(void) { puts("regular expression error"); exit(1); }
int ischar(int c) { return c >= 'a' && c <= 'z' || c == '.'; }
int eqchar(int op, int c) { return (op == '.') ? (c >= 'a' && c <= 'z') : (op == c); }
int regex(const char *re, const char *s);
int or(const char *re, const char *s)
{
const char *p1, *p2; int n1, n2;
p1 = strchr(re, '|');
if (p1 == NULL) error();
p2 = strchr(re, ')');
if (p2 == NULL || p2 < p1) error();
n1 = p1 - re;
n2 = p2 - p1 - 1;
if (strncmp(re, s, n1) == 0) return regex(p2 + 1, s + n1);
if (strncmp(p1 + 1, s, n2) == 0) return regex(p2 + 1, s + n2);
return 0;
}
int star(int op, const char *re, const char *s)
{
for (;;) {
if (regex(re, s)) return 1;
if (!eqchar(op, *s++)) return 0;
}
}
int regex(const char *re, const char *s)
{
for (;;) {
int op = *re++;
if (op == 0) return *s == '\0';
if (op == '(') return or(re, s);
if (!ischar(op)) error();
if (*re == '*') return star(op, ++re, s);
if (!eqchar(op, *s++)) return 0;
}
}
void grep(FILE *fp, const char *re)
{
char buf[1024], *p;
while (fgets(buf, sizeof buf, fp)) {
if (p = strchr(buf, '\n')) *p = '\0';
if (regex(re, buf)) puts(buf);
}
}
int main(int argc, char **argv)
{
switch (argc) {
default: return printf("usage: mygrep pattern [file]\n"), 1;
case 2: grep(stdin, argv[1]); break;
case 3: {
FILE *fp = fopen(argv[2], "r");
if (fp == NULL) return printf("can't open %s\n", argv[2]), 1;
grep(fp, argv[1]);
fclose(fp);
}
}
return 0;
}
|
