レポート提出ボックス

遅れて提出済み

C言語で正規表現エンジンを作る

文字列処理の自作したくないですか？私はしたいので簡単な正規表現エンジンをCで書きました．これはそのアウトプットです．Advent Calendar 2022と日付がかぶってますが全く関係ありません．

github.com

↑成果物です

正規表現の仕組み

正規表現の実現方法はDFA型とVM型があります．

DFA型

正規表現をNFAに変換し更にそれをDFAに変換してマッチングさせたい文字列をそのDFAに入力していく方法．GNU grepとかが使ってるらしいです．

VM型

正規表現を仮想機械の命令のバイト列に変換してマッチング処理をする方法．sedとかPerlとかPythonとかが使ってるらしいです．


DFA型は線形時間でのマッチングでVM型は指数時間でのマッチングらしいです．


今回はVM型の正規表現エンジンを作りました(CでDFAをどうやって実装するか思いつかなかったため(形式言語理論とか受けたほうが良い？))

仕様

今回は

  • 連接 (AB)
  • 選択 (A|B)
  • 繰り返し (A*)

を含む最小限の正規表現を実装します

実装

このサイト*1を参考にしました．今回作成する仮想機械はプログラムの現在地を示すPCと文字列の現在位置のポインタSPの2つのレジスタと下に示す4つの命令を持ちます．

  • char c: SPが指す文字とcが一致していたらPCとSPを先に進め，一致していなかったらマッチング失敗として終了します．
  • jmp x: xが指すプログラムの位置に飛びます． \mathrm{PC} \leftarrow xです．
  • split x, y: xが指すプログラムの位置とyが指すプログラムの位置から新しくスレッドを開始します．SPはその時の値を使います．
  • match: マッチングが成功したとして終了します．


処理の流れとしては字句解析→構文解析→バイトコードの生成→仮想機械を動かしてマッチングというようになります

字句解析

正規表現文字列を構文解析する前に字句解析をしてトークン列にする必要があります．

トークンの種類を以下のように定義します．

enum Kind{
    TOKEN_UNDEFINED = 0,
    TOKEN_EOF,
    TOKEN_CHARACTER,
    TOKEN_ASTERISK,
    TOKEN_LPAR,
    TOKEN_RPAR,
    TOKEN_BAR
};

またトークンのデータ構造は次の単連結リストを用います．

typedef struct __token Token;

typedef struct __token{
    enum Kind kind;
    char* s;
    unsigned len;
    Token* next;
}_token;

トークン文字列の保持は入力文字列の該当箇所の先頭文字へのポインタ(メンバ変数s)と長さ(メンバ変数len)を用います(わざわざそれ用にメモリの確保したくないので)(結局1つのトークン文字列の長さを1文字にしたのでlenいらない)．

あとはトークナイザをかくだけです．

void tokenize(char* s, Token* head){
    Token* cur;
    Token* tok;

    cur = head;
    while( *s != '\0'){
        if( isalnum(*s) ){
            tok = (Token*)malloc(sizeof(Token));
            tok->kind = TOKEN_CHARACTER;

            tok->s    = s;
            s++;

            tok->len = 1;
            tok->next = NULL;

            cur->next = tok;
            cur = tok;
        }

        else if(*s == '(' || *s == ')' || *s == '|' || *s == '*'){
            tok = (Token*)malloc(sizeof(Token));
            switch(*s){
                case '(':
                    tok->kind = TOKEN_LPAR;
                    break;
                case ')':
                    tok->kind = TOKEN_RPAR;
                    break;
                case '|':
                    tok->kind = TOKEN_BAR;
                    break;
                case '*':
                    tok->kind = TOKEN_ASTERISK;
                    break;                
            }
            tok->s    = s;
            s++;

            tok->len = 1;
            tok->next = NULL;

            cur->next = tok;
            cur = tok;
        }

        else if(*s == '\\'){
            s++;
            tok = (Token*)malloc(sizeof(Token));
            tok->kind = TOKEN_CHARACTER;
            tok->s    = s;
            s++;
            tok->len = 1;
            tok->next = NULL;

            cur->next = tok;
            cur = tok;
        }

        else{
            s++;
        }
    }
    tok = (Token*)malloc(sizeof(Token));
    tok->kind = TOKEN_EOF;
    tok->next = NULL;

    cur->next = tok;
}

各トークン文字列の長さが1文字なので基本的に1文字ずつ読み進めていけばいいです．あと一応エスケープにも対応しました．

トークンをメモリ領域の確保にmalloc()を使っているので後で開放しないといけません．開放するための関数freeToken()は次のように実装しました．

void freeToken(Token* head){
    Token* tok;
    Token* next;

    tok = head->next;

    while(tok != NULL){
        next = tok->next;
        free(tok);
        tok = next;
    }
}

最初から順にケツ要素(tok->next == NULLになる要素)まで開放します．

構文解析

codezine.jp

↑めちゃくちゃここを参考にしました(読むには無料の会員登録が必要です)

BNFはこんな感じになります

expr    := subexpr EOF
subexpr := seq '|' subexpr | seq
seq     := subseq | ''
subseq  := star subseq | star
star    := factor '*' | factor
factor  := '(' subexpr ')' | CHARACTER

ノードの種類とデータ構造はこれです．

enum NodeKind{
    NODE_UNION,
    NODE_ASTERISK,
    NODE_CONCAT,
    NODE_CHARACTER
};


struct __node{
    enum NodeKind kind;
    char c;
    Node* l;
    Node* r;
};

実装は上の記事をほぼそのままCで書いただけなので言うことないです．あるとすればメモリの確保とポインタ周りの話だと思います．

Node* expr(Token** ptok){
    // expr := subexpr EOF
    Node* node = subexpr(ptok);
    match(ptok, TOKEN_EOF);

    return node;
}

Node* subexpr(Token** ptok){
    // subexpr := seq '|' subexpr | seq
    Node* node = seq(ptok);

    if((*ptok)->kind == TOKEN_BAR){
        match(ptok, TOKEN_BAR);
        Node* node2 = subexpr(ptok);
        node = Union(node, node2);
    }

    return node;
}

Node* subseq(Token** ptok){
    Node* node1 = star(ptok);
    if((*ptok)->kind == TOKEN_LPAR ||
       (*ptok)->kind == TOKEN_CHARACTER){
        // subseq := star subseq
        Node* node2 = subseq(ptok);
        Node* node = Concat(node1, node2);
        return node;
    }
    else{
        // subseq := star
        return node1;
    }
}

Node* seq(Token** ptok){
    // seq     := subseq | ''
    if((*ptok)->kind == TOKEN_LPAR ||
       (*ptok)->kind == TOKEN_CHARACTER){
        // seq := subseq
        return subseq(ptok);
    }
    else{
        // seq := ''
        return Character('\0');
    }
}

Node* star(Token** ptok){
    // star    := factor '*' | factor
    Node* node = factor(ptok);
    if((*ptok)->kind == TOKEN_ASTERISK){
        match(ptok, TOKEN_ASTERISK);
        node = Asterisk(node);
    }

    return node;
}

Node* factor(Token** ptok){
    // factor := '(' subexpr ')'
    if((*ptok)->kind == TOKEN_LPAR){
        match(ptok, TOKEN_LPAR);
        Node* node = subexpr(ptok);

        match(ptok, TOKEN_RPAR);

        return node;
    }

    // factor := CHARACTER
    else {
        Node* node = Character( *(*ptok)->s);

        match( ptok, TOKEN_CHARACTER);

        return node;
    }
}

int match(Token** ptok, enum Kind k){
    if ((*ptok)->kind == k){
        *ptok = (*ptok)->next;
        return 1;
    }
    fprintf(stderr, "syntax error\n");
    exit(1);
}

Node* Character(const char c){
    Node* node = malloc(sizeof(Node));

    node->kind = NODE_CHARACTER;
    node->c = c;
    node->l = NULL;
    node->r = NULL;

    return node;
}

Node* Concat(Node* node1, Node* node2){
    Node* node = malloc(sizeof(Node));

    node->kind = NODE_CONCAT;
    node->l = node1;
    node->r = node2;

    return node;
}

Node* Asterisk(Node* node1){
    Node* node = malloc(sizeof(Node));

    node->kind = NODE_ASTERISK;
    node->l = node1;
    node->r = NULL;

    return node;
}

Node* Union(Node* node1, Node* node2){
    Node* node = malloc(sizeof(Node));

    node->kind = NODE_UNION;
    node->l = node1;
    node->r = node2;

    return node;
}

(BNFの定義順と合わせるために実際のソースと順番を変えています)

regex/parser.c at main · ouharetaso/regex · GitHub

バイトコードへの変換

抽象構文木から仮想機械のバイトコードへの変換は次のように機械的に行なえます

  • NODE_CHARACTER (文字)c:
    char c
  • NODE_CONCAT (連接) e_1 e_2:
    e1 # bytecodes of e1
    e2 # bytecodes of e2
  • NODE_UNION (選択)(e_1|e_2):
    split L1, L2
L1: e1 # bytecodes of e1
    jmp L3
L2: e2 # bytecodes of e2
L3:
  • NODE_ASTERISK (繰り返し) e*:
L1: split L2, L3
L2: e # bytecodes of e
    jmp L1
L3:

これに従って抽象構文木を命令列に変換します．私は再帰を使いました．

int convert(Node* node, Inst* inst, int* pos){
    switch(node->kind){
        case NODE_CHARACTER:
            (inst + *pos)->opcode = Char;
            (inst + *pos)->c      = node->c;
            (*pos)++;
            break;
        case NODE_CONCAT:
            convert(node->l, inst, pos);
            convert(node->r, inst, pos);
            break;
        case NODE_UNION:{
            int L1, L2, L3, L_Split, L_Jmp;

            (inst + *pos)->opcode = Split;
            L_Split = *pos;
            (*pos)++;
            L1 = *pos;

            convert(node->l, inst, pos);
            (inst + *pos)->opcode = Jmp;
            L_Jmp = *pos;
            (*pos)++;
            L2 = *pos;

            convert(node->r, inst, pos);
            L3 = *pos;
            (inst + L_Jmp)->x  = inst + L3;
            (inst + L_Split)->x = inst + L1;
            (inst + L_Split)->y = inst + L2;
            }
            break;
        case NODE_ASTERISK:{
            int L1, L2, L3;

            L1 = *pos;
            (inst + *pos)->opcode = Split;
            (*pos)++;
            L2 = *pos;

            convert(node->l, inst, pos);

            (inst + *pos)->opcode = Jmp;
            (inst + *pos)->x = inst + L1;
            (*pos)++;
            L3 = *pos;

            (inst + L1)->x = inst + L2;
            (inst + L1)->y = inst + L3;
            }
            break;
    }

    (inst + *pos)->opcode = Match;

    return 0;
}

case NODE_UNION:のところでsplitやjmpを命令列に書き込むとき，その時点では引数の値(分割して実行する先や飛び先のアドレス)が決定していないのであとからどうにかする必要があります．

あとアロー演算子->を使いたくてキモい書き方をしています．ゆるして．

仮想機械を動かしてマッチング

仮想機械のシミュレートは例のサイト*2を参考にしました．Cでsplit命令をシミュレートするのめんどくさそうですよね．私はどうすれば良いのかよくわからなかったので例のサイトの実装をほぼそのまんま実装しました．本当に参考程度か？ 違うのはchar '\0'(空文字)のとき任意の文字とマッチングさせるところです．(そうしないと拡張正規表現のa?を(|a)として表現できない)

int recursive(Inst* pc, char* sp){
    switch(pc->opcode){
        case Char:
            if(*sp != pc->c) {
                if( pc->c != '\0' ){
                    return 0;
                }
            }
            return recursive(pc+1, sp+1);
            break;
        case Match:
            return 1;
            break;
        case Jmp:
            return recursive(pc->x, sp);
            break;
        case Split:
            if(recursive(pc->x, sp)) return 1;
            return recursive(pc->y, sp);
            break;
    }
    return 0;
}

あとは生成した命令列とマッチングさせたい文字列をrecursive()に渡すと判定が出てきます．

感想

こうやって書き出してみると写経ばっかでほんとに自作か？って思うけどトークナイズと命令列の生成はじぶんでかけたし楽しかったのでOKだと思います．

あとは動的なメモリ確保がめんどくさいしガベージコレクタないしポインタの文法がクソだしで辛かったです．

おま○け

実行速度を測ってみます．ここ*3を参考に「正規表現a?ⁿaⁿつまり(|a)ⁿaⁿと，文字列aⁿ のマッチングにかかった時間 」を測定します．

環境
結果

nに対する実行時間のブラフ

ほぼ指数時間になりました．

参考文献

swtch.com qiita.com codezine.jp

*1:https://swtch.com/~rsc/regexp/regexp2.html

*2:https://swtch.com/~rsc/regexp/regexp2.html

*3:https://swtch.com/~rsc/regexp/regexp1.html