regexp.c

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

typedef struct _node {
  char c;
  struct _node *tr;
  struct _node *next;
} node;

node *create_node(char c, node *tr, node *next) {
  node *ret = malloc(sizeof(node));
  ret->c = c;
  ret->tr = tr;
  ret->next = next;
  return ret;
}

// -----------------------------------------------------------------------------

// expr   ::= term | term + expr
// term   ::= factor | factor term
// factor ::= atom | atom *
// atom   ::= a-z | (expr)
bool expr(const char **pattern, node **head, node **tail);
bool term(const char **pattern, node **head, node **tail);
bool factor(const char **pattern, node **head, node **tail);
bool atom(const char **pattern, node **head, node **tail);

bool expr(const char **pattern, node **r_head, node **r_tail) {
  node *head1, *tail1;
  bool ret = term(pattern, &head1, &tail1);
  if (!ret) return false;

  if (**pattern == '+') {
    (*pattern)++;

    node *head2, *tail2;
    expr(pattern, &head2, &tail2);

    //            head1   tail1
    // -> O -eps-> O -...-> O -> O -eps->
    //    |                      ^
    //    +--eps-> O -...-> O ---+
    //            head2   tail2

    node *head, *tail;
    head = create_node(-1, head1, create_node(-1, head2, NULL));
    tail = create_node(-1, NULL, NULL);
    tail1->tr = tail;
    tail2->tr = tail;
    *r_head = head;
    *r_tail = tail;
  } else {
    *r_head = head1;
    *r_tail = tail1;
  }
  return true;
}

bool term(const char **pattern, node **r_head, node **r_tail) {
  node *head, *tail;
  bool ret = factor(pattern, &head, &tail);
  if (!ret) return false;

  node *n_head, *n_tail;
  ret = term(pattern, &n_head, &n_tail);
  if (!ret) {
    *r_head = head;
    *r_tail = tail;
  } else {
    tail->tr = n_head;
    *r_head = head;
    *r_tail = n_tail;
  }
  return true;
}

bool factor(const char **pattern, node **r_head, node **r_tail) {
  node *head, *tail;
  bool ret = atom(pattern, &head, &tail);
  if (!ret) return false;

  if (**pattern == '*') {
    (*pattern)++;
    //                     head    tail
    // -> O -eps-> O -eps-> O -...-> O -> O -eps-> O -eps->
    //    |        ^                      |        ^
    //    |        +-----------eps--------+        |
    //    +--------------------eps-----------------+
    tail->tr = create_node(-1, NULL, NULL);
    tail = tail->tr;
    head = create_node(-1, head, NULL);
    tail->next = create_node(-1, head, tail->next);

    //            head                  tail
    // -> O -eps-> O -eps-> O -...-> O -> O -eps-> O -eps->
    //    |        ^                      |        ^
    //    |        +-----------eps--------+        |
    //    +--------------------eps-----------------+
    tail->tr = create_node(-1, NULL, NULL);
    tail = tail->tr;
    head = create_node(-1, head, NULL);
    head->next = create_node(-1, tail, head->next);

    //   head                                    tail
    // -> O -eps-> O -eps-> O -...-> O -> O -eps-> O -eps->
    //    |        ^                      |        ^
    //    |        +-----------eps--------+        |
    //    +--------------------eps-----------------+
  }

  *r_head = head;
  *r_tail = tail;
  return true;
}

bool atom(const char **pattern, node **r_head, node **r_tail) {
  if (**pattern == '(') {
    const char *saved_pos = *pattern;
    (*pattern)++;
    if (expr(pattern, r_head, r_tail)) {
      if (**pattern == ')') {
        (*pattern)++;
        return true;
      }
    }
    *pattern = saved_pos;
    return false;
  } else if ('a' <= **pattern && **pattern <= 'z') {
    node *n = create_node(**pattern, NULL, NULL);
    (*pattern)++;
    *r_head = n;
    *r_tail = n;
    return true;
  }
  return false;
}

// -----------------------------------------------------------------------------

bool match_node(node *n, const char *s) {
  if (n == NULL || *s == '\0') {
    return (n == NULL && *s == '\0');
  }

  while (n != NULL) {
    if (n->c == *s) {
      if (match_node(n->tr, s+1)) return true;
    } else if (n->c == -1) {
      if (match_node(n->tr, s)) return true;
    }
    n = n->next;
  }
  return false;
}

bool match(const char *pattern, const char *str) {
  node *head, *tail;
  if (!expr(&pattern, &head, &tail) || *pattern != '\0') {
    fprintf(stderr, "syntax error\n");
    exit(1);
  } else {
    return match_node(head, str);
  }
}

int main(int argc, char* argv[]) {
  const char *pattern = "(a+b+c+d)*e";
  const char *str = "aaaaaaaaaaaabcde";
  if (match(pattern, str)) {
    printf("'%s' matches '%s'\n", str, pattern);
  } else {
    printf("'%s' does not match '%s'\n", str, pattern);
  }
  return 0;
}