使用递归下降解析扩展 lambda 演算

Question

我正在用 C 语言编写基于简单 lambda 演算的语言的解释器。语言的 EBNF 是

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

我已经为相同的语法编写了解析器，但没有第四条产生式规则。但我该如何应对

{P}

？

当然，我可以只检查先行标记，如果它是 var、number 或 '('，则调用解析 P 的过程（例如

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) { /* i want to remove this check as if is actually done by 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");
}

Answer 1

您可以向

parse_primitive

添加一个参数来指示该原语是必需的还是可选的。如果它是可选的，则在不匹配时不要引发错误，而是返回

NULL

:

Ast *parse_primitive(Lexer *lexer, int mandatory) {
  if (lexer_match(lexer, TOK_LPAR)) {
    Ast *expr = parse_expr(lexer);
    if (!lexer_match(lexer, TOK_RPAR)) {
      // Here we unconditionally raise an error, as the opening bracket
      //    made the closing bracket mandatory.
      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);
  }
  // Conditionally raise an error
  if (mandatory) {
    parser_error("expected '(', number or var");
  }
  return NULL;
}

现在您的

parse_factor

函数可以如下所示：

Ast *parse_factor(Lexer *lexer) {
  Ast *factor = parse_primitive(lexer, 1); // Mandatory
  for (;;) {
    Ast *primitive = parse_primitive(lexer, 0); // Not mandatory
    if (!primitive) {
      return factor;
    }
    factor = make_app(factor, primitive);
  }
}