parse.js 的核心思路

好，我来详细解释 parse.js 怎么写。

parse.js 的核心思路

先理解数据流

用户输入文本
    ↓  sexp.ts 的 parser.parse()
syntax[]   ← 通用 S-expression 树（不懂 UTLC）
    ↓  我们写的 parse_expr()
exp AST    ← UTLC 专用 AST（懂语法规则）+ 错误列表

syntax[] 长什么样？

拿具体例子说明：输入 (lambda (x) x)

parser.parse() 返回：
[
  group {
    children: [
      atom { leaf: token("(") }        ← 下标 0: 左括号
      atom { leaf: token("lambda") }   ← 下标 1: 标识符 lambda
      atom { leaf: token(" ") }        ← 下标 2: 空格 (space)
      group {                          ← 下标 3: (x) 这个括号组
        children: [
          atom("("),
          atom("x"),
          atom(")")
        ]
      }
      atom { leaf: token(" ") }        ← 下标 4: 空格
      atom { leaf: token("x") }        ← 下标 5: body
      atom { leaf: token(")") }        ← 下标 6: 右括号
    ]
  }
]

关键点： group.children 里包含了括号 token 本身（第一个和最后一个），而且空白也在里面。

过滤噪音 → 提取"有意义的子节点"

写一个辅助函数，把 children 里的括号和空白都过滤掉：

// 从 group.children 里取出有意义的节点（去掉括号 token 和空白）
function meaningful_children(group) {
  return group.children.filter(child => {
    // 跳过空白
    if (child.tag === syntax.tag.atom && child.leaf.kind === token.kind.atom.space) {
      return false
    }
    // 跳过括号 token（group 的第一个和最后一个 children 是括号）
    if (child.tag === syntax.tag.atom) {
      const k = child.leaf.kind
      if (k === token.kind.parenthesis.left || k === token.kind.parenthesis.right) {
        return false
      }
    }
    return true
  })
}

过滤后，(lambda (x) x) 的 meaningful_children 就变成：

[ atom("lambda"),  group((x)),  atom("x") ]
   index 0          index 1      index 2

parse_expr 的决策树

输入一个 syntax 节点，判断 tag：

├── tag == atom
│   ├── 是空白 → 跳过（返回 null）
│   └── 是标识符 → 返回 var_ { name: "x" }
│
├── tag == lone  → 孤立括号，push 错误，返回 null
│
├── tag == mismatch → 括号不匹配，push 错误，返回 null
│
└── tag == group
    取 meaningful_children(group) → items[]
    ├── items[0] 是 atom("lambda")
    │   ├── items.length == 3 → abs { param: items[1], body: parse_expr(items[2]) }
    │   │   还要验证 items[1] 是一个 group，里面只有一个标识符
    │   ├── items.length < 3  → 错误：lambda 缺少参数
    │   └── items.length > 3  → 错误：lambda 参数过多
    │
    └── 否则（普通 application）
        ├── items.length == 2 → app { func: parse_expr(items[0]), arg: parse_expr(items[1]) }
        ├── items.length < 2  → 错误：application 缺少函数或参数
        └── items.length > 2  → 错误：application 参数过多

实际代码骨架

// parse.js (CommonJS)
const { parser, syntax, token } = require('./sexp.js')  // 编译后的 sexp

/**
 * @typedef {{ tag: 'var_', name: string, range: range }} VarExp
 * @typedef {{ tag: 'abs', param: string, body: Exp, range: range }} AbsExp
 * @typedef {{ tag: 'app', func: Exp, arg: Exp, range: range }} AppExp
 * @typedef {VarExp | AbsExp | AppExp} Exp
 *
 * @typedef {{ range: range, message: string }} ParseError
 */

/**
 * 过滤 group.children 中的括号和空白
 */
function meaningful_children(group_node) {
  return group_node.children.filter(child => {
    if (child.tag !== syntax.tag.atom) return true  // 非 atom 节点（group/lone/mismatch）保留
    const k = child.leaf.kind
    // 过滤空白
    if (k === token.kind.atom.space) return false
    // 过滤括号
    if (k === token.kind.parenthesis.left)  return false
    if (k === token.kind.parenthesis.right) return false
    return true
  })
}

/**
 * DFS 解析单个 syntax 节点为 exp
 * @param {import('./sexp').syntax} node
 * @param {ParseError[]} errors  - 收集错误（副作用）
 * @returns {Exp | null}
 */
function parse_expr(node, errors) {
  switch (node.tag) {

    case syntax.tag.atom: {
      const k = node.leaf.kind
      if (k === token.kind.atom.space) return null  // 空白，跳过
      // 普通标识符 → variable
      return {
        tag: 'var_',
        name: token.to_span(node.leaf, /* text */ ),  // 需要传入原始 text
        range: token.to_range(node.leaf)
      }
    }

    case syntax.tag.lone: {
      errors.push({
        range: token.to_range(node.leaf),
        message: `孤立的括号 '${token.to_span(node.leaf, text)}'`
      })
      return null
    }

    case syntax.tag.mismatch: {
      const open = syntax.open(node)
      errors.push({
        range: token.to_range(open),
        message: '括号不匹配'
      })
      return null
    }

    case syntax.tag.group: {
      const items = meaningful_children(node)
      // items[0] 是 lambda？
      if (items.length > 0
          && items[0].tag === syntax.tag.atom
          && token.to_span(items[0].leaf, text) === 'lambda') {

        // (lambda (binder) body) → 期望 items 有 3 个：lambda, (binder), body
        if (items.length !== 3) {
          errors.push({
            range: token.to_range(syntax.open(node)),
            message: `lambda 需要恰好 2 个参数 (binder 和 body)，实际得到 ${items.length - 1} 个`
          })
          return null
        }

        // items[1] 应该是 (binder) 这个 group
        const binder_group = items[1]
        if (binder_group.tag !== syntax.tag.group) {
          errors.push({
            range: ???,  // 用 items[1] 的 range
            message: 'lambda 的 binder 必须是 (binder) 格式'
          })
          return null
        }
        const binder_items = meaningful_children(binder_group)
        if (binder_items.length !== 1 || binder_items[0].tag !== syntax.tag.atom) {
          errors.push({ ... , message: 'binder 必须是单个标识符' })
          return null
        }

        const param_name = token.to_span(binder_items[0].leaf, text)
        const body = parse_expr(items[2], errors)

        return { tag: 'abs', param: param_name, body, range: ... }
      }

      // 普通 application (func arg)
      if (items.length < 2) {
        errors.push({ ..., message: 'application 需要至少一个函数和一个参数' })
        return null
      }
      if (items.length > 2) {
        errors.push({ ..., message: 'application 只接受一个参数' })
        return null
      }

      const func = parse_expr(items[0], errors)
      const arg  = parse_expr(items[1], errors)
      return { tag: 'app', func, arg, range: ... }
    }
  }
}

/**
 * 顶层入口：解析整段文本
 */
function parse(text) {
  const p = parser.make(text)
  const tree = parser.parse(p)  // syntax[]
  const errors = []
  const exprs = tree
    .map(node => parse_expr(node, errors, text))
    .filter(e => e !== null)
  return { exprs, errors }
}

module.exports = { parse }

一个具体的错误例子

输入 (lambda x x) ← binder 没有括号

parse_expr(group) 被调用
  items = [atom("lambda"), atom("x"), atom("x")]
  items.length === 3  ✓
  items[1] = atom("x")  ← 不是 group！
  → push error: "lambda 的 binder 必须是 (binder) 格式"
  → return null

需要注意的一个坑

token.to_span(token, text) 需要传入原始文本字符串 text，因为 token 只存了偏移量，实际内容要从原文里截取。所以 parse_expr 需要把 text 作为参数一路传下去（或者闭包捕获）。

明白了吗？有哪部分想深入聊的？