お待たせ(?)しました。なんとか出来上がりました。

プログラムは大きく5つの部分からできています。

1. パーサ (re_to_tree関数)

  re_to_tree関数は正規表現を引数に与えると、それを構文解析して構文木
を作ります。例えば、正規表現 a(ab)*b を構文解析(パース)すると、下の
ような構文木ができます。

          CONCAT(連結)
             ／ ＼
           ／     ＼
      CONCAT(連結)  b
         ／ ＼
       ／     ＼
      a  CLOSURE(繰り返し)
              ／
            ／
      CONCAT(連結)
         ／ ＼
       ／     ＼
      a         b


2. 構文木から状態遷移表を作る (tree_to_fa関数)

  パーサによって作られた構文木を元に、状態遷移表を作ります。状態遷移表
のデータ構造は、連結リストの配列です。各リストが状態遷移表の1つの状態に
対応していて、リストの要素は「1つの遷移」に対応しています。構文木から状
態遷移表を作るアルゴリズムは、かずまさん紹介の本を参考にしました。


3. 状態遷移表を使ってパターンマッチを行う (match関数)

  match関数は状態遷移表と、文字列を与えると、最左最長マッチ(left-most,
longest match)を行います。マッチに成功した場合、マッチした部分の先頭及
び末尾を指すポインタを、それぞれ、*begin, *end に格納して返します。


4. 構文木、状態遷移表の表示 (print_tree関数, print_fa関数)

  print_tree関数は構文木を与えるとそれを表示します。正規表現 a(ab)*b
は次のように表示されます。( + は連結を表します)

------ 構文木 ------
+
  +
    a
    *
      +
        a
        b
  b


print_fa関数は、状態遷移表を表示します。正規表現 a(ab)*b は次のよう
に表示されます。? はε遷移、@ は複数の文字を表します。

---- 状態遷移表 ----
  012345
 0   a                                                                  
 1                                                                      
 2 b                                                                    
 3  ?  a                                                                
 4   ?                                                                  
 5    b                                                                 


5. ドライバ (main関数)

  見ての通りです。 if (0) のところを if (1) にすると、構文木と状態遷移
表が表示されるようになります。

以上、自己満足でした。




#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/* ------------- エラー処理、下請け関数 ----------------- */

void error(const char *msg)
{
    fprintf(stderr, "error: %s\n", msg), exit(1);
}

void *my_malloc(size_t sz)
{
    void *p = malloc(sz);
    if (!p)    error("out out memory");
    return p;
}

/* ----- パーサ(正規表現を構文解析して構文木を作る) ----- */

const char *re_p;
char cur_token;

enum { END, CLOSURE, UNION, RPAREN,   EMPTY, CONCAT, LPAREN, EPS };

char gettoken(void)
{
    switch (*re_p++) {
    case '|':  return cur_token = UNION;
    case '*':  return cur_token = CLOSURE;
    case '(':  return cur_token = LPAREN;
    case ')':  return cur_token = RPAREN;
    case '\0': return cur_token = END;
    case '\\': return cur_token = *re_p++;
    default:   return cur_token = re_p[-1];
    }
}

typedef struct Tree {
    int c;
    struct Tree *left, *right;
} Tree;

Tree *make_node(int c, Tree *left, Tree *right)
{
    Tree *nd = my_malloc(sizeof *nd);

    nd->c = c;
    nd->left = left;
    nd->right = right;
    return nd;
}

Tree *parse(int level)
{
    Tree *t, *r;

    if (level == 2) {
        if (cur_token < 4)
            t = make_node(EMPTY, 0, 0);
        else if (cur_token == LPAREN) {
            gettoken();
            t = parse(0);
            if (cur_token != RPAREN) error("')' is expected");
            gettoken();
        } else
            t = make_node(cur_token, 0, 0), gettoken();

        while (cur_token == CLOSURE)
            t = make_node(CLOSURE, t, 0), gettoken();
        return t;
    }
    t = parse(level + 1);
    while (level == 0 && cur_token == UNION || level == 1 && cur_token >=4) {
        if (level == 0) gettoken();
        r = parse(level + 1);
        t = make_node(level ? CONCAT : UNION, t, r);
    }
    return t;
}

Tree *re_to_tree(const char *re)
{
    Tree *t;

    re_p = re;
    if (gettoken() == END) return 0;
    t = parse(0);
    if (cur_token != END) error("不正な')'");
    return t;
}

(つづく)

(つづきです)

/* ---------------- 構文木からNFAを作る ----------------- */

typedef struct Transition {
    int input;
    int to;
    struct Transition *next;
} Transition;

typedef struct {
    Transition **q;
    int num;
} FA;

int make_fa(FA *fa, int start, Tree *t, int goal)
{
    if (t == 0 || t->left == 0 && t->right == 0) {
        Transition *trans = my_malloc(sizeof *trans);
        trans->input = (t == 0 || t->c == EMPTY) ? EPS : t->c;
        trans->to = goal;
        trans->next = fa->q[start];
        fa->q[start] = trans;
        return trans->input == EPS;
    }

    switch (t->c) {
        int new, r1, r2;
    case CONCAT:
        new = fa->num++;
        r1 = make_fa(fa, start, t->left, new);
        r2 = make_fa(fa, new, t->right, goal);
        return r1 && r2;
    case UNION:
        r1 = make_fa(fa, start, t->right, goal);
        r2 = make_fa(fa, start, t->left, goal);
        return r1 || r2;
    case CLOSURE:
        make_fa(fa, start, 0, goal);
        new = fa->num++;
        if (make_fa(fa, start, t->left, new))
            error("不正な '*' のオペランド");
        make_fa(fa, new, 0, start);
        return 1;
    default:
        assert(0);
    }
}

FA *tree_to_fa(Tree *t)
{
    int i;  FA *fa = my_malloc(sizeof *fa);

    fa->q = malloc(sizeof(*fa->q) * 1024);
    for (i = 0; i < 1024; i++) fa->q[i] = 0;

    fa->num = 2;
    make_fa(fa, 0, t, 1);
    return fa;
}

/* ---- 有限オートマトンを使ってパターンマッチを行う ---- */

char *do_match(const FA *fa, char *p, int state)
{
    Transition *t;  char *rt;

    if (state == 1) return p;

    for (t = fa->q[state]; t; t = t->next)
        if (t->input == EPS || t->input == *p)
            if (rt = do_match(fa, t->input == EPS ? p : p + 1, t->to))
                return rt;
    return 0;
}

char *match(const FA *fa, char line[], char **begin, char **end)
{
    int i;

    for (i = 0; i < (int)strlen(line); i++)
        if (*end = do_match(fa, line + i, 0))
            return *begin = line + i, *end;
    return 0;
}

/* ------------ 構文木、状態遷移表の表示 ---------------- */

void print_tree_sub(Tree *t, int level)
{
    if (t == 0) return;

    printf("%*s", level * 2, "");

    switch (t->c) {
    case UNION:        putchar('|');    break;
    case CLOSURE:    putchar('*');    break;
    case CONCAT:    putchar('+');    break;
    case EMPTY:        printf("EMPTY"); break;
    default:        putchar(t->c);   break;
    }
    putchar('\n');
    print_tree_sub(t->left, level + 1);
    print_tree_sub(t->right, level + 1);
}

void print_tree(Tree *t)
{
    printf("------ 構文木 ------\n");
    print_tree_sub(t, 0);
}

void print_fa(FA *fa)
{
    int i;  Transition *p;

    printf("---- 状態遷移表 ----\n");

    printf("  ");
    for (i = 0; i < fa->num; i++)
        printf("%d", i % 10);
    putchar('\n');

    for (i = 0; i < fa->num; i++) {
        char s[70+1];  sprintf(s, "%*s", 70, "");
        for (p = fa->q[i]; p; p = p->next)
            if (s[p->to] != ' ')
                s[p->to] = '@';
            else if (p->input == EPS)
                s[p->to] = '?';
            else
                s[p->to] = p->input;
        printf("%2d%s\n", i, s);
    }
}

/* -------------------- ドライバ ------------------------ */

int main(int argc, char **argv)
{
    char line[1024], *begin, *end;  Tree *tree;  FA *fa;  FILE *fp = stdin;

    if (argc < 2)
        error("usage: program_name RE [infile]");

    if (argc == 3 && (fp = fopen(argv[2], "r")) == 0)
        error("cannot open the file");

    /* 正規表現を構文解析して構文木を作る */
    tree = re_to_tree(argv[1]);

    /* 構文木からNFAを作る */
    fa = tree_to_fa(tree);

    /* 構文木と状態遷移表を表示 */
    if (0) {
        print_tree(tree);
        print_fa(fa);
        return 0;
    }

    /* 入力行に対してパターンマッチを試みる */
    while (fgets(line, sizeof line, fp))
        if (match(fa, line, &begin, &end)) {
            if (argc == 2) {
                printf("%.*s", begin - line, line);
                printf("[これがマッチ→]");
                printf("%.*s", end - begin, begin);
                printf("[←これがマッチ]");
                printf("%s", end);
            } else
                printf("%s", line);
        }
    return 0;
}

(おわり)

>   match関数は状態遷移表と、文字列を与えると、最左最長マッチ(left-most,
> longest match)を行います。マッチに成功した場合、マッチした部分の先頭及
> び末尾を指すポインタを、それぞれ、*begin, *end に格納して返します。

正規表現 b|bb に abbba という入力を与えると、最左最長マッチなら、
a[これがマッチ→]bb[←これがマッチ]ba となるはずなのにそうなりません。
修正するとすれば、do_match でしょうか。

char *do_match(const FA *fa, char *p, int state)
{
    Transition *t;  char *rt, *max = 0;

    if (state == 1) return p;

    for (t = fa->q[state]; t; t = t->next)
        if (t->input == EPS || t->input == *p)
            if (rt = do_match(fa, t->input == EPS ? p : p + 1, t->to))
                max = rt;
    return max;
}

余談ですが、match 関数で、for ループ中に strlen(line) を書くのは無駄ですね。

    if (max == 0 || rt > max) max = rt; 

> 正規表現 b|bb に abbba という入力を与えると、最左最長マッチなら、
> a[これがマッチ→]bb[←これがマッチ]ba となるはずなのにそうなりません。

Perlの正規表現インタープリタ(以下正規表現エンジン)が行う最左最長
マッチでは正規表現 b|bb は abbba のうちの、最初の b ひとつにマッ
チします。つまり、次の Perl スクリプトを実行すると、

# ------------------- 例1 -------------------
'abbba' =~ /b|bb/;

print "$`";
print "[これがマッチ→]${&}[←これがマッチ]";
print "$'";
# -------------------------------------------

a[これがマッチ→]b[←これがマッチ]bba

と表示されます。Perl の正規表現エンジンは、'|' の左に書かれた正規表
現がマッチするかどうかをまず試し、もしマッチに成功したら、'|' の右側
の正規表現を試すことなく無視してしまいます。また、次のスクリプトを実
行すると、

# ------------------- 例2 -------------------
'aaabbbbb' =~ /a*(ab*|b)/;

print "$`";
print "[これがマッチ→]${&}[←これがマッチ]";
print "$'";
# -------------------------------------------

[これがマッチ→]aaabbbbb[←これがマッチ]

ではなく、

[これがマッチ→]aaab[←これがマッチ]bbbb

と表示されます。これは、a* が欲張って a を 3 つも消費したので、(ab*|b)
が b を 1 つしか消費することができなかったためです。もし a* が a を 2
 つしか消費しなければ、(ab*|b) は残りの abbbbb をすべて消費することが
でき、全体として本当の最長マッチになります。でも、a* は欲張って a を 3 
つ消費するので、全体として見た場合には最長マッチになっていません。

このようにPerl の正規表現エンジンには、

(1) '|'の左側でマッチに成功したら右側は調べないので、マッチする部分が最
    長にならないことがある。(例1のケース)

(2) 最終的な結果が最長になるように賢く欲張るのではなく、正規表現の部分部
    分が、やみくもに欲張るので、正規表現全体としてはマッチする部分が最長
    にならないことがある。(例2のケース)

という特徴があります。Perlの最長マッチは「本当の最長マッチ」ではありませ
んが、このようなマッチの方法でも、最長マッチと言って構わないようです(『プ
ログラミングPerl』ではPerlの正規表現エンジンの動作を説明するのに、「最左
最長マッチ」という言葉を使っています。)。

さて、この「Perl流の最長マッチ」の方法が一般的な最長マッチの方法なのかを
調べてみました。これが現在の成果です。


sed    使い方が分からない。マニュアルが英語なので読むのに時間がかかり
       そう。

awk    同上

vi     そもそも'|'が使えないみたい。(拡張正規表現が使えないみたい。)

Ruby  『オブジェクト指向スクリプト言語Ruby』を読む限りどちらか分から
       ない。(多分Perl流だと思う)

egrep  マッチした部分があるかないかを知ることはできるが、どの部分がマ
       ッチしたかを知ることはできないみたい。(多分DFAを使った最短マッ
       チだと思う)

mule   muleとタイプしたが 'mule: Command not found.' と表示された。


> 余談ですが、match 関数で、for ループ中に strlen(line) を書くのは無駄ですね。

お恥ずかしい。 s/i < (int)strlen(line)/line[i]/

[(a*)((((ab)*)|b))]
   |-[a*]
   |   |-[a]
   |   |-[*]
   |
   |-[(((ab)*)|b)]
   |   |-[((ab)*)|b]
   |   |   |-[(ab)*]
   |   |   |   |-[ab]
   |   |   |   |-[*]
   |   |   |
   |   |   |-[|]
   |   |   |-[b]
   |   |
   |

[(b|(bb))]
   |-[b|(bb)]
   |   |-[b]
   |   |-[|]
   |   |-[bb]
   |

[(a*)((((ab)*)|b))]
   |-[a*]
   |   |-[a]
   |   |-[*]
   |
   |-[(((ab)*)|b)]
   |   |-[((ab)*)|b]
   |   |   |-[(ab)*]
   |   |   |   |-[ab]
   |   |   |   |-[*]
   |   |   |
   |   |   |-[|]
   |   |   |-[b]
   |   |
   |

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

typedef struct token {
    char tok[256];
    struct token *atom;
    struct token *next;
} TOKEN;

/* 論理構造を表示する */
void display(TOKEN *tp, int n)
{
    do {
        int i = 0;
        while (i < n) printf(i++%3 == 2 ? " |" : " ");
        printf("%s[%s]\n", n ? "-" : "", tp->tok);
        if (tp->atom) display(tp->atom, n + 3);
    } while ((tp = tp->next) != NULL);
    for (n -= 3; n > 0; n -= 3) printf("   |");
    puts("");
}

void error(const char *p) { puts(p); exit(1); }
void delete(TOKEN *tp)
{
    if (tp == NULL) return;
    delete(tp->atom);  
    delete(tp->next);
    free(tp);
}

/* 対応する (, ), [, ] を探す */
char *paren(char *p, int d, const char *m)
{
    for (; *p && *p != m[0]; p += d)
        if (*p == m[1])
            if ((p = paren(p + d, d, m)) == NULL) return NULL;
    return *p ? p : NULL;
}

/* メタ文字 |, * にかかるアトムに括弧を付ける */
char *operator(char *p, char **s)
{
    char *b = *s + 1, *f;

    if (**s == '|' && *(*s+1) == '(') b = paren(*s + 2, 1, ")(");
    if (*(p-1) == ')') {
        f = paren(p - 2, -1, "()");
        if (*(f-1) != '(' || *(b+1) != ')') {
            memmove(f + 1, f, p - f);
            *f = '(';
            p += sprintf(p+1, **s == '*' ? "*)" : "|%.*s)",
                         b - *s, *s + 1) + 1;
        }
        else p += sprintf(p, **s == '*' ? "*" : "|%.*s", b - *s, *s + 1);
    }
    else if (*(p-2) != '(' || *(b+1) != ')')
        p += sprintf(p-1, **s == '*' ? "(%c*)" : "(%c|%.*s)",
                     *(p-1), b - *s, *s + 1) - 1;
    else p += sprintf(p, **s == '*' ? "*" : "|%.*s", b - *s, *s + 1);
    if (**s == '|') *s += b - *s;
    return p;
}

/* 優先順位を考える */
void regular(char *p, char *s)
{
    char *w = p, *b, buf[256] = {0}, wbuf[256] = {0};

    for (s = strcpy(buf, s), *p++ = '\0'; *s; s++)
        if (*s == '*') p = operator(p, &s);
        else if (*s == '.') *p++ = '(', *p++ = *s, *p++ = ')';
        else *p++ = *s;
    *p = '\0';
    for (p = w+1, s = strcpy(buf, w+1); *s; s++)
        if (*s == '|') {
            if (*(s+1)== '(') {
                b = paren(s + 2, 1, ")(") + 1;
                strcpy(wbuf, b);
                *b = '\0';
                regular(s + 1, s + 1);
                strcat(s, wbuf);
            }
            p = operator(p, &s);
        }
        else *p++ = *s;
    sprintf(w, "%.*s", p-w-1, w + 1);
}

/* 構文チェック */
int check(char *p)
{
    char buf[256] = {0};

    for (p = strcpy(buf + 1, p); *p; p++)
        if (*p == '(' && !(p = paren(p + 1,  1, ")(")))
            return -1;
    for (p--; *p; p--)
        if (*p == ')' && !(p = paren(p - 1, -1, "()")))
            return -1;
    for (p++; *p; p++) {
        if (*p == '*')
            if (*(p-1) == '|' || *(p-1) == '(' || *(p-1) == '\0')
                return -1;
        if (*p == '|')
            if (*(p-1) == '|' || *(p-1) == '(' || *(p-1) == '\0' ||
                *(p+1) == '|' || *(p+1) == ')' || *(p+1) == '\0' ||
                *(p+1) == '*')
                return -1;
    }
    return 0;
}

/* 対応する ) を探す */
char *get(char *p, TOKEN *tp)
{
    for (; *p != ')'; p++)
        if (*p == '(' || *p == '*' || *p == '|') {
            if (!tp->atom && !(tp->atom = calloc(1, sizeof(TOKEN))))
                error("error 1: calloc");
            if (*p == '(') p = get(p + 1, tp);
        }
    return p;
}

/* 正規表現 p を display() で表示されるような論理構造にする */
void divide(char *p, TOKEN *tp)
{
    TOKEN *rt = tp;

    if (*p == '\0') return;
    for (;;) {
        char *f = *p == '(' ? get(p+1, tp) : p;

        sprintf(tp->tok, "%.*s", f - p + (f == p ? 1 : -1), p + (f != p));
        if (*(p = f+1) == '\0') break;
        if (!(tp = tp->next = calloc(1, sizeof(TOKEN))))
            error("error 2: calloc");
    }
    for (tp = rt; tp != NULL; tp = tp->next)
        if (tp->atom) divide(tp->tok, tp->atom);
}

/* 文字列 p の最初が正規表現 s にマッチしているか調べる */
/* 拡張しようとして関数にしてみた                       */
char *part(char *p, char *s)
{
    int len = strlen(s);
    return *s != '.' && strncmp(p, s, len) ? NULL : p + len;
}

/* 文字列 p の最初がマッチしているか調べる */
char *matching(char *p, TOKEN *tp)
{
    while (tp && *p) {
        TOKEN *prev = tp;
        char *w = p;

        p = tp->atom ? matching(p, tp->atom) : part(p, tp->tok);
        tp = tp->next;
        if (p != NULL) {
            if (tp == NULL || *tp->tok == '|') return p;
            if (*tp->tok == '*') tp = prev;
        }
        else if (tp == NULL || (*tp->tok != '|' && *tp->tok != '*'))
            return NULL;
        else p = w, tp = tp->next;
    }
    return tp ? NULL : p;
}

/* 1行単位で、1つずつずらしながらマッチする部分を探す */
int match(const char *fn, TOKEN *tp)
{
    FILE *fp;  char buf[256], *p;  int line;

    if (fn == NULL) fp = stdin;
    else if ((fp = fopen(fn, "r")) == NULL) return -1;
    for (line = 1; fgets(buf, sizeof buf, fp); line++) {
        buf[strlen(buf) - 1] = '\0';
        for (p = buf; *p; p++)
            if (matching(p, tp)) {
                printf(fp == stdin ? "" : "%s:%d:", fn, line);
                puts(buf);
                break;
            }
    }
    return fclose(fp);
}

/* 主制御 */
int main(int argc, char *argv[])
{
    TOKEN root = { {0}, calloc(1, sizeof(TOKEN)) };
    char *p = root.tok, *s = argv[1];

    if (argc < 2) error("usage: 'THE FILE' pattern [file ...]");
    else if (root.atom == NULL) error("error 3: calloc");

    do if (!isspace(*s)) *p++ = *s; while (*s++);
    if (check(root.tok)) error("error 4: pattern");

    regular(root.tok, root.tok);
    divide(root.tok, root.atom);
    display(&root, 0);

    for (argv += 2; *argv; argv++)
        if (match(*argv, root.atom))
            error("error 5: fopen or fclose");
    if (argc == 2) match(NULL, root.atom);
    delete(root.atom);
    return 0;
}

else if ((root.atom = calloc(1, sizeof(TOKEN))) == NULL)
    error("error 3: calloc");

> お恥ずかしい。 s/i < (int)strlen(line)/line[i]/

やっぱりこうします。

char *match(const FA *fa, char line[], char **begin, char **end)
{
    for (; *line; line++)
        if (*end = do_match(fa, line, 0))
            return *begin = line, *end;
    return 0;
}

>> 正規表現 b|bb に abbba という入力を与えると、最左最長マッチなら、
>> a[これがマッチ→]bb[←これがマッチ]ba となるはずなのにそうなりません。
>
> Perlの正規表現インタープリタ(以下正規表現エンジン)が行う最左最長
> マッチでは正規表現 b|bb は abbba のうちの、最初の b ひとつにマッ
> チします。

POSIX標準として定義された正規表現について調べてみたところ、Perl
流の最長最左マッチは POSIX 標準を満たしていないことが分かりました。

------ re_format - POSIX 1003.2 regular expressions の一部 ------
                      (いい加減な私の訳付き)

In the event that an RE could match more than one substring of
a given string, the RE matches the one startingearliest in the
string.

もし正規表現が与えられた文字列の 2 つ以上の部分文字列にマッチで
きる場合、その正規表現はその文字列の中で最も早く始まる部分文字列
にマッチする。

If the RE could match more than one substring starting at that
point, it matches the longest.

もしその正規表現が 2 つ以上の部分文字列にその(最も早く始まる)地点
でマッチできるならば、その正規表現は最長のものにマッチする。

Subexpressions also match the longest possible substrings, subje-
ct to the constraint that the whole match beas long as possible,
with subexpressions starting earlier in the RE taking priority
over ones starting later.

部分正規表現(正規表現の一部である正規表現)もまた、最長の部分文字
列にマッチする。ただし、正規表現の中で、より早く始まる部分正規表
現は、より遅く始まる部分正規表現より優先するので、正規表現全体の
マッチができるだけ長くならなければならないという制約がある。

Note that higher-level subexpressions thus take priority over th-
eir lower-level component subexpressions.

このように、より上位の部分正規表現は、その正規表現の下位の部品で
ある部分正規表現よりも優先することに注意せよ。
-------------------------------------------------------------------

というわけで、Perl流最長最左マッチを一般的な最長最左マッチと考える
のは間違いだったようです。すみませんでした。