递归下降解析扩展λ演算：处理F::=P{P}产生式的问题

问题背景 #

我正在用C语言编写一个基于简单λ演算的解释器，语言的EBNF文法如下：

S ::= E
E ::= 'fn' var '->' E | T {'+' T} | T {'-' T}
T ::= F {'*' F} | F {'/' F}
F ::= P {P}
P ::= var | number | '(' E ')'

我已经实现了不含第4条产生式（F ::= P {P}）的解析器，但处理{P}部分时，当前的做法是在parse_factor里先检查前瞻token，如果是var、number或(就调用parse_primitive，但这和parse_primitive里的检查重复了，想去掉这个重复的检查。

我的代码如下：

Ast *parse_expr(Lexer *lexer) {
  if (match_token(lexer, TOK_KW_FN)) {
    expect_token(lexer, TOK_VAR);
    char *lexeme = get_last_lexeme(lexer);
    Ast *var = make_var(lexeme);
    expect_token(lexer, TOK_ARROW);
    Ast *body = parse_expr(lexer);
    return make_ast(var, body);
  } else {
    Ast *expr = parse_term(lexer);
    for (;;) {
      int op;
      if (match_token(lexer, TOK_PLUS)) {
        op = OP_ADD;
      } else if (match_token(lexer, TOK_MINUS)) {
        op = OP_SUB;
      } else {
        return expr;
      }
      Ast *term = parse_term(lexer);
      expr = make_binop(op, expr, term);
    }
  }
}

Ast *parse_term(Lexer *lexer) {
  Ast *term = parse_factor(lexer);
  for (;;) {
    int op;
    if (match_token(lexer, TOK_STAR)) {
      op = OP_MUL;
    } else if (match_token(lexer, TOK_SLASH)) {
      op = OP_DIV;
    } else {
      return term;
    }
    Ast *factor = parse_factor(lexer);
    term = make_binop(op, term, factor);
  }
}

Ast *parse_factor(Lexer *lexer) {
  Ast *factor = parse_primitive(lexer);
  for (;;) {
    int tok = lexer_peek(lexer);
    if (tok != TOK_LPAR && tok != TOK_VAR && tok != TOK_NUMBER) { /* 想移除这个重复检查，因为parse_primitive里已经做了 */
      return factor;
    }
    Ast *primitive= parse_primitive(lexer);
    factor = make_app(factor, primitive);
  }
}

Ast *parse_primitive(Lexer *lexer) {
  if (lexer_match(lexer, TOK_LPAR)) {
    Ast *expr = parse_expr(lexer);
    if (!lexer_match(lexer, TOK_RPAR)) {
      parser_error("expected ')'");
    }
    return expr;
  } else if (lexer_match(lexer, TOK_NUMBER)) {
    char *lexeme = get_last_lexeme(lexer);
    return make_number(lexeme);
  } else if (lexer_match(lexer, TOK_VAR)) {
    char *lexeme = get_last_lexeme(lexer);
    return make_var(lexeme);
  }
  parser_error("expected '(', number or var");
}

解决方案 #

核心是把primitive的匹配逻辑集中到一处，避免分散在多个函数里重复判断，提供两种可行方案：

方案1：新增“尝试解析primitive”的函数 #

新增一个不直接报错的try_parse_primitive函数，用于在parse_factor里尝试解析，失败则终止循环：

// 保存/恢复lexer状态的辅助函数，需自行实现（记录位置、行号等信息）
typedef struct {
  int pos;
  int line;
  // 其他需要保存的lexer状态字段
} LexerState;

LexerState lexer_save_state(Lexer *lexer) {
  LexerState state;
  state.pos = lexer->pos;
  state.line = lexer->line;
  return state;
}

void lexer_restore_state(Lexer *lexer, LexerState state) {
  lexer->pos = state.pos;
  lexer->line = state.line;
}

// 返回NULL表示当前token不是合法primitive，不触发报错
Ast *try_parse_primitive(Lexer *lexer) {
  LexerState state = lexer_save_state(lexer);
  
  if (lexer_match(lexer, TOK_LPAR)) {
    Ast *expr = parse_expr(lexer);
    if (!lexer_match(lexer, TOK_RPAR)) {
      lexer_restore_state(lexer, state);
      return NULL;
    }
    return expr;
  } else if (lexer_match(lexer, TOK_NUMBER)) {
    char *lexeme = get_last_lexeme(lexer);
    return make_number(lexeme);
  } else if (lexer_match(lexer, TOK_VAR)) {
    char *lexeme = get_last_lexeme(lexer);
    return make_var(lexeme);
  }
  
  lexer_restore_state(lexer, state);
  return NULL;
}

// 保留原有的parse_primitive，用于必须匹配primitive的场景
Ast *parse_primitive(Lexer *lexer) {
  Ast *ast = try_parse_primitive(lexer);
  if (!ast) {
    parser_error("expected '(', number or var");
  }
  return ast;
}

修改后的parse_factor无需手动检查token：

Ast *parse_factor(Lexer *lexer) {
  Ast *factor = parse_primitive(lexer);
  for (;;) {
    Ast *primitive = try_parse_primitive(lexer);
    if (!primitive) {
      return factor;
    }
    factor = make_app(factor, primitive);
  }
}

方案2：抽离token判断的辅助函数 #

如果不想新增函数，可以把primitive的token判断逻辑抽成一个独立函数，让parse_factor和parse_primitive复用：

bool is_primitive_token(int tok) {
  return tok == TOK_LPAR || tok == TOK_VAR || tok == TOK_NUMBER;
}

修改parse_factor的检查逻辑：

Ast *parse_factor(Lexer *lexer) {
  Ast *factor = parse_primitive(lexer);
  for (;;) {
    int tok = lexer_peek(lexer);
    if (!is_primitive_token(tok)) {
      return factor;
    }
    Ast *primitive= parse_primitive(lexer);
    factor = make_app(factor, primitive);
  }
}

后续扩展primitive类型时，只需要修改is_primitive_token一处即可，避免多处同步修改的遗漏问题。

内容的提问来源于stack exchange，提问作者Dendrit