micro-parser-combinators

2026/04/22 00:00:00·2026/05/19 10:23:00

简而言之，MPC就是一个语法解释器。其最主要的作用是用来设计新的编程语言，或者是用来解释一个己经存在的编程语言。

初印象

以下代码用来给读者带来一个对 mpc 的初印象：

//新的语法元素
mpc_parser_t *Expr  = mpc_new("expression");
mpc_parser_t *Prod  = mpc_new("product");
mpc_parser_t *Value = mpc_new("value");
mpc_parser_t *Maths = mpc_new("maths");

//新的语法结构
mpca_lang(MPCA_LANG_DEFAULT,
  " expression : <product> (('+' | '-') <product>)*; "
  " product    : <value>   (('*' | '/')   <value>)*; "
  " value      : /[0-9]+/ | '(' <expression> ')';    "
  " maths      : /^/ <expression> /$/;               ",
  Expr, Prod, Value, Maths, NULL);

mpc_result_t r;

if (mpc_parse("input", input, Maths, &r)) {
  mpc_ast_print(r.output);
  mpc_ast_delete(r.output);
} else {
  mpc_err_print(r.error);
  mpc_err_delete(r.error);
}

mpc_cleanup(4, Expr, Prod, Value, Maths);

Ast

Abstract syntax tree, 被存放在 mpca_* 命名域下。所有的 fold 与 destructor 都是内置的。

syntax	requirement
"ab"	"ab"
'a&39;	a
'a&39; 'b&39;	先要 a, 然后要 b
`'a' \| 'b'`	a 或 b
'a&39;+
'a&39;?	a 或什么都没有
'a&39;{x}	x 个 a
<expr>

typedef struct mpc_ast_t {
  char* tag;
  char* contents;
  mpc_state_t state;
  int children_num;
  struct mpc_ast_t** children;
} mpc_ast_t;

tag: 如：expr|number|regex contents: 结点的真实内容 '*&39; '(&39; '5&39; state: line number, column number chidren, children_num: 邦助我们可以遍历整棵树

Parsing

有了这些基本解析器之后，就可以对输入内容进行解析了。解析完以后会得到一个结果 =mpc_result_t=，结果的定义如下：

typedef union {
  mpc_err_t *error;
  mpc_val_t *output;
} mpc_result_t;

有以下几个函数可以被用来运行 parser:

int mpc_parse(const char *filename, const char *string, mpc_parser_t *p, mpc_result_t *r);
// 解析一个 string, 如：mpc_parse("<stdin>", input, Lispy, &r) ss
int mpc_parse_file(const char *filename, FILE *file, mpc_parser_t *p, mpc_result_t *r);
// 解析一个文件？？与解析文件的内容的区别在哪
int mpc_parse_pipe(const char *filename, FILE *pipe, mpc_parser_t *p, mpc_result_t *r);
//解析一个管道，如 stdin
int mpc_parse_contents(const char *filename, mpc_parser_t *p, mpc_result_t *r);
//解析一个文件的内容

Combinators

Combinator 同时取多个 parsers, 并且返回一个新的 parser.

C 语言使用手动内存管理，而如果解析过程中解析器失败，那么就需要清理所有过程中存储的变量。C 语方必须显式传入 destructor 为输入，从而清理收的数据。

mpc_parser_t *mpc_expect(mpc_parser_t *a, const char *e);
mpc_parser_t *mpc_expectf(mpc_parser_t *a, const char *fmt, ...);
// 成功就返回一个执行 a 的解析器，失败则告知本应得到什么（e）
mpc_parser_t *mpc_apply(mpc_parser_t *a, mpc_apply_t f);
mpc_parser_t *mpc_apply_to(mpc_parser_t *a, mpc_apply_to_t f, void *x);
// 对 a 的结果进行 f 处理
mpc_parser_t *mpc_check(mpc_parser_t *a, mpc_dtor_t da, mpc_check_t f, const char *e);
mpc_parser_t *mpc_check_with(mpc_parser_t *a, mpc_dtor_t da, mpc_check_with_t f, void *x, const char *e);
mpc_parser_t *mpc_checkf(mpc_parser_t *a, mpc_dtor_t da, mpc_check_t f, const char *fmt, ...);
mpc_parser_t *mpc_check_withf(mpc_parser_t *a, mpc_dtor_t da, mpc_check_with_t f, void *x, const char *fmt, ...);
// 将 f 施加到 a 的结果上，如果其值为 0，那就失败，并返回错误信息 e ，并使用 df 销毁。如果返回非零值，那就返回 a
mpc_parser_t *mpc_not(mpc_parser_t *a, mpc_dtor_t da);
mpc_parser_t *mpc_not_lift(mpc_parser_t *a, mpc_dtor_t da, mpc_ctor_t lf);
//Returns a parser with the following behaviour. If parser a succeeds, then it fails and consumes no input. If parser a fails, then it succeeds, consumes no input and returns NULL (or the result of lift function lf). Destructor da is used to destroy the result of a on success.
mpc_parser_t *mpc_maybe(mpc_parser_t *a);
mpc_parser_t *mpc_maybe_lift(mpc_parser_t *a, mpc_ctor_t lf);
//Returns a parser that runs a. If a is successful then it returns the result of a. If a is unsuccessful then it succeeds, but returns NULL (or the result of lf).
mpc_parser_t *mpc_many(mpc_fold_t f, mpc_parser_t *a);
mpc_parser_t *mpc_or(int n, ...);
mpc_parser_t *mpc_and(int n, mpc_fold_t f, ...);

函数类型

有用的函数

这些函数被写在 mpcf* 命名空间中，如 mpcf_strfold

mpc_val_t *strfold(int n, mpc_val_t **xs) {
  char *x = calloc(1, 1);
  int i;
  for (i = 0; i < n; i++) {
    x = realloc(x, strlen(x) + strlen(xs[i]) + 1);
    strcat(x, xs[i]);
    free(xs[i]);
  }
  return x;
}

正则

mpc_parser_t *ident = mpc_re("[a-zA-Z_][a-zA-Z_0-9]*");

/* Do Some Parsing... */

mpc_delete(ident);