主页 / user-28564964

Dendrit's questions

Martin Hope
Dendrit
Asked: 2024-12-01 05:10:39 +0800 CST
  • 5

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