守株阁

DFA 和 NFA 都只有有限状态。状态数量再多，也仍然是有限的。它们适合识别固定模式、分支和重复，但面对任意深度的嵌套结构时会遇到硬边界。 括号匹配就是最小例子。()、(())、(()()) 都合法，(()、())、)( 都非法。有限状态机可以识别“最多三层括号”“最多十层括号”，但只要深度没有上限，有限状态就不够用了。机器需要一种能随输入增长的记忆结构。 下推自动机（Pushdown Automaton，PDA）给有限状态机加了一只栈。状态仍然有限，但栈可以随着输入增长。读到左括号就压栈，读到右括号就弹栈；输入结束后，栈如果回到底部符号，括号就匹配完成。 栈解决的是后进先出问题 括号嵌套天然是后进先出结构。最近打开的左括号，必须最先被右括号关闭。 123456789(()())1234561: push (2: push (3: pop (4: push (5: pop (6: pop ( 第 2 个字符打开的括号，要在第 3 个字符关闭；第 4 个字符打开的括号，要在第 5 个字符关闭；第 1 个字符打开的括号最后关闭。这个顺序正好是栈。 有限状态机无法保存任意多个...

DFA 和 NFA 已经把“字符串识别”拆成了状态、输入字符、转移规则和接受状态。正则表达式站在更高一层：开发者写 a(b|c)*，机器负责把它变成可以执行的匹配过程。 这篇文章只处理传统正则表达式的核心结构：字面量、连接、选择和重复。现代正则 API 还包含捕获组、环视、反向引用、贪婪/非贪婪策略等扩展；这些扩展属于工程实现层，不影响本文要展示的主线。 核心链路很短： 1regex text -> regex AST -> NFA design -> accepts(text) 本文不写正则 parser，直接手工构造 AST。前面文章已经展示过“字符串到 AST”的方法，这里把注意力放在第二步：一个正则 AST 节点怎样编译成 NFA。 正则表达式先变成结构 a(b|c)* 不是一串神秘字符。按传统正则语义，它可以拆成四种结构。 正则片段 AST 节点 含义 a Literal("a") 匹配一个字符 bc Concatenate(Literal("b"), Literal("c"...

DFA 每次只处在一个状态里。读取一个字符，规则表给出唯一的下一个状态。这个约束让 DFA 很容易实现，也让它的执行轨迹很干净：current_state + character -> next_state。 非确定性有限自动机（Nondeterministic Finite Automaton，NFA）放宽了这个约束。同一个状态读取同一个字符时，可以走到多个下一状态；机器还可以在不消耗字符的情况下移动到别的状态。NFA 的实现方式并不神秘：把“当前状态”从单个值改成一个集合，一次保留所有可能路径。 这篇文章用 Python 写一个 NFA，识别两个字符串：ab 和 ba。这个示例足够小，但能完整覆盖 NFA 的两个核心机制：分支和空转移。 非确定性不是随机 “非确定性”容易被误解成机器随机选择一条路。NFA 的更好理解是：同一时刻保留多条候选路径，只要其中一条路径最后进入接受状态，整个输入就被接受。 问题 DFA NFA 当前状态 一个状态 一组状态 同一输入的下一状态 唯一 可以有多个 是否允许不读字符就移动 不允许 允许 接受条件 当前状态...

上一篇用指称语义把程序翻译成 Python 函数。程序语义这一段到这里已经形成闭环：AST 给出结构，大步语义、小步语义和指称语义分别给出不同角度的含义。接下来进入自动机。问题从“程序怎样执行”换成“机器怎样根据输入移动到下一个状态”。 确定性有限自动机（Deterministic Finite Automaton，DFA）是自动机部分的起点。它没有变量表，没有栈，没有堆，也没有可写纸带；它只记住一个当前状态，然后逐个读取输入字符。每读一个字符，机器就根据一张规则表换到下一个状态。输入读完后，当前状态如果属于接受状态，字符串就被接受；否则被拒绝。 这个模型很小，却足够解释很多工程直觉：订单状态流转、协议解析、词法分析、简单规则匹配，都可以先压成“当前状态 + 输入 -> 下一个状态”的形式。 从业务状态机收缩到形式模型 Java 程序员对状态机并不陌生。订单可以从 CREATED 变成 PAID，再变成 SHIPPED；审批单可以从 DRAFT 变成 SUBMITTED，再变成 APPROVED 或 REJECTED。这些状态机通常带着业务动作、数据库事务、权限检查、通知...

复旦、北大、上海奇绩智峰联合出的 Agentic Harness Engineering（AHE）做了一件很具体的事：让 GPT-5.4 驱动的 Coding Agent 在 Terminal-Bench 2 上的 pass@1 从 69.7% 涨到 77.0%，绝对 +7.3 个百分点，超过 OpenAI 官方 Codex-CLI 的 71.9%，也超过同期两条主流自演化基线 ACE（68.9%）和 TF-GRPO（72.3%）。换到 GPT-6.0 上，他们的同名 NexAU-AHE 在 Terminal-Bench 2 leaderboard 上跑到 84.7%，全球前三。 值得记下来的不是这几个数字，而是它怎么涨上去的。AHE 没有调模型权重，没有改评估框架，只让一个 Evolve Agent 在一个被严格围出来的工作区里改 Harness 自己。这件事能跑通的关键，是它把"哪些组件可以改、改了之后哪里能看到信号、看到信号之后用什么口径决策"全部当成一等公民设计了出来。 上一篇 把 Harness Engineering 的概念边界讲清楚：人怎么把 A...

很多人都遇到过这种场景：一个 JVM 进程因为 -Xmx 写错了一个字符，启动起来就死掉，控制台一行日志都没有；一个 Node.js CLI 比如 opencode 在前台 hang 住，光标不闪，也不退出；一个 Spring Boot 服务被 systemd 拉起来，systemctl status 显示 running，但端口永远不开。stderr 看不到、源码也没有，只能反复重启。 这类问题的共同点不是程序"出 bug"，而是进程在"出第一行日志"之前就已经失败或卡住。常规的"看日志找异常"那一套这时候没东西可看。需要的是另一类方法论：把进程当黑盒，从外部撬开它的状态。 下面把这套方法论拆成四步，先给通用框架，再给 JVM 与 Node.js 两个语言专题，最后用 opencode hang 这个具体例子推演一遍。 一、先把"看不到日志"分成四种情况 把"启动期黑盒"展开来看，至少是四种性质完全不同的故障。混在一起调，方向就错了。 类别 特征 进程状态 主要工具方向 ...

前两篇用操作语义解释程序。大步语义直接给最终结果，小步语义展示每一步规约。第 2 章还有第三种视角：指称语义（denotational semantics）。 指称语义把程序映射到某个更基础的对象。在本文的小语言里，表达式会变成一个 Python 函数，语句也会变成一个 Python 函数。程序的含义从“机器怎样跑”转到“它等价于哪个函数”。 对 Java 程序员来说，可以先把它理解成： 12Function<Environment, Value> // 表达式的含义Function<Environment, Environment> // 语句的含义 本文继续沿用前面的 AST，用 Python 函数重写这套小语言的含义。 三种语义回答三类问题 同一段程序可以从三种角度解释。 语义 关心的问题 本系列里的实现 大步语义 运行完成后得到什么 递归解释器 小步语义 每一步怎样变化 规约机器 指称语义 程序等价于什么对象 函数翻译器 大步和小步都属于操作语义。它们会描述程序在某种抽象机器上怎样执行。指称语义换成另一...

上一篇写了大步语义。大步语义像一次函数调用：给它程序和环境，它直接返回最终环境。小步语义换了观察角度：程序运行时会经历一串中间配置，每一步只做一个局部变化。 这个视角很适合 Java 程序员理解调试器、解释器、状态机和工作流引擎。断点、单步执行、重试、恢复、超时保护，都依赖“当前程序状态可以被保存，下一步可以被明确计算”。 本文继续使用上一篇的小语言，补上小步语义（small-step semantics）。核心目标很直接：把一个完整程序改写成一台可推进的机器。 程序状态变成机器配置 小步语义关心的是配置之间的变化。 1(statement, environment) -> (next_statement, next_environment) statement 是剩余要执行的程序，environment 是当前变量绑定。每执行一步，语句可能变小，环境也可能变化。 例如： 12(x = 1 + 2, {}) -> (x = 3, {})(x = 3, {}) -> (do-nothing, &...

上一篇已经把字符串解析成 AST。程序结构稳定以后，下一步是给它一套求值规则。最直接的规则叫大步语义（big-step semantics）：给定一个表达式和环境，直接得到最终值；给定一个语句和环境，直接得到新的环境。 大步语义适合写成递归解释器。表达式节点递归求值，语句节点递归改变环境。它不会展示每一个中间状态，只关心完整运行后的结果。 本文会实现一个小语言。它支持数字、布尔值、变量、加法、乘法、小于、赋值、顺序执行、条件分支和 while 循环。 大步语义关心最终关系 大步语义可以先记成两条关系： 12expression + environment => valuestatement + environment => new_environment 表达式会产生值，语句会改变环境。环境是变量名到值的映射。 例如： 1x + 1, {x = 2} => 3 赋值语句会得到一个新环境： 1x = x + 1, {x = 2} => {x = 3} 这套写法和 Java 程序员熟悉的递归下降解...

前一篇用 dataclass 手工创建了一个表达式： 1program = Add(Number(1), Add(Number(2), Number(3))) 这已经能演示解释器的基本形状，但它还绕开了一个关键步骤。真实程序通常从文本开始。读者写下的是 x + (2 + y) + 3，解释器需要先把这段文本变成结构化对象，后面的求值规则才有东西可操作。 本文做这件事：写一个很小的 tokenizer 和 parser，把字符串转成 AST（Abstract Syntax Tree，抽象语法树），再对 AST 求值。 程序文本进入系统后的三步 一段源码进入解释器后，可以先粗略拆成三步： 1source text -> tokens -> AST -> value source text 是原始字符串。tokens 是词法单元列表，比如数字、变量名、加号、括号。AST 是语法结构，表达“谁和谁相加”“括号包住哪一段”。value 是执行结果。 本文只实现一个小语言。它支持整数、变量、加法和括号： 1231 + 2x + 3x + (2 + y) + 3 语法规则也...