5.3 递归下降分析

递归下降（recursive descent）在宿主语言中用一组相互调用的函数来写语法分析器（parser），通常一个非终结符对应一个函数。它是手写自顶向下分析：控制流清晰、识别到语法结构时可以立即构造 AST，诊断也能借助当前语义上下文，而不是暴露一个抽象的表格单元。

它不是“写几个 if 就好”。可维护的递归下降语法分析器需要一个可靠的词法单元（token） API、专门整理成可预测形式的文法，以及一条严格约定：每个成功的 parseX 函数返回时，游标（cursor）必须正好停在 X 之后。

先建立小而可信的解析契约

多数语法分析器从词法单元导航原语开始：

peek()                 // 查看当前 token，不消费
previous()             // 最近消费的 token
at(kind)               // peek().kind 是否为 kind
advance()              // 恰好消费一个 token
match(kinds...)        // 若当前 token 属于 kinds，消费一个
expect(kind, message)  // 消费指定 token，否则给出定位错误

语法分析器拥有指向词法单元流的游标，流最后应有 EOF。expect 是最有价值的操作：它集中处理词法单元消费、源码范围和“期待 X，实际得到 Y”的诊断。除非恢复策略明确规定如何同步，否则期待失败后不应悄悄返回凭空构造的节点。

对下面的语句文法：

Stmt -> let IDENT = Expr ; | print Expr ;

分发逻辑可以直接表达预测：

parseStmt(): Stmt {
  if (match(LET)) {
    const name = expect(IDENT, "expected a variable name after 'let'");
    expect(EQUAL, "expected '=' after variable name");
    const value = parseExpr();
    expect(SEMICOLON, "expected ';' after variable declaration");
    return LetStmt(name, value);
  }
  if (match(PRINT)) return PrintStmt(parseExprThenSemicolon());
  throw error(peek(), "expected a statement");
}

该分支是安全的，因为两个候选右部的 FIRST 集互不相交，函数不需要猜测或回溯。

用循环表达左结合，而不是保留左递归

自然写出的 Expr -> Expr + Term | Term 是左递归；parseExpr() 会在尚未消费词法单元时再次调用自己，结果是无限递归，而不是左结合。第 4 章的文法变换可以消除这种形式，但源代码能用循环更直接地构造所需的 AST：

parseExpr(): Expr {
  let left = parseTerm();
  while (match(PLUS, MINUS)) {
    const operator = previous();
    const right = parseTerm();
    left = Binary(left, operator, right);
  }
  return left;
}

对 a - b - c，第一次循环生成 Binary(a, -, b)；第二次把它作为 left，生成 Binary(Binary(a, -, b), -, c)。代码在不保留左递归的情况下维护了左结合。像幂运算那样的右结合运算符通常在同一优先级层递归解析右侧。

这也说明语法识别与 AST 形状可以分离。文法可能有 ExprTail 这类辅助非终结符，但 AST 通常不应保留它们。它们存在是为了预测，不是为了成为语义模型的一部分。

候选、重复与安全 lookahead

三种常见文法形状可以直接映射到语法分析器代码：

• FIRST 集互不相交的候选，用 peek().kind 上的 if 或 switch。

• 可选片段，用它自身 FIRST 集作守卫的 if。

• 重复，用确实能启动下一次迭代的词法单元作守卫的 while。

对参数列表，分隔符必须设计得精确：

Args -> Expr ( , Expr )* | epsilon

parseArgs(): Expr[] {
  const args = [];
  if (at(RPAREN)) return args;
  do {
    args.push(parseExpr());
  } while (match(COMMA));
  return args;
}

空列表由 RPAREN 选择，而不是“parseExpr 失败时就当作空列表”。这个差别能避免把 f(,x) 误当成空参数列表，再在更晚的地方给出难懂的错误。

普通语言语法分析器不要盲目回溯。它会掩盖文法二义性、重复工作，并让诊断取决于最后一次失败的推测路径。若确实需要复杂前缀共享或表达式优先级，应有意识地选用普拉特解析（Pratt）、更多向前看的 LL、受控回溯的语法分析器组合子（parser combinator），或第 6 章的 LR 家族。

明确游标契约

每个 parseX 应说明起点、返回节点和成功后的游标。parseArgs 在 ) 开始才是空列表；在 , 开始不是空，而是错误。这个区分避免把 f(,x) 悄悄改读成 f()，再把错误怪到后面的 x。

left-associative repetition 用 loop；只有 recursive call 先消费输入时才递归。这条简单规则能抓住大多数无限递归 bug。