主页 / coding / 问题 / 79240503
Accepted
Dendrit
Asked: 2024-12-01 05:10:39 +0800 CST

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

  • 772

我正在用 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 ')'

我已经为相同语法编写了解析器，但没有第 4 条生成规则。但我该如何处理{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");
}
parsing

1 个回答

  1. Best Answer

    您可以添加一个参数来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);
  }
}

    没有额外的参数？

    ...然后创建该函数的两个版本：

    Ast *parse_if_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);
  }
  return NULL; // No primitive here
}

Ast *parse_primitive(Lexer *lexer) {
  Ast *primitive = parse_if_primitive(lexer);
  if (!primitive) {
    parser_error("expected '(', number or var");
  }
  return primitive;
}

    然后拨打您需要的电话：

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

相关问题