Cで作るPEGパーザコンビネータ

これまでPEGパーザコンビネータ作ってきた言語は、全て、レキシカルスコープの無名関数やそれに類似の機能を持っていたため、容易に作ることができましたが、C言語には無名関数のような機能が無いため、ちょっと頭をひねりました。とりあえず作ることを優先させたので、メモリ管理とか、ライブラリとしての再利用しやすいようにヘッダファイルに宣言を適切に分離するとか一切考慮してません。たとえば、動的なメモリ確保は、mallocした後、そのまま放置で、freeしてません。あと、C言語は普段使わないので、C言語バリバリに使っている方からすると、メモリ管理とか以外の基本的なところで、ツッコミどころ満載な気もするので、その辺も指摘していただければと思います。

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

#define RULE(name) Parser* name = proxy(NULL)
#define DEFINE(name, expr) name->env[0] = expr

typedef enum {SUCCESS, FAILURE} Status;
/* VALUE_CHAR, VALUE_FLOAT とかも必要に応じて追加する */
typedef enum {VALUE_INT, VALUE_DOUBLE, VALUE_REF} ValueKind;
typedef char* Input;

typedef struct {
  ValueKind kind;
  union {
    int v_int;
    double v_double;
    void* v_ref;
  };
} Value;

typedef struct List {
  Value value;
  struct List* next;
} List;

typedef struct {
  Value _1;
  Value _2;
} Pair;

typedef struct {
  Status status;
  Value value;
  Input rest;
} ParseResult;

typedef struct Parser Parser;

typedef ParseResult (*ParseFunction)(Parser* self, Input input);

typedef struct {
  Parser* (*action)(Value value);
} BindWrapper;

struct Parser {
  void** env;
  ParseFunction parse;
};

BindWrapper* BindWrapper_new(Parser* (*f)(Value value));
List* List_cons(Value value, List* next);
ParseResult Parser_parse(Parser* p, Input input);
Parser* Parser_new1(void* item, ParseFunction f);
Parser* Parser_new2(void* item1, void* item2, ParseFunction f);
Value Value_int(int v);
Value Value_double(double v);
Value Value_ref(void* v);
Value* Value_new(Value v);
Pair* Pair_new(Value _1, Value _2);

Parser* proxy(Parser* target);
Parser* ret(Value value);
Parser* str(char* param);
Parser* seq(Parser* p1, Parser* p2);
Parser* alt(Parser* p1, Parser* p2);
Parser* opt(Parser* p);
Parser* rep(Parser* p);
Parser* rep1(Parser* p);
Parser* not(Parser* p);
Parser* and(Parser* p);
Parser* bind(Parser* p, Parser* (*action)(Value value));

BindWrapper* BindWrapper_new(Parser* (*action)(Value value)) {
  BindWrapper* self = malloc(sizeof(BindWrapper));
  self->action = action;
  return self;
}

List* List_cons(Value value, List* next) {
  List* self = malloc(sizeof(List));
  self->value = value;
  self->next = next;
  return self;
}

Value Value_int(int v) {
  Value value;
  value.kind = VALUE_INT;
  value.v_int = v;
  return value;
}

Value Value_double(double v) {
  Value value;
  value.kind = VALUE_DOUBLE;
  value.v_double = v;
  return value;
}

Value Value_ref(void* v) {
  Value value;
  value.kind = VALUE_REF;
  value.v_ref = v;
  return value;
}

Value* Value_new(Value v) {
  Value* new_v = malloc(sizeof(Value));
  *new_v = v;
  return new_v;
}

Pair* Pair_new(Value _1, Value _2) {
  Pair* self = malloc(sizeof(Pair));
  self->_1 = _1;
  self->_2 = _2;
  return self;
}

ParseResult Parser_parse(Parser* p, Input input) { 
  return p->parse(p, input); 
}

ParseResult ParseResult_SUCCESS(Value value, Input rest) {
  ParseResult result = {SUCCESS, value, rest};
  return result;
}

ParseResult ParseResult_FAILURE(Value value, Input rest) {
  ParseResult result = {FAILURE, value, rest};
  return result;
}

Parser* Parser_new1(void* item, ParseFunction f) {
  Parser* self = malloc(sizeof(Parser));
  self->env = malloc(sizeof(void*));
  self->env[0] = item;
  self->parse = f;
  return self;
}

Parser* Parser_new2(void* item1, void* item2, ParseFunction f) {
  Parser* self = malloc(sizeof(Parser));
  self->env = malloc(sizeof(void*) * 2);
  self->env[0] = item1;
  self->env[1] = item2;
  self->parse = f;
  return self;
}

static ParseResult parse_proxy(Parser* p, Input input) {
  return Parser_parse((Parser*)p->env[0], input);
}

static ParseResult parse_ret(Parser* p, Input input) {
  return ParseResult_SUCCESS(*((Value*)p->env[0]), input);
}

static ParseResult parse_str(Parser* p, Input input) {
  char* param = p->env[0];
  int len = strlen(param);
  if(!strncmp(input, param, len)) {
    return ParseResult_SUCCESS(Value_ref(param), input + len);
  }
  return ParseResult_FAILURE(Value_ref(NULL), input);
}

static ParseResult parse_rep(Parser* p, Input input) {
  List* result = NULL;
  while(1) {
    ParseResult r = Parser_parse((Parser*)p->env[0], input);
    if(r.status == FAILURE) {
      return ParseResult_SUCCESS(Value_ref(result), r.rest);
    }
    result = List_cons(r.value, result);
    input = r.rest;
  }
}

static ParseResult parse_not(Parser* p, Input input) {
  ParseResult r = Parser_parse((Parser*)p->env[0], input);
  return r.status == FAILURE ? 
    ParseResult_SUCCESS(Value_ref(NULL), input) :
    ParseResult_FAILURE(Value_ref(NULL), input);
}

static ParseResult parse_seq(Parser* p, Input input) {
  ParseResult r1 = Parser_parse((Parser*)p->env[0], input);
  if(r1.status == FAILURE) return r1;
  ParseResult r2 = Parser_parse((Parser*)p->env[1], r1.rest);
  if(r2.status == FAILURE) return r2;
  return ParseResult_SUCCESS(Value_ref(Pair_new(r1.value, r2.value)), r2.rest);
}

static ParseResult parse_alt(Parser* p, Input input) {
  ParseResult r = Parser_parse((Parser*)p->env[0], input);
  if(r.status == SUCCESS) return r;
  return Parser_parse((Parser*)p->env[1], input);
}

static ParseResult parse_opt(Parser* p, Input input) {
  ParseResult r = Parser_parse((Parser*)p->env[0], input);
  if(r.status == SUCCESS) return r;
  return ParseResult_SUCCESS(Value_ref(NULL), input);
}

static ParseResult parse_bind(Parser* p, Input input) {
  ParseResult r = Parser_parse((Parser*)p->env[0], input);
  if(r.status == FAILURE) return r;
  return Parser_parse(((BindWrapper*)(p->env[1]))->action(r.value), r.rest);
}

Parser* proxy(Parser* target) {
  return Parser_new1(target, parse_proxy);
}

Parser* ret(Value v) {
  return Parser_new1(Value_new(v), parse_ret);
}

Parser* str(char* param) {
  return Parser_new1(param, parse_str);
}

Parser* seq(Parser* p1, Parser* p2) {
  return Parser_new2(p1, p2, parse_seq);
}

Parser* alt(Parser* p1, Parser* p2) {
  return Parser_new2(p1, p2, parse_alt);
}

Parser* opt(Parser* p) {
  return Parser_new1(p, parse_opt);
}

Parser* rep(Parser* p) {
  return Parser_new1(p, parse_rep);
}

static Parser* pair_cons(Value v) {
  Pair* p = v.v_ref;
  return ret(Value_ref(List_cons(p->_1, p->_2.v_ref)));
}

Parser* rep1(Parser* p) {
  return bind(seq(p, rep(p)), pair_cons);
}

Parser* not(Parser* p) {
  return Parser_new1(p, parse_not);
}

Parser* and(Parser* p) {
  return not(not(p));
}

Parser* bind(Parser* p, Parser* (*action)(Value value)) {
  return Parser_new2(p, BindWrapper_new(action), parse_bind);
}

int main(int argc, char**argv) {
  RULE(S);
  RULE(A);
  RULE(B);
  DEFINE(
      S, seq(and(seq(A, not(str("b")))),
        seq(rep1(str("a")),
          seq(B, not(str("c"))))));
  DEFINE(A, seq(str("a"), seq(opt(A), str("b"))));
  DEFINE(B, seq(str("b"), seq(opt(B), str("c"))));
  if(argc < 2) {
    printf("usage: peg <input_string>\n");
    return 0;
  }
  ParseResult r = Parser_parse(S, argv[1]);
  printf(
      "matching %s ... %s\n", 
      argv[1], r.status == SUCCESS ? "success" : "failure");
  return 0;
}