语法分析

在本章中，我们将学习如何使用 mpc 库来构建一个语法解析器。这是构建 Lisp 解释器的关键一步——我们需要将用户输入的文本转化为计算机可以理解的结构化数据。

为了验证 mpc 的威力，本章我们尝试实现一个简单的语法解析器——波兰表达式（Polish Notation），它是我们将要实现的 Lisp 的数学运算部分。

波兰表达式的语法规则可以用白话文描述：

• 程序：由一个操作符加上一个或多个表达式组成
• 表达式：可以是一个数字，或者是包裹在圆括号中的一个操作符加上一个或多个表达式
• 操作符：+、-、*、/
• 数字：可选的负号 - 后面跟着一个或多个数字字符

在表示数字和程序规则时，我们需要用到正则表达式。正则表达式适合定义一些小型的语法规则，例如单词或是数字等。

在 mpc 中，我们需要将正则表达式包裹在一对 / 中。例如，Number 可以用 /-?[0-9]+/ 来表示。

在编写语法解析器之前，我们需要安装 mpc 库。你可以从 mpc 项目主页 下载 mpc.h 和 mpc.c，放到你的源文件同目录下。

cc -std=c99 -Wall parsing.c mpc.c -ledit -lm -o parsing

cc -std=c99 -Wall parsing.c mpc.c -o parsing

下面是波兰表达式最终的语法规则：

/* Create Some Parsers */
mpc_parser_t* Number   = mpc_new("number");
mpc_parser_t* Operator = mpc_new("operator");
mpc_parser_t* Expr     = mpc_new("expr");
mpc_parser_t* Lispy    = mpc_new("lispy");

/* Define them with the following Language */
mpca_lang(MPCA_LANG_DEFAULT,
  "                                                     \
    number   : /-?[0-9]+/ ;                             \
    operator : '+' | '-' | '*' | '/' ;                  \
    expr     :  | '('  + ')' ;  \
    lispy    : /^/  + /$/ ;             \
  ",
  Number, Operator, Expr, Lispy);

在 main 函数的最后，还需要将使用完毕的解析器删除：

/* Undefine and Delete our Parsers */
mpc_cleanup(4, Number, Operator, Expr, Lispy);

现在我们可以使用解析器来解析用户的每一条输入。将之前的 printf 语句替换成下面的代码：

/* Attempt to Parse the user Input */
mpc_result_t r;
if (mpc_parse("", input, Lispy, &r)) {
  /* On Success Print the AST */
  mpc_ast_print(r.output);
  mpc_ast_delete(r.output);
} else {
  /* Otherwise Print the Error */
  mpc_err_print(r.error);
  mpc_err_delete(r.error);
}

Lispy Version 0.0.0.0.2
Press Ctrl+c to Exit

lispy> + 5 (* 2 2)
>
  regex
  operator|char:1:1 '+'
  expr|number|regex:1:3 '5'
  expr|>
    char:1:5 '('
    operator|char:1:6 '*'
    expr|number|regex:1:8 '2'
    expr|number|regex:1:10 '2'
    char:1:11 ')'
  regex
lispy> hello
:1:1: error: expected whitespace, '+', '-', '*' or '/' at 'h'