簡単な正規表現エンジンを書いた

学校の課題が「検索，置換を行うプログラムを作成しなさい．オプションとして，独自の機能を盛り込んでもよし」とあったので，簡単な正規表現のエンジンを書いてみた．

対応する文法は以下の3つ．

記号	意味
*	直前の文字の0回以上の繰り返し
x｜y	xまたはy
xy	xとyの連結

具体的な文法規則は以下のサイトにある，「文脈自由文法」（CFG: Context-free Grammer）による定義を使用した．
正規表現エンジンを作ろう（3） (2/3)：CodeZine（コードジン）(要会員登録)

CFGはその変数名に対応する関数を作り，それぞれの関数の中で再帰的に他のヘンス名に対応する関数を呼び出すことで，構文木を作成することができる．

a -> 'A' b | c

という定義があったら，


Node* parse(const char* text) {
  char* it = text;
  return a(&it);
}

Node* a(char** it) {
  Node* node;

  if (**it == 'A') {
    node = b();
    (*it)++;
  } else {
    node = c();
  }

  return node;
}

のように書いていけば良い．多分．

先ほど示したサイトではこの後，構文木からNFAを，NFAからDFAを作成することになると思うのだが，今回は以下のサイトを参考にしてVM型の正規表現エンジンにした．

Mokkosu - VM型の正規表現エンジンを実装する - Qiita

Regular Expression Matching: the Virtual Machine Approach

VM型とは，正規表現を一度専用のバイトコードへコンパイルし，そのバイトコードをVM(仮想マシン)によって実行することで，判定を行う方法．
以下に今回のVMの構造を示す．

名前	意味
mem	メモリ．コンパイルしたバイトコードを格納．
pc	プログラムカウンタ．これから実行するメモリ上の命令の位置を表す．
sp	文字列ポインタ．判定を行う文字を示す．

今回はスレッドを分ける必要があったため，pcとspをまとめてContextという構造体に入れた．
その他詳しい定義は先ほど示したリンクを参照してください．


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

/****************************************
 * 木構造
 ****************************************/

typedef enum {
    ND_Union,
    ND_Star,
    ND_Char,
    ND_Concat,
    ND_Empty
} NodeType;

typedef struct Node {
    NodeType type;
    char value;
    struct Node** chd;
    int chd_count;
} Node;

Node* new_node();
void add_chd(Node*, Node*);
void free_tree(Node*);
void print_tree(Node*, int);

Node* new_node() {
    Node* node = (Node*)malloc(sizeof(Node));
    node->value = 0;
    node->chd = NULL;
    node->chd_count = 0;
    return node;
}

void add_chd(Node* t, Node* p) {
    if (t->chd == NULL) t->chd = (Node* *)malloc(0);
    t->chd = (Node* *)realloc(t->chd, 1 * sizeof(Node*));
    t->chd[t->chd_count++] = p;
}

void print_tree(Node* t, int level) {
    char indent[256];
    int  cnt = -1;

    sprintf(indent, "%% %ds", level);
    printf(indent, "");
    printf("Type:");
    switch(t->type) {
        case ND_Concat:
            printf("Concat");
            break;
        case ND_Union:
            printf("Union");
            break;
        case ND_Star:
            printf("Star");
            break;
        case ND_Char:
            printf("Char");
            break;
        case ND_Empty:
            printf("Epsilon");
            break;
    }
    printf(",Val:%c, Chd:%d\n", t->value, t->chd_count);

    while (++cnt < t->chd_count)
        print_tree(t->chd[cnt], level+1);
}

void free_tree(Node* t) {
    int cnt = -1;

     while (++cnt < t->chd_count)
         free_tree(t->chd[cnt]);
    free(t);
}

/****************************************
 * コンパイラ
 ****************************************/
typedef enum {
    OP_Char,
    OP_Match,
    OP_Jump,
    OP_Split
} Opecode;

typedef struct {
    char opecode;
    char operand1;
    char operand2;
    char dummy;
}__attribute__((packed)) Inst;

void print_code(Inst* code, int len) {
    int pc;
    for (pc = 0; pc < len; pc++) {
        printf("%4d | %02x %02x %02x %02x | ", pc, code[pc].opecode, code[pc].operand1, code[pc].operand2, code[pc].dummy);

        switch (code[pc].opecode) {
            case OP_Jump:
                printf("JMP   %4d", code[pc].operand1);
                break;
            case OP_Split:
                printf("SPLIT %4d, %4d", code[pc].operand1, code[pc].operand2);
                break;
            case OP_Char:
                printf("CHAR  %4c", code[pc].operand1);
                break;
            case OP_Match:
                printf("MATCH");
                break;
        }
        printf("\n");
    }
}

int compile(Node*, Inst**);
void compile_node(Node*, Inst**, int*);

int compile(Node* ast, Inst** out) {
    int pc = 0;

    if (*out != NULL) free(*out);
    *out = (Inst*)malloc(0);

    compile_node(ast, out, &pc);

    *out = (Inst*)realloc(*out, sizeof(Inst) * (pc + 1));
    (*out)[pc].opecode = OP_Match;

    pc++;

    return pc;
}

void compile_node(Node* node, Inst** out, int* pc) {
    int tmp1, tmp2;
    int cnt = -1;

    switch(node->type) {
        case ND_Char:
            *out = (Inst*)realloc(*out, sizeof(Inst) * (*pc + 1));
            (*out)[*pc].opecode  = OP_Char;
            (*out)[*pc].operand1 = node->value;
            (*out)[*pc].operand2 = 0;
            (*pc)++;
            break;
        case ND_Union:
            *out = (Inst*)realloc(*out, sizeof(Inst) * (*pc + 1));
            (*out)[*pc].opecode  = OP_Split;
            (*out)[*pc].operand1 = *pc + 1;

            tmp1 = *pc;
            (*pc)++;

            compile_node(node->chd[0], out, pc);

            *out = (Inst*)realloc(*out, sizeof(Inst) * (*pc + 1));
            (*out)[*pc].opecode  = OP_Jump;
            (*out)[*pc].operand2 = 0;

            tmp2 = *pc;
            (*pc)++;

            compile_node(node->chd[1], out, pc);

            (*out)[tmp1].operand2 = tmp2 + 1;
            (*out)[tmp2].operand1 = *pc;

            break;
        case ND_Star:
            *out = (Inst*)realloc(*out, sizeof(Inst) * (*pc + 1));
            (*out)[*pc].opecode = OP_Split;
            (*out)[*pc].operand1 = *pc + 1;

            tmp1 = *pc;
            (*pc)++;

            compile_node(node->chd[0], out, pc);

            *out = (Inst*)realloc(*out, sizeof(Inst) * (*pc + 1));
            (*out)[*pc].opecode  = OP_Jump;
            (*out)[*pc].operand1 = tmp1;
            (*out)[*pc].operand2 = 0;

            (*pc)++;

            (*out)[tmp1].operand2 = *pc;

            break;
        case ND_Concat:
            compile_node(node->chd[0], out, pc);
            compile_node(node->chd[1], out, pc);
            break;
        case ND_Empty:
            break;
    }
}


/****************************************
 * 構文解析器
 ****************************************/
void parse(char[], Node**);
Node* parse_exp(char**);
Node* parse_subexp(char**);
Node* parse_factor(char**);
Node* parse_seq(char**);
Node* parse_subseq(char**);
Node* parse_star(char**);

void parse(char regexp[], Node** out) {
    char* it;

    if (*out != NULL) free(*out);

    it = regexp;

    *out = parse_exp(&it);
}

Node* parse_exp(char** it) {
    Node* node;

    node = parse_subexp(it);

    if (**it != '\0') printf("unexpected %c, expected EOF\n", **it);

    return node;
}

Node* parse_subexp(char** it) {
    Node* node;
    Node* node1;
    Node* node2;

    node = parse_subseq(it);

    if (**it == '|') {
        (*it)++;
        node1 = node;
        node2 = parse_subexp(it);
        node  = new_node();
        node->type = ND_Union;
        add_chd(node, node1);
        add_chd(node, node2);
    }

    return node;
}

Node* parse_factor(char** it) {
    Node* node;

    if (**it == '(') {
        (*it)++;
        node = parse_subexp(it);
    } else {
        node = new_node();
        node->type = ND_Char;
        node->value = **it;
    }

    (*it)++;

    return node;
}

Node* parse_seq(char** it) {
    Node* node;

    if (**it == '(' || (**it != '|' && **it != ')' && **it != '*' && **it != '\0')) {
        return parse_subseq(it);
    }

    node = new_node();
    node->type = ND_Empty;

    return node;
}

Node* parse_subseq(char** it) {
   Node* node;
   Node* node1;
   Node* node2;

   node = parse_star(it);
   if (**it == '(' || (**it != '|' && **it != ')' && **it != '*' && **it != '\0')) {
       node1 = node;
       node2 = parse_subseq(it);
       node  = new_node();
       node->type = ND_Concat;
       add_chd(node, node1);
       add_chd(node, node2);
   }

    return node;
}

Node* parse_star(char** it) {
    Node* node;
    Node* tmp;

    node = parse_factor(it);

    if (**it == '*') {
        tmp = node;
        node = new_node();
        node->type = ND_Star;
        add_chd(node, tmp);

        (*it)++;
    }

    return node;
}


/****************************************
 * VM
 ****************************************/

typedef struct {
    int pc;
    char* sp;
} Context;

typedef struct {
    Context ctx;
    Inst* mem;
} VM;

VM* new_vm();
int run(VM*);

VM* new_vm() {
    VM* vm = (VM*)malloc(sizeof(VM));

    vm->ctx.pc = 0;
    vm->ctx.sp = 0;
    vm->mem = NULL;

    return vm;
}

int run(VM* vm) {
    Context ctx;
    Inst* inst = vm->mem + vm->ctx.pc;

    switch(inst->opecode) {
        case OP_Jump:
            vm->ctx.pc = inst->operand1 - 1;
            break;
        case OP_Split:
            ctx = vm->ctx;
            vm->ctx.pc = inst->operand1;
            if (run(vm)) return 1;

            vm->ctx = ctx;
            vm->ctx.pc = inst->operand2;
            if (run(vm)) return 1;
            return 0;
        case OP_Char:
            if (*vm->ctx.sp == inst->operand1) {
                vm->ctx.sp++;
            } else {
                return 0;
            }
            break;
        case OP_Match:
            return 1;
    }

    vm->ctx.pc++;

    return run(vm);
}

/****************************************
 * main関数 
 ****************************************/

int main(int argc, char** argv) {
    Node* ast  = NULL;
    Inst* code = NULL;
    VM vm;
    int size;

    vm.ctx.sp = argv[1];
    
    printf("Text: %s, Pattern: %s\n\n", argv[1], argv[2]);

    parse(argv[2], &ast);

    printf("SYNTAX TREE:\n");
    print_tree(ast, 0);

    size = compile(ast, &code);

    printf("COMPILED CODE:\n");
    print_code(code, size);

    vm.mem = code;

    printf("TEST:\n");
    if (run(&vm)) {
        printf("Match!\n");
    }

    free_tree(ast);
    free(code);
}

MJHD

エモさ駆動開発

簡単な正規表現エンジンを書いた